现代密码学公钥密码体制课件

1、第6章 公钥密码体制 6.1 公钥密码的原理及典型公钥密码 6.2 椭圆曲线密码 6.3 超椭圆曲线密码 6.4 基于身份的公钥密码体制 第第6章章 公钥密码体制公钥密码体制 第6章 公钥密码体制 6.1 公钥密码的原理及典型公钥密码公钥密码的原理及典型公钥密码6.1.1 公钥密码的原理公钥密码的原理公钥密码的思想最早由Diffie和Hellman在其论文“New Directions in Cryptography”中提出。他们设想了一种无须事先传递密钥的密码体制，在该体制中，用户Alice有一对密钥：公开的加密密钥(简称公钥)和保密的解密密钥(简称私钥)。向Alice发送秘密信息时，用其公

2、钥加密，Alice收到信息后，用私钥解密。由于加密密钥与解密密钥不同，因此公钥密码体制又被称为非对称密码体制，而传统密码(分组密码、序列密码)被称为对称密码体制。第6章 公钥密码体制 与对称密码相比，公钥密码有以下特点：() 安全性取决于某些困难问题的难解性；() 无须事先传递密钥；() 计算量通常大于对称密码。公钥密码中常用的难解问题有分解大整数、离散对数问题、椭圆曲线上的离散对数问题等，其安全性取决于构造算法所依赖的数学问题的计算复杂性，所以公钥密码在理论上是不安全的，但在实际应用中可以选择足够安全的参数来保证计算上的安全性。第6章 公钥密码体制 6.1.2 Diffie-Hellman密

3、钥交换Diffie和Hellman给出了一种通信双方无须事先传递密钥也能利用对称密码体制进行保密通信的方法，这就是Diffie-Hellman密钥交换协议(简称D-H协议)，在该协议中，通信双方通过协商可以建立一个秘密的密钥。D-H协议充分体现了公钥密码的思想，其安全性基于离散对数问题。第6章 公钥密码体制 设系统中公开的参数为大素数p和模p的原根g，用户Alice和Bob为了协商一个公用的秘密密钥，需要进行如下步骤：(1) Alice随机选择整数xA，计算 ，将yA传给Bob；(2) Bob随机选择整数xB，计算，将yB传给Alice；(3) Alice计算，Bob计算，易知两者是相等的，从

4、而可将作为双方的通信密钥。D-H协议的安全性是基于这样一个假设，即已知和，求xB是困难的，Diffie和Hellman假设此问题的困难等价于离散对数问题。AAmodxygpBBmodxygpAA BBmodxxxygpBB AAmodx xxygpA BmodxxkgpA BxxgAxg第6章 公钥密码体制 6.1.3 RSA1977年，美国麻省理工学院的三位数学家Ron Rivest、Adi Shamir和Len Adleman成功地设计了一个公钥密码算法，该算法根据设计者的名字被命名为RSA，在其后的30年中，RSA成为世界上应用最为广泛的公钥密码体制。设RSA系统中每个用户有公开的加密密

5、钥n、e和保密的解密密钥d，这些密钥通过以下步骤确定：(1) 用户选择两个大素数p、q，计算n=pq及(n)=(p1)(q1)；第6章 公钥密码体制 (2) 选择随机数e，要求1e(n)，且gcd(e，(n)=1)；(3) 求出e模(n)的逆d，即ed1 mod (n)；(4) 将n、 e公开，d保密。加密时，首先将明文表示为小于n的整数，设m为明文，要将m加密并发送给用户Alice时，利用Alice的公开密钥nA、eA，计算求出的整数c即为密文。AAmodecmn第6章 公钥密码体制 Alice收到c后，利用自己的解密密钥dA，计算求出的m即为明文。AAmoddmcn第6章 公钥密码体制 6

