《应用密码学》课件第5章 非对称密码(2).pptx

1、12024-3-192024-3-19115.2 RSA密码算法密码算法 1976年，年，Diffie和和Hellman发表了非对称密码的奠基性的论文发表了非对称密码的奠基性的论文“密码学密码学的新方向的新方向”，建立了公钥密码的概念。，建立了公钥密码的概念。1978年，麻省理工学院的年，麻省理工学院的Rivest、Shamir和和Adleman在他们的论文在他们的论文“获获得数字签名和公钥密码系统的一种方法得数字签名和公钥密码系统的一种方法”中，实现了中，实现了Diffie和和Hellman提出提出的思想的一种算法，简称的思想的一种算法，简称RSA算法算法，即为三个人的名字的首字母的缩写。即

2、为三个人的名字的首字母的缩写。5.2.1 RSA算法简史算法简史2024-3-19这三个人中，Rivest和Shamir是计算机学家，负责提出解决方案。Adleman是数学家，负责指出方案的不足，让他们在错误的道路上少浪费时间。Rivest和Shamir花了一年的时间尝试各种想法，Adleman也花了一年时间一一击破。当他们非常失望的时候，Rivest终于找到了一种解决方案，这种方案就是我们现在看到的RSA算法。22024-3-192024-3-19222024-3-19据英国政府声称，他们在切尔特汉姆的政府通讯总部很早就发明了公开密钥密码术。这个最高机密的密码术是由战后的布莱切里庄园的余部发

3、明的。在那里，Ellis于1969年提出了与Diffie和Hellman相类似的非对称密码的思想，接下来的三年中，政府通讯总部的最聪明的头脑努力寻找一个能满足Ellis要求的单向函数，但毫无结果。接着，1973年9月，一个年轻的数学家Cocks加人了这个小组。六个星期后，上司告诉了Cocks 非对称密码的思想，Cocks很快提出了与RSA算法一致的公钥密码体制。科克斯回忆到:“从开始到结束，我总共没花半个小时的时间，我对自己很满意，我想哦，这很好，别人给我提了一个问题，而我解决了。”32024-3-192024-3-1933在公钥密码体制思想提出不久，RSA密码算法就被提出。该算法在非对称密码

4、算法发展史上有着重要的地位，也是至今为止理论上最为成熟完善的公钥密码体制，到现在还被广泛应用。从RSA算法的产生到现在，密码学家对算法的安全性进行了广泛的研究和讨论，并在实践中有了广泛的应用。后面介绍的数字签名算法和身份认证算法中，基于大数分解难题的算法，也是以RSA算法为基础的。42024-3-192024-3-1944l RSA数学基础数学基础:Euler定理，定理，并建立在大整数因子分解的困难性之上。并建立在大整数因子分解的困难性之上。()1(,)1,1(mod)(.mmula mermEa 设设是是大大于于 的的整整 定定理理则则定定理理数数，1 12024-3-1952024-3-1

5、92024-3-19555.2.2 RSA算法描述算法描述1密钥产生密钥产生 A.A.密钥的生成密钥的生成 （1 1）选两个大素数）选两个大素数p p和和q q。（2 2）计算计算n=pn=pq q，(n)=(p-1)(q-1)(n)=(p-1)(q-1)，其中其中(n)n)是是n n的欧拉函数值。的欧拉函数值。(3)(3)选一整数选一整数e e，满足满足11e e (n)(n)，且且gcd(gcd(n),e)=1(n),e)=1。（4 4）计算计算d d，满足满足de1 mod de1 mod (n)(n)，即即d d是是e e在模在模(n)n)下的乘法逆元。下的乘法逆元。（5 5）e,ne

6、,n为公钥，为公钥，d,nd,n为私钥。为私钥。2024-3-1962024-3-192024-3-1966B.B.加密加密(用用e,n)e,n)加密时首先将明文比特串分组，使得每个分组对应的十进制数小于加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n n，即即分组长度小于分组长度小于log2 nlog2 n。然后对每个明文分组然后对每个明文分组m m，作加密运算：作加密运算：即：明文：Mn 密文：.C.C.解密解密(用用d,p,q)d,p,q)密文：C 明文：2024-3-1972024-3-192024-3-1977 把该算法用于保密通信模型中，把该算法用于保密通信模型中，可以

