rsa算法的安全性分析new

《rsa算法的安全性分析new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第19卷专辑中南民族学院学报(自然科学版)Vol.19Sup2000年9月JournalofSouth2CentralUniversityforNationalities(Nat.Sci.)Sep.2000aRSA算法的安全性分析王启明王一凡(华中理工大学汉口分校)摘要详细论述了公开密钥密码技术、RSA加密算法、身份验证,论述了电子信息交换过程中如何进行加密和解密、身份认证等,讨论了公开密钥密码技术在电子信息交换过程中安全性、保密性等方面的应用.关键词公开密钥密码体制;RSA加密算法;信息交换;身份认证中图分类

2、号TP393.1文献标识码A文章编号100523018(2000)专20076203在今天的信息社会里,通信安全保密问题的研究已不仅仅出于军事、政治和外交上的需[1～4]要,特别是电子商务飞速发展的今天.所以保护信息的安全是信息时代的迫切需要.所谓密码技术,就是对信息进行重新编码,从而达到隐藏信息内容,使非法用户无法获取信息真实内容的一种手段.密钥,是密码体制安全的关键.公开密钥密码体制的产生主要是由于常规密钥密码体制的密钥分配问题和数字签名的需求.1978年由Rivest、Shamir和Adleman提出了第

3、一个比较完善的公钥密码算法,这就是著名的RSA算法.1RAS算法的描述RSA算法的理论基础是一种特殊的可逆模指数运算.它的安全性是基于分解大整数的困难性.其算法为:设n是2个不同奇素数p和q之积,即:n=pq,P=C=Zn,5(n)=(p-1)(q-1),K={(n,p,q,a,b)ûn=pq,p,q是素数,ab≡1mod5(n)}.b对每一个K=(n,p,q,a,b),定义加密变换为Ek(x)=xmodn,x∈Zn.a解密变换为Dk(y)=ymodn,y∈Zn.公开n和b,保密p,q和a.2RSA算法的安全性

4、分析若n=pq被因子分解,则RAS便被击破.a收稿日期2000206210作者简介王启明,男,33岁,工程师,华中理工大学汉口分校成教处,武汉430015专辑王启明等:RSA算法的安全性分析77因为若p,q已知,则5(n)=(p-1)(q-1)便可算出.解密密钥d关于e满足:de=1(modz),故d便也不难求得.因此RSA的安全性依赖于因子分解的困难性.目前因子分解速度最快的方法,其时间复杂性为:exp(sprt(ln(n)lnln(n))).若n被分解成功,则RSA便被攻破,但还不能证明对RSA攻击的难度和

5、分解n相当,故对RSA的攻击的困难不比大数分解更难.当然,若从求5(n)入手对RSA进行攻击,它的难度和分解n相当.但还不能证明对RSA的攻击,其难度和分解n相当,也没有比因数分解n更好的攻击的方法.2.1解密指数计算解密指数a的任何算法可作为分解n的一个概率算法的子程序或预言.该算法是基2于1模n的平方根的某些事实,我们知道同余方程x=1modp关于p有2个解,即x=±21modp.类似地,同余方程x=1modq关于q有2个解,即x=±1modq.因此,1模n有四个平方根,这4个平方根可由中国剩余定理找出.其

6、中2个是x=±1modn,称为1模n的平凡的平方根.另2个平方根称为1模n的非平凡的平方根.下面给出通过寻找1模n的一个非平凡的平方根分解n的算法.给定解密指数a,分解n的算法如下:1)随机地选择X使得1≤X≤n-1;2)计算x=gcd(X,n);3)如果1

7、1modn,完成下列各步:9)T0=T;210)T=Tmodn;11)如果T0=-1modn,那么停止(分解n失败);否则12)计算x=gcd(T0+1,n)(这时x=p或q,分解n成功).这个结果告诉我们,如果a被泄露,那么n也被危及,选择一个新的加密指数已不能保证系统的安全性,必须重新选择模n.2.2同模攻击假定用户B有一个RSA算法,模为n,加密指数为b1用户C也是一个具有同样算法且模为n,加密指数为b2,gcd(b1,b2)=1.如果用户A想加密同一个明文x送给B和C,那么A先bb计算y1=x1modn

8、和y2=x2modn,然后将y1发送给B,将y2发送给C.假定O截取到了y1和y2,那么O就可按下述步骤计算出x:-1cc-11)计算c1=b1modb2;2)计算c2=(c1b1-1)öb2;3)计算x=y11(y22)modn;这表明,无论密码系统多么“安全”,O解密A发送的明文是可能的.在有些应用场合,需要一个可信中心选择一个RSA模n,并对网上的每个用户分配不同的加、解密指数对