6.4基于身份的公钥密码体制第6章公钥密码体制6.1公钥密码的原理及典型公钥密码6.1.1公钥密码的原理公钥密码的思想最早由Diffie和Hellman在其论文“NewDirectionsinCryptography〞中提出。他们设想了一种无须事先传递密钥的密码体制，在该体制中，用户Alice有一对密钥：公开的加密密钥(简称公钥)和保密的解密密钥(简称私钥)。向Alice发送秘密信息时，用其公钥加密，Alice收到信息后，用私钥解密。由于加密密钥与解密密钥不同，因此公钥密码体制又被称为非对称密码体制，而传统密码(分组密码、序列密码)被称为对称密码体制。与对称密码相比，公钥密码有以下特点：
(１)平安性取决于某些困难问题的难解性；
(２)无须事先传递密钥；
(３)计算量通常大于对称密码。
公钥密码中常用的难解问题有分解大整数、离散对数问题、椭圆曲线上的离散对数问题
等，其平安性取决于构造算法所依赖的数学问题的计算复杂性，所以公钥密码在理论上是
不平安的，但在实际应用中可以选择足够平安的参数来保证计算上的平安性。6.1.2Diffie-Hellman密钥交换
Diffie和Hellman给出了一种通信双方无须事先传递密钥也能利用对称密码体制进行保密通信的方法，这就是Diffie-Hellman密钥交换协议(简称D-H协议)，在该协议中，通信双方通过协商可以建立一个秘密的密钥。D-H协议充分表达了公钥密码的思想，其平安性基于离散对数问题。设系统中公开的参数为大素数p和模p的原根g，用户Alice和Bob为了协商一个公用的秘密密钥，需要进行如下步骤：
(1)Alice随机选择整数xA，计算，将yA传给Bob；
(2)Bob随机选择整数xB，计算，将yB传给Alice；
(3)Alice计算，Bob计算
，易知两者是相等的，从而可将
作为双方的通信密钥。
D-H协议的平安性是基于这样一个假设，即和，求xB是困难的，Diffie和Hellman假设此问题的困难等价于离散对数问题。6.1.3RSA
1977年，美国麻省理工学院的三位数学家RonRivest、AdiShamir和LenAdleman成功地设计了一个公钥密码算法，该算法根据设计者的名字被命名为RSA，在其后的30年中，RSA成为世界上应用最为广泛的公钥密码体制。
设RSA系统中每个用户有公开的加密密钥n、e和保密的解密密钥d，这些密钥通过以下步骤确定：
(1)用户选择两个大素数p、q，计算n=pq及φ(n)=(p－1)(q－1)；(2)选择随机数e，要求1 (3)求出e模φ(n)的逆d，即ed≡1modφ(n)； (4)将n、e公开，d保密。 加密时，首先将明文表示为小于n的整数，设m为明文，要将m加密并发送给用户Alice时，利用Alice的公开密钥nA、eA，计算 求出的整数c即为密文。Alice收到c后，利用自己的解密密钥dA，计算 求出的m即为明文。6.1.4ElGamal ElGamal是基于离散对数问题的最著名的公钥密码体制，其系统参数如下： 选择大素数p和模p的原根g，随机选择整数x，计算 y=gxmodp，将p、g、y公开，x保密。 加密时，假设明文被编码为整数m，加密者随机选择整数k，满足gcd(k，p－1)=1，再计算 c1=gkmodp c2=mykmodp 那么密文为c=(c1，c2)。 接收方收到密文组(c1，c2)后，进行如下的解密运算： 6.2椭圆曲线密码6.2.1椭圆曲线(EllipticCurve)椭圆曲线的图像轨迹并不是椭圆，而是一个平面上的三次曲线，是人们在研究如何计算椭圆的弧长时发现的问题。定义6-1由三次威乐斯特拉斯方程(Weierstrass方程):y2+axy+by=x3+cx2+dx+e所确定的平面曲线称为椭圆曲线，满足方程的点称为曲线上的点。假设系数a，b，c，d，e来自有限域Fp，那么曲线上的点数目也是有限的，这些点再加上一个人为定义的无穷远点O，构成集合E(Fp)，E(Fp)的点数记作#E(Fp)。Hasse证明了如下结论： 在构造密码系统时，我们主要关心这样一种椭圆曲线，其方程为 y2=x3+ax+b x，y，a，b，∈Fp定理6-1椭圆曲线上的点集合E(Fp)对于如下定义的加法规那么构成一个Abel群： (1)O+O=O； (2)对(x，y)∈E(Fp)，(x，y)+O=(x，y)； (3)对(x，y)∈E(Fp)，(x，y)+(x，－y)=O，即点(x，y)的逆为(x，－y)； (4)假设x1≠x2，那么(x1，y1)+(x2，y2)=(x3，y3)，其中， (5)(倍点规那么)对(x1，y1)∈E(Fp)，y1≠0，有2(x1，y1)=(x2，y2)，其中, 以上规那么表达在曲线图形上，含义为 (1)O是加法单位元； (2)一条与x轴垂直的线和曲线相交于两个x坐标相同的点，即P1=(x，y)和P2=(x，－y)，同时它也与曲线相交于无穷远点，因此P2=－P1； (3)横坐标不同的两个点R和Q相加时，先在它们之间画一条直线并求直线与曲线的第三个交点P，此时有R+Q=－P； (4)对一个点Q加倍时，通过该点画一条切线并求切线与曲线的另一个交点S，Q+Q=2Q=－S。6.2.2椭圆曲线公钥密码体制 设P∈E(Fp)，点Q为P的倍数，即存在正整数x，使Q=xP，那么椭圆曲线离散对数问题ECPLP(EllipticCurveDiscreteLogarithmProblem)是指由给定的P和Q确定出x。从目前的研究 成果看，椭圆曲线上的离散对数问题比有限域上的离散对数似乎更难处理，这就为构造公钥密码体制提供了新的途径。基于椭圆曲线离散对数问题，人们构造了椭圆曲线密码体制。 定义6-2设E为椭圆曲线，P为E上的一点，假设存在正整数n，使nP=O，那么称n是点P的阶，这里O为无穷远点。系统的构造 选取基域Fp，椭圆曲线E，在E上选择阶为素数n的点P(xp，yp)。 公开信息为：域Fp、曲线方程E、点P及其阶n。 密钥的生成 用户Alice随机选取整数d，1 假设要给Alice发送秘密信息M，需执行以下步骤： (1)将明文M表示为域Fp中的一个元素m； (2)在［1，n－1］内随机选择整数k； (3)计算点(x1，y1)=kP； (4)计算点(x2，y2)=kQ，假设x2=0，那么重新选择k； (5)计算c=mx2； (6)将(x1，y1，c)发送给Alice。Alice收到密文后，利用秘密密钥d，计算: d(x1，y1)=dkP=k(dP)=kQ=(x2，y2) 再计算，得到明文m。 这里Q=dP是公开的，假设破译者能够解决椭圆曲线上的离散对数问题，就能从dP中恢复d，完成解密［21］。6.2.3基于椭圆曲线公钥密码体制的密码协议 在网络通信中，有时要求多个用户对同一消息进行签名与认证(如几位领导或当事人签署同一份文件)。能够实现这种多个协议方对同一消息进行签名的数字签名协议就称为多重数字签名(DigitalMultisignature)。根据签名协议过程的不同，多重数字签名又可以分为有序多重数字签名(SequentialMultisignature)与播送多重数字签名(BroadcastingMultisignature)。 1)有序多重数字签名 有序多重数字签名协议过程如图6-1所示。图6-1有序多重数字签名方案有序多重数字签名方案包含消息发送者(issuer)、消息签名者(signers)、签名验证者(verifier)三个协议方，消息发送者规定消息签名顺序，然后将消息发给第一个签名者。除了第一个签名者以外的每一位签名者收到签名消息后，首先验证上一签名的有效性，如果有效那么继续签名，然后将签名消息发送到下一个签名者；如果签名无效那么拒绝对消息进行签名，终止签名协议。签名验证者最后收到签名消息，对消息进行有效性验证，如果签名有效那么通过认证，否那么拒绝进一步的协议过程。2)播送多重数字签名 播送多重数字签名协议过程如图6-2所示。 播送多重数字签名方案包含消息发送者、消息签名者、签名收集者(signaturecollector)、签名验证者四个协议方。消息发送者将消息同时发送给每一位签名者进行签名；签名者将签名消息发送到签名收集者；收集者对各个签名消息进行处理并将结果发送给签名验证者；签名验证者完成对多重数字签名的有效性验证工作。图6-2播送多重数字签名方案 2.基于ECC的多重数字签名方案 1)有序多重数字签名方案 有序多重数字签名方案包括系统初始化、签名产生与签名验证过程，方案的协议方为消息发送者、消息签名者与签名验证者。 初始化过程设A为消息发送者，B1，B2，…，Bn为消息签名者，C为签名验证者。鉴于平安性和执行效率的考虑，系统参数设定为：Fp为特征值Char(Fq)>3的有限域，定义该域上的椭圆曲线E，E：y2=x3+ax+b(a，b∈Fp，4a3+27b2(modq)≠0，q为nbit的素数，n≥190)，P∈E(Fq)是一个公开基点，P的阶为L(L≥160bit)，#E(Fq)为椭圆曲线的阶，至少有50位以上的大素因子。 假设ki∈(1，2，…，q－1)分别为消息签名者Bi的私钥，Ki=kiP为Bi的公钥，共享的平安散列函数选择SHA_1或RIPEMD_160。消息发送者A预先设计一个签名顺序B1，B2，…，Bn，并且将签名顺序发送给每一位签名者Bi与验证者C。 签名产生过程 A将消息m发送到第一位签名者B1，规定此时的签名消息s=0。每一位签名者Bi(i≥2)收到签名信息(m，(si－1，Ri－1))后，先对签名进行验证，然后执行以下步骤： (1)Bi随机选取ui∈(1，2，…，q－1)，计算: m′=SHA_1(m)，Ri=uiP=(xi，yi)≠0， si=si－1+kixi－m′ui(modq) (6-1)(2)将(m，(si，Ri))发送到下一个签名者Bi+1，同时将Ri发送给Bi以后的签名者以及签名验证者C。 签名验证过程 签名者Bi(i≥2)要对B1，B2，…，Bi－1的签名进行验证，验证者C要对所有签名者B1，B2，…，Bn的签名进行验证。Bi验证 (6-2) 是否成立。假设等式成立，那么Bi认为B1，B2，…，Bi－1的签名消息有效；否那么判定签名无效，拒绝继续对消息签名。同样，C验证 (6-3) 是否成立。如果等式成立，那么认为B1，B2，…，Bn的签名有效；否那么认定为无效签名。签名验证中，由式(6-1)可得 (6-4) 因此 这就验证了上述有序多重数字签名方案的正确性。式(6-2)右边＝等式左边2)播送多重数字签名方案 初始化过程 此方案的系统初始化和参数设定与有序多重数字签名方案相同，且Bc为签名收集者。 A将消息m发送到每一位签名者Bi(i=1，2，…，n)和签名收集者Bc，规定此时的签名消息s=0。签名者Bi和收集者Bc收到消息后执行以下步骤： (1)Bi随机选取ui∈(1，2，…，q－1)计算Ri=uiP=(xi，yi)≠0，将Ri发送到签名收集者Bc;(2)签名收集者Bc收集到所有Ri(i=1，2，…，n)后，计算 ，随后Bc将R发送到每一位签名者Bi(i=1，2，…，n); (3)对于消息m，签名者Bi计算m′=RIPEMD_160(m)，然后生成签名 (6-5) 那么si作为签名者Bi对消息m的子签名，Bi将签名消息(m，si)发送到签名收集者Bc;(4)当Bc收集到所有(m，si)(i=1，2，…，n)后，计算 (6-6) 然后将(m，s，R)作为最后签名信息发送到签名验证者C。 C接收到签名信息(m，s，R)后，首先计算m′=RIPEMD_160(m)，然后验证 (6-7) 是否成立。如果等式成立，那么认为B1，B2，…，Bn对消息m的签名有效；否那么认定为无效签名。上述验证签名的等式中，由于 因此式(6-7)右边 =等式左边 上式验证了上述播送多重数字签名方案的正确性。3)方案分析 基于ECC的多重数字签名方案除表达了现有多重数字签名方案的优点外，还具有以下特点： (1)实现了一类透明的协议过程。播送多重签名中，签名收集者通过签名处理过程 的引入，隐蔽了各个签名者的随机中间参数Ri与单个子签名消息si，验证者与攻击者都无法将签名信息与单个签名者联系起来，因此方案对于外部攻击具有较强的抵抗能力。对于内部攻击，假定有m(m 或伪造签名信息(m,())(其中)满足有序多重签名公式(6-3)： 时，都是求解多重的椭圆曲线离散对数问题。即使对于签名收集者Bc，方案也具有较强的防伪造性，因为签名者Bi的私钥和随机参数ui对Bc是保密的，要伪造签名，面对的是求解椭圆曲线离散对数问题。(3)具有牢固的抗抵赖性。两种多重签名子方案中，签名验证者对各个签名者公钥进行遍历，完成验证后，签名者Bi不能否认对消息进行了签名，因为完成签名协议过程的前提是掌握Bi的私钥及相应随机数ui。 (4)算法简洁、高效。方案充分发挥了ECC密钥短、平安性高的优势，密钥长度仅需160bit就可以提供与1024bit的RSA或DSA同样的平安度。因此，该方案特别适用于计算能力和集成电路空间受限(如智能卡smartcard)、带宽受限(如无线通信和某些计算机网络)、要求高效率实现的情况。需要特别指出的是，方案中签名者Bi每次签名时必须更换随机产生的秘密参数ui。例如，在有序多重签名方案中，如不更换随机数且签名的顺序保持不变，那么攻击者根据变化了的si与m′的值，依据式(6-4)，在经过2(i－1)次协议过程后，就可以联立2(i－1)个关系式，从而求解出前面i－1个签名者的私钥与相应的随机数。同理，在播送多重签名中，可由式(6-5)、(6-6)得到 如不更换随机数，那么协议过程次数越多私钥就越不平安，当协议次数大于2n时，就完全有可能攻破私钥，伪造签名。4)方案的软件实现效率与平安性 椭圆曲线密码软件实现时的函数包括：模一般素整数运算函数集，其中有加、减、乘、除、求逆；大素数域GF(q)中运算函数集，这其中也有加、减、乘、除、求逆；椭圆曲线根本运算函数集，其中有点加、倍点、固定点标量乘(scalarmultiplication，即求固定点p的k倍)、随机点标量乘；辅助函数，如平安散列函数选择SHA_1或RIPEMD_160。模一般素整数运算与大素数域GF(q)中运算是ECC软件实现中调用最频繁的函数，这些函数采用汇编语言编写，其它的函数与算法用标准C语言编写。 定义6-3设F是域，是其代数闭域，那么F上亏格为g(g≥1)的超椭圆曲线C是指具有方程形式: C：v2+h(u)v=f(u)(6-8) 的曲线。这里h(u)∈F［u］是次数不大于g的多项式，f(u)∈F［u］是一个次数为2g+1的首一多项式，而且不存在 满足以下方程组: 如果g=1，那么称C为椭圆曲线。定义6-4设K是F上的一个扩域，那么C上的一个K-点P是符号∞(称为C上的无穷远点)或是方程C：v2+h(u)v=f(u)的一个解(x，y)∈K×K。C上的所有K-点记为C(K)。 定义6-5设P=(x，y)是一条椭圆曲线C：v2+h(u)v=f(u)上的一个有限K-点，那么它的相反点记为。如果P=∞，我们取。如果P是一个有限点且满足 ，那么称P是一个特殊点，否那么称P是一个普通点。引理6-1设C是由方程C：v2+h(u)v=f(u)定义的域F上的超椭圆曲线，那么满足： (1)如果h(u)=0，那么Char(F)≠2。 (2)如果Char(F)≠2，那么作变换u→u及v→v－h(u)/2，从而将C的形式变为v2=f(u)(其中deguf=2g+1)。6.3.2除子与Jacobian群 定义6-6一个除子d是C上假设干点的一种形式和: 其中只有有限个整数mP非零。整数称为d的度数，记为degd。d在P点的阶是mP，表示为ordP(d)=mP。设D表示C上所有除子的集合，那么D在如下加法规定之下是一个加群： 设D0={d∈D|degd=0}，那么D0是D的一个子群。 定义6-7设C是域F上的一条超椭圆曲线，域上C的坐标环是定义为 的商环。中的元素称为C上的多项式函数。 对每一个多项式函数，可以通过重复地将G(u，v)中的v2替换成f(u)－h(u)v来降低v的幂次，最终得到G(u，v)的一种唯一形式，可设为 定义6-8设是一个非零的多项式函数，P∈C，那么G在P点的阶记为ordP(G)，定义如下： (1)如果P=(x，y)是一个有限点，那么可设 G(u，v)=(u－r)r(a0(u)－b0(u)v)，这里r是可同时整除a(u)和b(u)的(u－x)的最高次幂。如果(a0(x)－b0(x)y)≠0，那么设s=0；否那么，设s是使(u－x)s整除范数 的最高次幂。如果P是一个普通点，那么定义ordP(G)=r+s； 如果P是一个特殊点，那么定义ordP(G)=2r+s。(2)如果P=∞，那么定义 ordP(G)=－max{2degu(a)，2g+1+2degu(b)} 对于一个非零的有理函数及C上的一个点P的阶定义为 ordP(R)=ordP(G)－ordP(H)定义6-9设是一个有理函数，那么R的除子定义为 例如，如果P是一个普通点，那么有;如果P是一个特殊点，那么有div(u－x)=2P－2∞。 显然，如果R=G/H，那么 div(R)=div(G)－div(H) 定义6-10设J(更准确地说为也可以用F的任何一个扩域代替)表示商域D0/P，J称为曲线C上的Jacobian群。 设d1，d2∈D0，如果d1－d2∈P，那么记d1～d2，并称d1与d2等价。 J中的每一个元素是D0中元素的一个等价类，它可以表示成d+P，或简单地记为，这里d∈D0是一个除子，并称为的一个代表元。很显然，该代表元不唯一。J中元又称为除子类。6.3.3超椭圆曲线Jacobian群中的运算 定理6-2设d=∑miPi－∞∑mi是一个半约化除子，这里Pi=(xi，yi)∈C，设 ，那么存在唯一的一对多项式(a(u)，b(u))满足d=gcd(div(a(u))，div(b(u)－v))。为了简便，通常将其写成div(a,b)。因此，J中的每一个元素可唯一地表示成。其中，多项式a(u)、b(u)满足degub＜degua＜g及a(u)|(b2(u)+b(u)h(u)－f(u))，因此J(Fq)是一个有限Abelian群，且其阶＃J(Fq)≤q2g。 设D*表示所有约化除子div(a，b)组成的集合，a，b∈F(u)，且满足degub＜degua＜g及a|(b2+bh－f)，那么集合J(F)与集合D*之间存在一个一一映射。在如下的讨论中，我们可以将J(F)看成是D*，将看成是div(a，b)，群J(F)的零元那么是div(1，0)。此处定义一种运算，称为J(F)中的加法，用标记，这也被称为超椭圆曲线Jacobian上的除子加。 设d1=div(a1，b1)，d2=div(a2，b2)∈D*，规定d1⊕d2=d(a，b)是由以下算法唯一确定的约化除子： (1)利用广义Euclidean算法找出多项式d，s1，s2，s3∈F(u)，满足: d=gcd(a1，a2，b1+b2+h)，d=s1a1+s2a2+s3(b1+b2+h) (2)置(3)置 (4)如果degua＞g，那么作变换a′←a，b′←b，并返回(3)。 (5)输出div(a，b)即为d。有限域上超椭圆曲线的Jacobian是一个有限交换群，超椭圆曲线的Jacobian上的根本运算包括除子加、倍除子和除子标量乘。Jacobian上实用的群运算算法最早是由Cantor提出的，当时只是限定在非特征2的域上。之后，NealKoblitz于1988年提出超椭圆曲线密码体制时将Cantor算法推广到了任意的域上。Cantor-Koblitz群运算法那么实际上等价于高斯的二元二次型归约算法。AndreasEnge将归约算法进行了推广，在除子运算中运用了扩展的Euclidean算法，对几种除子运算的计算量作了理论上的分析，得到了一次除子加用到有限域GF(qn)中运算的平均值，其数据如表6-2所示(超椭圆曲线为C：v2+h(u)v=f(u))。我们以［19］借助Frobenius自同态提出的一种快速除子标量乘算法为例，计算分析快速除子标量乘的运算量。Zhang的方法可推广为一类计算超椭圆曲线除子标量乘的方法，实现步骤如下： (1)输入一个除子D及一个正整数m; (2)计算曲线Jacobian上的Frobenius自同态的特征多项式P(T); (3)对于1≤i≤qg－1，预计算iD; (4)将m转换成符号q-进制：，其中 －qg+1≤i≤qg－1; (5)令B:=〈1，0〉; (6)对于i自l－1递减到0，计算: B：B+rD假设ri不为零 (7)输出B为mD。 下面我们以几条选定的GF(qn)上的超椭圆曲线为例，比较二元法与Zhang提出的方法计算qnP的运算量，如表6-3所示。(表中，a、m和s分别表示一次除子加、倍加和赋值运算。)6.3.4超椭圆曲线密码体制(HCC) 设C是Fq上亏格为g的超椭圆曲线，J(Fq)是它的Jacobian， ，n是160bit的大素数(h=1，或是较小的余因子)，q约为160bit。p∈J(Fq)是具有大素数阶n的一个约化除子， 在g=2时， 设，Q=kP=［aq，bq］≠0，那么Q可以作为公钥公布，k作为密钥保存，加密时将信息嵌入密钥当中。同时我们需要一个单射，将P对应于一个整数。设ψ表示该对应关系，那么ψ是一个从J(Fq)到有限整数集 的单射，将其记为(P)x或(P)q。很显然，这样的赋值映射是不唯一的。在实际密码应用中，可以根据给定的超椭圆曲线规定一个适当的映射的值域范围。下面是例子： (1)设β＝(c0，c1，…，c2g－1)是集合{a0，…，ag－1，b0，…，bg－1}上的一个置换映射，那么 是一个单的赋值映射。(2)先对每个ai与bi取模q，转换为不大于q－1的非负的整数，令 代理数字签名可以分为单个代理签名与多重代理数字签名。 1)单个代理签名 设A，B是某个数字签名体制(M，S，K，SIG，VER)的两个用户，他们的私钥和公钥分别是(xA，yA)与(xB，yB)，假设有以下5个条件成立，那么，就称A将他的数字签名权力委托给了B，称A为原始签名人，B为A的代理签名人，f为委托密钥，fAB为代理签名密钥。 (1)A利用他的密钥xA计算出一个数f，并将f秘密地交给B；(2)任何人(包括B)在试图求出xA时，f不会对其有任何帮助； (3)B利用xB和f生成一个新的签名密钥fAB； (4)存在一个公开的验证算法VERAB，满足对于任何s∈S和m∈M，都有VER(yA，s，m)=True，等价于s=SIG(fAB,m)； (5)任何人在试图求出xA，xB，f或fAB时，任何数字签名SIG(fAB，m)都不会对其产生帮助。2)多重代理数字签名 假设Ai(1≤i≤n)是某个数字签名体制(M，S，K，SIG，VER)的n个用户，Ai的秘钥与公钥对为(xi，yi)。假假设对于任意的Ai(1≤i≤n)都将他的签名权力委托给了B(设B得到的代理签名秘钥为fi)，B对某个特定的消息m∈M联合生成了一个多重签名s=SIG(f1，f2，…，fn，m)，使得验证这个多重签名的有效性时，必须使用所有Ai的公钥，那么称S为一个由B代表Ai(1≤i≤n)生成的多重代理签名［2］。 2.基于HCC的单一代理数字签名方案 方案包括系统初始化、委托过程、签名产生与签名验证过程，同时方案的协议方为原始签名者、代理签名者与签名验证者。1)初始化过程 设C是Fq上亏格为g的超椭圆曲线，J(Fq)是它的Jacobian，#J(Fq)=hl，l是190bit的大素数(h=1，或是较小的余因子)，q约为190/gbit。P，P1∈J(Fq)是具有大素数阶的约化除子，它们的阶分别为L0、L1(满足min(L0，L1)≥190bit)。n为一个大素数(满足n>max(L0，L1))。H0、H1、H2为平安的散列函数，H0，H1，H2{0，1}*→Zn。ka，kb∈分别为用户A和银行的私钥，Kb=kbP，Ka=kaP作为两者的公钥，密钥对(Ka，ka)、(Kb，kb)作为协议中的主密钥。ψ表示是一个从J(Fq)到有限整数集 ={0，1，…，q2g+1－1}的单射函数，将其记为(P)x或(P)q。公开n，P、P1和H0、H1、H2以及公钥Kb=kbP，Ka=kaP。设kA，kB∈(1，2，…，n－1)分别为A和B的私钥，KA=kAp，KB=kBp为A和B的公钥，共享的平安散列函数为H1和H2。2)委托过程 (1)A随机选取u∈(1，2，…，n－1)，计算: R=up≠0，h=H1((R)x) f=hkA+u(modn)(6-9) 并将(R，f)秘密地发送给B。 (2)B计算h=H1((R)x)，然后验证: fp=hKA+R 是否成立，假设成立那么计算 f′=f+kB(modn)(6-10)3)代理签名过程 对于某个消息m，B随机选取v∈(1，2，…，n－1)，计算得到T=vp≠0，再计算 m′=H2(m) s=(T)xf′－m′v(modn)(6-11) 并将(m，s，R，T)发送给签名验证者。4)代理签名验证过程 验证者接收到(m，s，R，T)后，计算 h=H1((R)x)，m′=H2(m) 验证 (T)x(hKA+R+KB)=sp+m′T(6-12) 是否成立。如果等式成立，那么认为B代理A的签名有效；否那么认定为无效签名。签名验证中，由式(6-11)可得 式(6-12)右边 这就验证了上述单一代理数字签名方案的正确性。3.基于HCC的多重代理数字签名方案 1)初始化过程 系统初始化和参数设定与单一代理数字签名的方案相同，假设ki，kB分别为Ai(i=1，2，…，n)和B的私钥，Ki=kip，KB=kBp为Ai和B的公钥，共享的平安散列函数为H1和H2。2)委托过程 (1)Ai随机选取ui∈(1，2，…，n－1)，计算 Ri=uip≠0，hi=H1((Ri)x) fi=hiki+ui(modn)(6-13) 并将(Ri，fi)秘密地发送给B。(2)B在收到(Ri，fi)(i=1，2，…，n)后，计算hi=H1((Ri)x)，然后验证 fip=hiKi+Ri 是否成立。假设成立那么认为(Ri，fi)是一个有效的子代理密钥;否那么B要求Ai重复(1)或终止协议过程。3)代理签名过程 B在收到所有(Ri，fi)后，计算出 (6-14) 对于某个消息m，B随机选取v∈(i=1，2，…，n－1)，计算 T=vp≠0，m′=H2(m) s=f′－(m′+(T)x)v(modn)(6-15) (s，T，R1，R2，…，Rn)为B代表Ai(i=1，2，…，n)生成的多重代理签名。4)代理签名验证过程 验证者收到(s，T，R1，R2，…，Rn)和消息m后，计算 hi=H1((Ri)x)，m′=H2(m) (6-16) 是否成立。如果等式成立，那么认为B代理Ai生成的多重代理签名有效；否那么认定为无效签名。签名验证中，由式(6-15)可得 式(6-16)右边 ＝等式左边 这就验证了上述多重代理数字签名方案的正确性。 4.代理数字签名方案分析 (1)代理签名方案可具有区分与身份证实性。根据式(6-10)，在单一代理签名中有 f′=f+kB(modn) 根据式(6-14)，在多重代理签名中有 或 (T)x(hKA+R+KB)=sp+m′T 后，原始签名者Ai不能否认将代理签名权委托给了B，代理签名者B也不能否认对消息进行了签名，因为完成委托与代理签名协议过程的前提是掌握相应的私钥及协议中产生的随机数。(4)代理签名权撤销灵活。当原始签名人想撤消代理签名者Bi的代理签名权时，他可以通过媒体公开宣布原有委托信息(Ri，fi)不再有效，注销代理签名密钥f′。但是这种播送方式必须要有签名机制，以防止攻击者发布伪造的撤销消息进行中间入侵攻击(intruder-in-middleattack)。(5)算法简洁、高效。方案充分发挥了HCC密钥短、平安性高的优势。当超椭圆曲线亏格为3时，方案所基于的有限域仅需60bit就可以提供与180bit的ECC相同的平安强度。 需要特别指出的是，签名者B每次签名时必须更换随机产生的秘密参数v，否那么攻击者根据si与m′值的变化，从单一代理签名式(6-9)、(6-10)、(6-11)可得 s=(T)x(hkA+u+kB)－m′v(modn) 经过四次协议过程就可以联立四个关系式，解出原始签名者与代理签名者的私钥与相应的随机数。同理，在多重代理签名中，依据式(6-13)~(6-15)可得 初始化(Setup)：给定平安参数k，输出系统参数params和主密钥，系统参数包括消息空间M、密文空间C。系统参数是公开的，而主密钥只有“私钥生成器〞PKG知道。 密钥提取(Extract)：输入系统参数params，主密钥和任意的ID∈{0，1}*，输出私钥d，其中ID为用户公钥，d为相应的私钥，提取算法由给定的公钥生成私钥d。 加密(Encrypt)：输入系统参数params、ID，以及m∈M，输出密文c∈C。 解密(Decrypt)：输入系统参数params、ID，私钥d以及c∈C，输出m∈M。这些算法必须满足一致性条件，即当d为由提取算法产生的相对于ID的私钥时，对任意m∈M，有 Decrypt(params，ID，c，d)=m 其中，c=Encrypt(params，ID，m)。 基于身份的密码体制建立在椭圆曲线密码学(ECC，EllipticCurveCryptography)的根底之上，ECC体制的平安根底是有限域中椭圆曲线上的点群中的离散对数问题(ECDLP，EllipticCurveDiscreteLogarithmProblem)。目前的研究结果说明，解决椭圆曲线离散问题比有限域上的离散对数问题更加困难。对椭圆曲线密码体制的研究与应用极大地促进了基于身份密码体制的研究。以下我们详细介绍Boneh和Franklin提出的IBE体制(BF方案)。 6.4.2BF方案及其平安性 1.平安模型 在公钥密码体制中，由于加密密钥公开，因此认为攻击者拥有所有用户的公钥，并且可以任意选择明文进行加密，此外攻击者还有时机获得密文，而且可能利用各种途径来获得解密。因此，足够平安的公钥密码体制应该能够抵抗选择密文攻击。公钥密码体制按照攻击者所掌握的条件及攻击目标的不同，可以分为 单向性(OW)平安：由密文不能恢复相应的明文； 不可区分性(IND)平安：对给定的两个明文，加密者随机选择其中一个进行加密，攻击者无法从密文中获知是对哪个明文的加密； 以上平安性概念是依次加强的，NM比IND平安，IND比OW平安。此外，公钥密码体制还可按照可能的攻击模型分为 选择明文(CPA)攻击：攻击者可以先适应性选择明文，获得相应的密文； 非适应性选择密文(CCA1)攻击：攻击者除了可以适应性选择明文攻击外，在给定目标密文前，还可以任意选择密文并获得相应的解密； 适应性选择密文(CCA2)攻击：攻击者的唯一限制就是不能直接获得与目标密文相对应的明文，即攻击者可以在给定目标密文后，任意选择密文并获得相应的解密。 同时考虑攻击目标和攻击模型，可以获得不同的平安性，其中最重要的是IND-CCA2和NM-CCA2平安，而二者被证明是等价的，所以通常意义上的选择密文攻击平安性是指IND-CCA2平安。1)IND-ID-CCA IND-CCA是一种被普遍接受的公钥密码平安性标准，在一般情况下，对于攻击者所掌握的条件可以定义为得到了某个公钥ID相对应的私钥，而在IBE中，选择密文攻击平安性的定义必须有所加强。这是因为攻击者在攻击时，可以任意选择系统中任何一个用户的ID。因此应该定义为允许攻击者任意选择公钥IDi，并得到与之相应的私钥。这个条件被称为私钥提取询问(PrivateKeyExtractionQuery)，而参加了私钥提取询问条件的IND-CCA记作IND-ID-CCA。在定义IND-ID-CCA平安的IBE系统时，Boneh和Franklin设计了如下攻击游戏： 初始化：挑战者选择平安参数k，运行IBE中的初始化算法，将系统参数送给敌手，而将主密钥保密。 阶段1：敌手发出m个询问q1，q2，…，qm。其中，qi可以是以下二者之一： (1)提取询问〈IDi〉，此时挑战者的响应是运行IBE中的密钥提取算法，产生相应于公钥IDi的私钥di并将其送给敌手。(2)解密询问〈IDi，ci〉，此时挑战者的响应是运行密钥提取算法，产生私钥di，然后运行解密算法，利用di对密文解密，将明文送给敌手。 敌手可以根据q1，q2，…，qi－1的结果自适应地选择qi为何种询问。 挑战：阶段1结束后，挑战者输出两个明文m0，m1∈M，以及要挑战的公钥ID，唯一的限制条件是ID不出现在阶段1的任何询问中。挑战者随机选择1比特b∈{0，1}，设置C=Encrypt(params，ID，Mb)，将C作为挑战发送给敌手。阶段2：敌手发出更多的询问qm+1，…，qn。其中，qi为以下二者之一： (1)提取询问〈IDi〉，其中IDi≠ID，挑战者的响应如阶段1。 (2)解密询问〈IDi，ci〉≠〈ID，c〉，挑战者的响应如阶段1。 猜测：敌手输出一个猜测b′∈{0，1}，如果b′=b，那么获胜。 进行以上攻击的敌手A被称为一个IND-ID-CCA攻击者，其优势定义为 如果不存在敌手A，能以不可忽略的优势在上述攻击游戏中获胜，那么说一个IBE系统在IND-ID-CCA下是语义平安的。“不可忽略的优势〞理解为存在某个多项式f，使得 ，其中k为系统的平安参数。2)OWE 为了证明IBE系统的平安性，需要采用一个弱化的平安概念，称为单向加密(OWE，One-WayEncryption)。OWE是针对标准公钥体制而定义的，其含义为：假设敌手A掌握了一个随机的公钥Kpub和密文c，c是利用Kpub对随机明文m加密的结果，攻击者的目标是恢复相应的明文，其优势定义为 Pr［A(Kpub，c)=m］。 中获胜，那么称一个IBE体制是基于身份的单向加密体制(ID-OWE)。攻击包括四个步骤： 初始化：挑战者选择平安参数k，运行IBE中的初始化算法，将系统参数给敌手，而将主密钥保密。阶段1：敌手发出私钥提取询问ID1，…，IDr，挑战者运行密钥提取算法，输出每个公钥IDi对应的私钥di，并将其传给敌手； 挑战：阶段1结束后，挑战者输出公钥ID≠ID1，…，IDr。ID为其要挑战的公钥，随机选择m∈M，并用ID对m加密，将密文c送给敌手。 阶段2：敌手发出更多的询问IDr+1，…，IDn，要求IDi≠ID，挑战者的响应如阶段1。 猜测：最后敌手输出消息m′∈M，如果m′=m，那么获胜。2.数学工具 1)双线性映射 定义6-11令G1和G2为两个阶为素数q的循环群，P为G1的生成元，如果映射e：G1×G1→G2满足如下性质，那么称e为双线性映射： (2)双线性性：对任意P，Q∈G1，a，b∈Zp，有e(aP，bQ)=e(P，Q)ab； (3)非退化性：存在P∈G1，使得e(P，P)≠1。此时，称G1为双线性群，如果其中的群运算以及双线性映射都是可以有效计算的。注意，映射e是对称的，因为 e(Pa，Pb)=e(P，P)ab=e(Pb，Pa)在加法群G1上，有如下一些数学难题： (1)离散对数问题(DLP)：对P，Q∈G1，找到一个整数n∈，使Q=nP成立； (2)Difie-Hellman判定问题(DDHP，DecisionalDiffie-HellmanProblem)：对于a，b，c∈，给定P，aP，bP，cP∈G1，判定c=abmodp是否成立； (3)Difie-Hellman计算问题(CDHP，ComputationalDiffie-HellmanProblem)：对a，b∈，给定P，aP，bP∈G1，计算abP。2)Weil对及其性质 令p为素数，满足p=2mod3，且存在素数q，使得 p=6q－1，令E/Fp为由Fp上方程y2=x3+1确定的椭圆曲线，这种曲线满足如下性质： (1)由于x3+1是Fp上的置换多项式，因而E/Fp中包含p+1个点，令O表示无穷远点，P∈E/Fp为阶群Gq中的生成元； (2)对任意y0∈Fp，存在唯一的点(x0，y0)∈E/Fp。从而假设(x，y)随机地取遍E/Fp上的非零点，那么y随机地取遍Fp上的所有点；(3)假设ζ∈，ζ≠1，为x3－1=0modp的根，那么映射φ(x，y)=(ζx，y)为曲线E上的自同构，注意到P=(x，y)∈E/Fp,从而有，但φ(P)E/Fp，因此P∈E/Fp与φ(P)线性无关； (4)由于点P与φ(P)线性无关，它们可以生成一个与Zq×Zq同构的群，将该群记作E［q］。 令μq为中由所有阶点构成的子群，曲线上的Weil对定义为映射 e：E［q］×E［q］→μq 定义修正后的Weil对为 (6-17)修正后的Weil对满足以下性质： (1)双线性性：对任意P，Q∈Gq，a，b∈Z，有 ； (2)非退化性： 是q阶元素，事实上，它是μq的生成元； (3)可计算性：给定P，Q∈Gq，存在一种有效的算法计算 。3)WeilDiffie-Hellman(WDH)假设 在双线性群中，BDHP问题是指P，aP，bP，cP∈G1，计算W=e(P，P)abc。在现有条件下，不存在多项式算法解决BDHP问题。 Jouxt和Nguyen指出［12］，在群Gq中，CDHP问题是困难的，而DDH(DecisionalDiffie-Hellman)问题容易解决。因为给定P，aP，bP，cP∈Gq，易知 从而修正后的Weil对提供了一种简单的方法来验证Diffie-Hellman向量，所以，不能利用DDH问题在群Gq上构建公钥密码体制，而必须依赖于以下的CDH假设的变体，即WDH(WeilDiffie-Hellman)假设。