7、有如下图所示的保密通信示意图。可以有如下图所示的保密通信示意图。2024-3-1982024-3-192024-3-1988RSA算法解密的正确性证明 证明：证明：由加密过程知由加密过程知cme mod n，所以，所以 cd mod nmed mod nm1 mod(n)mod nmk(n)+1 mod n 下面分两种情况：下面分两种情况：m与与n互素。由互素。由Euler定理得定理得 m(n)1 mod n,则则mk(n)1 mod n,故故mk(n)+1m mod n 即即cd mod nm。gcd(m,n)1，即，即m与与n不互素。不互素。m与与n不互素且不互素且mn,意味着意味着m要么

8、是要么是p的倍数，要的倍数，要么么q的倍数，不可能既是的倍数，不可能既是p的倍数也是的倍数也是q的倍数（否则的倍数（否则m也是也是q的倍数，从而是的倍数，从而是pq的倍数的倍数，与，与mn，由于计算时使用了模运，由于计算时使用了模运算，则不能通过解密算法正确求得明文算，则不能通过解密算法正确求得明文m，只能得到比，只能得到比n小且与小且与m mod n同余的整同余的整数。数。（6）至于密钥生成过程中的）至于密钥生成过程中的p,q,(n)，一般的说法是安全地销毁。由孙子定，一般的说法是安全地销毁。由孙子定理，理，p,q也可用于提高也可用于提高RSA算法的解密速度。算法的解密速度。（7）这里介绍的

9、只是理论上的）这里介绍的只是理论上的RSA，在实践中使用，在实践中使用RSA算法时，还有一些注算法时，还有一些注意事项，请关注后面的讨论。意事项，请关注后面的讨论。（8）在公钥密码体制中，通常认为公钥具有较长的使用周期，如）在公钥密码体制中，通常认为公钥具有较长的使用周期，如1年或者三年或者三五年，就像学生证或者工作证一样，在一定时间内可以认为代表了公钥持有者的五年，就像学生证或者工作证一样，在一定时间内可以认为代表了公钥持有者的身份。身份。2024-3-19122024-3-192024-3-1912125.2.3 RSA算法举例 例例5：在：在RSA算法密钥产生过程中，设算法密钥产生过程中

10、，设p=13，q=23，取公钥，取公钥e29，则私钥，则私钥d可以用可以用欧欧几里德扩展算法几里德扩展算法求出。求出。由已知可得由已知可得n=pq=13*23=299，(n)=(p-1)(q-1)=12*22=264。264=29*9+329=3*9+23=2+11=3-2=3-(29-3*9)=3*10-29=(264-29*9)*10-29=264*10-29*91-91173mod264由欧几里德扩展算法可得：由欧几里德扩展算法可得：d为为173。2024-3-19132024-3-192024-3-191313（1）加密过程：设）加密过程：设RSA算法的参数选择如上所述，当消息算法的参

11、数选择如上所述，当消息m=9所对应的密文的计算所对应的密文的计算过程为：过程为：929 mod 299211（2）解密过程：）解密过程：211173 mod 2999 这个过程可以采用平方乘算法或者模重复平方算法进行运算。这个过程可以采用平方乘算法或者模重复平方算法进行运算。2024-3-19142024-3-192024-3-191414例：例：p=47,q=61,(n)=(47-1)(61-1)=2760（n=47x61=2867）时，）时，SK=167（d）是否为秘密密钥的候选者？是否为秘密密钥的候选者？用欧几里得算法计算：用欧几里得算法计算：gcd(2760,167)=1 而而PK（e

12、）的选取满足：的选取满足：de1 mod (n)用扩展的欧几里德算法，求得用扩展的欧几里德算法，求得d的逆元的逆元e=1223。2024-3-19152024-3-192024-3-191515 (2)利用加密变换公式利用加密变换公式 C=mPK mod r,即即C=18191223 mod 2867=2756PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223(mod 2867)=18191024 1819128 181964 18194 18192 18191(mod 2867)=2756例：明文例：明文

