RSA加密算法及其改进算法的研究和实现

摘要：首先利用RSA加密算法对数据进行加密和解密，实现了数据的安全传输;然后针对RSA加密算法时间开销大和算法设计复杂的缺点，提出基于乘同余对称特性的SNM算法。通过对该改进RSA加密算法的实现发现加密运算速度明显提高且算法更简单，从而证明了本文所提改进算法的有效性。

0 引言

在当今信息社会中，每天都有大量的加密信息在传输、交换、存储和处理，一旦密码遭到破解就可能造成信息的丢失、篡改、伪造、假冒以及系统遭受破坏等严重后果，因此，如何保证信息的安全传输成为当前信息传输领域的热点问题。W.Diffie和M.E.Hellmam在1976年发表了具有划时代意义的“密码学的新方向”一文，提出了公钥密码体制思想，克服了传统对称密码体制的缺点，为近代密码学的发展指明了方向。它的出现是密码学研究领域中的一项重大突破，也是现代密码学诞生的标志之一。

本文首先对非对称加密算法RSA的原理和优点进行研究，然后实现其加密、解密功能。RSA算法在公钥密码体制中占有重要的地位。但该算法所采用的幂乘计算耗时太多，一直是制约其广泛应用的瓶颈。因此，为了提高加密和解密速度，本文提出一种新型的加密算法即基于乘同余对称特性的SMM算法。该算法采用简单的迭代来实现，不需要幂乘和乘法逆运算，从而在提高加密解密的速度同时也使得程序设计更简洁紧凑。

1 RSA加密算法原理

RSA加密算法的理论基础是一种特殊的可逆模指数运算，其算法描述如下：

(1)选择两个互异的大质数p和q(p和q必须保密，一般取1024位)。

(2)计算出n=p q，φ(n)=(p-1)(q-1)。

(3)选择一个比n小且与φ(n)互质(没有公因子)的数e。

(4)找出一个d，使得ed-1能够被φ(n)整除。其中，ed=1 mod(p-1)(q-1)。

(5)RSA是一种分组密码系统，所以公开密钥=(n，e)，私有密钥=(n，d)。

其中，n为模数，通信双方都必须知道，e为加密运算的指数，发送方需要知道，d为解密运算的指数，只有接受方才能知道。

将以上过程进一步描述如下：

公开密钥：n=pq(p，q分别为两个互异的大素数)，e与(p-1)(q-1)互质。

私有密钥：d=e-1{mod(p-1)(q-1)}。

加密：C=Me mod n，其中M为明文，C为密文。

解密：M=Cd(mod n)。

若要破译密码必须知道p，q，即对n作素因子分解，这在数学上是非常困难的。

2 RSA加密算法的实现

2.1 算法设计流程

RSA算法设计流程如图1所示，主要采用下述加密/解密变换。

(1)密钥的产生

a.选择两个保密的大素数p和q。

b.计算n=p q，φ(n)=(p-1)(q-1)，其中φ(n)是n的欧拉函数值。

c.选择一个整数e，满足1

d.计算私钥d，满足d=l(modφ(n))/e，d是e在模φ(n)下的乘法逆元。

e.以(e，n)为公钥，(d，n)为密钥，销毁P，q，φ(n)。

(2)加密

加密时首先将明文比特串进行分组，使得每个分组对应的串在数值上小于N，即分组的二进制长度小于1 092 N。然后，对每个明文分组M，作加密运算。

加密：C=Me(modn)，其中M为明文，C为密文。

(3)解密

对密文分组的解密运算为：M=Cd(modn)。

2.2 RSA加密算法的实现

(1) 生成密钥

随机选择两个大素数p和q，如果p和q足够大，那么n=p q就会变的很大，在理论上因式分解一个大数并准确地分解出p和q是很难实现的。本文随机选择P和q为61和67。根据φ(n)=(p-1)(q-1)可得n的欧拉函数值φ(n)为3960，如图2所示。

随机数e的选取要满足随机数和欧拉函数最大公约数gcd(eφ(n))=1这个条件。如果e比较大，加、解密速度变慢，也不便于存储，但是太小的e会导致安全性问题。所以限定1

(2)加密

输入明文，根据公钥(e，n)和公式C=Me(modn)可得密文。本文选择要加密的明文为1234，由公式可得密文为2793。根据计算结果可知此加密算法加密所用的时间为2.667 ms。

(3)解密

输入3调用第三个模块来实现解密功能。RSA加密算法解密所需要的条件是知道密文和私钥，根据M=Cd(modn)可得到明文。由计算得到密文为2793，私钥为233，所以可解的密文为1234，从而实现了解密功能。

RSA加密算法的实现过程如图2所示。

大整数因子分解问题向来被数学界视为世界性难题。正是基于这一点，RSA公钥密码体制才能够以其较高的安全性为人们广泛接受。但是RSA公钥密码体制也存在诸多不足之处：加解密算法中涉及大量的数值计算问题导致计算时间开销较大，在一定程度上限制了其应用范围。且密钥的产生受到素数产生技术的限制，因而很难做到一次一密。为保证安全性必须选取1024 bits或以上，但这就使得运算速度较慢，而且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化，致使其实现的难度增大，实用性降低。

因此，如何提高密钥产生技术，发展更快速、更精确的大素数生成方法，完善RSA加密算法的大整数模幂乘运算，设计运算速度更快的求模和求幂算法，是很有意义的—个探索方向。

3 RSA加密算法的改进及实现

针对RSA加密算法加密速度慢的问题，经过进一步的研究，提出了SMM算法。SMM(Symmetry of Modulo Multiplication)算法是利用乘同余对称特性来减少RSA加密计算中乘法和求模运算量的一种快速算法。RSA加密是对明文求幂剩余的过程为：

y=n (1)

传统RSA算法是将指数表示成二进制数的形式，并将幂乘变成一系列乘同余的迭代。SMM算法是在每步迭代中对乘数进行有条件的代换。乘同余和平方剩余的对称性有：

(n-i)(n-j)≡ijmod n (2)

(n-i)2mod n≡i2mod n (3)

j(n-j)≡(n-j)i≡-ijmod n (4)

其代换情况如下：如果ai-1表示第i-1步迭代的结果，则在进行第i步迭代时，若ai-1或g<(n-1)/2，则保持原数不变;如果ai-1或g≥(n-1)/2则使用n-ai或n-g来代替ai-1或g[8,9]。

由于使用SMM方法，减少了乘法时间和求模运算量，改进后的RSA加密算法理论上可以使得算法速度得到一定程度的提高。

为了方便将改进前后的算法做比较，本文随机素数p、q仍选择61和67。根据f(n)=(p-1)(q-1)可得f(n)为3960 c，随机数e选择17，可得公钥为(17，4087)，私钥为233。改进后的RSA加密算法运行结果如图3所示。与图2对比可知，相同初始条件下原RSA算法所用的加密时间为2.667 ms，改进后算法所用的加密时间为1.669 ms，加密速度提高了约37.4%，且程序的复杂度也有所降低。

改进后的RSA加密算法可以通过简单的循环迭代完成整个RSA加解密过程，减少了将十进制数据转化为二进制数组和用扩展的欧几里得算法求乘法逆元这两步，不仅降低了程序的复杂性，而且提高了运算的效率。

4 结论

本文针对RSA加密算法时间开销高和程序复杂的缺点，提出一种基于乘同余特性的SMM加密改进算法，该改进算法可减少RSA模幂乘运算过程耗时以及提高RSA加解密速度。最后通过改进前后算法的实例对比证明了本文所提改进RSA加密算法的有效性。