rsa密码体制研究及算法的局部改进和实现终结版.doc

南华大学数理学院毕业论文南 华 大 学毕业论文任务书学 院： 数理学院 题 目： 起 止 时 间： 2013 年 12 月 10日 至 2014 年 5 月 24日 学 生 姓 名： 专 业 班 级： 信息与计算科学 2010级01班 指 导 老 师： 系 主 任： 许友军 院 长： 欧 阳 自 根 2013 年 12 月 18 日毕业论文的内容及要求1. 毕业论文目标和内容：充分掌握RSA密码体制，以RSA算法为基础，局部改进算法，尽量考虑在不过多增加计算机运算负担的情况下提高算法的安全性，使改进的RSA密码体制能得到初步的实现；然后，通过软件设计实现算法。2. 毕业论文要求：1) 了解RSA密码体制的数学基础和不足。2) 掌握相关的数学知识，并利用这些知识改进RSA算法。3) 熟练运用C语言编程。3. 毕业论文进度安排：2009-2010学年第1学期1. 11.911.16指导老师指导学生选题。2. 11.1712.10指导老师给学生下任务书。3. 12.1110年1月19日学生完成文献综述和开题报告。2009-2010学年第2学期4. 第一周第八周完成论文主体初稿。5. 第九周第十周中期检查，指导教师审阅论文初稿，提出修改意见。6. 第十一周学生修改论文。7. 第十二周学生写论文中英文摘要。8. 第十三周毕业论文定稿和装订成册交指导老师和评阅老师。9. 第十四周毕业论文答辩。4. 主要参考文献：1 密码学（第二版），北京：机械工业出版社，2000,1-4002 Douglas R Stinson著，冯登国译.密码学原理与实践（第二版）.北京：电子工业出版社，2003,1-2623 李红军，缪旭东.数据加密在网络安全中的应用.微型机遇应用，2002（10）：31-334 潘承洞，潘成彪.数论（第二版）.北京：北京大学出版社，2004-115 李强，张继永.一种改进得分RSA快速算法.小型微型计算机系统，2001,22（1）：70-726 周德新.实现RSA的高效算法.桂林电子工业学院学报，1996，（6）：1-57 Michael Welschenbach.密码编码学加密方法的C与C+实现.北京：北京大学出版社，19998 谭浩强.C程序设计.北京：清华大学出版社，19959 陈运.一种新的快速RSA算法.电子科技大学学报，1996,24（2）：223-22810 陈运.一种组合RSA算法.电子科技大学学报，1996，25（2）：116-11911 Paul Garrett著，吴世忠等译.密码学导引.机械工业出版社，2003.8（注：不少于15篇参考文献）南华大学本科生毕业论文开题报告数理学院 信息与计算科学 2010级 01班 204390147 设计（论文）题目RSA密码体制研究及算法的局部改进和实现设计（论文）题目来源导师拟题设计（论文）题目类型理论研究型起止时间2013.10. 1-2014.5.22一、 设计（论文）依据及研究意义： 自20世纪90年代以来，计算机网络技术使得计算机应用得到进一步普及和发展，但是如何保证信息的安全却是一个十分重要的问题。公钥密码体制中，解密和加密密钥不同，解密和加密可分离，通信双方无须事先交换密钥就可建立起保密通信,较好地解决了传统密码体制在网络通信中出现的问题。另外，随着电子商务的发展，网络上资金的电子交换日益频繁，如何防止信息的伪造和欺骗也成为非常重要的问题。数字签名可以起到身份认证，核准数据完整性的作用。而RSA算法在公钥密码体制和数字签名中占有重要的地位。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。但RSA也是被研究得最广泛的公钥算法，再优秀的密码体制也存在着不足和安全隐患，因此对它进行适当改进，优化它的算法是一件很有意义的工作。二、 设计（论文）主要研究的内容、预期目标：（技术方案、路线）主要研究的内容：改进RSA密码体制所用到的数学知识，特别的数论方面；RSA加密解密算法和加密解密的过程；RSA的安全性和速度；根据RSA保密性能，如何优化它的算法，使它的安全性和加解密时间达到更优；如何设计软件来更好的实现这种改进的RSA密码体制。预期目标：首先，充分掌握RSA密码体制，以RSA算法为基础，局部改进算法，尽量考虑在不过多增加计算机运算负担的情况下提高算法的安全性，使改进的RSA密码体制能得到初步的实现；然后，通过软件设计实现算法。三、设计（论文）的研究重点及难点： 重点: 如何利用合适的数学知识来改进RSA的加密解密算法，使RSA算法的安全性和使用时间达到更优。难点：如何设计软件来更好的实现改进的RSA密码体制。 设计（论文）研究方法及步骤（进度安排）：方法：利用数学基础知识对密码体制算法进行优化。步骤：第一步：充分的了解密码学的相关背景和知识。 第二步：掌握RSA密码体制的数学基础知识。第三步：深入地对RSA密码体制进行研究。第四步：针对RSA密码体制的不足，对它进行适当的改进。第五步：对改进的RSA密码体制进行设计软件，使它初步的实现。第六步：进行设计测试用例。第七步：得出结论，分析改进的RSA密码体制的优缺点。 进行设计（论文）所需条件：在指导老师的指导下，选择各种有关参考资料。通过图书馆寻找有关参考文献，通过网络对RSA密码体制进一步的认识。在设计软件时，通过C语言编写改进的RSA密码算法，通过在计算机上实验，最终得出结果。 指导教师意见：签名： 年 月 日RSA密码体制研究及算法的局部改进和实现信息与计算科学专业2006级 （南华大学数理学院 湖南衡阳 421001）指导老师： 摘要：密码学是信息安全技术的核心，公钥密码体制又称为双钥体制，其加、解密密钥不同，可以公开加密密钥，而仅需保密解密密钥，从而具有数字签名、鉴别等新功能，被广泛应用于金融、商业等社会生活各领域。RSA加密算法是第一个较为完善的公开密钥算法。然而，该算法所采用的幂剩余计算会耗费太多的时间，一直是制约其广泛应用的瓶颈。本文首先对RSA的数论基础进行研究，并对RSA密码体制进行分析；然后在此基础上提出了一种高效算法，即在原算法的基础上，对有关实现环节进行了部分的改进，从而提高了加密解密的速度；最后用C语言实现了改进的算法并进行了对比测试。本论文所介绍的算法虽然对RSA算法进行了某些局部改进，但还有一些不够完善的地方，有待于进一步提高。关键词：密码学；RSA；快速算法；加密；解密Study on RSA cryptosystem and partial improved algorithm and its realizationChangHeng XuSchool of Mathematics and Physical Sciences, University of South China,Hengyang, Hunan, China, 421001,Tutor: Abstract：Cryptography is the core of the information security. The public key system is also called the double key system, where the encryption process is different with the decryption process. Since the public key system can publish its public key and keep its private key secret, it has part new applications such as the digital signature and authentication, which is widely used in every field of the society. RSA is the first quite perfect Public Key Algorithm. However the time-consuming modulo exponentiation computation, which has always been the bottleneck of RSA, restricts its wider application. First of all, this paper studies the number on the basis of RSA, and analyzes the RSA cryptosystem; Then on the basis, put forward an efficient algorithm, that is the basis of the original algorithm, right on the realization of part of the partial enhancement by improved the speed of encryption decryption; Finally, use Combined Language to implement the improved algorithm and have tested. Although this paper makes some improvement to the RSA algorithm, there are still some facets to be improved later.Keywords: Cryptography; RSA; Fast algorithm; Encryption; Decryption目录摘要iAbstractii目录iii引 言1第一章绪论21.1问题的提出21.2密码学概述31.3RSA的研究意义41.4本论文研究内容4第二章 RSA的数论基础52.1数论的基本概况52.2欧拉函数、欧拉定理和费尔马定理62.3同余及模运算6第三章 RSA密码体制的分析与研究83.1RSA简述83.2RSA算法的描述93.3RSA计算方法123.3.1加密和解密123.3.2密钥的生成123.3.3大数运算处理133.3.4素数的产生143.4RSA的安全性及分析163.4.1RSA的参数选择173.4.2RSA的安全性分析193.5RSA的速度20第四章 RSA算法分析与改进214.1RSA算法分析214.1.1传统RSA算法214.1.2目前主要的RSA算法244.2RSA算法的改进284.2.1对除法与取模进行改进284.2.2对BR (Binary Representation) 算法进行改进31第五章 RSA算法改进后的实现与测试335.1RSA实现的语言的选择335.2算法的设计流程345.3RSA加密体制的测试355.4原算法与新算法的比较39结束语41参考文献42致 谢44ix引 言随着计算机技术的快速发展促进了网络技术的迅速发展与广泛应用。通过网络传输或获取信息，已从军事、政治、外交等重要领域日益普及到人们日常生活的各个领域。因而，保障信息在网络传输的过程中不受各种干扰破坏或不发生泄露，已成为当今信息时代的一个重要问题。保障信息的安全就是要保障信息在传输、获取、存储、处理以及使用的过程中，信息的机密性、完整性、不可抵赖性和可用性不受到无意或恶意破坏。如今许多传统上基于纸面的签字盖章，诸如存单、支票、合同、租约等，已陆续转化为数字电子媒体的形式出现。这种转化前景辉煌，虽然在技术上还存在些问题，但对社会、经济、生活产生了深刻的影响。保密通信进入计算机网络，传统密码便暴露出它的严重弱点。传统密码要求通信双方用的密钥是通过秘密信道私下商定的，这本身就是极不安全的。RSA是一种国际公认的理想公钥密码体制，到目前为止仍不失为最有希望的一种公钥密码。它的基础是数论的欧拉定理，其安全性依赖于大数的因数分解的困难性。它表达方式简单，保密性强，没有密钥管理的麻烦；并且具有数字签名、认证和鉴别等功能，特别适合于现代保密通信的需要。但它的主要障碍在于大数的模幂乘算法效率比较低，难以实际应用，所以提高大数模幂乘运算的效率便成为非常重要的课题。第一章 绪论1.1 问题的提出科技的发展，信息从基于纸面转化为基于数字电子技术的形式，从中也产生了不少问题，在生成、传输、保存、验证和鉴定等多方面出现了新技术需求、问题和困难。特别是安全问题：怎样才能确保原始信息不被窃听，不被伪造、篡改，怎样确认信息发送者的真实性，怎样才能保证信息发送者无法抵赖等等。而且，我们有很多的机密、甚至价值高的重要信息要在公开的网络上传送，这无疑增加了困难。“公开密钥密码体制”的方法在一定的程度上成功地解决了一些问题，并在某个领域也得到了应用。在一定程度上说，网络安全就是信息安全。信息的保密性、完整性、可用性、可靠性和不可抵赖性等相关技术都是信息安全的研究领域。信息安全的技术可分为承载数据的系统安全、数据安全及事务安全三个方面。系统安全包括访问控制、防火墙、物理隔离等保护技术，入侵检测、安全审计、漏洞扫描、病毒扫描等检测技术，还包括负载均衡、冗余备份等恢复技术。而密码技术通过加密、鉴别、身份识别、数字签名等机制构成数据安全、事务安全的基本工具集。密码技术和访问控制技术共同构成信息安全保护的核心技术。一般网络信息安全保障的方法可分为两大类：以防火墙技术为中心的被动防卫；建立在数据加密上的开放型网络安全保障技术。防火墙是一种由计算机硬件和软件的组合，使互联网与内部网络间建立起一个安全网关，保护内部网免受非法用户的侵入，即一个把互联网与内部网隔开的屏障。使用防火墙是保障网络安全的第一步，选择一款合适的防火墙，是保护信息安全不可缺少的一道屏障。数据加密技术，也称密码技术，是与防火墙配合使用的安全技术，是为提高信息系统及数据的安全行和保密性，防止数据被外部窃取、破坏的主要技术手段。数据加密技术主要分为数据传输、数据存储、数据完整性的鉴别以及密钥管理技术四种。数据传输加密技术目的是对传输中的数据流加密；数据存储加密技术目的是防止在存储环节上的数据失密；数据完整性鉴别技术目的是对介入信息的传送、存取、处理的人的身份和相关数据内容进行验证，一般包括口令、密钥、身份、数据等项的鉴别；密钥管理积水包括密钥的产生、分配保存、更换与销毁等环节上的保密措施。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，它易于理解，操作简单。并且RSA被研究得最广泛的公钥算法，从提出到现在已由二十年，经历了各种攻击的考验，逐渐为人们接受，也被普遍认为是目前最优秀的公钥方案之一。但也有个缺点，RSA算法核心进行的都是大数计算，使得相同的条件下RSA最快情况也比DES慢上100倍，无论软件还是硬件实现，速度一直是RSA的缺陷。所以，研究RSA的效率是最有意义的课题。随着计算机的不断发展，网络的不断普及，网络安全更加成为人们的焦点，在这方面的研究领域将变的越来越重要。我们也知道世上没有绝对安全的网络，只有相对安全的网络。当然，网络安全的其得也必须通过不断地完善，不断地对现阶段的安全系统进行改进，提高安全系数。1.2 密码学概述密码学的历史悠久，可以追溯到远古时代，人类有记载的通信密码始于公元前400年。密码学的一些常用基本概念有：密码学是研究信息及信息系统安全传统的科学，它起源于保密通信技术。密码学又分为密码编码学与密码分析学。研究如何对信息编码，以实现信息及通信保密的科学成为密码编码学；研究如何破解或攻击加密信息的科学称为密码分析学。明文是指发送方想要发给接受方的消息；密文是指明文被加密后的消息；加密是将明文变换为密文的过程；解密是将密文恢复为明文的过程。密码学是在编码与破译的矛盾斗争中逐步发展起来的，并随着计算机等先进科学技术的发展与应用，已成为一门综合性、交叉性学科。它在发展中经历了4个阶段：古典密码术（手工操作密码），有几千年的历史；第二阶段机器密码时代；第三阶段是传统密码学，是种密码技术或密码术；第四阶段是现代公钥密码学。如今，密码学早已成为一门热门的学科，在理论和方法上都有了巨大的发展。根据加密和解密是否相同，可以对它进行密码体制的分类。大体分为单钥密码体制与双钥密码体制两类。单钥加密体制，即从其中一个容易推出另一个，典型的有：DES、三重DES、AES等；双钥密码体制（又称公钥密码体制），它有两个本质上完全不同的密钥，即利用私钥持有人的相应公钥对信息加密后通过公共信道发送给私钥持有人，其典型的有RSA密码体制等。1.3 RSA的研究意义 RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。RSA算法是第一个能同时用于加密和数字签名的算法，也很流行。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。RSA的缺点主要有：产生密钥比较麻烦，受到素数产生技术的限制。难以做到一次一密；分组长度太大，为保证安全性，n至少也要600bits以上，使运算代价很大，尤其是速度比较慢。1.4 本论文研究内容本文对RSA密码体制进行研究，对它的算法进行研究分析，提出RSA算法改进方案以提高计算效率。研究内容：（1）对RSA的数论基础进行研究；（2）对RSA密码体制进行分析与研究；（3）对RSA算法进行分析与改进；（4）综合以上研究，改进算法；（5）基于改进的算法，实现算法，测试结论。第二章 RSA的数论基础在密码学中需要使用到很多数学理论，例如数论、信息论、复杂度理论等，他们是设计密码系统及协议不可缺少的工具，其中数论是密码学中（特别是公钥密码体制系统中）最重要的数学基础，因此有必要对有关数学理论做些简单的介绍，下面主要介绍RSA算法的数学基础知识。2.1 数论的基本概况数论就是指研究整数性质的一门理论。整数的基本元素是素数，所以，数论的本质是对素数性质的研究。数论大致上可以分为初等数论（古典数论）和高等数论（近代数论）。如今RSA算法主要应用到的是初等数论，下面我们就真对初等数论进行简单的阐述。初等数论是数论中不求助于其他数学学科的帮助，研究数的规律，特别是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。换言之，初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论（用解析的方法研究数论。）、代数数论（用代数结构的方法研究数论）。它有着悠久的历史，初等数论已经经历了2000年的历史，公元前300年，欧几里得发现了素数是数论的基石，他自己证明了有无穷多个素数。公元前250年古希腊数学家埃拉托塞尼发明了一种筛法。2000年来，数论学的一个最重要的任务，就是寻找一个可以表示所有素数的统一公式，或者称为素数普遍公式，经过人类巨大的心血，后来发现了一种筛法可以转换成为一个素数产生公式。中国古代对初等数论的研究有也着光辉的成就，周髀算经、孙子算经、张邱建算经、数书九章等古文献上都有记载。孙子定理比欧洲早500年， 西方常称此定理为中国剩余定理，秦九韶的大衍求一术也驰名世界。如今初等数论不仅是研究纯数学的基础，也是许多学科的重要工具。它的应用是多方面的，如计算机科学、组合数学、密码学、信息论等。如公开密钥体制的提出是数论在密码学中的重要应用。2.2 欧拉函数、欧拉定理和费尔马定理欧拉函数：是一个定义在正整数上的函数，其值等于序列0，1，2，3，n-1中与n互素的数的个数。即(n)为模n既约剩余系中所有元素的个数。欧拉定理：对于互质的正整数a和n，即a和n的最大公约数是1，则有a(n) 1 (mod n)。其中(n)称为欧拉函数，它是比n小且与n互素的正整数的个数。证明：首先证明下面这个命题：对于集合Zn=x1,x2,.,x(n),其中xi(i=1,2,(n)是不大于n且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S = a*x1(mod n),a*x2(mod n),.,a*x(n)(mod n) ，则S = Zn 。证明：（1） 由于a,n互质，xi也与n互质，则a*xi也一定于p互质，因此，任意xi，a*xi(mod n) 必然是Zn的一个元素 ；（2） 对于Zn中两个元素xi和xj，如果xi xj 则a*xi(mod n) a*xi(mod n)，这个由a、p互质和消去律可以得出。所以，很明显，S=Zn 。既然这样，那么 （a*x1 a*x2.a*x(n)）(mod n) = （a*x1(mod n) a*x2(mod n) . a*x(n)(mod n)）(mod n) = （x1 x2 . x(n)）(mod n) ，考虑上面等式左边和右边，左边等于(a*（x1 x2 . x(n)）) (mod n)，右边等于x1 x2 . x(n)）(mod n)，而x1 x2 . x(n)(mod n)和n互质根据消去律，可以从等式两边约去，就得到：a(n) 1 (mod n)费尔马定理：a是不能被质数p整除的正整数，则有a(p-1) 1 (mod p)，同样有个推论，对于不能被质数p整除的正整数a，有ap a (mod p)。证明这定理很简单，由于(p) = p-1，代入欧拉定理即可证明。2.3 同余及模运算 同余：假定有三个整数a，b，m（m0），当我们称a在模m与b同余，是指当且仅当a与b的差为m的整数倍，即a-b=nm，其中n为任一整数。若a与b在模m中同余，我们可以写为a b (mod m)。剩余类：一个整数被正整数n除后，余数有n种情形：0，1，2，3，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。我们把所有与整数a对模n同余的整数构成的集合叫做模n的一个剩余类。 确切地说，若x是一个给定的正整数,则全体整数可以分成x个集，记作x,x,x-1,其中=0,1,-1 xi是由一切形如axi(a=0,1,2,)的整数所组成的集。完全剩余系：从模n的每个剩余类中各取一个数，得到一个由n个数组成的集合，叫做模n的一个完全剩余系。例如，一个数除以4的余数只能是0，1，2，3，0，1，2，3和4，5，-2，11是模4的完全剩余系。可以看出0和4，1和5，2和-2，3和11关于模4同余，这4组数分别属于4个剩余类。从0到n-1的整数组成的集合构成了模n的“完全剩余系”。这意味着，对每个整数a，它的模n剩余是从0到n-1之间的某个整数。所谓模运算就是运算a mod n，表示求a被n除的余数。既约剩余系：又称简化剩余系，即在模n互质的完全剩余类中，若将所有与n互素的剩余类形成一个集合，则称此集合为模n的既约剩余系。例如n=10时，0，1，2，3，4，5，6，7，8，9为模10的完全剩余系；而1,3,7,9,为模10的既约剩余系。第三章 RSA密码体制的分析与研究3.1 RSA简述公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的（论文NewDirectioninCryptography）。但目前最流行的RSA是1977年由MIT教授RonaldL.Rivest,AdiShamir和LeonardM.Adleman共同开发的,分别取自三名数学家的名字的第一个字母来构成的。1976年提出的公开密钥密码体制思想不同于传统的对称密钥密码体制，它要求密钥成对出现，一个为加密密钥(e)，另一个为解密密钥(d)，且不可能从其中一个推导出另一个。自1976年以来，已经提出了多种公开密钥密码算法，其中许多是不安全的，一些认为是安全的算法又有许多是不实用的，它们要么是密钥太大，要么密文扩展十分严重。多数密码算法的安全基础是基于一些数学难题，这些难题专家们认为在短期内不可能得到解决。因为一些问题(如因子分解问题)至今已有数千年的历史了。公钥加密算法也称非对称密钥算法，用两对密钥：一个公共密钥和一个专用密钥。用户要保障专用密钥的安全；公共密钥则可以发布出去。公共密钥与专用密钥是有紧密关系的，用公共密钥加密的信息只能用专用密钥解密，反之亦然。由于公钥算法不需要联机密钥服务器，密钥分配协议简单，所以极大简化了密钥管理。除加密功能外，公钥系统还可以提供数字签名。公钥加密算法中使用最广的是RSA。RSA使用两个密钥，一个公共密钥，一个专用密钥。如用其中一个加密，则可用另一个解密，密钥长度从40到2048bit可变，加密时也把明文分成块，块的大小可变，但不能超过密钥的长度，RSA算法把每一块明文转化为与密钥长度相同的密文块。密钥越长，加密效果越好，但加密解密的开销也大，所以要在安全与性能之间折衷考虑，一般64位是较合适的。RSA的一个比较知名的应用是SSL，在美国和加拿大SSL用128位RSA算法，由于出口限制，在其它地区（包括中国）通用的则是40位版本。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。RSA算法很好的完成对电文的数字签名以抗对数据的否认与抵赖；利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。目前为止，很多种加密技术采用了RSA算法，比如PGP（PrettyGoodPrivacy）加密系统，它是一个工具软件，向认证中心注册后就可以用它对文件进行加解密或数字签名，PGP所采用的就是RSA算法。由此可以看出RSA有很好的应用。3.2 RSA算法的描述 RSA使用了以大整数为模的同余指数运算。按照特定的方式选择一个大整数n，明文（密文）分组是小于数n的非负整数。即用二进制表示时分组长度必须小于或等于 。对于某个明文分组M和密文分组C，加密及解密的形式如下： =mod n =mod n=()mod n=mod n这里e称为加密指数，d称为解密指数。明文发送方和接收方都必须知道n的值。发送方知道e的值，而只有接收方知道d的值。这是一种公开密钥为KU=e，n，且私有密钥为KR=d，n的公开密钥加密算法。要使这个算法能够满足公开密钥加密的要求，必须符合如下条件：（1）有可能找到e、d、n的值，使得对所有Mn有 ；（2）对于所有Mn的值，要计算于相对来说是简单的；（3）仅知道e和n时，无法算出d。需要找到具有下列形式的关系： =给定两个互异的素数p和q，以及两个整数n和m，使得n=pq且0mn，m与n互素。由Enler定理，有 于是对于任意整数k，下列关系成立： 其中是欧拉totient函数，表示不超过n且与n互素的整数个数。对于互异的素数p和q，有。选择e、d使得 它等价于 也就是说d和e是以为模的乘法逆元，。注意到要求e与d均与是互素的。综上所述可以给出RSA方案。它的参数有：P、q：两个互异素数 （私有，选择）n：n=pq （公开，计算出）e：满足1e(n)及gcd（(n)，e）=1 （公开，选择）d：d （私有，计算出）私有密钥由d，n组成，公开密钥由e，n组成。假设用户A公布了它的公开密钥，而用户B希望向A发送一个报文M（0Mn），那么B计算出并传输C。在收到这个密文时，用户A通过计算进行解密。现在来检验计算确实恢复出明文M。选择了e和d，使得 ，即 所以可设 当gcd（M，n）=1时，由Euler定理可得 当gcd（M，n）1时，由gcd（M，n）|n知gcd（M，n）=p或q。不妨设gcd（M，n）=p，则p|M，令M=sp，1sq。因gcd（M，q）=1，由Fermat定理可得 于是 ，即 由此得 ，即另一方面，由p|M可得 因为gcd（p，q）=1，由初等知识可得 即 下图总结归纳了RSA算法的实现过程。1. 密钥的产生 选择大素数：p、q p和q是互异素数 计 算： n=pq 计 算： (n)=（p-1）（q-1） 选择 整数：e gcd（(n)，e）=1；1e(n) 计 算：d 公开 密钥： KU=e，n 私有 密钥： KR=d，n2. 加 密 明 文： 0Mn 密 文： 3. 解 密 密 文： 0 Cn 明 文： M=3.3 RSA计算方法现在转而讨论使用RSA时的计算复杂性问题。实际上需要考虑的问题有：加密/解密、密钥的生成、大数运算的处理和素数的产生。下面就来讨论下以上问题。3.3.1 加密和解密在RSA中，加密和解密都涉及计算一个整数的幂，然后模n。如果先对整数进行指数运算，然后再进行模n运算，那么中间结果将极其巨大。幸运的是，可以利用取模运算的一个特性：因而，可以对中间结果进行模n运算，这就使计算实际可行。另外一个考虑是指数运算的效率，因为在RSA中碰到的可能是非常大的指数。为了了解如何才能提高效率，考虑计算。直接的方法需要15次乘法：然而，可以只用4次乘法得到同样的最后结果。如果重复对每次的部分结果取平方，依次得到、。一般地，假定希望算出的值，其中和是整数。如果将表示为一个二进制数、，那么有： 因而 3.3.2 密钥的生成在应用RSA密码体制之前，必须先生产生密钥，即必须先选择两个大素数与，然后再选取相对较小的正整数，并计算出。由于与得积是公开的，所以为了防止攻击者用穷搜索法获得与，与必须是足够大的素数。因而，有效地获取大素数是实现RSA密码体制需要解决的一个关键问题。然而，遗憾的是，目前还没有特别有效的方法可以产生任意打的素数。现在通常的办法是：随机选取一个适当大的奇数，然后检验它是否为素数，若非素数，则随机选另一个奇数检测它是否为素数，如此继续，直到找到一个大素数为止。目前素性检测的方法基本上都是概率性的，即这些检测方法只能确定一个给定整数可能是素数。但有些检测方法可使检测一个整数是素数的概率接近1.0，比如附录中介绍的非常有效且被广泛采用的Miller-Rabin算法。2002年印度理工大学的3位学者提出一种（多项式时间）快速确定性算法，可以证明一个整数是素数。其效率不如概率算法高。确定了足够大的素数、后，就可借助扩展的Eucidean算法来求得满足条件及与互素的，并求得。3.3.3 大数运算处理RSA依赖大数运算，目前主流RSA算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等于64位，即：0xffffffffffffffff，也就是18446744073709551615，这远远达不到RSA的需要