RSA公钥密码体制简介课件

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,1,RSA,公钥密码算法,主要内容：,RSA,公钥密码算法，,RSA,公钥密码的实现。,重点：,RSA,算法，脱密的快速实现，素数生成算法。,难点：,素数生成算法。,1RSA公钥密码算法主要内容：RSA公钥密码算法，RSA公钥,2,RSA,体制,由,Rivest,、,Shamir,、,Adleman,于,1978,年首次发表；,最容易理解和实现的公钥算法,;,经受住了多年深入的攻击,;,其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；,RSA,既可用于加密，又可用于数字签名，已得到广泛采用；,RSA,已被许多标准化组织,(,如,ISO,、,ITU,、,IETF,和,SWIFT,等,),接纳；,目前许多国家标准仍采用,RSA,或它的变型,2RSA体制由Rivest、Shamir、Adleman于1,3,假设,m,为要传送的报文。,1,、任产生两个素数,p,与,q,，使得,n=pqm,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,算法描述,3假设m为要传送的报文。一、RSA算法1、RSA算法描述,4,定义,：任给一个正整数,m,，如果用,m,去除任意两个整数,a,、,b,所得的余数相同，称,a,、,b,对模,m,同余。记为： ，若余数不同，则,a,、,b,对模,m,不同余。记为： 。,定理,： ，当且仅当,m|(a-b),。,定理,：欧拉定理，对任意 有,推论,:,费尔马定理，,若,p,为素数，则,其中,2,、工作原理,4定义：任给一个正整数m，如果用m去除任意两个整数a、b所得,5,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,。,5RSA算法论证 E和D的可逆性要证明：D(E(M)=M,6,RSA,算法论证,在（,M,，,n,）,1,的情况下，根据数论,(Euler,定理,),，,M,t(n),1 mod n,，,于是有，,M,t(n)+1,M mod n,。,6RSA算法论证在（M，n）1的情况下，根据数论(Eule,7,RSA,算法论证,在（,M,，,n,）,1,的情况下，分两种情况：,第一种情况：,M1,2,3,n-1,因为,n=pq,，,p,和,q,为素数，,M1,2,3,n-1,，且（,M,，,n,）,1,。,这说明,M,必含,p,或,q,之一为其因子，而且不能同,时包含两者， 否则将有,Mn,， 与,M1,2,3,n-1,矛盾。,7RSA算法论证在（M，n）1的情况下，分两种情况：第一种,8,RSA,算法论证,8RSA算法论证,9,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,。,9RSA算法论证不妨设Map 。,10,于是，,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,算法论证,10于是，M t(n) bq+1，其中b为某整数。RSA,11,第二种情况：,M,0,当,M,0,时，直接验证，可知命题成立。,RSA,算法论证,11第二种情况：M0RSA算法论证,12,RSA,算法论证,加密和解密运算的可交换性,D(E(M)=(M,e,),d,=M,ed,=(M,d,),e,=E(D(M) mod n,所以，,RSA,密码可同时确保数据的秘密性和数据的,真实性。,12RSA算法论证加密和解密运算的可交换性D(E(M)=,13,RSA,算法论证,加解密算法的有效性,RSA,密码的加解密运算是,模幂运算,，有比较有效,的算法。,13RSA算法论证加解密算法的有效性RSA密码的加解密运算,14,RSA,算法论证,在计算上由公开密钥不能求出解密钥,小合数的因子分解是容易的，然而大合数的因子分,解却是十分困难的。关于大合数的因子分解的时间,复杂度下限目前尚没有一般的结果，迄今为止的各,种因子分解算法提示人们,这一时间下限,将不低于,O,（,EXP,（,lnNlnlnN,）,1/2,）,。,根据这一结论，只要合数足够大，进行因子分解是,相当困难的。,14RSA算法论证在计算上由公开密钥不能求出解密钥小合数的,15,RSA,算法论证,假设截获密文,C,，从中求出明文,M,。他知道,MC,d,mod n,，,因为,n,是公开的，要从,C,中求出明文,M,，必须,先求,出,d,，而,d,是保密的,。但他知道，,ed1 mod,(,n),，,e,是公开的，要从中求出,d,，必须先求出,(,n),，而,(,n),是保密的,。但他又知道，,(,n)=(p-1)(q-1),，,15RSA算法论证假设截获密文C，从中求出明文M。他知道M,16,要从中求出,(,n),，必须,先求出,p,和,q,，而,p,和,q,是保密的,。,但他知道，,n=pq,，,要从,n,求出,p,和,q,，只有对,n,进行因子分解。而当,n,足够大时，,这是很困难的。,RSA,算法论证,只要能对,n,进行因子分解，便可攻破,RSA,密码。由此可以,得出，,破译,RSA,密码的困难性对,n,因子分解的困难性。,目,前尚不能证明两者是否能确切相等，因为不能确知除了对,n,进行因子分解的方法外，是否还有别的更简捷的破译方,法。,16要从中求出(n)，必须先求出p和q，而p和q是保密的。,17,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,。,17 3、例子：7d mod20=1因e=7与,18,故,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,18故RSA体制明、密文空间: Z/(33)加密算法: c,19,二、,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,的差要大；,19二、RSA算法的参数选择为了确保RSA密码的安全，必须认,20,（,p-1,）和（,q-1,）的最大公因子要小,。,如果（,p-1,）和（,q-1,）的最大公因子太大，则易受,迭代加密,攻击,。, e,的选择,随机且含,1,多就安全，但加密速度慢。于是，有的学者建议取,e,216+1,65537, d,的选择,d,不能太小，要足够大, 不要许多用户共用一个模,n,；,易受共模攻击,20（p-1）和（q-1）的最大公因子要小。,21,1989,年,Lenstra, Manasse,利用二次筛法使用数百台工作站分解了,106,位十进制数；,1990,年,Lenstra, Manasse, Pollar,利用数域筛法使用,700,台工作站花费个月时间将,155,位十进制数分解成三个素数之积；,1994,年,Atkins, Graff, Lenstra, Lerland,利用多重二次筛法的双重大素数算法动用,1600,台计算机联网，,600,名志愿者花费个月时间分解了,129,位十进制数；,2002,年成功分解,158,位的十进制数。,结论：,154,位十进制数（,512bit,）的模长已经不安全，应使用,308,位十进制数（,1024bit,）模长。,211989年Lenstra, Manasse利用二次筛法使,22,三、,RSA,算法中大素数生成,RSA,的安全性基础是基于,大合数分解,的困难性，在,RSA,算法中要求模数,N,是两个大素数,p,和,q,的乘积。,用户选择模数,N,的方法是先找到两个素数，然后生成相应的模数,N,。,素数判定,是要解决的首要问题。,22三、RSA算法中大素数生成 RSA的安全性基础是基于大,23,1,、产生大素数的算法（,Rabin,素性检测算法,）,由欧拉定理知，若,n,为素数：,则,n,可能为素数，也可能为合数,。,Rabin,由此设计了一个,判定,n,是否为,素数的算法,。,反过来若： ，则,n,必为合数。,若,231、产生大素数的算法（Rabin素性检测算法）由欧拉定理,24,1,、产生大素数的算法,Rabin,素性检测算法,Rabin,素性检测法是一种,概率,素数测试法。,其输入为一奇数，输出为两种状态,Yes,或,No,。若输入一奇数,N,，而输出为,No,，即表示,N,必定为合数。若,输出为,Yes,，则表示,N,为素数的,概率为,1-,，其中,为此素数测试法中,可控制的任意小数,，但不能为,0,。（,是在,N,是合数的条件下误判为素数的条件概率。）,241、产生大素数的算法Rabin素性检测算法Rabin,25,Rabin,素性检测算法：,（1）,任取一个大奇数,n,（,2,）任取 且,(a,n)=1,（,3,）如果,则判,n,是素数；,否则判,n,是合数，重新选取,n,重复上过程。,Rabin,证明了由上述算法所产生的素数的误判概率,:,由此,我们将算法中的第,(2),和,(3),步骤重复,k,次,这样判定,n,为素数的误判概率小于等于,(1/4),k,。,计算复杂度为：,O(log,2,n),3,),25Rabin素性检测算法：Rabin证明了由上述算法所产生,26,Miller-Rabin,算法,随机选择一个奇整数,n(,如利用伪随机数产生器,),；,随机选择一个整数,an,；,执行诸如,Miller-Rabin,等概率素数测试。若,n,未通过测试，则转到第一步；,若,n,通过足够多次的测试，则接受,n,；否则转向第,2,步。,26Miller-Rabin算法 随机选择一个奇整数n(如,27,在实际使用中,通过首先检验待检测的随机数是否是小素数,(,例如所有小于,1000,的素数,),的倍数，待检测通过后再执行,Rabin,检测。,Miller-,Rabin,素数检测算法，已经作为标准的检测算法列入,IEEE P1363,的附录,和,NIST,的数字签名标准的附录,，作为密码学标准使用。,27 在实际使用中,通过首先检验待检测的随机数是否是小素,28,RSA,的加脱密计算都是在模,N,运算下进行的，尽管这两个加脱密计算公式形式上比较简单，但由于其加、脱密的两个主要运算，即,指数运算,与,模大整数运算,均涉及到很大的数，故,RSA,的实现还是有较大的难度。,快速乘方算法,28 RSA的加脱密计算都是在模N运算下进,29,指数运算 最简单而直接的计算方法，就是将,m,连续乘,e-1,次，如此就可以获得的值了。,当,m,或,e,很大时，其计算复杂度将是非常高的。,在指数运算中，比较有名的是,二元法（也称为平方乘法）,29 指数运算 最简单而直接的计算方法，,30,设,e,为,k,位二进制数，,w(e),为,e,的二进制系数中为,1,的个,数，则最多只需要计算,w(e) -1,次平方,和,w(e),次数的模,乘,。从而大大简化了计算。,30设e为k位二进制数，w(e)为e的二进制系数中为1的个,31,以,512,比特加密指数为例，整数,e,的二进制表示为,:,一般的加密过程为,:,31以512比特加密指数为例，整数e的二进制表示为:一般的加,32,当要对明文进行加密时，可先进行预处理，计算出,m,2,、,m,3,等，这种方法我们称之为窗口法。,32 当要对明文进行加密时，可先进行预处理，计算出m2,33,例：,计算,:,33例：计算:,34,第一步首先计算,第二步计算,第三步计算,第四步计算,最后一步计算,结论：,34第一步首先计算第二步计算第三步计算第四步计算最后一步计算,35,快速模乘算法,反复平方乘算法解决了快速乘方取模的问题，,仍未解决快速模乘的问题；,Montgomery,算法,是一种快速模乘的好算法；,将以上两种算法结合成为实现,RSA,密码的,有效,方法。,35快速模乘算法反复平方乘算法解决了快速乘方取模的问题，将,36,Montgomery,算法的思路：,要计算,Y=AB mod n ,因为,n,很大，取模运算困难，采取一,个小的模,R,，回避大模数的计算。,利用空间换时间，多用存储空间换取快速。,缺点：不能直接计算出,Y=AB mod n,，只能计算出中间,值,AB,R,-1,mod n,，因此还需要预处理和调整运算。一次性,计算,Y=AB mod n,并不划算。,适合：,RSA,等密码中多次的模乘计算。,36Montgomery算法的思路：,37,对称密钥密码学与公钥密码学,1,、对称密钥密码学的优点,（,1,）能够设计为具有很高的数据吞吐率。硬件实现可以达到每秒加密几百兆字节，而软件实现的吞吐率也达到了每秒兆字节的数量级。,（,2,）对称密码的密钥相对较短。,（,3,）对称密钥密码可以作为要素来构造各种密码机制。比如伪随机数生成器、杂凑函数、快速数字签名方案等,（,4,）对称密钥密码能合成强密码。简单变换容易被分拆，但是研究其弱点后，可用来构造强的乘积密码。,37对称密钥密码学与公钥密码学1、对称密钥密码学的优点（1）,38,2,、对称密钥密码学的缺点,（,1,）在一个双方的通信中，密钥必须在两端都保密。,（,2,）在大型网络中，要管理许多密钥对。其结果是，有效的密钥管理需要一个无条件可信的,TTP,。（称一个,TTP,是无条件可信的，如果它在所有事情上都可信。例如它也许可以访问用户的秘密密钥和私钥，还承担着公钥和标识符的联系）,（,3,）对实体,A,与,B,之间的一个双方通信，使用密钥的良好习惯是：经常更换密钥，通常是会话密钥一次一换。,（,4,）源自对称密钥加密的数字签名机制通常需要关于公开验证函数的大密钥，或者使用,TTP,。,382、对称密钥密码学的缺点（1）在一个双方的通信中，密钥必,39,3,、公钥密码学的优点,（,1,）只有私钥必须保密。（但必须保证公钥的真实性）,（,2,）与无条件可信的,TTP,相反，公钥密码管理需要的只是一个功能上可信的,TTP,（称一个,TTP,是功能上可信的，如果它是诚实且公正的，但是不可以访问用户的秘密密钥和私钥）。关于使用方式，和实时的需要使用相反，这个,TTP,也许只需以离线方式使用。,（,3,）依赖于使用方式的差别，一个私钥,/,公钥对可以在一段相当长的时期内保持不变，甚至数年。比如多次会话使用相同密钥。,393、公钥密码学的优点（1）只有私钥必须保密。（但必须保证,40,（,4,）许多公钥方案产生了相对有效的数字签名机制。用于刻画公开验证函数的密钥通常比对称密钥小很多。,（,5,）在大型网络中，所需密钥的数量要比对称密钥情形下少很多。,40（4）许多公钥方案产生了相对有效的数字签名机制。用于刻画,41,4,、公钥密码学的缺点,（,1,）在吞吐率方面，大多流行的公钥加密方法要比已知最好的对称密钥加密方案慢几个数量级。,（,2,）密钥长度（如,RSA,的,1024,比特）明显要比对称密钥（如,64,比特或,128,比特）加密所需大得多（,10,倍或更多）。这是因为针对对称密钥系统的最有效的攻击是密钥穷搜（这一般是设计要求），而对公钥系统来说，快捷攻击（如因子分解）比穷搜有效得多。,414、公钥密码学的缺点（1）在吞吐率方面，大多流行的公钥加,42,（,3,）没有公钥方案被证明是安全的（对分组秘密也一样）。至今发现的最有效的公钥加密方案都把安全性建立在一小批数论问题的困难性假定之上。,（,4,）公钥密码学没有对称密钥加密那样长久的历史，它在,20,世纪,70,年代中期才被发现。,42（3）没有公钥方案被证明是安全的（对分组秘密也一样）。至,43,5,、总结,对称密钥加密和公钥加密有许多互补的优点。目前的密码系统融合了两者的优势。,凭借公钥加密技术来建立密钥，然后用于实体,A,和,B,进行通信的对称密钥密码系统。,A,和,B,就可综合利用公钥方案的公钥与私钥对长期性，以及对称密钥方案的高效性。数据加密通常是加密过程耗费时间最多的部分，而公钥方案实现的密钥建立只是,A,和,B,之间整个加密过程的一小部分（从耗时来考虑）。,435、总结 对称密钥加密和公钥加密有许多,44,在计算效率上，公钥加密比不上对称加密，但也没有证明说一定是这样。总得来说，公钥密码学推动有效的签名（特别是不可抵赖性）和密钥管理，对称密钥密码学对加密及一些数据完整性应用很有效。,44 在计算效率上，公钥加密比不上对称加密，但,谢谢,45,45,