基于RSA的网络密码数据加密算法的优化与设计

目前，网络环境下运行的软件系统出于对安全的考虑，大都需要在网络中频繁传递密码数据。因此，这些密码自身的安全一直倍受关注。RSA公钥加密系统是目前最有影响的公钥加密算法之一，它能够抵抗到目前为止已知的所有密码攻击。

从RSA公钥加密系统特点上看，它非常适合对网络中传递的密码数据进行加密。但随着计算机技术的发展，破解RSA的风险正在加大，而RSA为保证自身的安全，其密钥长度在不断地增长，加密计算量也随之增加，这使得RSA加密速度越趋缓慢。我们在RSA公钥加密系统的基础上，针对网络密码数据提出了一种加密算法的优化方案，有效地提高了RSA的安全性，同
时也提高了其加密速度。

一、 RSA公钥加密系统

RSA加密算法基于一个十分简单的数论事实，将两个大素数相乘十分容易，但是想分解它们的乘积却极端困难，因此可以将乘积公开作为加密密钥。整个RSA加密算法的结构可以描述如下：

（1）选取两个大素数p和q（保密）；

（2）计算n，使得n=pq，并公开n；

（3）随机选取正整数e，使得e与y= (p-1)(q-1)互素，公开e；

（4）计算d，使得e×d mod y=l，d保密；

（5）加密；c=memod n；

（6）解密；m=Cd mod n；

（注：m是明文，c是m对应的密文。）

以上实现过程是：A欲传递密码给B，B则需要持有密钥d，并公开e和n，A用e和n对密码数据进行加密后传给B，B得到密码后用d和n进行解密。

RSA加密算法中，其安全性取决于p、q两个大素数的取值，且p、q取值越大，分解越困难，被破解的可能性就越小，但其加密的计算量也随之增大，加解密速度也随之变慢。

二、基于RSA的网络密码数据加密算法的优化与设计思路

1、动态加密

从前面叙述可知，RSA加密算法的安全性及计算速度都与p.q两个大素数的取值有着直接的关系。因此，把优化重点可放在p、q的取值上。为了能得到较为理想的运算速度，对p、q的取值不宜太大，能保证短时间不会被破解即可。在一定的素数生成周期T和动态范围(X，Y)内产生一系列的素数，并从中随机抽取p、q值，使得每次加解密所用的n、e、d均不同，以实现动态加密。p、q的取值长度和范围(X，Y)由周期T决定，原则是保证在NT(N∈Z，Z>0)时间内不会被破解。

2、动态密码数据

事实上，仅实现动态加密还不足以保证密码数据的安全。因为破解者只需获得一次加密信息，不管破解时间多长，只要破解成功同样获得正确的密码数据。因此，必须对密码数据限定一定的有效期，即实现动态的密码数据。

3、 实现签名机制

攻击RSA方法主要有选择密文攻击和公共模数攻击两种，对选择密文攻击的解决办法有：

(1)不对自己一无所知的信息签名。

(2)不对陌生人送来的随机文档签名。

而对公共模数攻击的解决办法只有一个，那就是不要共享模数n。在RSA中叠加MD5签证机制无疑是解决择密文攻击的有效方法。而对于公共模数攻击，动态加密过程实际上已实现了不共享模数的过程。

三、 动态生成素数的算法

要实现上述的优化与设计思路，最主要是要解决动态生成素数的问题。需要在一定的素数生成周期T和动态范围(X，Y)内生成一系列的素数，并从中随机抽取p、q。

1、 素数选取条件

首先，p、q的选取条件必须满足：

n=pq，T(n)=(T(n)为计算n的时间复杂度)；

则必须满足NT<T(n) (N∈Z，Z>O)。

2、生成素数序列算法

可以在动态范围(X，Y)内得到整数集合，然后逐个进行素数判别。以往判断一个数S是否为素数时，一般采用求距离S最近的质数β，β满足≤S。其求解方法可以采用8不被小于佰任何数整除（不含1）来测试，测试首数从S开始。但是该加密算法的时间复杂度为0（根号s），当S较大时计算时间很长。虽然前面提出不需要很大的素数，但从网络安全上考虑，所需要的素数位数也不能太小。因此，该判断素数的加密算法不能在此适用。

在此，我们采用Miller Rabin概率测试算法来判断素数。为了使整个素数判断过程更快，先用“筛选”法，将偶数和最后一位为5的数全部去掉，再用剩下的数进行Miller Rabin概率测试。其测试的计算机实现过程如下：

（1）假设测试数为n，找出整数k、q，使得n-1=（2-k）*q，其中k>0，q是奇数；

（2）随机选取整数a，2<a<n-1；

（3）z-a-m mod n；

（4）如果z=1或z= n-1，则n可能为素数，否则为合数；

（5）进行j=0到k-1的循环；

（6）如果a^((2^j)*q)mod n=n-1，则n可能为素数，否则为合数；

（7）j=j+1，如果j≤k-1，则转到（5）执行，否则跳出循环。

由于a是随机抽取，n通过测试但并不能确定它一定是素数，因此需要进行多次这样的测试，以确保得到的是一个素数（DDS的标准是要经过50次测试）。

3、随机数产生算法

解决素数生成问题后，还需要产生2个随机数，以实现动态生成p、q两个大素数。事实上本文所提到的加密算法安全主要是依赖动态方式来实现，如动态素数、动态密码等，以此来降低对p、q两个大素数位数的要求，以提高整个运算速度。同样，这里也可以降低随机数的产生质量来换取速度上的需求。

BBS随机数产生器虽然随机数的产生质量很好，但其运算复杂，速度较慢，因此可以采用线性同余算法来产生随机数，其随机数序列｛Xn}由方程：Xn+1= (aXn+c) mod m得到，其中模数m>0，乘数a满足0≤a<m，增量c满足0≤c<m，初始值O≤XO<m。当m、a、c、XO都是整数时，通过这个方程就能产生一系列[O，m]范围内的整数了。

4、 动态密码的产生

事实上，动态密码产生的方法很多，比如可以利用本地硬件序列号（如CPU、硬盘等）、本地时间（或服务器时间）等参数来设计动态生成密码的加密算法，这些参数可随公模传送或密码传送一起进行传送。

四、 叠加MD5签名机制

从上述分析中可以知道，选择密文攻击对RSA公钥加密系统造成的威胁是致命的。为了防止此类攻击，需要对所传送的信息实行签名机制，这样可以实现不对自己一无所知的信息签名，也不对陌生人送来的随机文档签名。

MD5是一种用于产生数字签名的单项散列加密算法，它的作用是让大容量信息在用数字签名软件签私人密匙前被“压缩”成一种保密的格式。不管字符信息容量多大，经MD5换算后都会输出一个128bit的大整数，该大整数对原字符信息中的每个字符都很敏感，原字符信息中的一个字符改变都会改变大整数的值。重要的是MD5是不可逆的，无法将一个MD5的值变换成原字符信息。很显然，在RSA中叠加MD5加密算法无疑大大增加了密码数据的安全性。

RSA叠加MD5过程如下：

（1）A请求给B传送密码数据。

（2）B随机计算出公钥和私钥，并将公钥传送给A。

（3）A拿到公钥后将密码文件加密成M，将M进行MD5换算，并得到一个128bit的大整数N。

（4）将M、N传送给B。

（5）B先进行MD5验证，通过验证后再用私钥解密。

本文所述加密算法的核心思想在于动态加密和动态产生密码，即保证在密码可能被破解的时间内改变加密密钥和密码数据的内容，以此来提高密码数据的安全性。