RSA公钥密码

单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,单击此处编辑母版标题样式,,1,公钥密码概述,,Diffie,-Hellman,密钥交换协议,,背包体制简介,,RSA,密码体制,,第四章 公钥密码技术,2,RSA,公钥密码算法,主要内容：,RSA,公钥密码算法，,RSA,公钥密码的实现重点：,,RSA,算法，脱密的快速实现，素数生成算法难点：,素数生成算法3,RSA,体制,由,Rivest,、,Shamir,、,Adleman,于,1978,年首次发表；,,最容易理解和实现的公钥算法,;,,经受住了多年深入的攻击,;,,其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；,,RSA,既可用于加密，又可用于数字签名，已得到广泛采用；,,RSA,已被许多标准化组织,(,如,ISO,、,ITU,、,IETF,和,SWIFT,等,),接纳；,,目前许多国家标准仍采用,RSA,或它的变型,,,4,假设,m,为要传送的报文1,、任产生两个素数,p,与,q,，使得,n=,pq,>m,,2,、随机选择数,e,：,e,与,(p-1)(q-1),互素,,3,、用辗转相除法求,d,：,ed,=1 mod(p-1)(q-1),,4,、公开：（,e,，,n,），保密：,d,,,,加密过程：,c=m,e,mod n,,,解密过程：,m=,c,d,,mod n,一、,RSA,算法,1,、,RSA,算法描述,5,定义,：任给一个正整数,m,，如果用,m,去除任意两个整数,a,、,b,所得的余数相同，称,a,、,b,对模,m,同余。

记为： ，若余数不同，则,a,、,b,对模,m,不同余记为： 定理,： ，当且仅当,m|(a-b,),定理,：欧拉定理，对任意 有,推论,:,费尔马定理，,若,p,为素数，则,其中,2,、工作原理,6,RSA,算法论证,① E,和,D,的可逆性,要证明：,D(E(M))=M,M,＝,C,d,＝,(M,e,),d,＝,M,ed,mod n,因为,ed,＝,1 mod,φ(,n),，这说明,ed,＝,t,φ(,n)+1,,其中,,t,为某整数所以,,,M,ed,＝,M,tφ(n)+1,mod n,因此要证明,M,ed,,＝,M mod n,，只需证明,,M,tφ(n)+1,,＝,M mod n,7,RSA,算法论证,在（,M,，,n,）＝,1,的情况下，根据数论,(Euler,定理,),，,,M,tφ(n),,＝,1 mod n,，,于是有，,,M,tφ(n)+1,＝,M mod n,8,RSA,算法论证,在（,M,，,n,）≠,1,的情况下，分两种情况：,第一种情况：,M∈{1,2,3,…,n-1},因为,n=,pq,，,p,和,q,为素数，,,M∈{1,2,3,…,n-1},，且（,M,，,n,）≠,1,。

这说明,M,必含,p,或,q,之一为其因子，而且不能同,,时包含两者， 否则将有,M≥n,,， 与,,M∈{1,2,3,…,n-1},矛盾9,RSA,算法论证,10,RSA,算法论证,不妨设,M,＝,ap,,又因,q,为素数，且,M,不包含,q,，故有（,M,，,q,）＝,1,，,,于是有，,M,φ(,q),＝,1 mod q,进一步有，,M,t(p-1),φ(,q),＝,1 mod q,因为,q,是素数，,φ(,q),＝（,q-1,），所以,t(p-1),φ(,q),＝,t,φ(,n),，,,所以有,,M,t,φ(,n),＝,1 mod q,11,于是，,M,t,φ(,n),＝,bq+1,，其中,b,为某整数两边同乘,M,，,,M,t,φ(,n)+1,＝,bqM+M,,因为,M,＝,ap,，故,,M,tφ(n)+1,＝,bqap+M =abn+M,取模,n,得，,,M,φ(n)+1,＝,M mod n,RSA,算法论证,12,第二种情况：,M,＝,0,,当,M,＝,0,时，直接验证，可知命题成立RSA,算法论证,13,RSA,算法论证,②加密和解密运算的可交换性,D(E(M))=(M,e,),d,=M,ed,=(M,d,)),e,=E(D(M)) mod n,所以，,RSA,密码可同时确保数据的秘密性和数据的,,真实性。

