RSA算法的改进

1. RSA 算法概述

公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲(Diffie) 和赫尔曼(Hellman)两人首先发明的，但目前最流行的RSA 是由分别取自三位发明此算法的数学家RonaldRivest,Adi Shamir 和Len Adleman的名字的第一个字母来构成的。[1]

RSA 已被国际上一些标准化组织如ISO、ITU 等作为标准采用,现在流行的PGP 也采用RSA 算法作为其解密和数字签名算法。它是第一个既能用于数据加密也能用于数字签名的算法。

但RSA 的安全性一直未能得到理论上的证明。RSA 的安全性依赖于大数难于分解这一特点。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。并且 RSA的加密算法速度与对称加密算法相比，其速度非常缓慢的。因此，研究快速的 RSA 算法是十分有意义的。至今，人们在此方面已经作了很多的研究，提出了许多快速的RSA 算法。其中分块模幂算法[2]，幂等价代换的改进[3]及 SMM 算法[4]等都极大的提高了 RSA 加密算法的速度。

2. RSA 算法的基本原理

RSA 体制用户i 的公开加密变换Ei 和保密的解密变换Di 的产生:(1)随机选取素数pi 和qi；(2)计算ni= piqi,Ф(ni)=(pi-1)(qi-1)；(3)随机选取整数ei 满足(ei,Ф(ni)) =1;(4)利用欧几里得算法计算di,满足eidi≡1 MOD Ф(ni);(5)公开ni,ei 作为Ei,记为Ei=< ni,ei>,保密pi,qi,di,Ф(ni)作为Di,记为Di=。加密算法:c = Ei(m) = mei(MOD ni),解密算法:m=Di(c)=cdi(MOD ni),在RSA 算法中,包含两个密钥:加密密钥PK 和解密密钥SK,加密密钥公开。[5]

3. RSA 算法的举例

要对2 运用RSA 算法进行加密，因为RSA 的原则是被加密的信息应该小于p 和q 的较小者，因此取p=5, q=3，求得n=p*q=5*3=15，m=(p-1)*(q-1)=(5-1)*(3-1)=8，然后生成较小的数e,使e 与8 互质,2 不对,3 是最小的,于是e=3 最后生成d,使d*e MOD m=1 , d*3 MOD8=1,d*3 除以8 余数为1，于是算出d=3，所以求出公钥e=3,n=15.私钥d=3,n=15.密钥计算完毕。加密:c=pe%n=23%15=8%15=8, 于是密文为8. 把8 传出去。同时应把公钥也传出去,好在收到时知道对应的是那个私钥。解密过程:接收者收到密文和公钥,找到对应的私钥:p=cd%n=83%15,经过运算，余数为2。

4.1 RSA 算法的改进

由于RSA 算法是基于大数分解的理论，应用了费尔马小定理[123123123]，在两个素数qi 和pi 的乘积n 被分解是最主要的攻击方法，因此提出了三重RSA 算法：用户j 的公开加密变换Ej 和保密的解密变换Dj 的产生:

(1)随机选取三个素数pj、qj 和rj；

(2)计算nj= pj*qj*rj,Ф(nj)=(pj-1)(qj-1)(rj-1)；

(3)随机选取整数ej 满足(ej,Ф(nj)) =1;

(4)利用欧几里得算法计算dj,满足ei*di≡1 MOD Ф(nj);

(5)公开nj,ej 作为Ej,记为Ej=< nj,ej>,保密pj,qj,rj,dj,Ф(nj)作为Dj,记为Dj=< pj,qj,rj,dj,Ф(nj)>。加密算法:c = Ej(m) = mej(MOD nj),解密算法:m = Dj(c) = cdj(MOD nj),在RSA 算法中,包含两个密钥:加密密钥PK 和解密密钥SK,加密密钥公开。

由于三重的RSA 算法成立，原来的RSA 算法也成立，因此推断N 重RSA 算法即：用户x 的公开加密变换Ex 和保密的解密变换Dx 的产生:

(1)随机选取N 个素数p1、p2……pn；

(2)计算nx= p1*p2……*pn,Ф(nx)=(p1-1)*(p2-1)*……*(rj-1)；

(3)随机选取整数ex 满足(ex,Ф(nx)) =1;

(4)利用欧几里得算法计算dx,满足ex*dx≡1 MOD Ф(nx);

(5)公开nx,ex 作为Ex,记为Ex=< nx,ex>,保密p1,p2,……,pn,Ф(nx)作为Dx,记为Dx=。加密算法:c = Ex(m) = mex(MOD nx),解密算法:m = Dx(c) =cdx(MOD nx),在N 重RSA 算法中,同样也包含两个密钥:加密密钥PK 和解密密钥SK,加密密钥公开。

