毕业设计（论文）RSA加密算法的研究与实现

1、rsa加密算法的研究与实现摘 要 在新信息时代，信息的保密尤为重要。公钥密码学的出现对现代保密体系起到了十分重要的作用，其中rsa算法是目前在理论和实际应用中最为成熟和完善的一种公钥密码体制。它运用最多的地方是加密，还可用来进行身份验证和数字签名，是一种典型的公钥密码体制。本文给出了rsa运算中的模幂乘速度上的改进，对rsa加解密变换、身份验证的基本原理进行了相应的分析，分析了当前针对rsa算法的攻击手段，归纳出提高rsa算法安全性应该考虑的几个因素。此外，论文还通过实验方式对改进的rsa算法进行了验证，通过比对，得出改进的算法比原有算法在效率上有一定程度提高的结论。论文还设计了一个加解密程序

2、，并对其进行了验证。关键词 rsa，密码学，算法研究abstractin the new information age, information confidential is particularly important.the emergence of modern public key cryptography to confidentiality system plays a very important role,including rsa algorithms are currently in theory and practical application of the mos

3、t mature and perfect a public key cryptosystems.it utilizes most place is encrypted,also can be used for identity authentication and digital signature,is a kind of typical public key cryptosystems. this paper gives the mould by rsa operation speed of the power of rsa encryption improvement,transform

4、,the basic principle of identity check the corresponding analysis,this article analyses the current according to the rsa algorithms attack methods, concludes improve safety should consider rsa algorithms of several factors.in addition,this paper also through experiments to improve rsa algorithms way

5、 is verified by comparing,concluded that the improved algorithm on efficiency than the original algorithm with a certain degree increase conclusion. this paper also designed a gal declassification procedures, and analyses the verification. keywords：rsa,cryptography,algorithms第一章 绪论11.1 问题的提出11.2 密码学

6、概述31.3 国内外研究现状与水平及其意义5第二章 rsa算法62.1 rsa算法62.2 rsa签名算法6第三章 rsa的安全性83.1 rsa参数选择83.2 rsa的安全性分析10第四章 rsa算法的研究124.1 rsa算法实现124.2 rsa改进算法134.3 结果分析16第五章 文件加密的设计175.1分析和设计175.2 对txt文本加解密19总 结22参考文献：23致 谢24第一章 绪论随着时代在进步，科技的发展。计算机的应用已经普遍化，网络达到了全球化。人与人之间交流不再有地域的限制，此外许多交往活动，包括商业贸易、金融财务和其他经济活动中，不少已以数字化信息的方式在网上流

7、动着，电子商业、电子银行和电子货币的研究、实施和标准化也已经形成了一定的规模。在生活中，人们常会遇到需要签字或者盖章的文件，比如支票、存折、法律文件、订单、合约、遗嘱、契约等等。现在，这些传统的基于纸面的重要凭据已经逐渐发展成数字电子媒体的形式。这一发展给人们带了的便利是不可估量的，让人看到了这一技术前景的辉煌。这一技术不仅对个人产生了重大影响，而且对于当代社会的经济、文化、金融等方面也产生了深刻的影响。1.1 问题的提出当代社会，各方面的信息都逐渐在向网络方面转化。那么随之而来的便出现了信息的安全问题：在信息的产生、传递、保存和验证等方面出现了很多问题和困难。那么怎样才能保证信息不被偷取、伪

8、造和篡改，如何来确认信息发送者的可靠性和真实性，如何找回丢失的信息，又如何使信息发送人无法抵赖等，这些都是当今社会信息传递所迫切的技术需求。对于那些机密文件的传送这就要求有更高的保密措施。网络的安全是指通过采用各种技术和管理措施，使网络系统正常运行，从而确保网络数据的可用性、完整性和保密性。网络安全从其本质上来讲就是网络上的信息安全。从广义来说，凡是涉及到网络上信息的保密性、完整性、可用性、真实性和可控性的相关技术和理论都是网络安全的研究领域。网络安全是一门涉及计算机科学、网络技术、通信技术、密码技术、信息安全技术、应用数学、数论、信息论等多种学科的综合性学科。信息安全技术包括多个方面，其核心

9、技术是加密技术。保护网络信息安全的方法一般分两大类：一是防火墙技术；二是数据加密技术。“防火墙”是一种形象的说法，其实它是一种计算机硬件和软件的组合，使互联网与内部网之间建立起一个安全网关，从而保护内部网免受非法用户的侵入。可以这样说，防火墙是网络信息安全的第一道屏障，选择一款合适的防火墙可在一定程度上对信息安全起到一定的保护作用。数据加密技术是与“防火墙”配合使用的安全技术。数据加密技术是为提高信息系统及数据的安全性和保密性，防止秘密数据被外部破析所采用的主要技术手段之一。随着信息技术的发展，网络安全与信息保密日益引起人们的关注。目前各国除了从法律上、管理上加强数据的安全保护外，从技术上分别