14,RSA,算法论证,③加解密算法的有效性,RSA,密码的加解密运算是,模幂运算,，有比较有效,,的算法15,RSA,算法论证,④在计算上由公开密钥不能求出解密钥,小合数的因子分解是容易的，然而大合数的因子分,,解却是十分困难的关于大合数的因子分解的时间,,复杂度下限目前尚没有一般的结果，迄今为止的各,,种因子分解算法提示人们,这一时间下限,将不低于,,O,（,EXP,（,lnNlnlnN,）,1/2,）,根据这一结论，只要合数足够大，进行因子分解是,,相当困难的16,RSA,算法论证,假设截获密文,C,，从中求出明文,M,他知道,M≡C,d,,mod n,，,,因为,n,是公开的，要从,C,中求出明文,M,，必须,先求,,出,d,，而,d,是保密的,但他知道，,,ed≡1 mod,φ(,n),，,,e,是公开的，要从中求出,d,，必须先求出,φ(,n),，而,,φ(,n),是保密的,但他又知道，,,φ(,n)=(p-1)(q-1),，,,17,要从中求出,φ(,n),，必须,先求出,p,和,q,，而,p,和,q,是保密的,但他知道，,,n=,pq,，,,要从,n,求出,p,和,q,，只有对,n,进行因子分解。

而当,n,足够大时，,,这是很困难的RSA,算法论证,只要能对,n,进行因子分解，便可攻破,RSA,密码由此可以,,得出，,破译,RSA,密码的困难性≤对,n,因子分解的困难性目,,前尚不能证明两者是否能确切相等，因为不能确知除了对,,n,进行因子分解的方法外，是否还有别的更简捷的破译方,,法18,3,、例子：,,,假设,RSA,体制中,p=3,q=11,,取加密密钥,e=7.,,(1),求脱密密钥,d;,,(2),写出相应的加密算法和脱密算法,;,,(3),对明文,m=8,加密7d,,mod20=1,因,e=7,与 互素,,,,故可解模方程 ，即,,解,:,此时,n,＝,p,×,q,＝,33,，且,得到,d,＝,3,19,故,RSA,体制明、密文空间,:,Z,/(33),,加密密钥：,(e, n) =(7, 33),,脱密密钥：,(d, p, q) =(3, 3,11),加密算法,:,,c,＝,m,7,mod33,,脱密算法,:,,m,＝,c,3,mod33,对明文,m,＝,8,加密，得,:,,,c,＝,8,7,mod33=2,20,,二、,RSA,算法的参数选择,为了确保,RSA,密码的安全，必须认真选择密码参数：,,①,p,和,q,要足够大；,,一般应用：,p,和,q,应,512 bits,,重要应用：,p,和,q,应,1024 bits,,②,p,和,q,应为强素数,,文献指出，只要,(p-1),、,(p+1),、,(q-1),、,(q+1),四,,个数之一只有小的素因子，,n,就容易分解。

③ p,和,q,的差要大；,21,④,（,p-1,）和（,q-1,）的最大公因子要小,如果（,p-1,）和（,q-1,）的最大公因子太大，则易受,迭代加密,,攻击,⑤ e,的选择,,随机且含,1,多就安全，但加密速度慢于是，有的学者建议取,,e,＝,216+1,＝,65537,,⑥ d,的选择,,d,不能太小，要足够大,,⑦ 不要许多用户共用一个模,n,；,易受共模攻击,22,1989,年,Lenstra,,,Manasse,利用二次筛法使用数百台工作站分解了,106,位十进制数；,,1990,年,Lenstra,,,Manasse,,,Pollar,利用数域筛法使用,700,台工作站花费４个月时间将,155,位十进制数分解成三个素数之积；,,1994,年,Atkins, Graff,,Lenstra,,,Lerland,利用多重二次筛法的双重大素数算法动用,1600,台计算机联网，,600,名志愿者花费９个月时间分解了,129,位十进制数；,,2002,年成功分解,158,位的十进制数结论：,154,位十进制数（,512bit,）的模长已经不安全，应使用,308,位十进制数（,1024bit,）模长。