13、=“RSA ALGORITHM”(1)明文用数字表示明文用数字表示 空白空白=00，A=01,B=02,Z=26(两位十进制数表示两位十进制数表示)1819 0100 0112 0715 1809 2008 13002024-3-19162024-3-192024-3-191616 将对应的密文将对应的密文“2756200105420669234704081815”SK=167=10100111 =27+25+22+21+20 =128+32+4+2+1 M=2756167(mod 2867)=2756128 275632 27564 27562 27561(mod 2867)=1819 依次

14、解密得到明文：依次解密得到明文：1819 0100 0112 0715 1809 2008 1300 依次加密得到密文：依次加密得到密文：2024-3-19172024-3-192024-3-191717选择两个大素数选择两个大素数p和和q，通常要求每个均大于通常要求每个均大于10150。u 计算计算npq和和z(p1)(q1)。u 选择一与选择一与z互素的数、令其为互素的数、令其为d。u 找到一个找到一个e满足满足ed1(mod z)。选好这些参数后，将明文划分成块，使得每个明文报文选好这些参数后，将明文划分成块，使得每个明文报文P长度长度m满足满足0mn。加密加密P时，计算时，计算CPe(

15、mod n)，解密解密C时计算时计算PCd(mod n)。由于模运算的对称性，由于模运算的对称性，可以证明，可以证明，在确定的范围内，加密和解密函数是互逆的。在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开为实现加密，需要公开(e,n)，为实现解密需要为实现解密需要(d,n)。RSA算法归纳算法归纳2024-3-19182024-3-192024-3-1918185.2.4 RSA算法的安全性及常用攻击算法的安全性及常用攻击 通过对通过对RSA算法的学习，我们可以看到，算法的学习，我们可以看到，因为因为e,n为公开密钥，破解为公开密钥，破解RSA算算法最直接的方法，就是分解法最直接

16、的方法，就是分解n，计算，计算n=pq,(n)=(p-1)(q-1),通过通过de1mod(n)求出求出d。所以说，。所以说，随着科学技术的不断发展，人类计算能力的提高，大整数分解的理论和实现随着科学技术的不断发展，人类计算能力的提高，大整数分解的理论和实现也取得了很大进展。也取得了很大进展。RSA-155（即（即n为为155位的十进制，约位的十进制，约512比特）于比特）于1999年年8月月被成功分解，被成功分解，得到两个得到两个78位的十进制素数。因此在使用位的十进制素数。因此在使用RSA的时候，要注意密钥的时候，要注意密钥的大小，现在使用的的大小，现在使用的RSA的的n的长度一般是的长度

17、一般是1024比特，估计在未来一段比较长的比特，估计在未来一段比较长的时间里，时间里，n的长度为的长度为2048比特是安全的。比特是安全的。2024-3-19-分解进展：分解进展：https:/en.wikipedia.org/wiki/RSA_Factoring_Challenge192024-3-192024-3-191919RSA的安全性-为什么要保密p,q,dd d是私钥，当然要保密。为什么要保密是私钥，当然要保密。为什么要保密p,qp,q？也就是说为什么也就是说为什么RSARSA是基是基于大数分解难题的？于大数分解难题的？因为知道了因为知道了p p和和q q，也就是说知道了也就是说知

18、道了n n的因子分解的因子分解，就可以算出，就可以算出EulerEuler函数函数(n)=(p-1)(q-1)n)=(p-1)(q-1)，也就可以利用辗转相除法，根据也就可以利用辗转相除法，根据ed1 mod ed1 mod (n),(n),由由e e求出求出d.d.2024-3-19202024-3-192024-3-192020因为基于大整数分解的公开密钥体制的安全性依赖于大整数（大合数因为基于大整数分解的公开密钥体制的安全性依赖于大整数（大合数分解）问题，所以分解）问题，所以但这只是一个推测，目前，还未能从数学上证明由但这只是一个推测，目前，还未能从数学上证明由d d和和e e计算出计算

19、出m m一定需一定需要分解要分解n n。然而，如果新方法能使密码分析者推算出然而，如果新方法能使密码分析者推算出d d，它也就成为大数分它也就成为大数分解的一个新方法。而且这种方法并不比分解解的一个新方法。而且这种方法并不比分解n n容易。容易。RSA的安全性-依赖大数分解2024-3-19212024-3-192024-3-192121RSA的安全性-|q p|要大*|q qp|p|要大：要大：设设q-p=k,q-p=k,则：则：(q+p)q+p)2 2-(q-p)-(q-p)2 2=4pq=4n=4pq=4n (q+p)(q+p)2 2=(q-p)=(q-p)2 2+4n=k+4n=k2