10、在软件和硬件两方面采取措施，推动着数据加密技术和物理防范技术的不断发展。按作用不同，数据加密技术主要分为数据传输、数据储存、数据完整性的鉴别以及密钥管理技术4种。现在为了保障信息安全，实际上就是数据加密，但关键在于要有一合适的加密算法，可以实现加密和解密的功能，并且要便于处理。那么，对密码算法的选择也就十分必要。rsa算法是一种常用的数据加密算法，易于理解和操作，从提出到现在已有二十多年，经历了各种攻击的考验，得到了人们的认可。它现在被应用在了各种安全和认证领域，得到了人们的一致好评。但rsa算法存在速度上的缺陷，限制其进一步发展。所以，如何提高rsa的效率也就成为了现阶段值得我们研究的一个课

11、题。当代社会网络无处不在，那么它的安全就会成为人们所关注点焦点，它现在的稳定发展可以给它进一步发展打下了良好的基础。网络安全不是绝对的，为了确保它的安全就需要不断的完善系统程序、加强保密技术。1.2 密码学概述密码学的历史极为久远，其起源可以追溯到远古时代，人类有记载的通信密码始于公元前400年【1】。密码学的一些常用基本概念有【2-5】：密码学是研究信息系统安全保密的科学，它包括两个分支，密码编码学和密码分析学；密码编码学是对信息进行编码实现信息隐蔽的技术和科学；密码分析学是研究分析破译密码的技术和科学；明文是指发送方想要发给接受方的消息；密文是指明文被加密后的消息；加密是将明文变换为密文的

12、过程；解密是将密文恢复为明文的过程。密码是实现秘密通讯的主要手段，是隐蔽语言、文字、图像的特种符号。凡是用特种符号按照通讯双方约定的方法把电文的原形隐蔽起来，不为第三者所识别的通讯方式称为密码通讯。在计算机通讯中，采用密码技术将信息隐蔽起来，再将隐蔽后的信息传输出去，使信息在传输过程中即使被窃取或截获，窃取者也不能了解信息的内容，从而保证信息传输的安全。近三十年来，密码学已成为一门热门的学科，在理论和方法上都有了巨大的发展。1949年香农(shannon)发表“保密系统的信息理论”【6】；1975年3月公开发表des算法(digital ep standard，数据加密标准)【7】，1977年

13、美国国家标准局宣布des可用于非国家保密机关，正式作为商用加密算法的标准；1976年由diffie和hellman在所谓“密码学的新方向”【8】一文中提出了公钥密码体制的思想，在此基础上1978年由rlrivest，ashamir和ladleman【9】提出并实现了rsa公钥密码系统，该系统己成为事实上的工业标准；随后des也改进为3des；1985年由nkobliz和vmiller把椭圆曲线密码(elliptic curves cryptography，简称ecc)理论应用到公钥密码系统中提出ecc算法；2000年10月2日美国国家标准与技术研究所确定用比利时密码学家joan daemen，

14、vincent rijmen发明的rijndael算法替代des算法，称为aes算法【10】；1990年我国学者来学嘉与瑞士密码学家james massey提出了著名的idea算法。同时还有许多新的加密方法，如用于电子邮件加密的pem(privacy enhanced mail)和pgp(pretty goodprivacy)；在网络系统中得到应用的加密算法还有美国国家标准局提出的dsa算法(digital signature algorithm)和标准局建议的可靠不可逆加密标准(shssurehash standard)以及数字签名中使用的sha.1等算法。根据加密密钥和解密密钥是否相同或者

15、本质上等同，可将现有的加密体制分为两种。一种是单钥加密体制(也叫对称加密密码体制)，即从其中一个容易推出另一个，其典型代表是美国的数据加密标准des(data ep standard)；另一种是公钥密码体制(也叫非对称加密密码体制)，其典型代表是rsa密码体制pj，其他比较重要的还有mceliece算法【11】、merkehellman背包算法【12】、椭圆曲线密码算法【2】和e1gamal算法【13】等。1.3 国内外研究现状与水平及其意义自从1976年公钥密码的思想提出以来，国际上已经提出了许多种公钥密码体制，其中rsa就是现在比较常用的一种，是1987年r.l.rivest，ashami

