计算机信息安全论文

您当前的位置:学术堂 > 计算机论文 > 计算机信息安全论文 >

RSA算法的攻击方法与防御建议

来源:学术堂 作者:姚老师
发布于:2015-03-30 共2109字
论文摘要

  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,有:C1=Pe1modn 和 C2=Pe2modn。如果攻击者获得 n、e1、e2、C1和 C2,就能得到 P。 因为 e1和 e2互质,故用欧几里德(Euclid)算法能找到 r 和 s,满足:r*e1+s*e2=1,设 r 为负数,则(C1-1)-r*C2s=(Pe1modn)r*(Pe2modn)s=(Pr*e1+s*e2)modn=Pmodn,如果 P<n,则 P 被获取。

  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<n1n2n3,可得 P= C3姨 。

  2.4 对 RSA 的选择密文攻击

  选择密文攻击指的是攻击者能选择不同的密文,并拥有对应的明文,由此推出想要的信息。一般攻击者会伪装若干信息,让拥有私钥的用户签名,由此获得有用的明文-密文对,然后推算想要的信息。

  例 1 攻击者想要伪造用户 u 对消息 x 的签名。 他可以先计算 x1,x2,使得 x≡(x1x2)(modn),并骗取 u 对 x1和 x2的签名 s1=x1d(modn)和 s2=x2d(modn), 则对 x 的签名可计算如:s=xd(modn)=(((x1x2)(modn))d)(modn)=((x1dmodn)(x2dmodn))modn=(s1s2)(modn)。

  例 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 算法才能发挥最大的效用。

  参考文献:
  [1]闫洪亮,牛军涛.实现 RSA 算法应注意的问题[J].计算机应用与软件,2008(5):253-254.
  [2]谢建全,阳春华.RSA 算法中几种可能泄密的参数选择[J].计算机工程 ,2006(16):118-119.
  [3]李志敏.基于 RSA 密码体制的选择密文攻击的研究[J].网络安全技术与应用,2009(1):12-13.

相关内容推荐
相关标签:
返回:计算机信息安全论文