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

降低。

因此，如何提高密钥产生技术，发展更快速、更精确的大素数生成方法，完善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加密算法的有效性。