改进的RSA加密算法设计与实现

祝 珂 雷冰冰 刘海波

(北方民族大学 计算机科学与工程学院,宁夏 银川750000)

置身在信息社会中，人们之间所传递的信息通常以网络数据作为载体。在其传输过程中，存在被攻击导致信息泄露的风险，继而给个人或企业带来经济损失。为了保证信息的安全性，经常使用签名和格密码等加密技术，比方说SHA、DES、RSA、Babai等。在诸多加密算法中，RSA加密算法是一个性能较强且便于理解操作的公钥密码技术，人们多采取融入SMM算法[1]、对算法结构改进[2]或者将素数个数增加[3]等措施来提升RSA加密算法的安全性。但是由算法原理可知，该算法安全性取决于分解大素数的素数因子难度，并且当加密位数过短或素数p、q相差不大时便会变得易于破解。因此本文在常规算法基础上，将传统素数生成改进为强素数生成算法，给出一个改进的RSA加密算法。

1 RSA算法相关研究

1.1 公钥加密算法原理

公钥加密需要两个密钥，分别用于加密和解密。其中用于解密的密钥是保密的，这就是我们所说的私钥，用于加密的密钥无需保密，两者合称为密钥对。以一方S向另一方F发送信息为例：某用户S生成密钥对；S将密钥对中的公钥发送给F；F使用接收到的公钥对明文进行加密，得到密文，将密文回送给S；S使用私钥对接收到的密文进行解密，得到初始明文。只有拥有私钥的用户S才能对密文进行解密，由此便可确保信息的安全。

1.2 RSA加密算法原理

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。近些年来，RSA加密算法不断被黑客攻击，但在许多场景下用户信息安全都得到了保障，体现出较好的保护作用，现已逐步被大众接受。传统的RSA加密算法流程主要包括随机生成素数、密钥生成、加密明文和解密密文。

1.2.1 随机生成素数

通常采用以下方法获取传统RSA加密算法中的随机素数：

试除判断法：获取一个随机数x，判断x是否能被2到sqrt（x）间的数整除，如果可以被整除说明x不是素数。一般适用于数据范围较小的情况；合数过滤筛选法：对于0到N范围内的所有数字，逐一删除为2到(N-1)倍数的数，那么其余的皆为素数；Miller-Rabin算法：随机生成几个a，利用费马小定理与二次探测定理来检测素数；以及生成伪素数并进行素性检测等。

1.2.2 密钥生成

用于生成加解密要用到的密钥对，过程如下：

（1）随机生成两个素数p和q，满足p≠q。

（2）计算出n=p*q，计算出Ø（n）=（p-1）*（q-1）。

（3）随机选择正整数e，要求满足1＜e＜n，gcd（e，Ø(n)）=1。

（4）计算得到d≡e-（1）modØ（n）

（5）得到密钥对，其中公钥为(n,e)，私钥为(n,d)。

1.2.3 加密

对原始数据处理获取密文的过程定义为加密。加密计算公式如下：

其中M为原始数据，(n,e)为传输给用户的公钥，C为加密后得到的密文。

1.2.4 解密

利用私钥解开密文得到原始数据的过程定义为解密。解密计算公式如下：

其中C为回传的密文，(n,d)为私钥，M为解密后得到的原始数据。

1.3 RSA加密算法的实现

本文实验中随机选取p和q分别为53和61，计算得到n为3233，Ø（n）为3120，并选取随机数e为17，计算e对Ø（n）的模反元素d，得到d=2753，至此完成计算。对应得到公钥(e,n)=(17,3233)，私钥(n,d)=(3233,2753)。设定要加密的明文为357，由公式(1)可得到加密后的数据为2115。设定要解密的密文数据为2115，由公式(2)可得到解密后的明文为357。

图1 传统RSA加密算法实现过程

经过对RSA加密算法的不断研究可以发现，传统RSA加密算法的安全性过于依赖两个随机生成素数乘积的正确分解，也就是说随机生成的这两个素数是整个算法的关键。因此，本文将通过增加正确分解成初始素数的难度，来避免这一问题。

2 RSA加密算法的优化和改进

由算法过程可知，随机生成的素数是整个算法的关键。针对随机生成的素数值可能过小从而导致的安全性降低问题，本文引入强素数概念，使用强素数替换传统素数，增加其被分解得到正确素数因子的难度，使得改进后的RSA加密算法安全性更高。

随机生成强素数算法：

关于一个素数P何时能被定义为强素数，需满足以下四点：

(1)P必须是很大的素数。

(2)P-1有很大的素数因子。即对于任意整数a1以及大素数R，满足P=a1R+1。

(3)R有很大的素数因子。即对于任意整数a2以及大素数S，满足R=a2S+1。

(4)P+1有很大的素数因子。即对于任意整数a3以及大素数T，满足P=a3T-1。

在具体的应用当中，也可以根据用户的需求来加入附加条件，如对a1、a2额外赋值。

随机生成强素数算法流程如下：

(1)本文中以500以内素数作为初始素数数组，在素数数组中随机选取一个素数h1。

(2)随机生成一个1～9的整数x，结合第一步得到的素数h1，计算2ah1+1，a的取值从x开始逐渐加一，利用素数判断函数得到第一个出现的素数，记为h2。

(3)随机生成一个1～9的整数y，计算2bh2+1，b的取值从y开始逐渐加一，利用素数判断函数得到第一个出现的素数，记为h3。

(4)令P=2h3-1，使用素数判断函数确定P是否为素数，如果P并不是素数就执行(3)，反之就执行(5)。

(5)输出P，P为生成的强素数值。

证明：结合强素数的定义以及上述流程（4）可以得到，素数P=2h3-1，即P+1有一个很大的素数因子h3；由流程（3）、（4）得知，素数P=2h3-1=2（2bh2+1）-1，即P-1有一个很大的素数因子h2；由流程（2）得知，素数h2=2ah1+1，也就是说h2-1具有一个很大的素数因子h1，其中h1是初始选取的素数因子。至此便可以判定生成的素数P满足强素数的条件，即P为强素数。

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

图2 改进的RSA加密算法实现过程

本文实验中通过运行两次随机生成强素数算法，得到两个强素数值分别为7537和57373，通过计算得到n的值为432420301，Ø（n）的值为432355392，在实验中选取随机数e的值 为 13， 对 应 得 到 公 钥 (13,432420301)， 私 钥 为(432420301,305919877)。设定要加密的明文为23，通过公式(1)可得到加密后的数据为261901546。设定要解密的密文数据为261901546，由公式(2)可得到解密后的明文为23。通过将随机生成强素数算法与传统RSA加密算法结合，一定程度上提升了运行速度，增强了RSA加密算法的安全性。

3 结论

本文对RSA加密算法进行研究，通过分析得知其仍存在安全性问题。相较于改进RSA结构等方法，随机生成强素数算法是增加安全性的更好选择。本文使用强素数作为RSA加密算法的初始素数因子，使得算法安全性和加密运算效率都得到了有效的提升，让RSA加密算法有了更好的应用场景。