23,三、,RSA,算法中大素数生成,RSA,的安全性基础是基于,大合数分解,的困难性，在,RSA,算法中要求模数,N,是两个大素数,p,和,q,的乘积用户选择模数,N,的方法是先找到两个素数，然后生成相应的模数,N,素数判定,是要解决的首要问题24,1,、产生大素数的算法（,Rabin,素性检测算法,）,由欧拉定理知，若,n,为素数：,则,n,可能为素数，也可能为合数,Rabin,由此设计了一个,判定,n,是否为,素数的算法,反过来若： ，则,n,必为合数若,25,1,、产生大素数的算法,——,Rabin,素性检测算法,Rabin,素性检测法是一种,概率,素数测试法其输入为一奇数，输出为两种状态,Yes,或,No,若输入一奇数,N,，而输出为,No,，即表示,N,必定为合数若,输出为,Yes,，则表示,N,为素数的,概率为,1-,ε,，其中,ε,为此素数测试法中,可控制的任意小数,，但不能为,0,ε,是在,N,是合数的条件下误判为素数的条件概率26,Rabin,素性检测算法：,,（1）,任取一个大奇数,n,,（,2,）任取 且,(,a,n,)=1,,（,3,）如果,,,则判,n,是素数；,,否则判,n,是合数，重新选取,n,重复上过程。

Rabin,证明了由上述算法所产生的素数的误判概率,:,由此,,,我们将算法中的第,(2),和,(3),步骤重复,k,次,,,,这样判定,n,为素数的误判概率小于等于,(1/4),k,计算复杂度为：,O((log,2,n),3,),27,Miller-Rabin,算法,,,随机选择一个奇整数,n(,如利用伪随机数产生器,),；,,随机选择一个整数,a

①快速乘方算法,30,,,,指数运算 最简单而直接的计算方法，就是将,m,连续乘,e-1,次，如此就可以获得的值了当,m,或,e,很大时，其计算复杂度将是非常高的在指数运算中，比较有名的是,二元法（也称为平方乘法）,31,设,e,为,k,位二进制数，,w(e,),为,e,的二进制系数中为,1,的个,,数，则最多只需要计算,w(e,) -1,次平方,和,w(e,),次数的模,,乘,从而大大简化了计算32,以,512,比特加密指数为例，整数,e,的二进制表示为,:,一般的加密过程为,:,33,,,,,,,,当要对明文进行加密时，可先进行预处理，计算出,m,2,、,m,3,等，这种方法我们称之为窗口法34,例：,,计算,:,,,,,,35,第一步首先计算,,第二步计算,,第三步计算,,第四步计算,,最后一步计算,,,结论：,36,②快速模乘算法,反复平方乘算法解决了快速乘方取模的问题，,,仍未解决快速模乘的问题；,,Montgomery,算法,是一种快速模乘的好算法；,将以上两种算法结合成为实现,RSA,密码的,,有效,方法37,,,,,Montgomery,算法的思路：,,•,要计算,Y=AB mod n ,,因为,n,很大，取模运算困难，采取一,,个小的模,R,，回避大模数的计算。