16、r和ladleman三人在文章实现数字签名和公钥密码体制的一种方法中共同提出了的rsa公钥密码体制，是最具代表性的公钥密码体制。由于算法既可用于数据加密，又可用于数字签名，安全性良好，易于实现和理解，rsa已成为一种应用极广的公钥密码体制，它的提出真正使得互不相识的通信双方在一个不安全的信道上进行安全通信最终成为可能。在广泛的应用中，不仅它的实现技术日趋成熟，而且安全性也逐渐得到事实的证明，因此人们对rsa十分重视。但在实现过程中，由于算法中包含有大数的乘方运算，在计算机上运算时，会耗费大量的时间，严重影响了rsa的加密效率，制约了它的应用。对于如何提高rsa的运算速度，这是现在研究rsa算法

17、的一个重点，也是现阶段人们讨论较多的一个话题。 加快rsa算法的计算速度，这是很有现实意义的。第二章 rsa算法2.1 rsa算法rsa算法采用下述加密解密变换。1密钥的产生（1）选择两个保密的大素数p和q。（2）计算n=pq，=(p一1)(q一1)，其中是n的欧拉函数值。（3）选择一个整数e，满足le，且gcd(，e)=1。（4）计算私钥d(解密密钥)，满足ed1mod ，d是e在模下的乘法逆元，因e与互素，由模运算可知，它的乘法逆元一定存在；（5）以e,n为公开钥，d，n为秘密钥。2加密加密时首先将明文比特串进行分组，使得每个分组对应的十进制数小于n，即分组的二进制长度小于log2n。然后

18、，对每个明文分组m，作加密运算：cmemod n3解密对密文分组的解密运算为：mcdmod n2.2 rsa签名算法并非所有的公开密钥系统，均可同时达到秘密性与数字签名功能。一般而言，一公开密钥系统若作为密码系统，则无法作为数字签名，反之亦然。只有很少数系统可同时作为密码系统和数字签名，如本文讨论的rsa系统【14】。rsa签名算法如下【5，15】：设n=pq，且p和q是两个大素数，e和d满足edl(mod )。公开密钥：n，e私有密钥：d签名过程：发送方使用自己的私钥d对明文x进行数字签名变换：y=xd mod n；并将加密后的消息和签名y发送给接收方；验证过程：接收方使用发送方的公钥e对收

