《应用密码学》课件9-非对称密码

非对称密码体制

（公钥密码体制）公钥密码体制提出和分类公钥密码体制概念单陷门函数概念RSA算法EIGamal算法椭圆曲线密码算法密钥分配：加密者指定一个密钥后，必须得想方设法把密钥分发出去给解密者，同时还得小心翼翼确保密钥不被泄露。这是对称密码算法固有的一个矛盾，如何解决呢？对称密码进行密钥分配的要求：已经共享一个密钥：利用密钥分配中心：第一个密钥如何获得和KDC之间的密钥如何获得公钥密码体制的提出公钥密码---密钥问题

使用非对称密钥密码体制进行秘密通信时，假设一个网络中有n个用户，则需要2n个密钥，若n=1000，则2000，则与对称密码体制的密钥500000，密钥管理的复杂度大大缩小。非对称密码体制密钥的复杂度是线性的2n

对称密码体制密钥的复杂度是平方级的n(n-1)/2实际需要－密钥管理6公钥加密模型公钥加密体制的原理密钥分配Bob（发送端）Alice（接收端）公开的密钥7

公钥密码体制的原理8公钥加密体制的原理邮箱的例子任何人可以向邮箱投举报信用户(审计人员)才能打开邮箱，读信的内容9公钥加密体制的原理公钥密钥对参数生成需满足的要求：公开密钥(public-key),可以被任何人知道,用于加密或验证签名；私钥(private-key),只能被消息的接收者或签名者知道,用于解密或签名；由私钥及公开参数容易计算出公开密钥；由公钥及公开参数推导私钥是困难的；10定义单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像x∈X，且由x易于计算它的像y，由y计算它的原像x是不可行的.一个函数是单向陷门函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成.单向陷门函数11单向陷门函数是一族可逆函数fk，满足①Y=fk1(X)易于计算（当k1和X已知时）.②X=f-1k2(Y)易于计算（当k2和Y已知时）.③X=f-1k2(Y)计算上是不可行的（当Y已知，但k2未知时）已知K1，计算出K2是不可行的（当K1已知，但k2未知时）研究公钥密码算法就是要找出合适的陷门单向函数单向陷门函数公钥密码体制的发展历史Diffie和Hellman公钥密码体制的发展历史RonaldRivest,AdiShamir,andLenAdleman14RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。它既可用于加密、又可用于数字签字。

RSA算法的安全性基于数论中大整数分解的困难性。

RLRivest,AShamir,LAdleman,"OnDigitalSignaturesandPublicKeyCryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb1978RSA算法151.密钥的产生①选两个安全的大素数p和q。②计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。③选一整数e，满足1<e<φ(n)，且gcd(φ(n),e)=1。④计算d，满足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。(一般公钥取值为65537（216+1））⑤以{e,n}为公开钥（PK）,{d,n}为秘密钥（SK）。RSA算法1选取大素数的方法：随机产生一个大整数，利用素性检测算法判定该整数是否为素数2以往素检测的算法都是概率性的，即存在一定的错误概率；32003年，印度人发表文章“PrimesisinP”，证明了素判定问题是一个多项式时间问题。1）辗转相除法2）利用欧拉定理求e^{φ(

φ(n))}-1思考：分析两种计算方法的效率162.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：

c≡memodnRSA算法173.解密对密文分组的解密运算为：m≡cdmodn证明RSA算法中解密过程的正确性.证明：由加密过程知c≡memodn，所以cdmodn≡medmodn≡m1

modφ(n)modn≡mkφ(n)+1modnRSA算法18下面分两种情况：①m与n互素，则由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn即cdmodn≡m。②gcd(m,n)≠1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)≠1意味着m是p的倍数或q的倍数，不妨设m=tp，其中t为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与m<n=pq矛盾RSA算法19

由gcd(m,q)=1及Euler定理得mφ(q)≡1modq，所以mkφ(q)≡1modq,［mkφ(q)］φ(p)≡1modq,mkφ(n)≡1modq

