李家兰
（广东石油化工学院计算机系，广东 茂名 525000）
【摘 要】RSA算法是迄今在网络安全领域应用最为广泛的非对称密码算法，其安全性是基于大整数的因数分解难问题的，算法的攻破一般被认为等同于大数分解。另一方面，对RSA算法的攻击可针对设计与应用该算法的系统的某些缺陷。本文研究了对RSA算法的攻击的主要方法，并对攻击防御提出了建议。
教育期刊网 http://www.jyqkw.com
关键词 网络安全；RSA算法；算法攻击；攻击防御
基金项目：广东石油化工学院科学研究基金资助项目（200839）。
作者简介：李家兰（1977—），男，广东茂名人，硕士，讲师，研究方向为计算机网络与信息安全。
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),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则可证明发送者的身份。
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)，进而从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发送给以上三人，使用各人的公钥加密得：
C1=P3(modn1)，C2=P3(modn2)和C3=P3(modn3)
一般地，n1，n2，n3互素（否则，会比较容易求出公因子，降低安全性），根据中国剩余定理，可由C1，C2，C3计算：C=P3(modn1n2n3)
如果P<n1, P<n2, P<n3, 有P3<n1 n2 n3，可得
2.4 对RSA的选择密文攻击
选择密文攻击指的是攻击者能选择不同的密文，并拥有对应的明文，由此推出想要的信息。一般攻击者会伪装若干信息，让拥有私钥的用户签名，由此获得有用的明文-密文对，然后推算想要的信息。
例2 攻击者获得了用户u使用公钥e加密的密文y=xe(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算法的系统的设计缺陷，改进方法为：1）在多用户系统中必须采用多个模数；2）避免为了图求方便而使用取值太小的公钥e。[1-2]
攻击4最为复杂，从算法上无法解决这一问题，主要对应策略有两条：1）私钥持有者不对不信任的信息签名；2）签名信息时，先使用Hash函数生成的摘要，再对摘要签名，避免直接对信息的签名。[3]
以上防御方案并不能解决所有的RSA安全问题，我们建议利用RSA算法的系统仔细审核安全需求，投入使用先进行测试，并对系统安全做一个全面的审核。必须对各种安全策略及程序进行合理优化，才能尽可能地降低风险，RSA算法才能发挥最大的效用。
教育期刊网 http://www.jyqkw.com
参考文献
［1］闫洪亮,牛军涛.实现RSA算法应注意的问题[J].计算机应用与软件,2008(5):253-254.
［2］谢建全,阳春华.RSA算法中几种可能泄密的参数选择[J].计算机工程,2006(16):118-119.
［3］李志敏.基于RSA密码体制的选择密文攻击的研究[J].网络安全技术与应用,2009(1):12-13.
［责任编辑：汤静］