第6章 公钥密码体制(RSA算法).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,密码学基础,赵海燕,,第,6,章公钥密码体制,(RSA,算法,),6,1,概述,问题的提出：,密钥管理困难,传统密钥管理两两分别用一对密钥时，则,n,个用户需要,C(n,2)=n(n-1)/2,个密钥，当用户量增大时,密钥空间急剧增大,如,:,n=100,时,C(100,2)=4,995,n=5000,时,C(5000,2)=12,497,500,陌生人间的保密通信问题,数字签名的问题,传统加密算法无法实现抗抵赖的需求,公钥密码体制,公钥密码又称为双钥密码、非对称密码,公钥密码体制提出的标志性文献：,1976,年，,Diffie,和,Hellman,，,密码学的新方向,W.Diffie and M.E.Hellman,New Directions in Cryptography,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654,公钥密码算法,基于数学函数,而不是代替和换位操作支持数字签名,：用两个密钥中的任何一个加密的内容，都可以用对应的另一个密钥解密。

对公钥密码体制的要求,（,1,）参与方,B,容易通过计算产生一对密钥（公开密钥,K,Ub,和私有密钥,K,Rb,）2,）在知道公开密钥和待加密报文,M,的情况下，对于发送方,A,，很容易通过,公开密钥,计算产生对应的密文：,C,E,KUb,（,M,）,（,3,）接收方,B,使用,私有密钥,容易通过计算解密所得的密文以便恢复原来的报文：,M,D,KRb,（,C,）,D,KRb,（,E,KUb,（,M,）,（,4,）敌对方即使知道公开密钥,K,Ub,，要确定私有密钥,K,Rb,在计算上是不可行的5,）敌对方即使知道公开密钥,K,Ub,和密文,C,，要想恢复原来的报文,M,在计算上也是不可行的6,）加密和解密函数可以以两个次序中的任何一个来使用（适用于部分公钥密码体制）,:,M,D,KRb,(E,KUb,(M),（机密性）,M=E,KUb,(D,KRb,(M),（数字签名）,对公钥密码体制的要求,陷门,设计公钥密码算法的关键,单向,陷门函数,满足下列条件的函数,f,叫做单向陷门函数：,(,1),给定,x,，计算,y=f(x),是容易的,(2),给定,y,计算,x,使,y=f(x),是不可行的,(3),存在,，已知,时,对给定的任何,y,，若相应的,x,存在，则计算,x,使,y=f(x),是容易的,设计公钥密码算法的关键,单向,陷门函数,单向函数,陷门性,陷门信息,（,1,）当用陷门函数,f,作为加密函数时，可将,f,公开，这相当于公开加密密钥。

此时加密密钥便称为公开密钥，记为,Pk,2,）,f,函数的设计者将,保密，用作解密密钥，此时,称为秘密密钥，记为,Sk,3,）由于加密函数是公开的，任何人都可以将信息,x,加密成,y=f(x),，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有,Sk,，他自然可以解出,x=f,-1,(y),4,）窃听者由于没有,Sk,，则他由截获的密文,y=f(x),推测,x,是不可行的设计公钥密码算法的关键,单向,陷门函数,公开密钥密码系统的分析方法,蛮力攻击,(,对密钥,),防范措施：采用长密钥,公开密钥算法本身可能被攻破,找到从公钥计算私钥的方法,可能报文攻击,(,对报文本身的强行攻击,),搜索报文本身的所有可能，跟密文匹配,同等加密强度下,DES,和,RSA,密钥,长度的比较,公钥密码系统的应用,加密,/,解密,数字签名（第,9,章）,密钥,交换（第,7,章）,并不是所有的公开密钥密码体制都支持加密解密、数字签名和密钥交换如,RSA,、,ECC,三种都支持；,DSA,只用于数字签名；,DH,只用于密钥交换混合密码系统,加密,用对称密码加密明文，,发挥速度优势,用非对称密码加密密钥，,发挥密钥分发管理优势,混合密码系统,解密,用非对称密码,解密密钥,用对称密码,解密密文,6,2,RSA,由,Rivest,，,Shamir,和,Adleman,在,1978,年提出，是目前唯一被广泛接受并实现的通用公开密钥密码算法。

其数学基础是,Euler,定理，并建立在大整数因子分解困难问题之上陷门,RSA,密码体制描述,明文空间,P,密文空间,C=Z,n,密钥的生成,选择互异素数,p,、,q,，计算,n=pq,，,(n)=(p-1)(q-1),选择满足条件,gcd(,(n),e)=1,，,0e,(n),的整数,e,计算,d,，,使d=e,-1,mod,(n),公钥,Pk=e,，,n,私钥,Sk=d,，,p,，,q,RSA,密码体制描述,加密,(,用,e,，,n),明文：,Mn,（若明文比,n,长，则对明文进行分组，确保每一个分组满足,Mn,）,密文：,C=M,e,(mod n),解密,(,用,d,，,n),密文：,C,明文：,M=C,d,(mod n),Bob,为接收（实现）者：,Bob,选择,p=7,和,q,17,则,n=119,(n)=616,96,2,5,3,选择一个正整数,e(0e,(n),能用作加密指数，当且仅当,e,不能被,2,，,3,所整除，即满足,(e,，,(n),1,假设,Bob,选择,e=5,，那么用辗转相除法将求得：,d=e,-1,77(mod 96),Bob,的私钥,d=77,，,7,，,17,，保密；公钥为,5,，,119,，公开,RSA,的例子,RSA,的例子,现假设,Alice,想发送明文,19,给,Bob,：,Alice,计算：,19,5,mod119,66,，在开放信道上发送密文,66,给,Bob,；,Bob,收到密文计算：,66,77,mod119,19,，从而恢复明文。

例：,p=47,q=61,(n)=(47-1)(61-1)=2760,时，,选择,e=167,是否,满足秘密密,钥的,条件,？,Q,X1,X2,X3,Y1,Y2,Y3,1,0,2760,0,1,167,16,0,1,167,1,16,88,1,1,16,88,1,17,79,1,1,17,79,2,33,9,8,2,33,9,17,281,7,1,17,281,7,19,314,2,3,19,314,2,74,1223,1,用,辗转相除法,计算：,gcd(2760,167)=1,即可证明,e,满足条件,RSA,密码体制的证明,欧拉定理：,若整数,a,与整数,n,互素，则,a,(n),1(mod n),RSA,密码体制的证明,(1),当,n,非常大时，攻击者要将其分解为两个不同素数,p,、,q,的乘积是非常困难的，这就是著名的大整数因子分解困难的问题这就保证了攻击者不能得到,(n)=(p,1)(q,1),从而不能从公钥,e,推导出私钥,d=e,-1,mod,(n),来RSA,密码体制的分析,RSA,密码体制的分析,(2),加密函数,C=M,e,(mod n),是一个单向函数，由,M,、,e,、,n,计算密文,C,容易；但在不知道陷门信息,d,、,p,、,q(,私钥,),的情况下，已知,C,、,e,、,n,恢复明文,M,是非常困难的。

3),接收方由于拥有私钥,d,、,p,、,q(,即陷门,),，则可以通过,M=C,d,(mod n),直接恢复出明文RSA,的实例,例：设,p=43,，,q=59,，取,e=13,，用,RSA,算法加密和解密恢复明文“,public”,解：,1,）计算：,n=p,q=4359,2539,；,(n)=(p-1),(,q-1,),=4259=2436,；,d=e,-1,mod,(n)=13,-1,mod 2436=937,2,）将明文代替为数字，代替方案为：,a-00,，,b-01,，,，,z-25(,两位十进制数表示,),考虑到,n=2539,，这样，就可将明文,“,public”,两个字符一组转化为：,1520,，,0111,和,0802,，保证,Mn,条件的满足3,）加密：,C=M,e,mod n=1520,13,mod 2539,0095,其余两组可类似得出：,1684,和,1410,4,）解密：,M=C,d,mod n=0095,937,mod2539=1520,其余两组可类似得出：,0111,和,0802,RSA,的实例,要求：若使,RSA,安全，,p,与,q,必为足够大的素数，使分析者没有办法在有效时间内将,n,分解出来。

建议：选择,p,和,q,大约是,100,位的十进制素数，模,n,的长度要求至少是,200,位十进制数,（,512,比特）,，,e,或者,d,也各为,100,位左右RSA,算法归纳,1999,年，一个国际密码研究小组通过一台,Cray900-16,超级计算机和,300,台个人计算机，花费,7,个多月成功地分解了,155,位的十进制数（,512,比特）RSA,算法归纳,为了抵抗现有的整数分解算法，对,RSA,模,n,的素因子,p,和,q,还有如下要求：,(1)|p-q|,很大，但通常,p,和,q,的长度应相差不大；,(2)p-1,和,q-1,分别含有大素因子,p,1,和,q,1,(3)gcd(p,1,-1,q,1,-1),应该很小为了提高加密速度，通常取,e,为特定的小整数，如通常使用,e=2,4,+1=17,或,e,2,16,1,65537,，这是因为它们的二进制中只有,2,个,1,为了提高加密速度，有时候甚至允许取,e,3,，这时加密速度一般比解密速度快,10,倍以上RSA,的实现,问题：,(1),如何快速计算,a,m,mod n,（快速取模指数算法）？,(2),如何判断两个数互素（求出,gcd,）？,(3),如何判定一个给定的整数是素数？,(4),如何找到足够大的素数,p,和,q?,(5),如何求得,d=e,-1,(mod,(n),（扩展欧几里得算法）？,。