因此存在一整数r，使得mkφ(n)=1+rq，两边同乘以m=tp得mkφ(n)+1=m+rtpq=m+rtn即mkφ(n)+1≡mmodn，所以cdmodn≡m.RSA算法RSA保密通信示意图欧拉(Euler)函数

设

(m)为小于或等于m且与m互素的正整数个数，称

(m)为欧拉(Euler)函数。例如，

(3)＝2，

(5)＝4，

(8)＝4。显然，当p为素数时，

(p)＝p－1。关于欧拉函数的重要结论关于欧拉函数的重要结论。若(m1，m2)＝1，则

(m1m2)＝

(m1)

(m2),尤其是当m1，m2都为素数时，

(m1m2)＝

(m1)

(m2)＝(m1-1)(m2-1).例如，

(15)=

(3)×

(5)=2×4=8.实际上，这些数是1，2，4，7，8，11，13，14，共8个。可以用等差数列的方式证明当m1，m2都为素数时的情形欧拉定理

欧拉定理设n≥2且(a，n)＝1，则a

(n)

1(modn)例如，求132001mod17。因为(13，17)＝1，所以13

(17)

1(mod17)，因为

(17)＝16，即1316≡1(mod17)。而2001＝125×16＋1，132001＝（1316）125·13≡13(mod17)，即被17除得的余数为13。当n为素数p时，就是费尔马定理。费尔马定理若p是素数，(a，p)＝1，则ap-1≡1(modp).RSA算法举例在RSA算法密钥产生过程中，设p=13，q=23，取公钥e＝29，则私钥d可以用欧几里德扩展算法求出。由已知可得n=pq=13*23=299，φ(n)=(p-1)(q-1)=12*22=264。e*d≡1modφ(n)怎么求解264=29*9+329=3*9+23=2+1

1=3-2=3-(29-3*9)=3*10-29=(264-29*9)*10-29=264*10-29*91=-91≡173mod264由欧几里德扩展算法可得：d为173。逆元设m是正整数，a是整数，如果存在a’,使得a×a’≡1(modm)成立，则a叫模m的可逆元，a’叫a模m的逆元。例如，设m为11，则8模11的逆元为7，因为8×7≡1(mod11)当a和m互素的情况下，即（a,m）=1,则a的模m的逆元总是存在的，且可以用上面的辗转相除法求得。求逆元举例例如，我们知道89是素数，求60模89的逆元，可以用下面方法。89=1×60+2960=2×29+229=14×2+1则1=29-14×2=29-14×(60-2×29)=29×29-14×60=(89-60)×29-14×60=89×29-60×43求逆元举例等式两端同时mod89得：60×(-43)≡1mod89故60模89的逆元为-43，为方便记为最小非负数，因为-43≡46mod89，故一般说60模89的逆元为46.如何用程序实现求逆元？实际上，这里的逆元通常称为乘法逆元。从后面的学习可以看到，定义不同的运算和单位元，就可能有不同情况下的逆元。RSA算法举例（1）加密过程：设RSA算法的参数选择如上所述，当消息m=9所对应的密文的计算过程为：929mod299＝211（2）解密过程：211173mod299≡929例：选p=7，q=17.取e=5，设明文m=19，求密文c求得n=p×q=119，φ(n)=(p-1)(q-1)=96.取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1，计算满足d·e=1mod96且小于96的d.因为77×5=385=4×96+1，所以d为77，因此公开钥为{5，119}，秘密钥为{77，119}.设明文m=19，则由加密过程得密文为c≡195mod119≡2476099mod119≡66;解密过程为m≡6677mod119≡19.RSA算法30RSA中的计算问题1.RSA的加密与解密过程

RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677mod119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(a×b)modn=[(amodn)×(bmodn)]modn就可减小中间结果。RSA算法模幂运算问题31

2.模指数运算的快速算法

例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此bk=0而bk-i=1或者bk-i=0RSA算法模幂运算32例：求a1919=1×24+0×23+0×22+1×21+1×20所以

a19=((((a1)2a0)2a0)2a1)2a1练习：求a7和a8，并统计快速运算法的运算次数.