•,利用空间换时间，多用存储空间换取快速•,缺点：不能直接计算出,Y=AB mod n,，只能计算出中间,,值,AB,R,-1,mod n,，因此还需要预处理和调整运算一次性,,计算,Y=AB mod n,并不划算•,适合：,RSA,等密码中多次的模乘计算38,对称密钥密码学与公钥密码学,1,、对称密钥密码学的优点,（,1,）能够设计为具有很高的数据吞吐率硬件实现可以达到每秒加密几百兆字节，而软件实现的吞吐率也达到了每秒兆字节的数量级2,）对称密码的密钥相对较短3,）对称密钥密码可以作为要素来构造各种密码机制比如伪随机数生成器、杂凑函数、快速数字签名方案等,（,4,）对称密钥密码能合成强密码简单变换容易被分拆，但是研究其弱点后，可用来构造强的乘积密码39,2,、对称密钥密码学的缺点,（,1,）在一个双方的通信中，密钥必须在两端都保密2,）在大型网络中，要管理许多密钥对其结果是，有效的密钥管理需要一个无条件可信的,TTP,称一个,TTP,是无条件可信的，如果它在所有事情上都可信例如它也许可以访问用户的秘密密钥和私钥，还承担着公钥和标识符的联系）,,（,3,）对实体,A,与,B,之间的一个双方通信，使用密钥的良好习惯是：经常更换密钥，通常是会话密钥一次一换。

4,）源自对称密钥加密的数字签名机制通常需要关于公开验证函数的大密钥，或者使用,TTP,40,3,、公钥密码学的优点,（,1,）只有私钥必须保密但必须保证公钥的真实性）,,（,2,）与无条件可信的,TTP,相反，公钥密码管理需要的只是一个功能上可信的,TTP,（称一个,TTP,是功能上可信的，如果它是诚实且公正的，但是不可以访问用户的秘密密钥和私钥）关于使用方式，和实时的需要使用相反，这个,TTP,也许只需以离线方式使用3,）依赖于使用方式的差别，一个私钥,/,公钥对可以在一段相当长的时期内保持不变，甚至数年比如多次会话使用相同密钥41,（,4,）许多公钥方案产生了相对有效的数字签名机制用于刻画公开验证函数的密钥通常比对称密钥小很多5,）在大型网络中，所需密钥的数量要比对称密钥情形下少很多42,4,、公钥密码学的缺点,（,1,）在吞吐率方面，大多流行的公钥加密方法要比已知最好的对称密钥加密方案慢几个数量级2,）密钥长度（如,RSA,的,1024,比特）明显要比对称密钥（如,64,比特或,128,比特）加密所需大得多（,10,倍或更多）这是因为针对对称密钥系统的最有效的攻击是密钥穷搜（这一般是设计要求），而对公钥系统来说，快捷攻击（如因子分解）比穷搜有效得多。

43,（,3,）没有公钥方案被证明是安全的（对分组秘密也一样）至今发现的最有效的公钥加密方案都把安全性建立在一小批数论问题的困难性假定之上4,）公钥密码学没有对称密钥加密那样长久的历史，它在,20,世纪,70,年代中期才被发现44,5,、比较总结,,对称密钥加密和公钥加密有许多互补的优点目前的密码系统融合了两者的优势凭借公钥加密技术来建立密钥，然后用于实体,A,和,B,进行通信的对称密钥密码系统A,和,B,就可综合利用公钥方案的公钥与私钥对长期性，以及对称密钥方案的高效性数据加密通常是加密过程耗费时间最多的部分，而公钥方案实现的密钥建立只是,A,和,B,之间整个加密过程的一小部分（从耗时来考虑）45,,在计算效率上，公钥加密比不上对称加密，但也没有证明说一定是这样总得来说，公钥密码学推动有效的签名（特别是不可抵赖性）和密钥管理，对称密钥密码学对加密及一些数据完整性应用很有效习题,,46,①利用,RSA,,令,p=3,q=11,d=7,m=5,,手算密文,C,,② 设,RSA,密码的,e=7,n=35,C=10,,手算明文,M,③编程实现,RSA,密码的加解密运算④在,RSA,中使用,e=3,作为加密指数有和优缺点？,,使用,d=3,作解密指数的做法好吗？为什么？,。