6、.1.4 ElGamalElGamal是基于离散对数问题的最著名的公钥密码体制，其系统参数如下：选择大素数p和模p的原根g，随机选择整数x，计算y=gx mod p，将p、g、y公开，x保密。加密时，假设明文被编码为整数m，加密者随机选择整数k，满足gcd(k，p1)=1，再计算c1=gk mod pc2=myk mod p则密文为c=(c1，c2)。接收方收到密文组(c1，c2)后，进行如下的解密运算：11121()()()modxkkxkxkxccmygmggmp第6章 公钥密码体制 6.2 椭圆曲线密码椭圆曲线密码6.2.1 椭圆曲线椭圆曲线(Elliptic Curve)椭圆曲线的图像

7、轨迹并不是椭圆，而是一个平面上的三次曲线，是人们在研究如何计算椭圆的弧长时发现的问题。定义定义6-1 由三次威乐斯特拉斯方程(Weierstrass方程):y2+axy+by=x3+cx2+dx+e所确定的平面曲线称为椭圆曲线，满足方程的点称为曲线上的点。若系数a，b，c，d，e来自有限域Fp，则曲线上的点数目也是有限的，这些点再加上一个人为定义的无穷远点O，构成集合E(Fp)，E(Fp)的点数记作#E(Fp)。第6章 公钥密码体制 Hasse证明了如下结论： 在构造密码系统时，我们主要关心这样一种椭圆曲线，其方程为y2=x3+ax+b x，y，a，b，Fp12#()12pppE Fpp 第6

8、章 公钥密码体制 定理定理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) 若x1x2，则(x1，y1)+(x2，y2)=(x3，y3)，其中，231221213131,()xxxyyxxyxxy第6章 公钥密码体制 (5) (倍点规则)对(x1，y1)E(Fp)，y10，有2(x1，y1)=(x2，y2)，其中,222111212123,2()xxxayyxxy第6章 公钥密码体制 以上

