浅析RSA加密算法

摘要：RSA算法不但能用于数据加密，也能用于数字签名，还能检测素数的算法，所以它是目前最有影响力的公钥加密算法，能够抵抗到目前为止已知的所有密码攻击。其安全性依赖于大素数因数分解的困难性。文章主要介绍RSA的加密算法原理、加密与解密过程，存在的攻击，以及参数选择。

关键词：非对称密码；RSA算法；加密；素数；参数；量子算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）09-2062-02

近年来，网络的发展和普及，解除了人们传统意义上的时间和空间上的束缚，真正实现了全球信息化。但与此同时，由于网络的开放性、互动性和全球性等特性，信息篡改、假冒和窃取等不安全问题也日益增多。因此，信息安全成为当今社会一个热门的话题。

在传输信息过程中，为确保信息的安全性和保密性，信息加密成为一种主要措施。加密算法的种类不胜枚举。从2012年为期5天的RSA大会中，可见RSA已经运用到社会中的各个领域，受到了全世界的关注。这主要基于RSA加密算法不仅易于理解和实现，而且安全性好。

1 RSA加密算法

1.1算法原理

文献[1]中描述RSA算法是在1977年由Rivest、SchaMir和AdleMan发明的。RSA算法是一种既用于数据加密也可以数字签名的非对称密码算法，其安全性依赖于因子分解大数问题。

RSA密码算法是利用陷门单向函数的一种可逆模指数运算，它的安全性是基于大数分解的困难性。下面给出RSA体制的算法流程：

1）RSA加解密算法的初始化

第一，加解密系统随机地选取两个非公开的大素数p和q。

第二，计算出公开的模数N和非公开的欧拉函数，[N=pq]，[φN=p-1q-1]。

第三，随机生成一个整数e作为加密秘钥，并使成立。

第四，计算d（私钥），使得）成立，即，为安全起见立即销毁p、q及e。

2 RSA算法存在攻击

尽管对于RSA的密码分析已经研究了三十多年，但它依然是流行和可靠的。可是，在RSA算法实现的细节上存在一些缺陷，这导致了RSA的安全性下降，从而使RSA被攻击者攻破。下面简单地概述一下目前对RSA算法攻击的几种主要方法。

2.1 数学攻击

实质上就是直接对两个素数乘积N的因式分解。这是一种最直接和最困难的的方法。一旦对N进行分解成功，就很容易得到密钥e。大整数因子分解一直是数论和密码学理论研究中的主要课题。根据目前的研究表明，目前最快的因式分解算法的复杂度为[Ο2（log2n）log2log2n]。此外，在文献[4]中，作者提出了用于分解强素数乘积构成的RSA模数N的算法，能够进一步提高了运算效率。

2.2时间攻击

依赖解密算法的运行时间。P.Kocher提出，利用测定RSA解密所进行的模指数的运算时间来估计解密指数d，然后再确定d的值；可以通过将解密运算量与参数d无关来挫败时间攻击；不断强力穷举密钥。

2.3密文攻击

攻击者非法获取密文通，过对密文反复用公开密钥加密，可以使明文出现。例：如果取RSA参数（N，e）为（35，17），明文M为33，加密明文：[c=3317mod35=3]；再次加密：[317mod35=33]，从而得到明文。

2.4 RSA的部分明文攻击

另外，攻击者不仅对可以密文进行攻击，也可以通过获取明文消息的部分信息进行破译或恢复整个明文。这也是RSA存在的另一个安全性的重要问题。

2.5对RSA小指数的攻击

此攻击方法主要针对RSA算法实现中的细节。如果为了加快加密和验证，选较小的e，并且用这些e向多个用户加密同一个消息（N不同），利用中国剩余定理可以联立方程求解明文。

2.6公用模攻击

如果需要多个密钥对，有一种做法：不再重新寻找p、q，而只是重新选d、e，即若干对密钥使用同一个模N。这时可以不用重新分组，也方便管理。但可能遭到公用模攻击。这样，如果同一信息用两个不同的指数e加密，并且两个指数e是互素的，则不需要任何解密密钥便能恢复出明文。设M是明文，两个互素的加密密钥分别是[e1、e2]，共同的模数为N，两个密文分别[c1=Me1modN]、[c2=Me2modN]。由于[e1、e2]互素，根据扩展Euclid算法可以找到a和b，使其满足[ae1+be2=1]。假设a是负数（在a、b中，肯定有一个是负数），再次使用Euclid算法可以计算出c1-1故可得到[（（c-11）-rc2s）MmodN]。