19、到的消息y进行数字签名验证变换x=yemod n，并使用发送方的密钥解密恢复消息x，比较一与x，如果x=x则证实发送方的身份合法。这样，用户a若想用rsa签名方案对消息x签名，他只需公开他的公钥n和e，由于签名算法是保密的，因此a是唯一能产生签名的人，任何要验证用户a签名的用户只需查到a的公钥即可验证签名。对于实现签名和公钥加密的组合，常用方法是：假定通信双方为a和b。对于明文x，a计算他的签名y=xd mod n，然后利用b的公开加密函数eb。对信息对(x，y)加密得到z，将密文z传送给b，当b收到密文z后，他首先用他的解密函数db占来解密得到(x，y)=db(z)=db(eb(x，y)，然

20、后利用a的验证算法来检查x=x=ye mod n是否成立。第三章 rsa的安全性3.1 rsa参数选择根据rsa算法的加解密过程，其主要的参数有三个：模数n，加密密钥e和解密密钥d。（1）n的选取rsa算法中，n是由p和q两个大素数相乘得出的，之后再通过运算的得到密钥对。那么，模数n的分解就是最直接、最显然的攻击方法。如果n被分解那么信息将被窃取，这是显然的。所以，选择一个合适的模数n是十分必要的。一般的，模数n的确定有以下几条原则【16】：p和q之差要大。当p和q相差很小时，在已知n的情况下，可假定二者的平均值为，然后利用（）-n=（），若等式右边可开方，则得到和即n被分解。p-l和q-1的

21、最大公因子应很小。p和q必须为强素数。一素数p如果满足条件一：存在两个大素数p1，p2，使得p1/p-1且p2/p+l；条件二：存在四个大素数r1，r2，s1，s2，使得r1/p1-1，s1/p1+1,r2/p2-1,s2/p2+1。则此素数为强素数。其中r1,r2,s1,s2称为3级的素数，p1,p2称为2级的素数，p则称为1级的素数，很明显地，任何素数均为3级的素数。只有两个强素数的积所构成的n，其因子分解才是较难的数学问题。p和q应大到使得因子分解n为计算上不可能。rsa的安全性依赖于大数的因子分解，若能因子分解模数n，则rsa即被攻破，因此模数n必须足够大直至因子分解n在计算上不可行。

22、因子分解问题为密码学最基本的难题之一，如今，因子分解的算法已有长足的进步，但仍不足以说明rsa可破解。为保证安全性，实际应用中所选择的素数p和q至少应该为300位以上的二进制数，相应的模数n将是600位以上的二进制数。目前，set(secure electronic transaction)协议中要求ca采用2048比特长的密钥，其他实体使用1024比特的密钥。随着计算能力的提高和分布式运算的发展，安全密钥的长度将是动态增长的。(2)e的选取由rsa算法可知，e和互素的条件容易满足，若选取较小的e，则就加快了加解密运算速度，同时也易储存，但安全性不高。 一般地，e有以下选取原则：e不能够太小。

23、在rsa系统中，每人的公开密钥e只要满足gcd (e，)1即可，也即e可以任意选择，为了减少加密运算时间，很多人采用尽可能小的e值，如5。但已经证明低指数将会导致安全问题【17】，因此，一般选择e为16位的素数，可以有效防止攻击，又有较快速度。应使e在mod的阶为最大。即存在i，使得ei 1(mod)，i(p-1)(q-1)/2，可以有效抗击攻击。（3）d的选取原则私密密钥d不能太小，一般要大于【17】。这是因为：若d的长度太小，则可以利用已知明文m加密后得c=me mod n，再直接猜测d，求出cd mod n是否等于m。若是，则d就是解密密钥，否则继续猜测。若d的长度过小，则猜测的空间变小

24、，猜中的可能性加大，已有证明当d时，可以由连分式算法在多项式时间内求出d值。因此其长度不能过小。3.2 rsa的安全性分析对rsa算法的攻击主要有以下几种：（1）对分解模数n的攻击最直接、最显然的攻击目标是模数n，但也是最困难的。攻击者可以合法的获得公开密钥e和模数n；如果n=pq被因式分解，则攻击者通过p，q便可计算出=(p1)(q1)，再由edl(mod)得到解密密钥d，明文也就不再保密。 （2）共模攻击【18】在实现rsa时，为了方便，可能给每一用户相同的模数n，虽然加解密密钥不同，但这样做是不行的。设明文是m，两个用户公开钥分别是e1和e2，且二者互素，则两个密文是：c1me mod

25、nc2me mod n若获取c1，c2，则用推广的euclid算法可求出满足re1+se2=1的两整数r和s，其中一个为负，设为s。再由euclid得c1-1，则可得（c1-1）-rc2sm mod n。即密码分析者知n，e1，e2，c1，c2，就可得出m。（3）低指数攻击在现实中，用户为了快速实现加密和验证签名的速度，选择较小的公开钥e和解密钥d。但e，d太小就易受到低指数攻击，即低加密指数攻击和低解密指数攻击。通过独立随机数字对明文消息x进行填充，这样使得xe(mod n)xe，可以有效地抗击小指数攻击。第四章 rsa算法的研究4.1 rsa算法实现用rsa算法对0-9这十个数进行加解密：

26、先分别定义两个素数p和q，之后得出加密密钥e和解密密钥d，再进行加解密运算。加解密过程如下所示：令p=3，q=5，通过rsa算法得出加密密钥e=3和解密密钥d=3，之后对0-9这十个书进行加解密，主要程序及结果如下：主要程序对0-9进行加密和解密for(j=0;j10;j+)a=j; m=1;for(i=1;i=e;i+)m=m*a;c=m%r; printf(明文a=%d,a); printf(密文c=%d,c);n=1;for(i=1;i=d;i+) n=c*n;g=n%r;printf(解密 g=%dn,g);得出结果如图4-1所示：图 4-14.2 rsa改进算法加解密速度慢是rsa算

27、法显著的缺陷【19】。设m为明文m（m1，m2，m3，mk），相应c为密文c（c1，c2，c3，ck），则按照rsa算法，有 加密运算cimiemod n， i1，2，3，k解密运算micidmod n， i1，2，3，k由上可得，加、解密都需要执行k 次幂剩余运算。为了提高运算速度，也就是要尽可能地减少幂剩余运算的次数，可以用加法剩余运算。改进的rsa 算法如下：加密运算cjmj+mj-1（mod n），jk，k-1，k-2，2c1m1e （mod n）解密运算m1c1d （mod n）mjcj-mj-1 （mod n），j2，3，4，k改进算法实现加密运算：令p=3，q=5，得出e=3 i

28、nt c100； /存放明文的数组，最后输出printf（plase input the mdata k：）； /输入需加密的字符数量（不大于100）scanf（%d，&k）；printf（plase input the m： ）； /输入需加密的明文数据（字符串）for（i=0；i=1；i-） /加密mk，mk-1，m2ci=（mi+mi-1）%n；c0=1；for（j=1；j=e；j+） /计算c1m1e （mod n）c0=（c0*m0）%n；printf（the encryption c is：n）；for（int j=0；jk；j+） /输出加密后的密文printf（%dn，cj）；

29、得出的结果如下图4-2：图 4-2解密运算：p=3，q=5，d=3printf(请输入要解密的字符数kn);scanf(%d,&k);printf(输入要解密的密文数据n);for(j=0;jk;j+)scanf(%d,&cj);m0=1;for(j=1;j=d;j+)/计算m1c1d（mod n）m0=m0*c0;m0=m0%n;for(i=1;ik;i+)/解密c2，c3ckmi=(ci-mi-1)%n;for(j=0;jk;j+)/输出解密后的明文printf(明文为：%dn,mj);得出的结果如下图4-3图 4-34.3 结果分析通过比较改进前与改进后的rsa算法，可知，改进后的rsa

30、算法加密和解密都只需要执行1 次幂剩余运算和k-1次加法剩余运算。而一次加法剩余运算比一次幂剩余运算的速度至少要快mimin（e，d）倍。因此，改进的rsa算法比没有改进的rsa算法运算速度至少要快（k-1）mimin（e，d）=33=27倍。k、m、min（e，d）越大，运算速度提高了越显著。然而，安全性与没有改进前的rsa算法一样高。第五章 文件加密的设计5.1分析和设计1.分析和设计（1）生成两个大素数首先，产生随机数；其次，规定随机数的长度；最后，对随机数进行是否是素数的判断。（2） 用产生的素数生成密钥对。知道了两个素数，可以根据rsa算法分别计算出合适的加密密钥e和解密密钥d。（3

31、） 根据密钥对对txt文本进行加解密，并得到相应的密文和明文。使用方法：在软件中运行程序，按生成的窗口所显示的内容操作即可。加解密流程示意图5-1开始产生随机数并判断是否是素数生成密钥对需要加密文件的路径对文件内容加密生成密文解密回复文件原内容结束图5-12.运行环境和所用工具运行采用的硬件环境为pc机，主要配置：处理器 intel(r) core(tm)2 duo cpu t6400 2.00ghz 2.00ghz，内存 2.00gb，硬盘200g；软件环境为windows vista。所用工具：microsoft visual c+ 6.05.2 对txt文本加解密1.运行程序得出结果如图

32、5-2图5-22.输入r：随机素数和密钥对如图5-3图5-33.输入e：输入加密的文件路径对其加密如图5-4图5-44.输入d：输入解密文件路径对其解密如图5-5图5-55.退出输入q即可经多次测试，加解密可行，达到所要的目的。该设计现在只能对txt文本进行加解密，对于其他文件还未能进行加解密的操作。总 结（1）论文主要做了几个方面的介绍：1.对密码学、信息安全做了简要的概述，介绍了当今密码学的基本动态，阐述了目前rsa加密体制的现状和不足，列举了rsa加密体制中所采用的主要实现算法。2.对rsa算法做了简单的分析，分析了rsa实现加解密变换、数字签名的过程。结合当前针对rsa算法的攻击手段与

33、对策，归纳总结了提高其安全性的原则。3.用rsa算法对txt文本做了加解密实现，并做了验证。本文的设计只能是对于txt文本，对于其他文件还不能实现加密解密，这是要进一步改进的。（2） rsa算法存在有明显的缺点：1. 大素数的产生是一个难点，产生密钥对也就相对比较困难2.速度太慢，由于rsa的分组长度太大，为保证安全性，n至少也要600位以上二进制数，使运算代价很高，尤其是速度较慢；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。参考文献：【l】李红军，缪旭东数据加密在网络安全中的应用微型机与应用，2002(10)：31-33【2】施奈尔应用密码学(第二版)北京：机械工业出

34、版社，2000【3】王育民，刘建伟通信网的安全西安：西安电子科技大学出版社，1999【4】冯登国，裴定一密码学导引北京：科学出版社，1999【5】douglas r stinson著，冯登国译密码学原理与实践(第二版)北京：电子工业出版社，2003【6】c e shannoncommunication theory of secrecy systemsbell systems technical jounral，1949，(28)，656-719【7】data ep standard(des)federal information processing standard publication

35、 46，1977【8】whitfield diffie，martine e hellmannew directions incryptographyieee transactions on informationtheory，1976，it22(6)：644-654【9】r lrivest，a shamir，and ladlemana method for obtaining digital signatures and publickey cryptosystem，communications of the acm，1978，21(2)：120126【10】j nechaev，e barker，l bassham，e