9、规则体现在曲线图形上，含义为(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章 公钥密码体制 6.2.2 椭圆曲线公钥密码体制椭圆曲线公钥密码体制设PE(Fp)，点Q为P的倍数，即存在正整数x，使Q=xP，则椭圆曲线离散对数问题ECPLP(Elliptic Curve Dis

10、crete Logarithm Problem)是指由给定的P和Q确定出x。从目前的研究成果看，椭圆曲线上的离散对数问题比有限域上的离散对数似乎更难处理，这就为构造公钥密码体制提供了新的途径。基于椭圆曲线离散对数问题，人们构造了椭圆曲线密码体制。定义定义6-2 设E为椭圆曲线，P为E上的一点，若存在正整数n，使nP=O，则称n是点P的阶，这里O为无穷远点。第6章 公钥密码体制 系统的构造系统的构造选取基域Fp，椭圆曲线E，在E上选择阶为素数n的点P(xp，yp)。公开信息为：域Fp、曲线方程E、点P及其阶n。 密钥的生成密钥的生成用户Alice随机选取整数d，13的有限域，定义该域上的椭圆曲线

11、E，E：y2=x3+ax+b(a，bFp，4a3+27b2(mod q) 0，q为 n bit的素数，n 190)，PE(Fq) 是一个公开基点，P的阶为L(L160 bit)，#E(Fq)为椭圆曲线的阶，至少有50位以上的大素因子。假设ki(1，2，q1)分别为消息签名者Bi的私钥，Ki=kiP为Bi的公钥，共享的安全散列函数选择SHA_1或RIPEMD_160。消息发送者A预先设计一个签名顺序B1，B2，Bn，并且将签名顺序发送给每一位签名者Bi与验证者C。第6章 公钥密码体制 签名产生过程签名产生过程A将消息m发送到第一位签名者B1，规定此时的签名消息s=0。每一位签名者Bi(i2)收到

12、签名信息(m，(si1，Ri1)后，先对签名进行验证，然后执行以下步骤：(1) Bi随机选取ui(1，2，q1)，计算:m=SHA_1(m)，Ri=uiP=(xi，yi)0，si=si1+kiximui(mod q)(6-1)第6章 公钥密码体制 (2) 将(m，(si，Ri)发送到下一个签名者Bi+1，同时将Ri发送给Bi以后的签名者以及签名验证者C。签名验证过程签名验证过程签名者Bi(i2)要对B1，B2，Bi1的签名进行验证，验证者C要对所有签名者B1，B2，Bn的签名进行验证。Bi验证 (6-2)是否成立。若等式成立，则Bi认为B1，B2，Bi1的签名消息有效；否则判定签名无效，拒绝继

13、续对消息签名。1111iijjjijjx KmRs P第6章 公钥密码体制 同样，C验证(6-3)是否成立。如果等式成立，则认为B1，B2，Bn的签名有效；否则认定为无效签名。11nnjjjnjjx KmRs P第6章 公钥密码体制 签名验证中，由式(6-1)可得(6-4)因此 这就验证了上述有序多重数字签名方案的正确性。111(mod ) ()(mod )iiiiiijjjjssk xm uqk xm uq111111111111()(mod )()(mod )(mod )ijijiijjjjjjijjjjjiijjjjjjmRs pmu pk xm uq pm uk xm uq pk xq

14、 px K式(6-2)右边等式左边第6章 公钥密码体制 2) 广播多重数字签名方案初始化过程此方案的系统初始化和参数设定与有序多重数字签名方案相同，且Bc为签名收集者。签名产生过程A将消息m发送到每一位签名者Bi(i=1，2，n)和签名收集者Bc，规定此时的签名消息s=0。签名者Bi和收集者Bc收到消息后执行以下步骤：(1) Bi随机选取ui(1，2，q1)计算Ri=uiP=(xi，yi)0，将Ri发送到签名收集者Bc;第6章 公钥密码体制 (2) 签名收集者Bc收集到所有Ri(i=1，2，n)后，计算， 随后Bc将R发送到每一位签名者Bi(i=1，2，n);(3) 对于消息m，签名者Bi计算

15、m=RIPEMD_160(m)，然后生成签名 (6-5)则si作为签名者Bi对消息m的子签名，Bi将签名消息(m， si)发送到签名收集者Bc;niiiRxR1),()(mod)(quxkmsiiii第6章 公钥密码体制 (4) 当Bc收集到所有(m， si)(i=1，2，n)后，计算 (6-6)然后将(m，s，R)作为最后签名信息发送到签名验证者C。 njjqss1)(mod第6章 公钥密码体制 签名验证过程签名验证过程C接收到签名信息(m，s，R)后，首先计算m=RIPEMD_160(m)，然后验证(6-7)是否成立。如果等式成立，则认为B1，B2，Bn 对消息m的签名有效；否则认定为无效

16、签名。1()niim KRsp第6章 公钥密码体制 上述验证签名的等式中，由于因此 式(6-7)右边=等式左边上式验证了上述广播多重数字签名方案的正确性。niiiiniiquxkmqss11)(mod)()(mod1111()()()nniiiiiiiniiiiiiniiRspx RmKx Rx RmKx RmK第6章 公钥密码体制 3) 方案分析基于ECC的多重数字签名方案除体现了现有多重数字签名方案的优点外，还具有以下特点：(1) 实现了一类透明的协议过程。广播多重签名中，签名收集者通过签名处理过程11( , ),()(mod )nniiiiiiiRx Rsmkxuq 第6章 公钥密码体制

17、 的引入，隐蔽了各个签名者的随机中间参数Ri与单个子签名消息si，验证者与攻击者都无法将签名信息与单个签名者联系起来，因此方案对于外部攻击具有较强的抵抗能力。对于内部攻击，假定有m(mmax(L0，L1)。H0、 H1、 H2为安全的散列函数，H0，H1，H20，1 *Zn。ka， kb分别为用户A和银行的私钥，Kb=kbP，Ka=kaP作为两者的公钥，密钥对 (Ka，ka)、 (Kb，kb)作为协议中的主密钥。表示是一个从J(Fq)到有限整数集=0，1，q2g+11的单射函数，将其记为(P)x或(P)q。公开n，P、 P1和H0、 H1、 H2以及公钥Kb=kbP，Ka=kaP。设kA，kB

18、(1，2，n1)分别为A和B的私钥， KA=kAp，KB=kBp为A和B的公钥，共享的安全散列函数为H1和H2。*nZ21gqZ第6章 公钥密码体制 2) 委托过程(1) A随机选取u(1，2， n1)，计算:R=up0，h=H1(R) x)f=hkA+u(mod n) (6-9)并将(R，f)秘密地发送给B。 (2) B计算h=H1(R) x)，然后验证:fp=hKA+R是否成立，若成立则计算f=f+kB(mod n)(6-10)第6章 公钥密码体制 3) 代理签名过程对于某个消息m，B随机选取v(1，2， n1)，计算得到T=vp0，再计算m=H2(m)s=(T) xfmv(mod n)(

19、6-11)并将(m，s，R，T)发送给签名验证者。第6章 公钥密码体制 4) 代理签名验证过程验证者接收到(m，s，R，T)后，计算h=H1(R) x)，m=H2(m)验证(T) x(hKA+R+KB)=sp+mT (6-12)是否成立。如果等式成立，则认为B代理A的签名有效；否则认定为无效签名。第6章 公钥密码体制 签名验证中，由式(6-11)可得式(6-12)右边=等式左边这就验证了上述单一代理数字签名方案的正确性。ABAB( )( )( ) ()( ) ()xxxxspm TTfm v pm vpTf pThkukpThKRK第6章 公钥密码体制 3. 基于基于HCC的多重代理数字签名方

