rsa 算法的攻击方法研究-化工

《rsa 算法的攻击方法研究-化工》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、RSA算法的攻击方法研究-化工RSA算法的攻击方法研究李家兰（广东石油化工学院计算机系，广东茂名525000）【摘　要】RSA算法是迄今在网络安全领域应用最为广泛的非对称密码算法，其安全性是基于大整数的因数分解难问题的，算法的攻破一般被认为等同于大数分解。另一方面，对RSA算法的攻击可针对设计与应用该算法的系统的某些缺陷。本文研究了对RSA算法的攻击的主要方法，并对攻击防御提出了建议。关键词网络安全；RSA算法；算法攻击；攻击防御基金项目：广东石油化工学院科学研究基金资助项目（200839）。作者简介：李家兰（1977—），男，广东茂名人，硕士，讲师，研究方

2、向为计算机网络与信息安全。1　RSA算法描述RSA算法是由R.Rivest、A.Shamir和L.Adlernan三人于1978年研究提出的，是迄今得到最广泛应用的非对称密码算法。RSA算法理论完善，安全性良好，可用于数据加密、数字签名与身份认证，满足网络安全的多方面需求，同时算法易于实现，得到了广泛的应用和深入的研究，其实现技术日趋成熟。RSA算法的初始化与应用描述如下：1.1　RSA算法的初始化（１）选取两个非常大的、互异的质数p，q；（2）计算n=pq及?准(n)=(p-1)(q-1)；（3）在开区间(0,?准(n))上取素数e，满足gcd(?准(n)

3、,e)=1；（4）计算d使得de≡1mod?准(n)；（5）公布（e,n）为公钥，保密（d,n）为私钥，销毁p、q。1.2　RSA算法用于加/解密如需对明文m（二进制表示）加密，须先把m分成等长s的数据块m1，m2，…，mi，2s=n，加密mi得到密文：ci=mie(modn)。对密文ci解密得明文：mi=cid(modn)。1.3　RSA算法用于数字签名发送者如需对信息m进行数字签名，须使用私钥d对m作运算：s=md(modn)得到签名，然后将信息m和签名s一起发送给接收方。接收方使用发送者的公钥e对s作运算得：m=se(modn)，如果m=m则可证明发送

4、者的身份。2　RSA算法的攻击方法RSA算法的安全性依赖于大整数分解的困难性。最直接的攻击方法是分解n得到p,q，进而基于e计算d，随着计算机运算能力的不断提高，通过二次筛法已能分解180多位的十进制素数，增加p,q的长度已成为许多安全应用系统的加密要求。另一方面，利用系统设计和实现的缺陷，人们也提出了一些基于非因子分解方式破解RSA算法的方案。目前，对RSA算法的攻击主要有以下几种：2.1　对模数n的因子分解分解模数n是最直接的攻击方法，也是最困难的方法。攻击者可以获得公钥e和模数n；如果n=pq被成功分解，则攻击者可以计算出φ(n)=(p-1)(q-1)

5、，进而从ed≡1modφ(n)解得私钥d。2.2　对RSA的公共模数攻击若一个多用户系统中只采用一个模数n，不同的用户拥有不同的e和d，系统将是危险的。在此系统中，若有同一消息用不同的公钥加密，这些公钥共模且互质，那该信息无需私钥就可解密。举例来说，设P为信息明文，两个加密公钥为e1和e2，公共模数是n，有：2.3　对RSA的小指数攻击如果RSA系统的公钥e选取较小的值，可以使加密和验证签名的速度有所提高。但如果e取得太小，就容易受到小指数攻击。例如，有同一系统的三个用户，分别使用不同的模数n1，n2，n3，但都选取e=3；另有一用户欲将同一明文消息P发送给

6、以上三人，使用各人的公钥加密得：C1=P3(modn1)，C2=P3(modn2)和C3=P3(modn3)一般地，n1，n2，n3互素（否则，会比较容易求出公因子，降低安全性），根据中国剩余定理，可由C1，C2，C3计算：C=P3(modn1n2n3)如果Pn1,Pn2,Pn3,有P3n1n2n3，可得2.4　对RSA的选择密文攻击选择密文攻击指的是攻击者能选择不同的密文，并拥有对应的明文，由此推出想要的信息。一般攻击者会伪装若干信息，让拥有私钥的用户签名，由此获得有用的明文-密文对，然后推算想要的信息。例2　攻击者获得了用户u使用公钥e加密的密文y=xe

7、(modn)，想要得到x。他可以先计算y′=re(modn)（r是小于n的随机数），y″=(yy′)(modn)，然后骗取u对y″的签名s=y″d(modn)。则通过计算(r-1s)(modn)可以恢复出x，这是因为：(r-1s)(modn)=((y′dmodn)-1y″d)(modn)=(y′-dy″d)(modn)=(y′-dydy′d)(modn)=yd(modn)=x。3　对RSA算法的攻击的防御建议对于以上几种攻击，防御方案各不相同。攻击1源于RSA算法的数学安全基础，增加初始化参数长度是有效的提高安全度的方法。而攻击2和攻击3源于应用RSA算法的

8、系统的设计缺陷，改进方法为：1）在多用户系统中必须采