3 参数的选择

RSA体制是将安全性基于因子分解的第一个系统。虽然无法证明因子分解等于破解RSA系统，但若能分解因子N，便能破解RSA系统，所以RSA对公开的N的选择是很关键的。对于公开密钥e和解密密钥d也需要加以限制，否则会使RSA不安全。选择参数会影响RSA整个系统的安全，常用的参数选择应注意要求如下：

3.1 p，q的选择

要想提高RSA的效率和安全性，可以从p、q两个参数以下两个方面着手：素数的检测算法和对p、q的破解。

素数的检测算法。在RSA算法中，首先要产生两个大素数。但是要判断一个大整数是否为素数却一直是个难点。素数检测算法有确定性素数检测法和概率性素数检测法两类。目前，在RSA密码的应用中都使用概率性检测法来判断一个大数是否是素数。但是通过概率性监测算法的检测，还是存在伪素数的情况。

对p、q的破解。从RSA算法原理中，我们知道欧拉函数[φN]和模数N：[φN=p-1q-1]和[N=pq]。那么根据这两个式子可以构造关于p、q的一元二次方程，即[χ2-N-φ（N）+1χ+N=0]。其中p、q满足：

[[N=pq]p+q=N-φN+1]

解之得 p，q= [1/2N+1-φ（N）±（N+1-φ（N））2-4N]

由文献[4]提出的一种强素数的量子算法，可求得[φN]，这样就可以得到p、q的值，即分解了模数N，RSA就被破解了。

总之，为了抗穷举，p、q都要大；p、q的差要大，如果p、q的差不大，可以用N开方估算p、q；p-1、q-1要有大的素因子，p、q要为强素数；p-1、q-1的公因数要小。

3.2 模数N取几个素数乘积

从RSA算法原理，我们知道模数N是由两个素数相乘得到的。那么模数N可以由多个素数相乘得到吗？答案是肯定的。Euler函数[φ（N）]表示小于N并且与N互素的正整数个数。如果模数N可因式分解为[N=Piai]（其中，[ai>0]，[ai]互不相同），则[φ（N）=Piai×（1-1/Pi）]即：[φ（N） =N（1-1/p1）（1-1/p2）...（1-1/pn）]。文献[1]已经证明了该推断的正确性。

无论取多个素数还是两个素数相乘，一旦计算出模数N的值，就会都被丢掉。所以这多个素数和两个素数的保密性是一样的，RSA的加密和解密过程是相同的。那么在确定N时应尽可能的选择多个素数相乘。但是如果通过量子算法[4]来对多个素数乘积的模数N进行分解的话，那么就不能构成一元二次方程，分解模数N的难度就更大。

3.3 e，d的选择

e不能太小，如果e小，则可能而未取模，这样可以直接对密文开方求出明文；e太小易遭低指数攻击。为了有效防止被攻击，同时有较快的加解密速度，通常加密密钥e选取16位的素数，并且为[modφ（N）]的阶数，即i要达到[（p-1）（q-1）/2]。

d不能太小，应该[d>N14]。解密密钥d的值越小，系统签名和解密运算的速度越快，这对于我们常用的智能卡的加密、银行系统的签名特别重要。

4 小结

综上所述，RSA是一种安全性较好的非对称密码算法。它的安全性依赖于对模数N的因式分解。在日常生活中，RSA算法已广泛地运用到各个领域。那么对RSA算法的攻击无时不在。特别地，当选择的参数不当时，RSA很容易被攻击。要确保RSA的效率和保密性，我们应注意以下几点：对素数检测算法进行改进；用量子算法来研究RSA算法。

参考文献：

[1] 武亚宁.RSA 公钥算法的新探讨及改进[J].信息安全与技术，2012（9）：27-28.

[2] 白洁.RSA大会，安全领袖眼中的世界[J].信息安全与通信保密，2010（4）：16-19.

[3] 张宏，刘方圆.四素数RSA加密算法的研究与分析[J].2010：29-30.

[4] 潘峰，申军伟.一种强素数因式分解的量子算法[J].2010，46（10）：73-74.

[5] 陈磊.RSA算法的改进[J].信息安全与技术，2011：24-26.