20、案的多重代理数字签名方案1) 初始化过程系统初始化和参数设定与单一代理数字签名的方案相同，假设ki，kB分别为Ai(i=1，2，n) 和B的私钥， Ki=kip，KB=kBp为Ai和B的公钥，共享的安全散列函数为H1和H2。第6章 公钥密码体制 2) 委托过程(1) Ai随机选取ui(1，2， n1)，计算Ri=uip0，hi=H1(Ri) x)fi=hiki+ui(mod n)(6-13)并将(Ri，fi)秘密地发送给B。第6章 公钥密码体制 (2) B在收到(Ri，fi)(i=1，2，n)后，计算hi=H1(Ri)x)，然后验证fip=hiKi+Ri是否成立。若成立则认为(Ri，fi)是一

21、个有效的子代理密钥; 否则B要求Ai重复(1)或终止协议过程。第6章 公钥密码体制 3) 代理签名过程B在收到所有(Ri，fi)后，计算出 (6-14)对于某个消息m，B随机选取v(i=1，2， n1)，计算T=vp0，m=H2(m)s=f(m+(T) x)v(mod n)(6-15)(s，T，R1，R2， Rn)为B代表Ai(i=1，2，n)生成的多重代理签名。)(mod1nfkfniiB第6章 公钥密码体制 4) 代理签名验证过程验证者收到(s，T，R1，R2， Rn)和消息m后，计算hi=H1(Ri) x)，m=H2(m)验证(6-16)是否成立。如果等式成立，则认为B代理Ai生成的多重