RSA算法平方乘算法/***令m=bk2k+bk-12k-1+…+b12+b0，求am=?***/d=1;fori=kdownto0{d≡(d×d)modn;ifbi=1then{d≡(d×a)modn}}returnd注意：在RSA中，运算的形式一般是memodn,则在程序或算法中，所有的乘法或乘方运算之后都有一个模运算。练习题求解1177mod23=？练习题求解1177mod23=？77=(1001101)2ibidd=1611*11mod23≡115011*11mod23≡6406*6mod23≡133113*13mod23≡88*11mod23≡192119*19mod23≡1616*11mod23≡151015*15mod23≡180118*18mod23≡22*11mod23≡2236

整数分解问题：已知n是两个大素数的乘积，求n的素分解RSA的安全性是基于分解大整数困难的假定

如果RSA的模数n被成功地分解为p×q，则获得φ(n)=(p-1)(q-1)，从而攻击者能够从公钥e解出d，即d≡e-1modφ(n)，攻击成功.

RSA算法的安全性37

至今还未能证明分解大整数就是NPC问题，也许有尚未发现的多项式时间分解算法.

随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解.例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130已于1996年4月被成功分解.RSA算法的安全性38

分解算法的进一步改进.过去分解算法都采用二次筛法,

如对RSA-129的分解.而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%.1）在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的.RSA算法的安全性392）|p-q|要大由，如果|p-q|小，则(p-q)2/4也小；因此(p+q)2/4稍大于n,即(p+q)/2稍大于n1/2。那么①顺序检查大于n1/2的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。②由x2-n=y2，得n=(x+y)(x-y)，可得n的分解.例如若n=79523，则n1/2

>281，则2822-79523=1，因此p=282+1=283，q=282-1=281RSA算法的安全性403）p-1和q-1都应有大素因子设攻击者截获密文c，可如下进行重复加密：

RSA算法的安全性41若，即，则有，即，所以在重复加密的倒数第2步就可以恢复出明文m.这种攻击法只有在t较小时才是可行的，为抵抗这种攻击，应保证使t很大.所以为使t大，p-1和q-1都应有大的素因子，且Φ((p-1)*(q-1))有大的素因子RSA算法的安全性RSA算法的安全性4）RSA的选择密文攻击一般攻击者是将希望解密的信息C作一下伪装reC，让拥有私钥的实体解密（签名）。然后，经过解密计算就可得到它所想要的信息。

(reC)d=red*Cdmodn=r*Mmodn，所以M=(reC)d*r-1这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，只有采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密。RSA算法的安全性5）RSA的公共模数攻击若系统中用户共有一个模数n，而拥有不同的e和d。若存在同一信息（设为P）分别用不同的公钥（e1和e2）加密，C1=Pe1modn；C2=pe2modn设密码分析者截获n、e1、e2、C1和C2，若恰好e1和e2互质，则他可以得到P。RSA算法的安全性证明：因为e1和e2互质，故用Euclidean算法能找到r和s，满足：r*e1+s*e2=1则(C1)r*(C2)s=(Pe1)r*(pe2)smodn=Pr*e1+s*e2modn=Pmodn不要共享模数n其它共模攻击方法：在共模假设下，一对e和d将有利于攻击者分解模数；或者计算出其它成对的e’和d’，而无需分解模数。45RSA算法的安全性RSA存在很多种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的，为保证算法足够安全，参数须满足下面几个基本要求：需要选择足够大的素数p,q,|p-q|较大，且(p-1)和(q-1)没有小的素因子.通常选择小的加密指数e,且与ø(N)

互素，