20、2+4n+4n 如果如果k k的值小，则可以容易找到这样的的值小，则可以容易找到这样的k,k,使得使得k k2 2+4n+4n是一个完是一个完全平方数，从得出全平方数，从得出q+pq+p和和q-pq-p的值，联立求解可得到的值，联立求解可得到q q、p p。例：例：q=313,p=311,q=313,p=311,则则n=97343,(q+p)n=97343,(q+p)2 2=389376=389376 4n=389372,4n=389372,则则(q+p)q+p)2 2-4n-4n4 4，很简单就得到了很简单就得到了k k的值。的值。所以，所以，q,pq,p的差必须很大，最好差几个比特位。的差

21、必须很大，最好差几个比特位。2024-3-19222024-3-192024-3-192222 p-1和和q-1都应有大的素因子。都应有大的素因子。一般是选择两个大素数一般是选择两个大素数p1与与q1,使得使得p=2p1+1与与q=2q1+1也是素数。也是素数。P1是素数时，形如是素数时，形如p=2p1+1的素数通常称为安全素数。的素数通常称为安全素数。2024-3-19232024-3-192024-3-192323RSA的评价 RSA RSA方法在理论上存在一个空白点，即不能确切知道它的保密性方法在理论上存在一个空白点，即不能确切知道它的保密性能如何，能够作出的结论是：攻破能如何，能够作出

22、的结论是：攻破RSARSA公开密钥系统不会比分解因子的公开密钥系统不会比分解因子的问题更困难。问题更困难。这个结论并不排除找到一个破译这个结论并不排除找到一个破译RSARSA密码的有效算法，但找不到相密码的有效算法，但找不到相应的分解因子的快速算法的可能性。应的分解因子的快速算法的可能性。2024-3-19242024-3-192024-3-192424RSA的安全性不同用户选用的素数不能相同2024-3-19252024-3-192024-3-192525RSA的常用攻击-共模攻击不同用户不可共享模不同用户不可共享模n 假定用户B1与B2共享模数为n，它们的加密密钥分别是e1和e2，且（e1

23、,e2）=1，某用户对同一消息m分别以e1和e2加密得到密文c1与c2。12ee12cm modncm modn 攻击者截获密文攻击者截获密文c1与与c2后，由于后，由于(e1,e2)=1，攻击者能够（使用扩展欧几里德算攻击者能够（使用扩展欧几里德算法）计算得到法）计算得到r与与s满足满足re1+se2=1，然后，攻击者将进行如下计算。然后，攻击者将进行如下计算。1212eere+sersrs12c c modn(m)(m)modnmm2024-3-19262024-3-192024-3-192626RSA的常用攻击-共模攻击举例A,B都取p=19,q=23，则n=p*q=437,(n)=(p

24、-1)(q-1)=18*22=396A取e=5,则d=317,B取e=7,则d=283设他们对同一个消息m=8加密A得到c1=memod437=85430mod437B得到c2=memod43787=426mod437,其逆为426-1mod437278因为5*3-2*7=1故4303*426-2mod437=94*(278-1)-2mod437=94*3728mod43712e1e2cm modncm modn（e1,e2）=1re1+se2=1rs12c c modnm2024-3-19272024-3-192024-3-192727除此之外，为保证RSA算法的安全性，还有一些注意事项。（

25、1）不同的用户不能用相同的模数n.大素数的个数是十分庞大的资源，不用担心会被用完。（2）p与q的差值要大（3）p-1和q-1都应有大的素因子。（4）私钥d的选择。如果私钥d的值比较小，由RSA的解密算法可知，对数据进行解密的速度越快。但是，私钥d的值不能太小，一般要求dn1/4。282024-3-192024-3-192828（5）更换密钥如果私钥d被泄露，则在模n的情况下重新计算一对密钥是不够的，而是必须选择一个新的公钥n.（6）e不可太小，否则不安全。根据PKCS#1的建议，公钥指数e是可以选取较小的素数3或65537(=216+1)。选用e=3作为RSA的公钥指数时，如果在实现上遵循PK

