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

摘要：首先利用RSA加密算法对数据进行加密和解密，实现了数据的安全传输;然后针对RSA加密算法时间开销大和算法设计复杂的缺点，提出基于乘同余对称特性的SNM算法。通过对该改进RSA加密算法的实现发现加密运算速度明显提高且算法更简单，从而证明了本文所提改进算法的有效性。

0 引言

在当今信息社会中，每天都有大量的加密信息在传输、交换、存储和处理，一旦密码遭到破解就可能造成信息的丢失、篡改、伪造、假冒以及系统遭受破坏等严重后果，因此，如何保证信息的安全传输成为当前信息传输领域的热点问题。W.Diffie和M.E.Hellmam在1976年发表了具有划时代意义的“密码学的新方向”一文，提出了公钥密码体制思想，克服了传统对称密码体制的缺点，为近代密码学的发展指明了方向。它的出现是密码学研究领域中的一项重大突破，也是现代密码学诞生的标志之一。

本文首先对非对称加密算法RSA的原理和优点进行研究，然后实现其加密、解密功能。RSA算法在公钥密码体制中占有重要的地位。但该算法所采用的幂乘计算耗时太多，一直是制约其广泛应用的瓶颈。因此，为了提高加密和解密速度，本文提出一种新型的加密算法即基于乘同余对称特性的SMM算法。该算法采用简单的迭代来实现，不需要幂乘和乘法逆运算，从而在提高加密解密的速度同时也使得程序设计更简洁紧凑。

1 RSA加密算法原理

RSA加密算法的理论基础是一种特殊的可逆模指数运算，其算法描述如下：

(1)选择两个互异的大质数p和q(p和q必须保密，一般取1024位)。

(2)计算出n=p q，φ(n)=(p-1)(q-1)。

(3)选择一个比n小且与φ(n)互质(没有公因子)的数e。

(4)找出一个d，使得ed-1能够被φ(n)整除。其中，ed=1 mod(p-1)(q-1)。

(5)RSA是一种分组密码系统，所以公开密钥=(n，e)，私有密钥=(n，d)。

其中，n为模数，通信双方都必须知道，e为加密运算的指数，发送方需要知道，d为解密运算的指数，只有接受方才能知道。

将以上过程进一步描述如下：

公开密钥：n=pq(p，q分别为两个互异的大素数)，e与(p-1)(q-1)互质。

私有密钥：d=e-1{mod(p-1)(q-1)}。

加密：C=Me mod n，其中M为明文，C为密文。

解密：M=Cd(mod n)。

若要破译密码必须知道p，q，即对n作素因子分解，这在数学上是非常困难的。

2 RSA加密算法的实现

2.1 算法设计流程

RSA算法设计流程如图1所示，主要采用下述加密/解密变换。

(1)密钥的产生

a.选择两个保密的大素数p和q。

b.计算n=p q，φ(n)=(p-1)(q-1)，其中φ(n)是n的欧拉函数值。

c.选择一个整数e，满足1

d.计算私钥d，满足d=l(modφ(n))/e，d是e在模φ(n)下的乘法逆元。

e.以(e，n)为公钥，(d，n)为密钥，销毁P，q，φ(n)。

(2)加密

加密时首先将明文比特串进行分组，使得每个分组对应的串在数值上小于N，即分组的二进制长度小于1 092 N。然后，对每个明文分组M，作加密运算。

加密：C=Me(modn)，其中M为明文，C为密文。

(3)解密

对密文分组的解密运算为：M=Cd(modn)。

2.2 RSA加密算法的实现

(1) 生成密钥

随机选择两个大素数p和q，如果p和q足够大，那么n=p q就会变的很大，在理论上因式分解一个大数并准确地分解出p和q是很难实现的。本文随机选择P和q为61和67。根据φ(n)=(p-1)(q-1)可得n的欧拉函数值φ(n)为3960，如图2所示。

随机数e的选取要满足随机数和欧拉函数最大公约数gcd(eφ(n))=1这个条件。如果e比较大，加、解密速度变慢，也不便于存储，但是太小的e会导致安全性问题。所以限定1

(2)加密

输入明文，根据公钥(e，n)和公式C=Me(modn)可得密文。本文选择要加密的明文为1234，由公式可得密文为2793。根据计算结果可知此加密算法加密所用的时间为2.667 ms。

(3)解密

输入3调用第三个模块来实现解密功能。RSA加密算法解密所需要的条件是知道密文和私钥，根据M=Cd(modn)可得到明文。由计算得到密文为2793，私钥为233，所以可解的密文为1234，从而实现了解密功能。

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

大整数因子分解问题向来被数学界视为世界性难题。正是基于这一点，RSA公钥密码体制才能够以其较高的安全性为人们广泛接受。但是RSA公钥密码体制也存在诸多不足之处：加解密算法中涉及大量的数值计算问题导致计算时间开销较大，在一定程度上限制了其应用范围。且密钥的产生受到素数产生技术的限制，因而很难做到一次一密。为保证安全性必须选取1024 bits或以上，但这就使得运算速度较慢，而且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化，致使其实现的难度增大，实用性