公钥密码体制RSA介绍.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式日,rff,第二级,e,第三级,f,第四级,d,第五级,f,*,1,公钥密码体制概述,2 RSA,公钥密码体制,公钥密码体制,1,1,公钥密码体制概述,私钥密码体制的局限性,密钥量大：,n,个用户相互通信,需用个,n,(,n,-,1)/2,密钥,.,应用范围小：不易实现数字签名,公钥密码体制思想的产生,1976,年,斯坦福大学的博士生,W.Diffie,和其导师,M.E.Hellman,提出了公钥密码的新思想,W.,Diffie,and M.E.Hellman,New direction in cryptography,IEEE Trans.on Information Theory,1976,IT-22.(6),pp.644-654.,1978,年,Merkle,和,Hellman,联合提出了基于组合数学中“背包问题”的公钥密码体制,(MH,背包公钥密码体制,).,不久被攻破,.,2,1,公钥密码体制概述,公钥密码体制,(PKC:public key cryptosystem),原理,密钥,K,=(,P,K,S,K,):,加密密钥,P,K,公开,;,解密密钥,S,K,保密,.,在计算上由,P,K,推出,S,K,是困难的,.,加密算法,E,Pk,:,c,=,E,Pk,(,m,),解密算法,D,Sk,满足,:,m,=,D,Pk,(,c,),D,SK,(,E,PK,(,x,)=,x,.,3,1,公钥密码体制概述,公钥密码体制的要求,用户：产生密钥对,K,=(,P,K,S,K,),在计算上是可行的,发送方：已知公钥与明文，产生密文是容易的,接收方：利用私钥解密密文在计算上是可行的,攻击者：利用公钥求解私钥在计算上是不可行的,攻击者：已知公钥与密文，在不知道私钥的情况下，恢复明文在计算上是不可行的,4,2 RSA,密码体制,1978,年,R.,Rivest,A.Shamir,L.,Adleman,提出,RSA,密码体制,R.,Rivest,A.Shamir,L.,Adleman,A method for obtaining digital signatures and public-key cryptosystem,Comm.ACM,21(2)(1978),pp.120-126.,基于大合数因式分解的困难性,安全,易懂,.,可用于加密与数字签名,.,ISO,ITU,SWIFT,把,RSA,选为加密标准,;Internet,的,E-Mail,的保密系统,GPG,国际,VISA,和,MASTER,组织的电子商务协议,(SET,协议,),都将,RSA,作为传送会话密钥和数字签名的标准,.,5,2 RSA,密码体制,6,2 RSA,密码体制,RSA,密码体制算法,密钥生成算法,(1),选取两个大素数,p,q,(2),计算,n,=,p,q,(,n,)=(,p,-1)(,q,-1),(3),随机选取,e,:1,e,(,n,),，与,(,n,),互素,(4),根据欧几里德算法计算,e,的逆,d,=,e,1,:,1,e,(,n,),，,e,d,1 mod,(,n,).,(5),公钥,:,P,K,=,(,n,e,),私钥,:,S,K,=(,p,q,d,).,7,2 RSA,密码体制,RSA,密码体制算法,加密算法,:,消息,m,:0,m,n,，,密文,c,=,E,PK,(,m,)=,m,e,(mod,n,),解密算法,:,密文,c,:0,c,n,，,明文,m,=,D,SK,(,c,)=,c,d,(mod,n,),8,2 RSA,密码体制,RSA,密码体制算法,解密算法的正确性,9,2 RSA,密码体制,例,4.1,设,p,=11,q,=13.,令,n,=1113=143,(,n,)=(,p,-1)(,q,-1)=(11-1)(13-1)=120,取公钥,:,P,K,=(,n,e,)=(143,e,=17),，,计算,:,d,=,e,-1,=17,-1,=113 (mod 120),(,因为,:17113=1921=16120+1).,私钥,:,S,K,=(,p,q,d,)=(11,13,113).,对于明文,:,m,=24,密文,:,c,=,E,PK,(,m,)=24,17,=7(mod 143).,对于密文,:,c,=7,解密,:,m,=,D,SK,(,c,)=7,113,=24 (mod 143).,10,2 RSA,密码体制,RSA,密码算法的实现,模幂算法,:,m,e,(mod,n,)(,高效算法：平方乘算法,),11,2 RSA,密码体制,RSA,密码算法的实现,模幂算法,:,m,e,(mod,n,)(,高效算法：平方乘算法,),例,4.2,设,p,=17,q,=11,，有,n,=1711=187,(,n,)=(,p,-1)(,q,-1)=1610=160,取公钥,:,e,=7,，计算私钥,:,d,=23.,明文,:,m,=88,计算密文,:,c,=88,7,(mod 187).,12,2 RSA,密码体制,例,4.2,设,p,=17,q,=11,，有,n,=1711=187,(,n,)=(,p,-1)(,q,-1)=1610=160,取公钥,:,e,=7,，计算私钥,:,d,=23.,明文,:,m,=88,计算密文,:,c,=88,7,=11(mod 187).,对于密文,:,c,=11,解密,:,m,=11,23,=7 (mod 187).,13,2 RSA,密码体制,Z,n,上的运算,:,设,x,和,y,的二进制表示分别有,k,和,l,位,(,k,l,).,x,+,y,:,O,(,k,),x,-,y,:,O,(,k,),x,y,:,O,(,k,l,),x,/,y,:,O,(,l,(,k,-,l,),gcd(,x,y,):,O,(,k,3,)(Euclidean,算法,),Z,n,上的模,n,运算,:,设,n,的二进制表示有,k,0,m,1,m,2,n,-,1,.,m,1,+,m,2,(mod,n,):,O,(,k,),m,1,-,m,2,(mod,n,):,O,(,k,),m,1,m,2,(mod,n,):,O,(,k,2,),(,m,1,),-,1,(mod,n,):,O,(,k,3,),(,m,1,),c,(mod,n,):,O,(,k,2,log,c,)(,平方,-,乘算法,).,RSA,密码算法的实现,14,对,RSA,的攻击,攻击方法,1,：分解,n,已知,n,=,p,q,(,n,)=,(,p,-,1,)(,q,-,1,),a,=,b,-,1,mod,(,n,).,分解,n,的最新水平,:,二进制表示有,512,位,.,n,应为,1024,2048,位,.,攻击方法,2,：直接计算,(,n,),已知,(,n,),e,=,d,-1,mod,(,n,).,计算,(,n,),并不比分解,n,容易,.,设,p,q,=,n,(,p,-1,)(,q,-1,),=,(,n,),p,2,-(,n,-,(,n,)+1),p,+,n,=0,求出,p,q,=,n,/,p,求出,n,=,p,q,.,例,:,设,n,=84773093,(,n,)=84754668,p,2,-18426,p,[phone]=0,p,=9539,q,=,n,/,p,=8887,n,=84773093=,95398887.,15,对,RSA,的攻击,攻击方法,3,：共模攻击,如果两个用户,A,与,B,使用相同的模,n,，设,A,与,B,的解密密钥分别为,d,A,与,d,B,加密密钥分别为,e,A,与,e,B,.,对明文,m,加密的两个密文,:,攻击者可以恢复明文,m,！,16,对,RSA,的攻击,攻击方法,4,：选择密文攻击,(RSA,密码不能抵抗！,),假设攻击者获得了公钥,(,n,e,),截获到密文,c,1,.,设明文为,m,1,，有,攻击者选取一个消息,m,，计算,攻击者想办法让解密者对,c,2,进行解密，从而获得的明文,m,2,.,攻击者就可以计算出明文,m,1,！,17,对,RSA,的攻击,攻击方法,5,：解密指数法,如果私钥,d,已知,则可能分解,n,.,即计算,d,并不比分解,n,容易,.,如果私钥,d,被泄漏,不能只更换公钥,e,必须更换模,n,.,攻击方法,6,：低解密指数攻击法,当解密指数,d,n,0.5,18,RSA,的安全参数,p,和,q,要足够大,:,n,=,pq,为,1024,位,或,2048,位,.,p,和,q,应为强素数,(strong prime).,如果素数,p,满足以下条件,则称为,强素数,.,(1),p,-1,有大素数因子,r,;,(2),p,+1,有大素数因子,s,;,(3),r,-1,有大素数因子,t,.,例如,:,理想的强素数为,:,r,=2,t,+1;,p,=2,r,+1=4,t,+3;,p,=2,s,-1.,19,RSA,的安全参数,|,p,-,q,|,要大,.,如果,|,p,-,q,|,较小,则,(,p,+,q,)/2,n,1/2,(,(,p,-,q,)/2,),2,=(,(,p,+,q,)/2,),2,-,n,.,可求出,p,和,q,.,例,:,对于,n,=164009,有,n,1/2,405.,令,(,p,+,q,)/2,=405,(,(,p,-,q,)/2,),2,=405,2,-,n,=16,p,+,q,=810,p,-,q,=8 ,p,=409,q,=401,164009=409401.,20,RSA,的安全参数,p,-1,和,q,-1,的最大公因子要小,设攻击者截获到密文,y,1,=,x,e,mod,n,迭代加密,:,y,i,=,y,i,-1,e,=,x,e,e,e,mod,n,(,i,=2,3,4,),如果有,i,使得,:,d,i,=1 mod,(,n,),则有,:,y,i,=,x,mod,n,因此,如果,i,很小,则容易求得明文,x,.,由,Euler,定理和,d,i,=1 mod,(,n,),可得,i,=,(,(,n,)=,(,p,-1)(,q,-1)=,D,(,p,-1),(,q,-1)/,(,D,),其中,D,=gcd(,p,-1,q,-1).,当,D,小时,(,D,),就小,从而,i,大,.,21,RSA,的安全参数,p,-1,和,q,-1,的最大公因子要小,设,p,和,q,是理想的强素数,即,p,=2,a,+1,q,=2,b,+1 (,a,b,为奇素数,),D,=2,(,D,)=1,i,=2,(,a,-1),(,b,-1).,例,:,设,p,=17,q,=11,n,=187,d,=7,D,=gcd(,p,-1,q,-1)=gcd(16,10)=2.,对,x,=123,有,y,1,=123,7,=183,mod 187,y,2,=,y,1,7,=183,7,=72,mod 187,y,3,=,y,2,7,=72,7,=30,mod 187,y,4,=,y,3,7,=30,7,=123,(=,x,)mod 187.,22,RSA,的安全参数,加密指数,d,的选择,为使加密速度快,应使,e,的二进制表示中,1,的个数尽量小,但不能太小,.,可取,:,e,=3,2,16,+1=65537(,在二进制表示中只有,2,个,1).,解密指数,d,的选择,在,d,的二进制表示中,1,的个数尽量小,但不能太小,.3,d,n,1/4,.,23,