26、CS#1 v2.1描述的填充方法(OAEP，Optimal Asymmetric Encryption Padding），目前仍然是安全的。292024-3-192024-3-192929结论：结论：如果私钥d被泄露，则在模n的情况下重新计算一对密钥是不够的，而是必须选择一个新的公钥n.从已知的算法可知，在私钥d泄露的情况下，可以成功分解n的成功概率至少为1/2.说明说明：我们知道ed 1mod(n),也即ed=k(n)+1.但是知道e,d并不能一下子就求得(n)，因为k的取值范围也很大，然而利用已知的算法是可以分解n的，请看例子。RSA的安全性私钥泄露(1)302024-3-192024-3

27、-193030例：设p=9103,q=9871,则n=pq=89 855 713=9871*9103取e=34 986 517,则d=82 330 933ed=2 880 472 587 030 361ed-1=2 880 472 587 030 360(n)=9870*9102=89 836 740(ed1)/(n)=32 063 414由此例可以看出，知道d的值并不是可以很快就能求出(n)的值，也就不能很快分解n,但有算法已经证明知道d是可以分解n的，成功的概率为1/2。所以，一旦d泄露，就要更换n.RSA的安全性私钥泄露(2)312024-3-192024-3-1931315.4.5 R

28、SA算法的实现（略）如何判定一个给定的整数是素数？如何找到足够大的素数p和q?如何计算abmodn？问题问题2024-3-19-知识点：素性检测、欧拉函数、欧几里德算法、模重复平方等！知识点：素性检测、欧拉函数、欧几里德算法、模重复平方等！322024-3-192024-3-193232322024-3-192024-3-193232 知识回顾知识回顾素数个数定理1,0001681451.16100,000959286861.1010,000,0006645796202411.071,000,000,00050847478482549421.05332024-3-192024-3-193333

29、332024-3-192024-3-1933331.如果每个人都需要一个不同的素数，难道素数不会被用光吗？当然不会，事实上，小于n的素数的总数为n/(lnn)，这个结论称为素数个数定理。例：小于10100 的素数个数x x=10100/ln10100 ln10100log210100=100*log210 10100/400如果是21024呢？算法实现对素数的一些认识342024-3-192024-3-193434342024-3-192024-3-1934342、是否会有两个人偶然地选择了同样的素数的情况呢？这种情况不会发生。生日悖论：在一个随机选择的23个成员的组里面，至少有两个人生日相同

30、的概率至少为1/2.一个结论：q=1.17M1/2也就是说，从M个素数中选出q个素数，至少有两个素数相同的概率至少为1/2.在生日悖论中，M365，q23。3、如果有人建立了所有素数的数据库，难道他不能用这个数据库来破译公开密钥算法？算法实现对素数的一些认识352024-3-192024-3-193535352024-3-192024-3-1935354、产生素数困难吗？由素数个数定理，如果在1N之间任取一个数，其为素数的概率为1/lnN，如果取N2512，约为10160,则1/lnN约为1/355，如果再去掉2、3、5、7等的倍数，尝试的次数就不会很多了。算法实现对素数的一些认识362024

31、-3-192024-3-193636362024-3-192024-3-193636-回顾回顾素数的产生（略）素数的产生（略）在非对称密码体制中，无论是基于大数分解难题，还是离散对数难题，都要用到大素数。对于一个大整数是不是素数，数学家们已经做了很多探索，也提出了一些有效的算法()，人们常采用的是Miller-Rabin（）算法，如果该算法判定一个数是合数，这个数肯定是合数。372024-3-192024-3-193737372024-3-192024-3-193737（1）Miller-Rabin概率检测算法 如果n是素数，该等式一定成立；如果n不是素数，该等式一般不成立。如果n不是素数而又

32、使得该等式成立，称n为对于基b的拟素数。整数63是合数，当b=8时，该等式成立，称整数63是对于基b=8的拟素数 Miller-Rabin算法是一个概率算法。算法是一个概率算法。即即该算法判定一个大整数是素数，该算法判定一个大整数是素数，该整数不是素数的概率很小该整数不是素数的概率很小。382024-3-192024-3-193838382024-3-192024-3-193838392024-3-192024-3-193939392024-3-192024-3-193939-Miller-Rabin概率检测算法的实现思路概率检测算法的实现思路 故若故若bn-11(modn)，则下面等式至少有

