RSA算法及其安全性研究

1 RSA算法

自从1976年Diffie和Hellman两位教授提出公开密钥密码学的新概念后, 由于公开密钥密码学具有优良的密码学特性和广阔的应用前景, 很快吸引了全世界的密码爱好者, 他们提出了各种各样的公开密钥密码算法和应用方案, 密码学进入了一个空前繁荣的阶段然而公开密钥密码学的研究绝非易事, 尽管提出的算法很多, 但是能经得起时间考验的却寥寥无几。

RSA算法是由美国麻省理工学院的学者Ron Rivest, Adi Shamir和Leonard Adleman于1978年提出的公开密钥算法, 该算法已经经受了密码分析家多年深入的分析.该算法基于大数分解的困难性, 其公开密钥和私人密钥是一对大素数的函数, 从一个公开密钥和密文中恢复出明文, 难度等价于分解两个大素数的乘积.该算法具体描述如下:随机选择两个大素数p和q, 计算n=pq及, 随机选取公钥e使得, 用扩展欧几里德算法计算私钥d, 使d满足, 公开n, e, 保密p, q, d.加密消息m时加密算法为c=memodn, 解密算法为m=cdmodn。

2 对RSA的攻击

目前对于RSA算法的攻击主要有以下方式。

2.1 选择明文攻击

RSA的模指数运算能够保持输入的乘法结构, 即Ek (ab) =Ek (a) Ek (b) (modn) , 这一特点使得RSA能够用于消息的隐藏, 适于盲签名但它也影响了RSA算法的安全性。

2.1.1 破译密文

假设A的公钥为 (e, n) , 攻击者B通过窃听得到发给A的密文c=memodn, 为了获得明文, 攻击者随机选取r∈Zn*, 计算y=remodnt=ycmodn, 令k=r-1modn, 则k=y-dmodn, 现在攻击者B让A用他的私钥对t签名, 攻击者就可以得到s=tdmodn, 这样攻击者可以计算ks≡y-dtd≡y-dydcd≡cd≡med≡m (modn) 于是攻击者获得了明文m。

2.1.2 骗取签名

攻击者B想要获得A对一则非法消息m`的签名, 他有多种方法。

方法1:B首先随即选取x∈Zn*, 计算y=xemodn, 然后攻击者计算m=ym`m odn, 并将m发送给A以获得A对无害消息m的有效签名, A向B发送签名, 现在攻击者B计算mdx-1modn=ydm`dx-1modn=xe dm`dx-1modn=m`dmodn, 这样, 攻击者B得到了A对非法消息m`的签名。

方法2:攻击者B首先产生两份消息m1, m2, 满足m`=m1m2modn, 如果攻击者B能获得A对m1, m2的签名, 那么他可以计算mdmodn=m1dm2dmodn, 从而获得A对非法消息m`的签名。

所以, 为了安全起见, 不要对陌生人提交的随机性文件签名, 并且最好先使用单向Hash函数对消息进行散列运算.ISO9796分组格式可用来防止这种攻击。

2.2 公共模数攻击[1]

如果系统中每个人拥有相同的模数n, 即使每个人采用不同的公/私钥对, 系统安全仍然会收到巨大的威胁.设消息为m, 两个加密密钥为分别为e1, e2, 且满足gcd (e1, e2) =1, 两个密文为c1=me1modn, c2=me2modn, 由于, 攻击者很容易由扩展欧几里德算法得到r, s, 满足re1+se2=1, 那么c1rc2smodn=mre1+mse2modn=m。因此, 在一组用户之间共享模数是不安全的。

2.3 低加密指数攻击[2]

在RSA加密和数字签验证中, 如果选取了较低的e值可以加快速度, 但这是不安全的, Hastad证明如果采用不同的模数n, 相同的公钥e, 则对e (e+1) /2个线性相关的消息加密, 系统安全会受到威胁.如果消息比较短, 或者消息不相关, 就不存在这个问题.如果消息相同, 那么只要有个消息就可以攻击系统.一般来讲, 选取16位以上的素数速度比较快, 而且可以阻止该攻击.对于较短的消息, 使用独立随机值填充消息, 可以阻止该攻击, 这也能保证memodn≠me。

2.4 低解密指数攻击

Machael Wiener给出了另外一种攻击[3], 可以成功地计算解密指数d, 前提是满足如下条件:3d

2.5 定时攻击

定时攻击[4]主要针对RSA核心运算是非常耗时间的模乘, 只要能精确监视RSA的解密过程, 获得解密时间, 就可以估算出私有密钥d。模指数运算是通过一位一位来计算的每次迭代执行一次模乘, 并且如果当前位是1则还需要进行一次模乘.对于有些密码, 后一次模乘执行速度会极慢, 攻击者就可以在观测数据解密时, 根据执行时间判断当前位是1还是0, 不过这种方法只是理论上可以考虑, 实际操作很困难.如果在加密前对数据做盲化处理, 再进行加密, 使得加密时间具有随机性, 最后进行去盲, 这样可以抵抗定时攻击, 不过增加了数据处理步骤。

摘要：主要讨论RSA算法的安全性, 描述了当前大数分解的状况及推荐的安全密钥空间, 并在大数分解问题困难性的假设下, 简单讨论了自RSA算法提出以来, 研究者对该算法提出的各种攻击.

关键词：RSA算法,安全性,因子分解

参考文献

[1] G.J.Simmons.A weak privacy pro-tocol using the RSA cryptosystems.Cryptologia[J].1984, 7:180～182.

[2] J.Hastas.On using RSA with lowexponent in a public key network[J].Advancees in Cryptology-CRYPTO’85 Proceedings, Spring-Verlag, 1986:403～408.

[3] M.J.Winner.Cryptanalysis of shortRSA secret exponent, IEEE Transac-tions on Information Theory, vol36 (3) , 1990, 36 (3) :553～558.

[4] P.kocher.Timing attacks on imple-mentations of Diffie-Hellman, RSA, DSS, and other systems.In CRYPTO’96, Lecture Notes in Computer Science, Spring-Verlag, 1996, 1109:104～113.