e对所有用户可以是相同的，最初建议使用e=3，现在3太小，常使用e=216-1=65535.解密指数比较大素数的产生在非对称密码体制中，无论是基于大数分解难题，还是离散对数难题，都要用到大素数。因而，寻找大素数一直是密码学家十分关注的。对于一个大整数是不是素数，数学家们已经做了很多探索，也提出了一些有效地算法，人们常采用的是Miller-Rabin算法，该算法常用来判断一个大整数是否素数的算法。如果该算法判定一个数是合数，这个数肯定是合数。Miller-Rabin算法是一个概率算法。也就是说，该算法判定一个大整数是素数，该整数不是素数的概率很小。Miller-Rabin概率检测算法Miller-Rabin概率检测算法的理论基础是费尔马定理，即设n是正奇整数，如果n是素数，由费尔马定理，对于任意整数b(1<b<n-1),有bn-1≡1modn.如果n是素数，该等式一定成立；如果n不是素数，该等式一般不成立。如果n不是素数而又使得该等式成立，称n为对于基b的拟素数。拟素数就表示不是素数是合数。整数63是合数，当b=8时，该等式成立，称整数63是对于基b=8的拟素数由此可知，如果对整数b(1<b<n-1),(n,b)=1,使得bn-1≡1modn不成立，则n是一个合数。Miller-Rabin概率检测算法由上面的讨论可知，判断一个正奇整数是不是合数，可以通过尝试找整数b(1<b<n-1),(n,b)=1,使得bn-1≡1modn成立与否。如果不成立，则n是一个合数，如果成立，则n可能是素数，可以通过再找别的整数b(1<b<n-1)进行尝试。Miller-Rabin概率检测算法正是如此Miller-Rabin概率检测算法的实现思路计算n-1=2st，则有：故若bn-1≡1(modn)，则下面等式至少有一个成立。，Miller-Rabin概率检测算法可如下描述Miller-Rabin(n)//把n-1写成n-1=2st,其中t是一个奇数,选取随机整数a,使得1<a<n-1b≡at(modn)ifb≡1(modn)thenreturn(“n通过测试，n可能是素数”),结束fori=0tos-1{ifb≡-1(modn)thenreturn(“n通过测试，n可能是素数”),结束

elseb≡b2(modn)}return(“n是合数”)Miller-Rabin概率检测算法举例Miller-Rabin概率检测算法举例例5-3：取n=29，29-1=22*7,即s=2,t=7设a=3,b=37(mod29)≡12,i=0,b2=144(mod29)≡-1输出：n是素数设a=4,b=47(mod29)≡28,i=0,b=28(mod29)≡-1输出：n是素数此例为判定合数为素数的例子以n=25,a=7为例。取n=25，25-1=23*3,即s=3,t=3由算法，b=73≡18mod25i=0,b2=182≡-1(mod25),输出：n是素数实际上，25是合数。这时可以通过另选择一个a(1<a<n-1),(n,a)=1,如a=2，再次运行算法。由算法，b=23≡8mod25i=0,b2=82=64≡14(mod25)i=1,b2=142=196≡21(mod25)i=2,b2=212=441≡16(mod25)循环完毕，输出：n是合数由此判断n肯定是个合数。（2）大素数个数的估计通过一个简单的例子，可以明白大素数的个数是十分庞大的资源，不用担心会被用完。例5-8：小于10100

的素数个数x大概为多少？由素数个数定理，x=10100/ln10100因

ln10100<log210100=100*log210<100*4=400

故x=10100/ln10100>10100/400可以看到，这是非常可观的数量。事实上，素数的分布是数字越大越稀，所以没有上面估计的这么乐观，但也没有必要杞人忧天到去担心是不是会用完的这种状况。非对称密码体制的分类主要分成如下几类：（1）基于大数分解难题的，包括RSA密码体制，Rabin密码等。（2）基于离散对数难题的，如ElGamal密码，有限域上的离散对数问题的难度和大整数因子分解问题的难度相当。（3）基于椭圆曲线离散对数的密码体制。严格说来，它可以归与基于离散对数难题的密码体制中。另外，颇受关注的还有NTRU作业（测试）(1)在RSA算法密钥产生过程中，设p=19，q=11，取公钥的参数e＝7，则求RSA的公钥和私钥？若明文m=19，求密文？

(2)若已知RSA中公钥参数e=5，模数n=194477，能否破解出私钥参数d的值？（写出破解过程）