33、一个成立。，则下面等式至少有一个成立。121221(1)(1).(1)(1)ssnttttbbbbb 12(1)0mod(1)0mod.10modstttbnbnbn Miller-Rabin概率检测算法的实现思路可以描述为：概率检测算法的实现思路可以描述为：计算计算n-1=2st，则有：，则有：402024-3-192024-3-194040402024-3-192024-3-194040-Miller-Rabin概率检测算法：概率检测算法：Miller-Rabin概率检测算法概率检测算法(伪伪C语言语言)可如下描述：可如下描述：Miller-Rabin(n)/把把n-1写成写成n-1=2s

34、t,其中其中t是一个奇数是一个奇数,选取随机整数选取随机整数a,使得使得 1a=1;if(N100)srand(N);for(inti=0;i15;i+)b=rand()%N;if(b2)b+=2;s=m;r0=1;for(intj=0;j0)continue;else if(r0%N=1)continue;else tag=FALSE;break;elsefor(b=2;bN;b+)432024-3-192024-3-194343s=m;r0=1;for(intj=0;j0)continue;elseif(r0%N=1)continue;elsetag=FALSE;break;442024-

35、3-192024-3-194444442024-3-192024-3-194444-Miller-Rabin概率检测算法举例(1)452024-3-192024-3-194545452024-3-192024-3-194545-Miller-Rabin概率检测算法举例概率检测算法举例(2)462024-3-192024-3-194646462024-3-192024-3-194646 根据现有的研究成果，根据现有的研究成果，如果如果n是一个奇合数且能通过是一个奇合数且能通过Miller-Rabin检测检测算法的概率不超过算法的概率不超过25%。但可以通过多次选取但可以通过多次选取a来运行算法，

36、提高结果的准确性。来运行算法，提高结果的准确性。对于奇数对于奇数n，如果选择，如果选择t个不同的个不同的a来运行算法，且返回的结果都是素数来运行算法，且返回的结果都是素数，则，则n是合数的可能性至多为是合数的可能性至多为4-t（即（即1/4t）。）。472024-3-192024-3-194747（1）随机选一个奇数）随机选一个奇数n(伪随机数发生器伪随机数发生器)（2）随机选择一个整数）随机选择一个整数a n（3）执行概率素数判定测试执行概率素数判定测试,如果如果n 未测试通过未测试通过,则则 拒绝数值拒绝数值n,转向步骤转向步骤1（4）如果）如果n已通过足够的测试已通过足够的测试,则接受则