22、代理签名有效；否则认定为无效签名。TTmspKRKhxBiinii)(?)(1TTmspKRKhxBiinii)(?)(1第6章 公钥密码体制 签名验证中，由式(6-15)可得式(6-16)右边等式左边这就验证了上述多重代理数字签名方案的正确性。B1B1( ) )( ) ) )( ) )()()xxxniiniiiispmTTfmTv pmTTf pfkphKRK第6章 公钥密码体制 4. 代理数字签名方案分析代理数字签名方案分析(1) 代理签名方案可具有区分与身份证实性。根据式(6-10)，在单一代理签名中有f=f+kB(mod n)根据式(6-14)，在多重代理签名中有)(mod1nfkf

23、niiB第6章 公钥密码体制 所以代理签名密钥的产生依赖于原始签名人的普通签名密钥，但不同于原始签名者的普通签名密钥，因此与原始签名密钥是可区分的，而且在存在多个代理签名者的情况下，每个代理签名者的子代理密钥(Ri，fi)也是不相同的。所以，原始签名者可以将不同的代理者区分开，有效地实现对代理者的监督，防止代理签名权力的滥用。在出现问题时，第三方也可以将原始签名者与代理签名者、不同的代理者区分开来。第6章 公钥密码体制 (2) 具有较强的防伪造性。除了原始签名人A以外，任何人(包括代理签名者)在不知道私钥kA的情况下，都不能伪造原始签名人的普通签名信息。同理，代理签名者的签名秘钥对于攻击者(包

24、括原始签名者)也是安全的。如果原始签名者委托了多人代理签名，则根据式(6-10) 、(6-14)，由于代理签名秘钥f中引入了代理签名者的私钥kB，各个代理签名者之间也不能伪造签名信息，因为要伪造签名必须攻击相应代理签名者的私钥及随机数v，这就使得面对的都是求解HCDLP问题。对于内部攻击，假定有m(m3，使得p=6q1，E为由Fp上方程y2=x3+1确定的椭圆曲线，在E/Fp上随机选取q阶点P；Step2：随机选择，令Ppub=sP；Step3：选择Hash函数H：0，1 n，G：0，1*Fp，在安全性分析中，将H与G视为随机预言机(Random Oracle)。*qsZ2pF第6章 公钥密码

25、体制 系统的消息空间为M=0，1 n，密文空间为C=E/Fp0，1n，系统参数为params=p，n，P，Ppub，G，H，主密钥为。提取：对给定的串ID0,1*，算法通过如下方法生成私钥d。Step1：利用MapToPoint将ID映射为E/Fp上的q阶元QID；Step2：计算私钥dID=sQID，其中s为主密钥。加密：对消息mM加密时，进行如下步骤。Step1：利用MapToPoint将ID映射为E/Fp上的q阶元QID；Step2：随机选择rZq；Step3：计算密文其中， 。*qsZID,()rcrP mH g2IDIDpub(,)pge QPF第6章 公钥密码体制 解密：解密：令c

26、=(U，V)C为利用公钥ID加密后的密文，如果U不是E/Fp上的q阶点，则丢弃此密文，否则，利用私钥dID进行如下计算来解密：ID ( (,)VH e dUm第6章 公钥密码体制 以下定理表明，在WDH假设成立的前提下，BasicIdent方案具有单向性。定理定理6-3 令H与G为随机预言机，假设存在一个ID-OWE敌手A，能以优势攻破BasicIdent，并且假设A最多进行了qE0次私钥提取询问及qH0次Hash询问，那么存在算法B，能以至少的优势计算WDH，其中e2.71，为自然对数的底，而B的运行时间是O(time(A)。证明详见参考文献5。EHH1(1)2neqqq第6章 公钥密码体制 4. 具有选择密文攻击安全性的具有选择密文攻击安全性的IBE利用Fujisaki-Okamoto在参考文献13中提供的方法，可以将BasicIdent方案转化为在随机预言模型下具有选择密文攻击安全性的IBE。设E为一个公钥加密方案，用Epk(m; r)表示在公钥pk下利用随机比特r对m加密的结果，Fujisaki-Okamoto定义了混合方案Ehy如下：其中，为随机生成的串; H1，G1为Hash函数。Fujisaki-Okamoto证明了如果E为单向加密方案，则Ehy是在随机预言模型下选择密文攻击安全(IN