基于RSA算法的分析和研究

王方鑫

摘要：RSA算法是世界上目前应用范围最为广泛的公钥加密体制。它的安全性基于大素数分解的困难性。该文对RSA算法中密钥的生成及其加密解密的原理进行了分析和讨论。

关键词：RSA；公钥加密体制；加密；解密

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）26-0030-02

随着科学技术的进步和发展，信息保密和存储安全问题越来越重要。无论是个人信息的保密还是网络信息存储的安全，都依赖于信息安全技术。其中，信息安全技术的核心又是密码学技术，它是现代化发展的重要环节。

本文对RSA算法进行了简单的介绍，给出了RSA算法加密、解密、密钥生成的流程，并对RSA的安全性进行了分析。

1 RSA算法简介

1976年，两名美国的计算机学家提出Diffie和Hellman提出公钥密码体制的设想，可以在不直接传递密钥的情况下，实现解密。随后在1977年，三位美国的数学家Rivest、Shamir和Adleman联合提出了RSA公钥加密体制。

RSA算法是世界上第一个实用的公开密钥的算法。它的安全性依赖于大整数因子分解的困难性，大整数因子分解问题是世界性的数学难题，一直到现在都没有解决方案，也因此保证了RSA算法的安全性。目前而言，密钥长度为1024位的RSA算法被认为是安全的。

2 RSA算法步骤

2.1 RSA密钥生成算法

1） 选取两个大素数[r]和[q]

2） 计算[n=p·q] ，[?n=p-1?q-1]

3） 随机选取整数[e]，满足[gcd（e，?（n））]=1

4） 计算[d]，满足[d*e=1mod ?n] ，其中[e]和[n]是公钥，[d]是私钥

2.2 加密算法和解密算法

加密算法：[c=Em=memod n]

解密算法：[m=Dc=cdmod n]

2.3 RSA密码体制总结

表1为RSA密码体制。

3 [RSA]算法的安全性

3.1 针对[n] 分解的攻击

这种攻击理论的原理在于，若p 和q 已知，则[?n=p-1q-1]就可以计算出来。而同时公钥d和私钥e满足[d*e=1mod ?n]，于是可以求出私钥d。从中我们可以看出，RSA算法的安全性依赖于大整数分解的困难性，而大整数分解至今为止都没有很好的解决办法。因此我们认为密钥长度大于1024位比特的RSA算法是安全的。

3.2 二次筛因子分解法

这种攻击理论的原理基于著名的费马因子分解：找出正整数[x、y]，使得 [x2≡y2]，即存在整数c满足[cn=x2-y2=x-yx+y]，并且满足[x≠±ymod n]，因此[n]是数[x2-y2=x-yx+y] 的因子，故[gcdx+y，n]或者[gcdx-y，n]均为n的因子，于是可以将n分解。

随着近些年科学技术的发展，尤其是网络上的分布式计算加快了因子分解的速度，表2给出近些年来实现的因子分解位数的记录。

3.3 侧信道攻击

这种攻击方式主要是通过对信息的加密、解密软件进行分析，通过收集和分析加密和解密的时间，电源的消耗，发出的噪声，发出的热量等来对数据进行推测，来分析出算法的执行流程和步骤，从而攻克该密码体制。这种攻击方法所需要的设备成本低、攻击效果显著，严重威胁了密码设备的安全性。

4 RSA算法的优缺点

4.1 RSA算法的优点

1） RSA 是高强度非对称加密系统，密钥长度少则512位，多则2048位，非常难破解，至今尚未有人能破解超过1024位以上的RSA。

2） RSA算法实现比较简单，易于理解和接受。

4.2 RSA算法的缺点

1） 产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。

2） 安全性， RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。目前，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击RSA的方法，如选择密文攻击，一般攻击者是将某一信息作一下伪装（Blind），让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。

3） 速度太慢，由于RSA 的分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。SET（Secure Electronic Transaction）协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。

5 结束语

RSA算法是一种安全性非常高的算法，人们对RSA算法进行了很长时间的研究，却依旧很难完全攻克RSA算法，这也从侧面证实了其安全性。与此同时，RSA算法易于理解并且方便硬件的实现，随着时间的推移，逐步被人们认可和接受，也被很多人推崇为最优秀的公钥算法之一。但是，RSA算法也存在着一定的缺陷，它的运行速度比较慢。RSA算法和一些对称密码算法相比，运行的速度误差了几个数量级。并且随着人们对大数分解问题研究的逐步深入，RSA算法的分组长度和密钥长度很有可能会继续的增加，从而更加影响它的运行性能。因此，对RSA的进一步研究和分析是很有意义的，RSA算法具有良好的应用背景和发展前途。

参考文献：

[1] 谷利泽，郑世慧，杨义先.现代密码学教程[M].北京邮电大学出版社，2009.

[2] 卢开澄.计算机密码学[M].北京：清華大学出版社，2003.

[3] 杨晓元.现代密码学[M].西安：西安电子科技大学出版社，2009.

[4] 杨波.现代密码学：第二版[M].北京：清华大学出版社，2007.

[通联编辑：代影]