(3)假设攻击者已知用户A的公钥（7,119），用户B的公钥（5,119)，然后用户A和用户B对同一信息P进行加密，得到密文分别为C1=9，C2=32，求解出明文P？（采用共模攻击方法）习题讲解(1)n=p*q=209，φ(n)=（p-1)(q-1)=18*10=180e*d≡1（mod180），即7*d≡1（mod180）180=25*7+57=1*5+25=2*2+11=5-2*2=5-2*(7-5)=3*5-2*7=(180-25*7)*3-2*7=180*3-77*7,两边同时模180，可得1≡-77*7（mod180);私钥d参数d=180-77=103RSA私钥为(103,209),公钥为（7,209）（2）m=19则密文c≡197(mod209)c≡(192)3*19(mod209)≡(152)3*19(mod209)≡57习题讲解(2)若已知RSA中公钥参数e=5，模数n=194477，能否破解出私钥参数d的值？（写出破解过程）

解：猜测p和q相差不大，则模数n>4402

，则需要寻找一个x>440，满足x2-n=y2，则从x=441开始尝试4412-194477=4=22，因此（x-2)(x+2)=194477(441-2)(441+2)=194477，因此p=439，q=443φ(n)=（p-1)(q-1)=438*442=1935965*d≡1（mod193595）193596=38719*5+11=193596-5*38719私钥d=-38719≡193595-38719（mod193595）d=154877习题讲解(3)假设攻击者已知用户A的公钥（7,119），用户B的公钥（5,119)，然后用户A和用户B对同一信息P进行加密，得到密文分别为C1=9，C2=32，求解出明文P？（采用共模攻击方法）解：r*e1+s*e2=1，即：r*7+s*5=15*s≡1（mod7）7=5+25=2*2+11=5-2*（7-5）=3*5-2*7，因此r=-2，s=3P=(C1)r*(C2)s=(9)-2*(32)3mod119=(9-1)2*(32)3mod119(9-1)mod119,求逆元119=13*9+29=4*2+11=9-4*2=9-4*(119-13*9)=-4*119+53*9(9-1)mod119=53,因此P=(53)2*(32)3mod119=72*43mod119=2，明文是是119补充内容RSA算法数学基础RSA算法的实现:快速模幂运算（FastExponentiation）扩展欧几里得算法（ExtendedEuler’sAlgorithm）模求逆（Modularinverses）费马定理(Fermat’sLittleTheorem)中国剩余定理CRT(ChineseRemainderTheorem)素数检测算法RSA算法的实现在RSA算法的实现过程中，参考已知文献，需要考虑以下的问题：①如何判定一个大的整数是不是素数困难吗？②指定长度的素数个数是有限的，当有很多人使用RSA算法时会不会发生两个人用同一个素数的情况？③从RSA算法可以看到，算法中的主要运算都集中在指数运算以及模运算上。如何有效提高这两种运算，可以加快算法的加解密速度。另外，具体实现RSA算法时，还要参考RSA的加密标准(PKCS#1,IEEEP1363)，可以提高算法加密的安全性。大整数是否素数的判定定理5-2：小于n的素数的总数近似为n/(lnn)，这个结论称为素数个数定理。（1）大整数是否素数的判定，产生素数困难吗？大整数是否素数的判定可以参考5.1.5节。由素数个数定理，如果在1~N之间任取一个数，其为素数的概率为1/lnN，如果取N＝2512，约为10160,则1/lnN约为1/355，如果再去掉2、3、5、7等的倍数，尝试的次数就不会很多了。63RSA算法RSA的快速实现加密很快，指数小；解密比较慢，指数较大.利用中国剩余定理CRT，加快计算速度.CRT对RSA解密算法生成两个解密方程（利用M=CdmodR）即:M1=Mmodp=(Cmodp)dmod(p-1)modp

M2=Mmodq=(Cmodq)dmod(q-1)modq解方程组M=M1modp;M=M2modq.利用CRT,具有唯一解：M=[((M2+q-M1)umodq]p+M1.其中p.umodq=1.中国剩余定理中国剩余定理mod3:Nmod3=1中国剩余定理mod5:Nmod5=2中国剩余定理mod7:Nmod7=2中国剩余定理Na(mod3)N

b(mod5)N

c(mod7)N如何求解？中国剩余定理设m1,m2,…,mn是两两互素的正整数，令m=m1m2…mn=miMi,MiMi’≡1modmi,i∈[1,n]，则方程组：的解为：x≡M1M1’b1+M2M2’b2+…+MnMn’bn(modm)注意，

m=m1m2…mn=miMi，故Mi=m/mi。m1,m2,…,mn是两两互素的正整数，故（Mi,mi）=1,通过MiMi’≡1modmi计算的逆元一定存在。韩信点兵有兵若干，若列成5行纵队，则末行1人，若列成6行纵队，则末行5人，若列成7行纵队，则末行4人，若列成11行纵队，则末行10人，求兵数？解：由题意得x≡1(mod5)，x≡5(mod6)，x≡4(mod7)，x≡10(mod11)。令m1＝5，m2＝6，m3＝7，m4＝11，b1＝1，b2＝5，b3＝4，b4＝10。则m＝2310，M1＝462，M2＝385，M3＝330，M4＝210。利用辗转相除法得M1’＝－2，M2’＝1，M3’＝1，M4’＝1。x≡1·(－2)·462＋5·1·385＋4·1·330＋10·1·210≡4421≡2111(mod2310)练习题x1(mod3)x

2(mod5)x

2(mod7)x如何求解？平方剩余设m为大于1的正整数，(a,m)=1,如果方程x2≡a(modm)有解，则称a为modm的平方剩余，也称二次剩余；若方程无解，则称a为modm的平方非剩余。以m=11为例。12≡1，22≡4，32≡9，42≡5，52≡3，62≡3，72≡5，82≡9，92≡4，102≡1mod11由定义5-1知，1，3，4，5，9为mod11的平方剩余，故2，6，7，8，10为mod11的平方非剩余。也就是说，我们找不到一个整数，使得它的平方在mod11后，其余数是2，6，7，8，10这5个整数中的一个。勒让得符号设p为奇素数，a为整数，定义勒让得(Legendre)符号为：

通过计算勒让得符号，容易判断二次方程x2≡a(modp)(p是奇素数)有没有解。因此5不是模23的平方剩余离散对数设p为奇素数，对于整数g,1<g<p,使得g?≡1(modp)成立的最小正整数如果是p-1,则g就是模p的原根。离散对数问题已知g是模p的原根，对于集合G={gk,k=0,1,2,…p-1}，给定的x,x为整数，计算y≡gxmodp是容易的，但对于给定的y∈G,x可以表示为x≡loggymodp，当p是一个大素数的时候，要计算x是困难的。求解x≡loggymodp的问题，称为离散对数问题。76Diffie-Hellmankeydistributionscheme的变形能够用于安全交换密钥Publishedin1985byElGamal:T.ElGamal,"APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms",IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.

安全性基于有限域上的离散对数问题的困难性.缺点：增加了传送信息长度（2倍）ElGamal算法771)密钥产生过程：

首先选择一素数p,生成元g和小于p的随机数x，计算y≡gxmodp，以(y,g,p)作为公开密钥，x作为秘密密钥.2)加密过程：设欲加密明文消息为M.

