模幂运算的周期性对RSA算法的安全性威胁

摘要：当前各种加密算法已经非常成熟，并已经运用到了社会的各个领域，虽然安全性相对较高，但仍然存在着一些缺陷，本文对RSA加密算法的安全性进行分析，并提出了一种新的破译方法，希望通过本文能够提高人们对加密算法安全性的关注与研究。

关键词：加密技术；安全；RSA算法；模幂运算

中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2013）30-0122-02

一、RSA加密算法思想

加密算法按照加密思想分为对称加密算法和公开密钥加密算法，相对来说，公开秘钥加密算法的安全性较高，从公开秘钥加密算法提出至今，人们已经认识到其不足，很多人尝试着对其进行各种攻击与破译，当一种新的破译方法出现时，人们会对该算法进行弥补，以保证其安全性，能够达到人们的要求，到目前为止，RSA加密算法是较为安全而且实用的加密算法，在金融等各个领域用的比较多。任何一种公开密钥算法都是建立在非常严格的数学基础上的，我们称其为单向陷门函数，[1]在该算法中，秘钥包括公钥和私钥两部分，这两个秘钥是由数学方法产生的，公开密钥算法的安全性都是以某一个数学难解作为基础上的，不同的算法，所解决的数学难题也有所不同。

对RSA算法的加密过程进行分析，一切数据都是由素数p和q得来的，其中公开模数n为p与q的乘积，RSA算法的核心是模幂运算。在该算法中，公开的有公开模数n和公钥e。通过人们对RSA算法的分析后，发现该算法同样也存在着几个典型的安全问题，[2]本文中将不再累述。本文将对RSA算法的模幂运算进行分析，提出新的破译方法。

二、RSA算法的安全性分析

RSA算法的安全性取决于p、q的保密性，以及分解大数的难度，既将公开模数n进行分解，得到素数p和q的困难性。[3]现有的素因子分解算法已经能够分解130位（十进制）的整数，所以在具体的应用中，用户所选用的素数p和q的合理长度应该在100位（十进制）左右，以使n=p×q的长度达到200位（十进制）。为了增大n的值，人们在选取p、q值时通常注意以下几个问题：

1.p和q为长度在100位以上的强素数，以保证n值足够大，使得在计算机上直接分解n这种方法行不通。

2.p与q的值相差10倍以上。假设p和q值相差不大，就可以认为p和q值相等，则可由■≈■，在■附近找到p和q。

3.公钥e随机生成，并且不能太小，否则也很容易被猜测出来。

4.私钥d的取值要大于n1/4。经过人们的研究，为了保证系统的安全性，d的长度应在1024比特左右。

对于RSA算法来说来说，密钥越长其安全性就越好，RSA加密算法使用了两个强素数来产生秘钥。假设采用因数分解的方法能够获得私钥，这个操作对于当前的计算机来说，其计算量是巨大的，即在现实中是行不通的。这也是人们广泛使用RSA算法进行加密的原因。公钥加密算法的安全性是指在计算上的安全性。前面已经分析过：RSA算法的安全性建立在对大数的因数分解困难的基础上，破译者要解密密文C，除了采用效率较低的穷举法外，只能获得私钥，而求私钥d需要先求φ（n），求φ（n）应先求p和q，而求p和q就要分解n，因此破译RSA算法的方法最终还是归结到对大数的因式分解上来，但在现实中人们还只是推测：RSA的安全性取决于对大数的因式分解问题，但并没有得到人们的证明，于是我们猜测可能还会有其他的方法破译RSA算法。

三、通过模幂运算破译RSA算法

经过前面的分析，我们知道：RSA算法的安全性建立在对大数的分解上，为了保证其安全性，在选择p、q值时，我们可以增大其位数，如果密码分析者试图从将n分解为两个素因子入手，来获取解密密钥，进而破译RSA算法，依靠当今计算机的处理能力来说是非常困难的，通过这个角度分析该算法是安全的，但这并不意味着密码分析者不能从其它途径来破译该算法，我们发现如果对信息的明文M按照RSA算法的思想，进行反复加密的时候，某一次的密文便和明文的内容相同，也就是说当破译人员截获到信息的密文后，再使用公开的秘钥按照RSA算法的加密方法对密文进行若干次的加密后，便可以恢复出相应的明文。利用RSA算法存在的这个弊端，便可以对该算法进行破译。

如：明文m=123，n=187，e=7，我们对其进行反复加密：

m1=me mod n=1237 mod 187=183

m2=m1e mod n=1837 mod 187=72

m3=m2e mod n=727 mod 187=30

m4=m3e mod n=307 mod 187=123

m5=m4e mod n= 1237 mod 187=183

我们发现m5=m1，m1是明文加密后所得到的密文，也就是最后进行信息传递的数据，攻击者可以截获该信息，n是公开的，对于攻击者来说是已知的，e是公钥，可以查阅公钥簿来获取，这样密码破译者可以在以上信息的基础上，使用上述方法，反复对密文进行加密，当发现某一次的数据与所截获的密文相同时，前一次运算的结果（这里为m4）便为信息的明文。我们发现不采用对大数n进行分解，利用RSA算法的这个弊端同样可以对RSA算法进行解密还原出明文。现在我们提出质疑，在RSA算法中是不是所有的密文，经过反复加密后，都可以还原出明文，也就是说，上面的特性是否具有通用性，是否只是所举例子的一种巧合？接下来我们证明，模幂运算的结果是否具有周期性。

证明：设2k对正整数m的余数是a，即2kmod m=a；则：2k+1 mod m的余数为2a，即：

2k+1modm=2×2k modm=2modm×2k modm=2a；

每次余数都是前一次的2倍。直到余数大于m时，余数变成（2x）a-m，即第x-1次时的余数和第1次的余数相同。

因为对正整数m的余数最多只有从0到m-1共m个，所以，经过有限次后，必然有两个余数是相同的。一旦余数相同，余数就会按照这两个相同的数值之间的数据进行重复循环出现。所以得证：模幂运算结果具有周期性。进而分析，当m递增时m mod n呈现周期性变化，其周期随着n的值而变化，其周期为n，也就是说不管n值多大，只要m不断增大，其结果就会出现循环。经过证明我们发现因为模幂运算具有周期性，所以反复运算C=（Me） mod n，t次后将还原为最初的M，即M=（Me）t mod n。人们针对其进行改进的措施主要是在选取e时，要求e为强素数，这样使t足够大，但是我们知道不管t多大[3]，但始终还是存在这样的一个数，使人们不通过对n进行分解，仍然可以对RSA算法进行解密，而且该种方法的破译难度要远远低于对大数的分解，再有随着计算机速度的提高，其破译的时间也将越来越短。

四、总结

由于RSA加密算法的安全性相对于传统的对称加密算法的安全性较高，在日常生活中大多采用的都是RSA加密算法，就要求该算法要经得住考验，当前对RSA加密算法的攻击方法也多，但大部分都是针对如何提高对大数分解角度进行的，在本文中，笔者通过模幂运算的周期性提出了一种新的攻击思想，希望通过本文能够引起人们的关注，从另一个角度想办法来保证RSA算法的安全性。

参考文献：

[1]郑子伟.基于偶次幂因子分解的RSA快速算法[J].曲阜师范大学学报，2005，31（2）：48-52.

[2]Bruce Schneier.应用密码学[M].北京：机械工业出版社，2000：50-132.

[3]游新娥.RSA算法中安全大素数生成方法及其改进[J].吉首大学学报（自然科学版），2007，28（5）：34-37.