37、接受n,否则转向步骤（否则转向步骤（2）;说明：说明：随机选取大约用随机选取大约用 ln(N)/2的次数，如的次数，如ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。好在生成密钥对时才用到，慢一点还可忍受。确定素数确定素数p和和q以后，只需选取以后，只需选取e,满足满足gcd(e,(n)=1,计算计算d=e-1 mod (n)（扩展的欧拉算法）扩展的欧拉算法）-如何找到足够大的素数如何找到足够大的素数p和和q?2024-3-19482024-3-192024-3-194848 在实现在实现RSA算法时，在提高指数运算速度上，可以采用模重复平方算法时，在提高指数运算速度上，可

38、以采用模重复平方计算法，或者平方乘算法。计算法，或者平方乘算法。在具体实现时，还常采用蒙哥马利算法来提在具体实现时，还常采用蒙哥马利算法来提高模乘运算的速度高模乘运算的速度。由于蒙哥马利算法不容易理解，这里从略。由于蒙哥马利算法不容易理解，这里从略。模重复模重复平方计算法和平方乘算法这两种算法的实现思路、时间和空间代价等相平方计算法和平方乘算法这两种算法的实现思路、时间和空间代价等相似，这里只介绍平方乘算似，这里只介绍平方乘算法。法。2024-3-19492024-3-192024-3-194949492024-3-192024-3-194949 要点要点1：(a x b)mod n=(a m

39、od n)x(b mod n)mod n 要点要点2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的问题：更一般性的问题：amm的二进制表示为的二进制表示为bkbk-1b0,则则 am mod n=a(2i)mod n =a(2i)mod nbi 0bi 0ikiibm202024-3-19502024-3-192024-3-195050快速取模指数算法计算abmodn c 0;d 1 for i k down to 0 do c 2c d (d d)mod n if bi=1 then c c+1 d (d a)mod n return d2024-3-195

40、12024-3-192024-3-195151快速取模指数算法：例子快速取模指数算法：例子i9876543210bi1000110000c=01248173570140280560d=17491575261602412981666717560mod561=12024-3-19522024-3-192024-3-1952522024-3-19532024-3-192024-3-195353DES和RSA性能比较（同等强度）2024-3-19542024-3-192024-3-1954545.3 ElGamal密码算法（略）ElGamal密码算法是基于离散对数难题的公钥密码体制密码算法是基于离散对

41、数难题的公钥密码体制。5.3.1 ElGamal 算法描述算法描述 2024-3-19552024-3-192024-3-1955552024-3-19562024-3-192024-3-195656（1）密钥产生）密钥产生 设设p是一个大素数，使得求解（是一个大素数，使得求解（,）上的离散对数问题在计算上是困难的。）上的离散对数问题在计算上是困难的。令令 是一个本原元。选择是一个本原元。选择x，1xp-1,计算计算yx mod p。其中其中,y,p是公开密钥，是公开密钥，,x,p 是秘密密钥。是秘密密钥。（2）加密算法）加密算法 对于消息对于消息m,发送方选择一个秘密的随机数发送方选择一个秘

42、密的随机数k,1kp,计算：计算：C1k mod p，C2myk mod p 然后把然后把C1,C2发送给接受方。发送给接受方。（3）解密算法）解密算法 接收方接收到接收方接收到C1，C2后，计算后，计算C1-x C2 mod p m，即为发送方的秘密消息。，即为发送方的秘密消息。因为因为(C1-x)C2-xkmxkm mod p。2024-3-19572024-3-192024-3-195757 （1）如同）如同RSA算法一样，对本算法的理解，要放到保密通信模型中去。算法一样，对本算法的理解，要放到保密通信模型中去。读者容读者容易陷入去记忆和理解算法而忽视了算法应用的背景。清楚加密方知道哪些

43、信息，解易陷入去记忆和理解算法而忽视了算法应用的背景。清楚加密方知道哪些信息，解密方知道哪些信息，这有助于对算法的理解，以及对公钥密码体制的理解。密方知道哪些信息，这有助于对算法的理解，以及对公钥密码体制的理解。（2）对于，若）对于，若p为素数，则为素数，则1,2,3,p-1都是与都是与p互素的。互素的。（3）在密钥产生过程中，要求）在密钥产生过程中，要求1xp-1。因为因为1=，p-11modp,1和和显然是显然是不能用来作为公钥的。不能用来作为公钥的。（4）ElGamal 加密算法是一个非确定性的算法。也就是说，对于相同的消息加密算法是一个非确定性的算法。也就是说，对于相同的消息m,由于随

44、机数由于随机数k的选择不同，所得到的密文也不同。的选择不同，所得到的密文也不同。（5）ElGamal加密算法的一个缺点是加密算法的一个缺点是“信息扩展信息扩展”，即密文长度是所对应的明文，即密文长度是所对应的明文长度的两倍。长度的两倍。2024-3-19582024-3-192024-3-195858 5.3.2 ElGamal算法举例例例5-10：用户：用户A选取选取p=41，因，因6是模是模41的一个生成元，取的一个生成元，取g=6，又取私钥，又取私钥r=4，计，计算算=gr mod p25。公布。公布(p,g,)=（41，6，25），保密），保密r=4。若用户若用户B相向相向A发送秘密信

45、息发送秘密信息m=13,他先取得他先取得A的公钥的公钥(p,g,)=（41，6，25），然后选取随机整数），然后选取随机整数k=19，计算，计算c1=gk mod p=619mod 4134,c2=m()k mod p=13*2519 mod 4113*23 mod 41299 mod 4112B发送发送(c1,c2)=(34,12)给给A。A在接收到在接收到B发送给自己的信息发送给自己的信息(c1,c2)=(34,12)后，计算后，计算c1-r c2 mod p=34-4*12 mod 4125*12 mod 4113。2024-3-19592024-3-192024-3-1959592024-3-19