随机选一与p-1互素的整数k，0<=k<=p-1；计算密文对:C={C1,C2},发送给接收者.C1≡gkmodp,C2≡ykMmodp.ElGamal算法78

3)

解密过程:

计算明文:因为.ElGamal算法k需要永久保密，且不能重复使用.为什么？791)密钥生成.

选择公开参数：p=97

及本原根

a=5

；

Bob选择秘密钥xB=58，计算并发布公钥yB=558=44mod97.

2)Alice要加密M=3

给Bob.

首先得到Bob的公开密钥yB=44，选择随机k=36

计算:

K=4436=75mod97.计算密文对:C1=536=50mod97

；

C2=75.3mod97=31mod97.发送{50,31}

给Bob.3)Bob解密消息.恢复消息密钥K=5058=75mod97.Bob计算K-1=22mod97.Bob恢复明文M=31*22=3mod97.ElGamal算法ElGamal算法有限域上离散对数问题已知（Zp，+，*）是一个有限域，g为Zp*的生成元，y∈Zp，求x使得y=gxmodp如果求离散对数问题是容易的，则获得公钥攻击者能够解出x，则算法完全破译.RSA与ElGamal比较RSAElGamal加密一次模幂运算两次模幂+一次模乘解密一次模幂运算一次模幂运算密文密文不扩张密文扩张确定算法不确定算法安全RSA问题离散对数问题RSA与EIGamal算法比较512位768位1024位加密0.03秒0.05秒0.08秒解密0.16秒0.48秒0.93秒签名0.16秒0.52秒0.97秒验证0.02秒0.07秒0.08秒512位768位1024位加密0.33秒0.80秒1.09秒解密0.24秒0.58秒0.77秒签名0.25秒0.47秒0.63秒验证1.37秒5.12秒9.30秒具有8位公开密钥RSA对于不同长度模数的加解密速度（SPARCII上）具有160位指数的EIGamal对于不同长度模数的加解密速度（SPARCII上）