下面对N 重RSA 算法给与证明。

应用2.2中提出的定理1：

若p, q是相异质数, d*e==1 MOD (p- 1)(q- 1), a 是任意一个正整数b==aeMOD p*q,c==bdMOD p*q, 则c==a MOD p*q。

可以得出推论1：

若p1,p2,……,pn是相异质数, d*e==1 MOD (p1- 1)*(p2- 1)*……*（pn-1）, a 是任意一个正整数b==aeMOD p1*p2*……*pn, c==bdMOD p1*p2*……*pn, 则c==a MODp1*p2*……*pn。

证明推论1的过程中过程如下:

由n（n>=2）个质数时，推论1成立。

当n+1时d’*e’==1 MOD(p1- 1)*(p2- 1)*……*pn*（p(n+1)-1）a’是任意一个正整数

b’==a’e’MOD p1*p2*……*pn*p(n+1), ①

c’==b’d’MOD p1*p2*……*pn*p(n+1) ②

因此通过①②式可以得到方程组

由于里面的a’、b’、p1,p2,……,pn, p(n+1)都是已知数，就c’是未知数，所以可以求得c’==b’d’MOD p1*p2*……*pn*p(n+1)因此可以知道推论1 成立。

可以证明N 重RSA 算法的正确性,因为N 重RSA 算法是正确的所以三重的RSA 算法想当然是正确的。

4.2 RSA 改进算法的性能

RSA 算法使用方便，尤其是公开密钥的特征使得用户在数据传输之前无需交换密钥，就算是和多个用户进行秘密通信，也没有必要记住所有的密钥，N 个用户通信，要有N 对密钥，每个用户只需记住自己的密钥，并到公共存储区去取得其他公钥就可以了。但是由于RSA 算法的实现是以大素数来为基础，依赖于计算机的速度和容量，效率比较低。根据统计，对相同数据块的加密，对称算法比RSA 算法的效率要高几十倍。

改进的N 重RSA 算法中，由于所取得素数比较多，取多少个也是有应用N 重RSA 算法的用户决定的，所以就可以把所取得素数的大小取得小一点，这样就提高了计算机的运算速度，加快了RSA 算法的运算效率。由于N 重RSA 算法根本没有违背RSA 算法，所以其安全性也是毋庸置疑的。

4.3 RSA 改进算法举例

要对2 运用N=3 的N 重RSA 算法进行加密，取p1=5, p2=3,p3=7，求得n=p1*p2*p3=105，m=(p1-1)*(p2-1)*(p3-1)=(5-1)*(3-1)*(7-1)=48，然后生成较小的数e,使e 与48 互质,2 不对,5是最小的,于是e=5 最后生成d,使d*e MOD m=1 , d*5 MOD 48=1,d*3 除以48 余数为1，于是算出d=29 ， 所以求出公钥e=5,n=105. 私钥d=29,n=105. 密钥计算完毕。加密:c=pe%n=25%105=8%105=8, 于是密文为8。把8 传出去。同时应把公钥也传出去,好在收到时知道对应的是那个私钥。解密过程:接收者收到密文和公钥,找到对应的私钥:p=cd%n=829%105,经过运算，余数为2。

上面运用了N=3 时的N 重RSA 算法，在这种非对称的RSA 加密算法中，充分利用了大数分解的思想，这样在改进的N 重RSA 算法中加进了多个是相乘，由于这样每次都有可能有不同多个数得出的结论来完成的加密密钥和公钥的计算，所以在更大程度上也保证的算法的安全性和保密性。

5. 小结

本文是在对传统的RSA 算法的充分研究和深刻理解上，对RSA 算法效率低的问题进行=了改进得到了基于原有算法的N 重RSA 算法。在增加了素数的情况下降低了所选素数的个数，以达到小数相乘运算速度比大数相乘效率高的特点。由于N 重RSA 算法还是在原有的RSA 算法的基础上，因此它的安全性和保密性都和原来的RSA 算法是一样的，因此在应用上还是和原有的RSA 算法是相同的，所以N 重RSA 算法是否等同于大数分解依然不能得到理论上的证明。在N重RSA算法中,传送保密信息的主要工作密钥参数p1, p2……pn, ex, dx,都具有一次使用的特征,即每次通信使用到的这些工作密钥参数都在随机变化。在某种意义上,它接近于一次一密的密码体制[6],显然它的保密性要远优于工作密钥在一个较长时间内固定不变的原有的RSA 算法。并且减少了每一个随机产生素数的位数，因此也在一定义以上加快了RSA 算法计算机实现的效率问题。但是由于在几个小素数相乘后得到的还是一个较大的数，所以还是没有从根本上解决RSA 算法基本只用于较少的数字加密，例如数字签名上的问题。