龙源期刊网 http://www.qikan.com.cn
RSA算法的应用与实现
作者：白晓 蔡贵荣
来源：《科技视界》2013年第31期
【摘 要】RSA 算法是使用最广泛的一种非对称密码体制. 在对RSA 算法的原理、算法描述等进行研究的基础上，近一步研究了RSA 算法在数字签名、密钥交换等方面的应用. 最后在.NET平台中使用C#语言进行编程，实现RSA数字签名算法。 【关键词】RSA算法；数字签名；加密；解密 1 RSA简述
随着IT技术迅猛的发展，各个行业的信息化、网络化的增强，信息的安全性越来越得到人们的重视。一个完整的、先进的信息系统无不考虑到信息安全技术的应用。
RSA加密体制是一种公开的密码体制。RSA公匙密码体制是又R.L.Rivest，A.Shamir和L.Adelman于1978年提出的。RSA算法完善，既可用于加密，又可用于签名，并为用户的公开密钥签发公钥证书、发放证书、管理证书等提高了服务质量，RSA公钥密码体制在世界许多地方已经成为事实上的标准。
RSA是一个基于数论的非对称密码体制，是一种分组密码体制，是一种基于因子分解的指数函数作为单向陷门函数的公钥体制算法。它基础是数论的欧拉定理，素数检测，它的安全性是基于大数分解，后者在数学上是一个困难问题。 2 RSA算法 2.1 RSA算法描述
RSA的安全性基于复杂性理论中的计算安全性，依赖于大整数分解这一NP难题。可靠性与所用密钥的长度有很大关系，假如有人找到一种很快的分解因子的算法，即从一个公钥中通过因数分解得到私钥，那么用RSA加密的信息的可靠性肯定会极度下降。但由于其工作量巨大，按目前计算机的处理能力是不可能实现的。实践证明，在当前的技术和方法下，密钥不小于1024 bit的RSA算法仍然是安全的。这充分说明RSA系统具有良好的保密性能。 因此，尽管先后出现了很多新的公钥体制算法，但RSA仍然在不同应用领域占据了重要的位置。随着计算机运算速度的提高以及因子分解算法的突破，RSA的密钥长度将越来越大，其软硬件实现速度将成为制约其使用的重要因素。 RSA系统由以下几部分组成[1]：
龙源期刊网 http://www.qikan.com.cn
1）随机选取的在素数P和Q，还有N ，其中N=P*Q，P和Q保密，N公开。 2）任取Φ（n）=（P-1）*（Q-1），其中（n）表示比n小的素数的个数，任取2 3）计算d，使e*d=1（mod （n）），称d为e对模（n）的逆，其中d为解密秘钥，保密。在RSA系统中，设m为明文，且明文块的数值大于n，c为密文，则其加密和解密算法为：加密算法C=E（m）=m^e（mod n）解密算法 m=D（c）=c^d（mod n）
在RSA系统中（e，n）构成加密秘钥，即公钥，（d，n）构成解密秘钥，即私钥。 2.2 RSA安全性的分析
在公布RSA算法之后，在使用RSA密码体制和分析RSA算法发现了一系列的算法本身脆弱性及其存在的问题。
1）RSA公钥密码体制在加密或解密中涉及大量的数值计算，其加密和解密的运算时间比较长，以致于实际使用RSA密码体制无法应用到软件产品，必须用超大规模集成电路的硬件产品。
2）虽然提高N位数会大大提高RSA密码体制的安全性，但其计算量呈指数增长，以致使其实现的难度增大，实用性降低。
3）RSA公钥密码体制的算法完整性（指密钥控制加密或解密变换的唯一性）和安全性（指密码算法除密钥本身外，不应该存在其它可破译密码体制的可能性）沿有等进一步完善。 4）RSA算法面临着数学方法的进步和计算机技术飞跃发展带来的破译密码能力日趋增强的严重挑战。RSA公开密钥密码算法在信息交换过程中使用比较广泛，安全性比较高。以当前的计算机水平，如选择1024位长的密钥（相当于300位十进制数字）就认为是无法攻破的。
3 基于RSA的数字签名[2] 3.1 RSA数字签名算法描述
RSA是目前使用最为广泛、最著名的公开密钥系统，它是由麻省理工学院的三位学者Rivest、Shamir和Adleman于1978年提出的。RSA密码系统可以完成数据加密、数字签名以及密钥交换等功能，其安全性是建立在大素数因子分解困难问题上的[3]。
设n=pq，p、q是两个大素数，消息空间和签名空间为P=A=Zn，定义K={（n，p，q，a，b）ln=pq，p，q为素数，ab=l（modφ（n））}。值n和b公开的，p、q、a是保密的。对K=（n，p，q，a，b），签名及验证算法定义如下：
龙源期刊网 http://www.qikan.com.cn
签名算法： 验证算法：
如果B使用RSA解密规则Dk签一个消息x，那么B是能产生签名的唯一的人，这是因为Dk是保密的。验证算法使用RSA的加密规则Ek，因为Ek是公开的，保存在公开的信任机构服务器中，所以任何人能验证一个签名。 3.2 RSA数字签名算法实现步骤
3.2.1 签名算法（包括两步：消息摘要计算，RSA加密）
1）消息摘要MD的计算：消息在签名前首先通过MD5计算，生成128位的消息摘要；MD5函数是一种单向散列函数，它将任意长度的消息压缩成128位的消息摘要。应用MD5的单向性（即给定散列值，计算消息很难）和抗碰撞性（即给定消息M，要找到另一消息M’并满足两者的散列值很难），可以实现信息的完整性检验。另外该函数的设计不基于任何假设和密码体制而直接构造，执行的速度快，是一种被广泛认可的单向散列算法。
2）对MD作RSA加密算法：采用签名者的私钥加密消息摘要，得到加密后的字符串即数字签名；
3.2.2 验证签名算法（RSA解密、对消息摘要计算和比较）
验证签名算法包括两步：RSA解密得签名者的消息摘要，验证者对原消息计算摘要，比较两个消息摘要。验证签名的过程输入为消息，签名者的公钥，签名；输出为验证的结果，即是否是正确的签名。
1）RSA解密：签名实际是加密的消息摘要，用以上所述的RSA解密方法采用签名者的公钥对这个加密的消息摘要解密，解密的结果应为128位的消息摘要。
2）消息摘要计算和比较：验证者对消息用MD5算法重新计算，得到验证者自己的消息摘要。验证者比较解密得到的消息摘要和自己的消息摘要，如果两者相同，则验证成功，可以确认消息的完整性及签名确实为签名者的；否则，验证失败，确认签名被冒充或是被篡改。 3.3 RSA数字签名方案的弱点
1）随着计算机速度的提高，以及集群计算技术的应用，RSA算法已经不足够安全，对RSA的破解也成为可能。RSA算法运行中所需要的密钥长度变得越来越大，使其计算量也猛增。经过实验得到，密钥长度为1024位至2048位是比较合理的，既可以保证系统的安全性，计算量又可以接受。然而密钥长度的猛增，对RSA的应用带来严重的负面影响，使其应用范围越来越受到制约。