当前的技术进展使分解算法和计算能力在不断提高，计算所需的硬件费用在不断下降。

RSA-129：110位十进制数字早已能分解。Rivest等最初悬赏$100的RSA-129，已由包括五大洲43个国家600多人参加，用1600台机子同时产生820条指令数据，通过Internet网，耗时8个月，于1994年4月2日利用二次筛法分解出为64位和65位的两个因子，原来估计要用4亿亿年。所给密文的译文为“这些魔文是容易受惊的鱼鹰”。这是有史以来最大规模的数学运算。

RSA-130于1996年4月10日利用数域筛法分解出来。

RSA-140于1999年2月分解出来。

RSA-155(512bit)于1999年8月分解出来大数分解进程

目前RSA的攻击现状是有关RSA-155分解，其具体情况是1999年8月22日，来自六个不同国家的科学家们在CWI（CWI是在荷兰的一个数学和计算机科学的国家研究学会）的HermanteRiele的带领下，在对RSA-155的攻击中，利用数域筛法（NFS）成功的分解出了512-bitRSA模的素因子。要分解RSA-155所需的CPU时间大约为8400MIPS年（MIPS-年指以每秒执行1000000条指令的计算机运行一年），这大约为分解RSA-140所需时间的4倍。分解RSA-155总共用了7个月的时间。密码分析者估计在3年内分解RSA-155所用到的算法和计算技术至少在科技界将会得到普及，因此RSA-155将不再安全。并且人们预计，在十年内RSA-232也将被攻破。大数分解进程2005年，作为公共研究一部分的有663bit长的RSA-200已经被一种一般用途的方法所分解。

采用广义数域筛分解不同长度RSA公钥模所需的计算机资源

密钥长(bit)所需的MIPS-年*

116(Blacknet密钥)4001295,00051230,000768200,000,0001024300,000,000,0002048300,000,000,000,000,000,000*MIPS-年指以每秒执行1,000,000条指令的计算机运行一年

椭圆曲线密码体制概述为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（ellipticcurvecryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景。ECC已被IEEE公钥密码标准P1363采用椭圆曲线举例一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：

