RSA密码算法的研究与改进

周伟

摘 要 隨着计算机在全世界普及，网络技术已经进一步融入日常生产工作，成为了信息化时代交流和反馈的重要渠道。所以，网络技术的不断发展带来了人们生活的便利化，但是计算机系统的安全保障在网络技术的发展下受到了更大的威胁，因此需要不断完善和发展信息保密技术。本文着重探析RSA密码体制原理。RSA算法是一种安全可靠的密码算法，一定程度上可以免疫绝大部分密码攻击手段。人们通过不断改进和完善进一步提高了RSA密码算法的安全性。但伴随先进技术的层出不穷以及网络科技的高速发展，RSA密码体制也面临着更多挑战。

关键词 RSA；欧几里德算法；大整数运算

中图分类号 TP3 文献标识码 A 文章编号 2095-6363（2017）14-0089-02

在信息技术高速发展的时代，海量的信息不再是确切存在的实物，而是由存在的实体通过计算机转换成了数字代码。如果没有对这些数字代码采取适当的保密手段，很容易发生数字代码被人截获被破译者利用。在计算机网络的发展过程中，人们在信息安全理论中引进了密码学理论，通过各种形式的加密以保证信息的可靠传输。因此，计算机系统安全以及信息传输安全已经离不开密码学理论。

1 RSA传统算法概述

2 RSA算法的分析与改进

RSA算法的密钥中的e加密密钥是和互素的任何数字，由此我们可先行选取一个随机的大数，然后检验这个数是否和互素，如果不是互素，则再次循环这两个步骤，到与互素停止。这里检验两个大数是否互素就需要考虑他们的最大公约数，自然而然就需要运用到求最大公约数的欧几里德法[1]。

欧几里德算法是按照辗转相除的思想计算两个正整数最大公约数的算法。

欧几里德算法的优点：综合上面的证明可知，求模运算计算得到余数r是最大公约数c的倍数，因为他们的倍数关系简化了最大公约数冗长繁复的计算。与此同时，不需要进行试商这样的运算，只需要对余数进行相应的计算就可以直接得到最大公约数，极大地提高了运算的效率。

欧几里德算法的缺点：在大整数计算的时候欧几里德算法会出现很大的缺陷。考虑到现行的运行系统和硬件平台，操作过程中的整数一般较大的也就只有64位，对于这些整数，他们之间的求模运算是不算太难。但是对于位数更多的素数，像这样的计算过程就只能落到用户肩上，由用户自己来设计。但是这个过程不仅复杂，而且会耗费很大一部分CPU时间。而对于现现今情况下的密码算法，要求计算128位以上的素数的情况层出不穷，所以在这样的程序设计急需要摒弃除法运算和取模运算。

辗转相减的方法（尼考曼彻斯法）是按照辗转相减的思想计算两个整数最大公约数的算法。该算法描述为：1）将两个正整数相减；2）辗转相减（大一点的数就作被减数）；3）计算得到的差和减数的最大公约数就是原来要求的两个数的最大公约数。

下面举个例子：取两个自然数42和12，用大一点的数减去小一点的数，（42，12）到（30，12）到（18，12） 到（6，12），此时，6小于12，就要做一次交换，把大数12作为被减数，即（12，6）到（6，6），再做一次相减，6—6的结果等于0，这样也就求出了42和12的最大公约数6。

而这个方法在面对大素数的时候也会显得过分的冗长，例如两个128位的大数相减其结果可能还为128位的大数，这样就不利于算法的运行。

考虑到辗转相除法对于大整数除法运算的难度以及辗转相减法对于大整数减法的繁复，本文考虑将两种方法结合起来，对欧几里德算法求最大公约数进行改进，希望达到简化算法复杂程度的效果。

例：以gcd（42，12）为例：

第一步在数组i中，2是42和12的因子，故gcd（42，12）=2* gcd（21，6）；第二步在数组i中，3是21和6的因子，故gcd（42，12）=2* gcd（21，6）=2*3*gcd（7，2）；第三步在数组i中，2是2的因子但不是7的因子，7是7的因子但不是2的因子，故gcd（42，12）=2* gcd（21，6）=2*3*gcd（7，2）=2*3*gcd（1，1）=2*3*1=6。

这种方法简化了大整数除法的复杂性，提取大整数的小因子发挥了除法的在运算中的跳跃性，如果没有办法从大数中提取因子，那就采用辗转相减的方法进行处理，比之原来的欧几里德算法直接大整数相除在计算上有了极大的简化。

改进后的欧几里德法通过C语言编程计算五组数123456和987456、125478和369854、125478和325874、1254789和36541、235478和124785最大公约数所需时间为24.348秒，而传统欧几里德法计算五组最大公约数所需要的时间为63.795秒。由实验结果显然可以得到以下结论，本文改进后的欧几里德算法确实优化了大整数除法耗时长的缺点。从而提高了RSA密码算法的速度。

参考文献

[1]闵嗣鹤，严士健.初等数论[M].北京：高等教育出版社，1982.