RSA 算法的攻击方法研究

  • 投稿穆刀
  • 更新时间2015-09-23
  • 阅读量741次
  • 评分4
  • 15
  • 0

李家兰

(广东石油化工学院计算机系,广东 茂名 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算法的初始化

(1)选取两个非常大的、互异的质数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.

[责任编辑:汤静]