y2+axy+by=x3+cx2+dx+e(4.1)其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。加法运算椭圆曲线上的加法运算定义如下：如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）：①O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。②设P1=(x,y)是椭圆曲线上的一点（如图4.4，见书），它的加法逆元定义为P2=-P1=(x,-y)。这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，还可得O=-O加法运算③设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下：画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。④点Q的倍数定义如下：在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…，等。密码学中用的椭圆曲线最为常用的椭圆曲线是由方程y2≡x3+ax+b(modp)(a,b∈GF(p),4a3+27b2(modp)≠0) (4.2)定义的曲线。例p=23，a=b=1，4a3+27b2(mod23)≡8≠0，方程为y2≡x3+x+1，其图形是连续曲线，由图4.4(b)所示。设Ep(a,b)表示方程(4.2)所定义的椭圆曲线上的点集{(x,y)|0≤x<p,0≤y<p，且x,y均为整数}并上无穷远点O。椭圆曲线上点的产生一般来说，Ep(a,b)由以下方式产生：①对每一x(0≤x<p且x为整数），计算x3+ax+b(modp)。

②决定①中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0时只有一个平方根）。加法定义Ep(a,b)上的加法定义如下：设P，Q∈Ep(a,b)，则①P+O=P。②如果P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，表示为-P。由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如上例，P=(13,7)∈E23(1,1)，-P=(13,-7)，而-7mod23≡16，所以-P=(13,16)，也在E23(1,1)中。加法定义③设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下规则确定：

x3≡λ2-x1-x2(modp) y3≡λ(x1-x3)-y1(modp)其中加法举例－不同点相加以E23(1,1)为例，设P=(3,10)，Q=(9,7)，计算P+Q加法举例－同点相加求2P，P=(3,10)

在椭圆曲线上实现Diffie-Hellman的体制。假定椭圆曲线E定义在Zq域上。设P∈E，要求由P产生的群的元素足够多。A和B分别选a和b予以保密，但将aP,bP∈E公开。A、B间通信用的密钥为abP，这是第三者无法得知的。

椭圆曲线上实现DH体制DH体制第1步，选取椭圆曲线，其上面的点构成的Abel群Ep(a,b)第2步，取Ep(a,b)的一个生成元G(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数。两用户A和B之间的密钥交换如下进行：①A选一小于n的整数nA，作为秘密钥，并由PA=nAG产生Ep(a,b)上的一点作为公开钥。②B类似地选取自己的秘密钥nB和公开钥PB。③A、B分别由K=nAPB和K=nBPA产生出双方共享的秘密钥。这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA。攻击者若想获取K，则必须由PA和G求出nA，或由PB和G求出nB，即需要求椭圆曲线上的离散对数，因此是不可行的。DH体制例p=211，Ep(0,-4)，即椭圆曲线为y2≡x3-4，G=(2,2)是E211(0,-4)的阶为241的一个生成元，即241G=O。A的秘密钥取为nA=121，公开钥为PA=121(2,2)=(115,48)。B的秘密钥取为nB=203，公开钥为PB=203(2,2)=(130,203)。由此得到的共享密钥为121(130,203)=203(115,48)=(161,169)，即共享密钥是一对数。DH体制举例离散对数问题（DLP）：给定一个素数p，Zp*的一个生成元g及一个元素b∈Zp*，寻找整数x，使得gx≡bmodp。另一个取法：给定一个素数p，g是Zp*的一个q阶元素，b∈Zp*，寻找整数x，使得gx≡bmodp。例：如果p=41，6是模11的一个生成元，若取g=6，它的阶为40。如果p=41，6是模11的一个生成元，64mod41=25，若取g=25，它的阶为10。离散对数问题ElGamal公钥密码：（1）密钥产生过程。A选择一个素数p以及整数模p的乘法群Zp*的一个生成元g。选取一个随机整数r(1≤r≤p-2)，计算β=grmodp。以(p,g,β)作为公钥，r作为私钥。（2）加密过程。设B欲向A发送的明文消息为m。B获取公钥(p,g,β)，将消息m表示成{0,1,…,p-1}范围内的整数。选取随机整数k(1≤k≤p-2)，计算c1=gkmodp和c2=m(β)kmodp，得密文为c=(c1,c2)；B发送(c1,c2)给A.（3）解密过程。A计算c1-rc2modp恢复出m

（因为(c1-r)c2≡g-rkmgrk≡mmodp）。ElGamal公钥密码用户A选取p=41，因6是模11的一个生成元，取g=6，又取私钥r=4，计算β=grmodp=25。公布(p,g,β)=（41