RSA密码体制研究及算法的局部改进和实现_毕业论文终结版

1、南华大学毕业论文任务书学院:题目:起止时间:学生姓名:专业班级:指导老师:系主任:院长:数理学院2013年12月10日至2014年5月24日信息与计算科学2010级01班许友军欧阳自根2013年 12 月 18 日毕业论文的内容及要求1. 毕业论文目标和内容：充分掌握rsa密码体制，以rsa算法为基础，局部改进算法，尽量考虑在 不过多增加计算机运算负担的情况下提高算法的安全性，使改进的rsa密码体 制能得到初步的实现；然后，通过软件设计实现算法。2. 毕业论文要求：1）了解rsa密码体制的数学基础和不足。2）掌握相关的数学知识，并利用这些知识改进rsa算法。3）熟练运用c语言编程。3. 毕业论

2、文进度安排：2009-2010学年第1学期1. 11. 911. 16指导老师指导学生选题。2. 11. 17-12. 10指导老师给学生卜任务书。3. 12.1110年1月19 fi学生完成文献综述和开题报告。2009-2010学年第2学期4. 第一周第八周完成论文主休初稿。5. 第九周第十周中期检查，指导教师审阅论文初稿，捉出修改意见。6. 第十一周学生修改论文。7. 第十二周学生写论文中英文摘要。&第十三周毕业论文定稿和装订成册交指导老师和评阅老师。9.第十四周毕业论文答辩。4. 主要参考文献：1 密码学（第二版），北京：机械工业出版社，2000, 1-4002 douglas

3、r stinson著，冯登国译.密码学原理与实践（第二版）北京：电子工业 出版社，2003, 1-2623 李红军，缪旭东数据加密在网络安全中的应用.微型机遇应用，2002 （10）： 31-334 潘承洞，潘成彪.数论（笫二版）北京：北京大学出版社，2004-115 李强,张继永.一种改进得分rsa快速算法.小型微型计算机系统,2001,22 （1）：6 周德新实现rsa的高效算法.桂林电了工业学院学报，1996, (6)： 1-57 michael welschenbach.密码编码学加密方法的c与c+实现.北京：北京人学出版社,19998 谭浩强.c程序设计.北京：清华大学出版社，199

4、59 陈运.一种新的快速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

5、年代以来，计算机网络技术使得计算机应用得到进一步普及和 发展，但是如何保证信息的安全却是一个十分重要的问题。公钥密码体制中，解 密和加密密钥不同，解密和加密可分离，通信双方无须事先交换密钥就可建立起 保密通信,较好地解决了传统密码体制在网络通信中出现的问题。另外，随着电 子商务的发展，网络上资金的电子交换日益频繁，如何防止信息的伪造和欺骗也 成为非常重要的问题。数字签名可以起到身份认证，核准数据完整性的作用。而 rsa算法在公钥密码体制和数字签名中占有重要的地位。rsa算法是第一个能同 时用于加密和数字签名的算法，也易于理解和操作。从捉岀到现在已近二十年， 经历了各种攻击的考验，逐渐为人们接受

6、，普遍认为是目前最优秀的公钥方案z 一。但rsa也是被研究得最广泛的公钥算法，再优秀的密码体制也存在着不足和 安全隐患，因此对它进行适当改进，优化它的算法是一件很有意义的工作。二、设计（论文）主要研究的内容、预期目标：（技术方案、路线）主要研究的内容：改进rsa密码体制所用到的数学知识，特别的数论方而； rsa加密解密算法和加密解密的过程；rsa的安全性和速度；根据rsa保密性能， 如何优化它的算法，使它的安全性和加解密时间达到更优；如何设计软件來更好 的实现这种改进的rsa密码体制。预期目标：首先，充分掌握rsa密码体制，以rsa算法为基础，局部改进算 法，尽量考虑在不过多增加计算机运算负担

7、的情况下捉高算法的安全性，使改进 的rsa密码体制能得到初步的实现；然后，通过软件设计实现算法。三、设计（论文）的研究重点及难点：重点：如何利用合适的数学知识来改进rsa的加密解密算法，使rsa算法的 安全性和使用时间达到更优。难点：如何设计软件来更好的实现改进的rsa密码休制。 设计（论文）研究方法及步骤（进度安排人方法：利用数学基础知识对密码体制算法进行优化。步骤：第一步：充分的了解密码学的相关背景和知识。第二步：掌握rsa密码体制的数学基础知识。第三步：深入地对rsa密码体制进行研究。第四步：针对rsa密码体制的不足，对它进行适当的改进。第五步：对改进的rsa密码体制进行设计软件，使它初

8、步的实现。第六步：进行设计测试用例。第七步：得出结论，分析改进的rsa密码体制的优缺点。进行设计（论文）所需条件：在指导老师的指导下，选择各种冇关参考资料。通过图书馆寻找冇关参考文 献，通过网络对rsa密码体制进一步的认识。在设计软件时，通过c语言编写改 进的rsa密码算法，通过在计算机上实验，最终得出结果。指导教师意见:签名:rsa密码体制研究及算法的局部改进和实现信息与计算科学专业2006级（南华大学数理学院 湖南衡阳421001 ）指导老师：摘要：密码学是信息安全技术的核心，公钥密码体制又称为双钥体制，其加、 解密密钥不同，可以公开加密密钥，而仅需保密解密密钥，从而具有数字签名、 鉴别等

9、新功能，被广泛应用于金融、商业等社会生活各领域。rsa加密算法是 第一个较为完善的公开密钥算法。然而，该算法所采用的舉剩余计算会耗费太 多的时间，一直是制约其广泛应用的瓶颈。本文首先对rsa的数论基础进行研 究，并对rsa密码体制进行分析；然后在此基础上提出了一种高效算法，即在 原算法的基础上，对有关实现环节进行了部分的改进，从而提高了加密解密的 速度；最后用c语言实现了改进的算法并进行了对比测试。本论文所介绍的算 法虽然对rsa算法进行了某些局部改进，但还有一些不够完善的地方，有待于 进一步提高。关键词：密码学；rsa;快速算法；加密；解密study on rsa cryptosystem

10、and partial improvedalgorithm and its realizationchangheng xuschool of mathematics and physical sciences, university of south china,hengyang, hunan, china, 421(x)1,tutor:abstract： cryptography is the core of the information security. the public key system is also called the double key system, where

11、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

12、 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

13、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

14、improvement to the rsa algorithm, there are still some facets to be improved late匚keywords: cryptography; rsa; fast algorithm; encryption; decryption目录摘要viabstractvii目录viii耳i 二1第二舊蠢二二二二二二二二二二二二二二二二二二二二二 21.1 问题的提出21.2 密码学概述31.3 rsa的研究意义41.4 本论文研究内容4第二章rsa的数论基础52.1 数论的基本概况52. 2欧拉函数、欧拉定理和费尔马定理62.3同余及模

15、运算6第三章rsa密码体制的分析与研究83. 1rsa 简述83.2 rsa算法的描述93.3 rsa计算方法123.3. 1加密和解密123.3.2 密钥的生成123.3.3 大数运算处理133.3.4 素数的产生143.4 rsa的安全性及分析163.4. 1rsa的参数选择173.4.2 rsa的安全性分析193.5 rsa的速度20第四章rsa算法分析与改进214. 1rsa算法分析214. 1. 1传统rsa算法214. 1.2目前主要的rsa算法244.2 rsa算法的改进284.2.1对除法与取模进行改进284. 2. 2对 br (binary representation)算

16、法进行改进30第五章rsa算法改进后的实现与测试325.1 rsa实现的语言的选择335.2 算法的设计流程345.3 rsa加密体制的测试345.4 原算法与新算法的比较39结束语41参考文献42致谢44随着计算机技术的快速发展促进了网络技术的迅速发展与广泛应用。通过 网络传输或获取信息，已从军事、政治、外交等重要领域日益普及到人们日常 生活的各个领域。因而，保障信息在网络传输的过程屮不受各种干扰破坏或不 发生泄露，已成为当今信息时代的一个重要问题。保障信息的安全就是耍保障 信息在传输、获取、存储、处理以及使用的过程中，信息的机密性、完整性、 不可抵赖性和可用性不受到无意或恶意破坏。如今许多

17、传统上基于纸面的签字 盖章，诸如存单、支票、合同、租约等，已陆续转化为数字电子媒体的形式出 现。这种转化前景辉煌，虽然在技术上述存在些问题，但对社会、经济、生活 产生了深刻的影响。保密通信进入计算机网络，传统密码便暴露出它的严重弱点。传统密码要 求通信双方用的密钥是通过秘密信道私下商定的，这木身就是极不安全的。rsa是一种国际公认的理想公钥密码体制，到目前为止仍不失为最有希望 的一种公钥密码。它的基础是数论的欧拉定理，其安全性依赖丁大数的因数分 解的困难性。它表达方式简单，保密性强，没有密钥管理的麻烦；并且貝有数 字签名、认证和鉴别等功能，特别适合于现代保密通信的需要。但它的主要障 碍在于大数

18、的模幕乘算法效率比较低，难以实际应用，所以提高大数模幕乘运 算的效率便成为非常重要的课题。第一章绪论1.1问题的提出科技的发展，信息从基于纸面转化为基于数字电了技术的形式，从中也产 生了不少问题，在生成、传输、保存、验证和鉴定等多方面岀现了新技术需求、 问题和怵i难。特别是安全问题：怎样才能确保原始信息不被窃听，不被伪造、 篡改，怎样确认信息发送者的真实性，怎样才能保证信息发送者无法抵赖等等。 而且，我们冇很多的机'密、其至价值高的重要信息要在公开的网络上传送，这 无疑增加了困难。“公开密钥密码体制”的方法在一定的程度上成功地解决了一 些问题，并在某个领域也得到了应用。在一定程度上说，

19、网络安全就是信息安全。信息的保密性、完整性、可用 性、可靠性和不可抵赖性等相关技术都是信息安全的研究领域。信息安全的技 术可分为承载数据的系统安全、数据安全及事务安全三个方而。系统安全包括 访问控制、防火墙、物理隔离等保护技术，入侵检测、安全审计、漏洞扫描、 病毒扫描等检测技术，还包括负载均衡、兀余备份等恢复技术。而密码技术通 过加密、鉴别、身份识别、数字签名等机制构成数据安全、事务安全的基本工 具集。密码技术和访问控制技术共同构成信息安全保护的核心技术。一般网络信息安全保障的方法可分为两大类：以防火墙技术为屮心的被动 防卫；建立在数据加密上的开放型网络安全保障技术。防火墙是一种由计算机硬件和

20、软件的组合，使互联网与内部网络间建立起 一个安全网关，保护内部网免受非法用户的侵入，即一个把互联网与内部网隔 开的屏障。使用防火墙是保障网络安全的第一步，选择一款合适的防火墙，是 保护信息安全不可缺少的一道屏障。数据加密技术，也称密码技术，是与防火墙配合使用的安全技术，是为提 高信息系统及数据的安全行和保密性，防止数据被外部窃取、破坏的主要技术 手段。数据加密技术主要分为数据传输、数据存储、数据完整性的鉴别以及密 钥管理技术四种。数拯传输加密技术目的是对传输中的数据流加密；数据存储 加密技术目的是防止在存储环节上的数据失密；数据完整性鉴别技术目的是对 介入信息的传送、存取、处理的人的身份和相关

21、数据内容进行验证，一般包括 口令、密钥、身份、数据等项的鉴别；密钥管理积水包括密钥的产生、分配保 存、更换与销毁等环节上的保密措施。rsa算法是第一个既能用于数据加密也能用于数字签名的算法，它易于理 解，操作简单。并且rsa被研究得最广泛的公钥算法，从提出到现在已由二十 年，经历了各种攻击的考验，逐渐为人们接受，也被普遍认为是目前最优秀的 公钥方案之一。但也冇个缺点，rsa算法核心进行的都是大数计算，使得相同 的条件卜rsa最快情况也比des慢上100倍，无论软件还是硬件实现，速度一 直是rsa的缺陷。所以，研究rsa的效率是最冇意义的课题。随着计算机的不断发展，网络的不断普及，网络安全更加成

22、为人们的焦点, 在这方面的研究领域将变的越来越重要。我们也知道世上没有绝对安全的网络, 只冇相对安全的网络。当然，网络安全的其得也必须通过不断地完善，不断地 对现阶段的安全系统进行改进，提高安全系数。1.2密码学概述密码学的历史悠久，可以追溯到远古时代，人类有记载的通信密码始于公 元前400年。密码学的一些常用基本概念fl17'81：密码学是研究信息及信息 系统安全传统的科学，它起源于保密通信技术。密码学又分为密码编码学与密 码分析学。研究如何对信息编码，以实现信息及通信保密的科学成为密码编码 学；研究如何破解或攻击加密信息的科学称为密码分析学。明文是指发送方想 要发给接受方的消息；密

23、文是指明文被加密后的消息；加密是将明文变换为密 文的过程；解密是将密文恢复为明文的过程。密码学是在编码与破译的矛盾斗争中逐步发展起來的，并随着计算机等先 进科学技术的发展与应用，已成为一门综合性、交叉性学科。它在发展屮经历 了 4个阶段：古典密码术（手工操作密码），有儿千年的历史；第二阶段机器密 码时代；第三阶段是传统密码学，是种密码技术或密码术；第四阶段是现代公 钥密码学。如今，密码学早已成为一门热门的学科，在理论和方法上都有了巨 大的发展。根据加密和解密是否相同，可以对它进行密码体制的分类。大体分为单钥 密码体制与双钥密码体制两类。单钥加密体制，即从其中一个容易推岀另一个, 典型的有:de

24、s、三重des、aes等；双钥密码体制（又称公钥密码体制）, 它有两个木质上完全不同的密钥，即利用私钥持有人的相应公钥对信息加密后通过公共信道发送给私钥持有人，其典型的有rsa密码体制等。1.3 rsa的研究意义rsa是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知 的所有密码攻击，已被iso推荐为公钥数据加密标准。rsa算法基于一个 十分简单的数论事实：将两个大索数相乘十分容易，但那时想要对其乘积 进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。rsa算法 是第一个能同时用于加密和数字签名的算法，也很流行。rsa是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历 了各种

25、攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案 之一。rsa的安全性依赖于大数的因子分解，但并没有从理论上证明破译 rsa的难度与大数分解难度等价。即rsa的重大缺陷是无法从理论上把 握它的保密性能如何，而口密码学界多数人士倾向于i大i子分解不是npc 问题。rsa的缺点主要有：产生密钥比较麻烦，受到素数产生技术的限制。 难以做到一次一密；分组长度太大，为保证安全性，n至少也要600bits 以上，使运算代价很大，尤其是速度比较慢。1.4本论文研究内容木文对rsa密码体制进行研究，对它的算法进行研究分析，提出rsa 算法改进方案以提高计算效率。研究内容：(1) 对rsa的数论基础进

26、行研究；(2) 对rsa密码体制进行分析与研究；(3) 对rsa算法进行分析与改进；(4) 综合以上研究，改进算法；(5) 基于改进的算法，实现算法，测试结论。第二章rsa的数论基础在密码学中需要使用到很多数学理论，例如数论、信息论、复杂度理 论等，他们是设计密码系统及协议不可缺少的工具，其中数论是密码学中 （特别是公钥密码体制系统中）最重要的数学基础，因此有必要对有关数 学理论做些简单的介绍，下面主要介绍rsa算法的数学基础知识。2.1数论的基本概况数论就是指研究整数性质的一门理论。整数的基本元素是素数，所以， 数论的木质是对素数性质的研究。数论大致上可以分为初等数论（占典数 论）和高等数论

27、（近代数论）。如今rsa算法主要应用到的是初等数论， 下面我们就真对初等数论进行简单的阐述。初等数论是数论中不求助于其他数学学科的帮助，研究数的规律，特别 是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为 主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某 些特殊不定方程。换言之，初等数论就是用初等、朴索的方法去研究数论。 另外还有解析数论（用解析的方法研究数论。）、代数数论（用代数结构的 方法研究数论）。它有着悠久的历史，初等数论已经经历了 2000年的历史, 公元前300年，欧几里得发现了素数是数论的基石，他自己证明了有无穷 多个素数。公元丽250年古希腊数学

28、家埃拉托塞尼发明了一种筛法。2000 年來，数论学的一个最重要的任务，就是寻找一个可以表示所有索数的统 一公式，或者称为素数普遍公式，经过人类巨大的心血，后来发现了一种 筛法可以转换成为一个素数产生公式。中国古代对初等数论的研究冇也着光辉的成就，周髀算经、孙子 算经、张邱建算经、数书九章等占文献上都有记载。孙了定理比欧 洲早500年，西方常称此定理为中国剩余定理，秦九韶的大衍求一术也 驰名世界。如今初等数论不仅是研究纯数学的基础，也是许多学科的重要 工具。它的应用是多方面的，如计算机科学、组合数学、密码学、信息论 等。如公开密钥体制的捉出是数论在密码学屮的重要应用。2.2欧拉函数、欧拉定理和费

29、尔马定理欧拉函数是一个定义在正整数上的函数，其值等于序列0, 1, 2, 3,，中与n互素的数的个数。即(p(n)为模n既约剩余系中所有元素 的个数。欧拉定理何：对丁互质的正整数a和n,即a和n的最人公约数是1, 则有aa(p(n)三1 (mod n)。其中p(n)称为欧拉函数，它是比n小且与n互 素的正整数的个数。证明：首先证明f面这个命题:对于集合zn=x1,x2,.,x(p(n),其中 xi(i=1,2,.(p(n)是不大于n且与n互索的数，即n的一个化简剩余系，或 称简系，或称缩系)，考虑集合 s = a*x1(mod n),a*x2(mod n),.,a*x(p(n)(mod n),

30、则 s = zn。证明：(1) 由于 a,n 互质，xi 也 与n互质，则a*xi也一定于p互质，因此，任意xi, a*xi(mod n)必然是 zn的一个元素；(2)对于zn中两个元素xi和xj,如果xi t xj贝ij a*xi(mod n) # a*xi(mod n),这个由a、p互质和消去律口j以得出。所以，很明显， s=zn。既然这样，那么(a*x1 x a*x2x.xa*x(p(n)(mod n) = (a*x1(mod n) x a*x2(mod n) x . x a*x(p(n)(mod n) (mod n) =(x1 x x2 x . xx(p(n) (mod n),考虑上而

31、等式左边和右边，左边等于(a* (x1 x x2 x . x x(p(n) (mod n),右边等于 x1 x x2 x . x x(p(n) (mod n), w x1 x x2 x . x x(p(n)(mod n)和n互质根据消去律，口j以从等式两边约去，就得到：aa(p(n) =1 (mod n)费尔马定理w a是不能被质数p整除的正整数，则有aa(p-1)三1 (mod p),同样有个推论，对于不能被质数p整除的正整数a,有a”三a (mod p)o证明这定理很简单，由于(p(p) = p-1,代入欧拉定理即可证明。2.3同余及模运算同余】：假定有三个整数a, b, m (mo),当

32、我们称a在模m与b 同余，是指当且仅当a与b的差为m的整数倍，即a-b=nm,其中n为任一 整数。若a与b在模m中同余，我们可以写为a= b (mod m)o剩余类：一个整数被正整数n除后，余数有n种情形：0, 1, 2, 3, n-1,它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一 个对模n同余。这样一來，按模n是否同余对整数集进行分类，可以将整 数集分成n个两两不相交的子集。我们把所有与整数a对模n同余的整数 构成的集合叫做模n的一个剩余类。确切地说，若x是一个给定的正整 数,则全体整数可以分成x个集，记作xn,xd,.,xn-1,其中口xi 是由一切形如ax+i(a=0,&#

33、177;1,±2,.)的整数所组成的集。完全剩余系：从模n的每个剩余类中各取一个数，得到一个由n个数 组成的集合，叫做模n的一个完全剩余系。例如，一个数除以4的余数只 能是0, 1, 2, 3, 0, 1, 2, 3和4, 5,2, "是模4的完全剩余系。 可以看出0和4, 1和5, 2和3和笛关于模4同余，这4组数分别 属于4个剩余类。从0到的整数组成的集合构成了模n的“完全剩余系”。这意味 着，对每个整数a,它的模n剩余是从0到之间的某个整数。所谓模运算就是运算a mod n,表示求a被n除的余数。e约剩余系：又称简化剩余系，即在模n互质的完全剩余类屮，若将所有与n互素

34、的剩余类形成一个集合，则称此集合为模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'1)o但目前最 流 行 的 rsa 是 1977 年 由 mit 教 授 ronaldl.rivest,adishamir 和 leonardm.adleman共同开发

35、的，分别取自三名数学家的名字的第一个字母来构 成的。1976年提出的公开密钥密码体制思想不同于传统的对称密钥密码体制，它 要求密钥成对出现，一个为加密密钥(e),另一个为解密密钥(d),且不可能从其 中一个推导出另一个。自1976年以来，已经提出了多种公开密钥密码算法，其 中许多是不安全的，一些认为是安全的算法乂有许多是不实用的，它们要么是 密钥太大，要么密文扩展十分严重。多数密码算法的安全基础是基于一些数学 难题，这些难题专家们认为在短期内不可能得到解决。因为一些问题(如因了分 解问题)至今已冇数千年的历史了。公钥加密算法也称非对称密钥算法，用两对密钥：一个公共密钥和一个专 用密钥。用户要保

36、障专用密钥的安全；公共密钥则可以发布出去。公共密钥与 专用密钥是有紧密关系的，用公共密钥加密的信息只能用专用密钥解密，反z 亦然。由于公钥算法不需耍联机密钥服务器，密钥分配协议简单，所以极大简 化了密钥管理。除加密功能外，公钥系统还可以提供数字签名。公钥加密算法屮使用最广的是rsao rsa使用两个密钥，一个公共密钥， 一个专用密钥。如用其中一个加密，则可用另一个解密，密钥长度从40到2048bit 可变，加密时也把明文分成块，块的大小可变，但不能超过密钥的长度，rsa 算法把每一块明文转化为与密钥长度相同的密文块。密钥越长，加密效杲越好, 但加密解密的开销也大，所以要在安全与性能之间折衷考虑

37、，一般64位是较合 适的。rsa的一个比较知名的应用是ssl,在美国和加拿大ssl用128位rsa 算法，由于出口限制，在其它地区(包括中国)通用的则是40位版本。rsa算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决des 算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了 这个难题；还可利用rsa來完成对电文的数字签名以抗对电文的否认与抵赖； 同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据 信息的完整性。rsa算法很好的完成对电文的数字签名以抗对数据的否认与抵赖；利用数 字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。目 前

38、为止，很多种加密技术采用了 rsa算法，比如pgp （prettygoodprivacy）加 密系统，它是一个工具软件，向认证中心注册后就可以用它对文件进行加解密 或数字签名，pgp所采用的就是rsa算法。出此口j以看出rsa冇很好的应用。3.2 rsa算法的描述rsa使用了以大整数为模的同余指数运算。按照特定的方式选择一个 大整数n,明文（密文）分组是小于数n的非负整数。即用二进制表示时 分组长度必须小于或等于 。对于某个明文分组m和密文分组c,加密及 解密的形式如下：c = mod nm -cd mod n二（m"）“mod n二mmod n这里e称为加密指数，d称为解密指数。明

39、文发送方和接收方都必须 知道n的值。发送方知道e的值，而只有接收方知道d的值。这是一种公 开密钥为ku=e, n,且私有密钥为kr=d, n的公开密钥加密算法。要 使这个算法能够满足公开密钥加密的要求，必须符合如下条件：（1）有可能找到e、d、n的值，使得对所有m5有 ；（2）对于所有m5的值，要计算at于c相对来说是简单的；（3）仅知道e和n时，无法算出do需要找到具有下列形式的关系：med = mmodn给定两个互异的素数p和q,以及两个整数n和m,使得n=pq且0<m<n, m与n互素。由enler定理，有m 必）三 lmodn于是对于任意整数k,下列关系成立：戶5)+1 =

40、加心-1)(9-1)+1 = m mocj n其'i1（pn）是欧拉totient函数，表示不超过n且与n互素的整数个数。对于互异的素数p和q,有（p（pq） = （p-l）（q-l）。选择e、d使得ed = k(p(n) +1它等价于ed = 1 mod(p(n)也就是说d和e是以0（）为模的乘法逆元，d = e'1 mod(n) o 注意到ed = k（p（n +1耍求e与d均与0（斤）是互素的。综上所述可以给岀rsa方案。它的参数有:p、q：两个互异素数（私有,选择）n： n二pq（公开,计算出）e：满足 l<e<(p(n)及 gcd (p(n), e) =1

41、（公开,选择）d： d= el inod(n)（私有，计算出）私有密钥由d, n组成，公开密钥dhe, n组成。假设用户a公布了它的公开密钥，而用户b希累向a发送一个报文m（0<m<n）,那么b计算出c = m“（modn）并传输c。在收到这个密文时，用户a通过计算m = cj（modn）进行解密。现在来检验计算cj（modzz）确实恢复出明文m。选择了 e和d,使得el mod(p(h),即ed = 1 mod9(/2)所以可设ed = k(p(n) + 1当gcd （m, n） =1时，出euler定理口j得cd = (me)d modn = med modn = m modn

42、第io页共44页 当 gcd (m, n) h1 时，由 gcd (m, n) |n 知 gcd (m, n)二p 或 q。不妨 设 gcd (m, n)二p,则 p|m,令 m二sp, lwsq。因gcd (m, q)二1,由fermat定理可得m7-1 = 1 mod q于是(m7-1 三 1 mod q ,即m 如")三 1 mod q由此得m (m)+1 三 m mod q ,即 med 三 m mod q另一方面，由p|m可得med = 0 = m mod p因为gcd (p, q)二,由初等知识可得med = m mod pq即cd =med =mmodn下图总结归纳了

43、rsa算法的实现过程。1.密钥的产生选择人素数：p、qp和q是互异素数计算：n=pq计算：(p(n)= (p-1) (q-1)选择整数：egcd (<p(n), e) =1 ； 1<e<(p(n)计算：dd = el mod公开密钥：ku=e, n私有密钥：kr二d, n2.加密明0wm5密文:c = mc (mod n)3.解密密文：ow c<n明文：m = cd (modn) m=3.3 rsa计算方法现在转而讨论使用rsa时的计算复杂性问题。实际上需要考虑的问题有： 加密/解密、密钥的生成、大数运算的处理和索数的产生。下面就來讨论下以上 问题。3. 3. 1加密和

44、解密在rsa加密和解密都涉及计算一个整数的幕，然后模n。如果先对整数进行指数运算，然后再进行模n运算，那么中间结果将极其巨大。幸运的是, 可以利用取模运算的一个特性：(amod/2)x (/? modn)mod/t = (a x b)modn因而，可以对中间结果进行模n运算，这就使计算实际可行。另外一个考虑是指数运算的效率，因为在rsa中碰到的可能是非常大的指 数。为了了解如何才能提高效率，考虑计算兀”。直接的方法需要15次乘法：x16 = xxxxxxxxxxxxxxxx然而，可以只用4次乘法得到同样的最后结果。如果重复对每次的部分结果取平方,依次得到、x16o般地，假定希望算出/的值，其中

45、d和加是整数。如果将加表示为一个二进制数仪、"-»,那么冇：m 二go因而严=ya2am modn = )modn =匸3 mod/?)gogo3. 3.2密钥的生成在应用rsa密码体制之前，必须先生产生密钥，即必须先选择两个大索数p 与g,然后再选取相对较小的正整数一并计算出d。由于0与q得积pq = n是公开的，所以为了防止攻击者用穷搜索法获得p与q，与g必须是足够大的素数。因而，有效地获取大素数是实现rsa密码 体制需要解决的一个关键问题。然而，遗憾的是，目前还没有特别冇效的方法 可以产生任意打的素数。现在通常的办法是：随机选取一个适当大的奇数，然 后检验它是否为素数

46、，若非素数，则随机选另一个奇数检测它是否为素数，如 此继续，直到找到一个大素数为止。目前素性检测的方法基本上都是概率性的，即这些检测方法只能确定一个 给定整数可能是索数。但冇些检测方法口j使检测一个整数是索数的概率接近 1.0,比如附录中介绍的非常有效且被广泛采用的miller-rabin算法。2002年 印度理工大学的3位学者提出一种(多项式时间)快速确定性算法，可以证明 一个整数是素数。其效率不如概率算法高。确定了足够大的素数、q后，就可借助扩展的eucidean算法来求得满足条件l<e<(p(n)及与卩(n)互素的e ,并求得d = el mod(p(n)。3. 3. 3大数

47、运算处理rsa依赖人数运算，目前主流rsa算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数 必须小于等于 64 位，即：oxffffffffffffffff,也就是 18446744073709551615, 这远远达不到rsa的需要，于是需要专门建立大数运算库来解决这一问题。最 简单的办法是将大数当做数组进行处理，数组的各元素也就是大数每一位上的 数字，通常采用最容易理解的十进制数字0-9.然后对“数字数组”编写加减乘 除函数。但是这样做效率很低，因为二进制为1024位的大数在十进制下也有三 百多位，对于任何一种运算，都需要在两个有

48、数百个元索的数组空间上多次重 循环，述需要许多额外的空间存放计算的进退位标志及中间结果。另外，对于 某些特殊的运算而言，采用二进制会使计算过程大大简化，而这种大数表示方 法转化成二进制显然非常麻烦，所以在某些实例中则干脆采用二进制数组的方 法來记录大数，当然这样效率就更低了。一个有效的改进方法是将大数表示为 一个n进制数组，对于目前的32位系统而言n可以取值为2的32次方，即 0x100000000,假如将一个二进制为1024位的大数转化成0x100000000进制， 就变成了 32位，而每一位的取值范围不再是二进制的09,而是 0-0x ffffffff,我们正好可以用一个32位的dword

49、 (如：无符号长整数， unsigned long)类型来表示该值。所以1024位的大数就变成一个含有32个元 素的dword数组，而针对dword数组进行各种运算所需的循环规模至多32次而 已。如人数 18446744073709551615,等于 oxffffffffffffffff，其表示方式就 相当于十进制的99：有两位,只是每位上的元素不是9,而都是oxffffffffo 而 18446744073709551616 等于 0x000000010000000000000000,就相当于十进 制的100：冇三位，第一位是1,其它两位都是0在实际应用中，“数字数组” 的排列顺序采用低位在

50、而高位在后的方式，这样，大数a就可以方便地用数学 表达式来表示其值：x = y x/ (r = 0x100000000,0 << r)1=()任何整数运算最终都能分解成数字与数字z间的运算，在0x100000000进 制卜其“数字”最大达到oxffffffff,其数字与数字z间的运算，结果也必然 超出了目前32位系统的字长。然而在vc卄中，存在一个int64类型可以处理 64位整形，就需要采用更小的进制方式来存储大数，例如16位的word类型可 以用来表示0x10000进制。但效率更高的办法还是采用32位的dword类型。3. 3.4素数的产生素数的生成流程可分为素数搜索、素数预筛

51、选和素数的测试三个阶段。1. 素数搜索方法大索数的分布不均匀，并h对一个大素数进行索性检测也很费吋，这使人 素数的产生很慢。产生一个rsa密钥需将大部分的时间都屁在素数的寻找上， 所以好的搜索方法是提高索数生成速度的重要手段。常用的搜索方法有随机搜 索和随机递增搜索法两种。(1) 随机搜索法：随机产生一个奇数厂进行素数测试，若是素数，则结束;否则，重新随机产生一个奇数进行素性测试，直至找到一个素数戸。（2）随机递增搜索法：随机产生一个奇数，对于该数起点的奇数依次进行 测试，直至找到一个索数。分别釆用以上两种方法进行搜索，并各自产生1000个1024位的素数。搜 索次数统计结果如表3. 1.可见

52、，随机递增搜索法的搜索次数是随机搜索的85%, 随机递增搜索法优于随机搜索法。表3.1随机搜索法和随机递增搜索法的比较随机搜索法次数随机递增搜索法次数110214528462351000682184平均363296次测试后，被测试数是合数的可能性不超过1/2。lehmann算法是一种更简单 的测试，和solovay-strassen算法一样，利用lehmann算法对被测数进彳亍r次 测试后，被测试可能是索数的错误风险不超过1/2。miller-rabin算法是一个 容易实现且被广泛使用的算法，它基于gary miller的部分想法，而由michael rabin发展完善。和前面两种算法比较起来

53、，miller-rabin算法的运算速度更 快，且通过测试后被测数是素数的准确率更高（通过r次测试后，错误概率不 超过1/4）。rabin-miller测试的算法思想如下：首先选择一个代测的随机数p，计算b, b是2整除p-l的次数。然后计算m,使得n=l+（2 b）mo（1）选择一个小于p的随机数a。（2）设 j二0 口 z二af mod p。（3）如果z二1或z二p-1,那麽p通过测试，可能使素数。（4）如杲j>0且z二1,那麽p不是素数。（5）设 j二j+1。如果 j 且 z<>p-l,设 z二z"2 mod p,然后回到（4）。如果 z二pt, 那麽p通过测

54、试，可能为素数。（6）如果j二b且z<>p-l,不是素数。如表3.2,可以看到miller-rabin中,最耗时的模幕运算只有一次,因此 在速度上是有一定优势的（表中的p是随机二进制序列中某处连续出现的“0” 的个数，通常p不会太大）。表3. 2素性测试算法比较减法移位模幕模乘miller-rabin1p11lehmann112无3.4 rsa的安全性及分析密码学所讨论的系统，其实安全性是重要的。再好的密码系统，如果安全性不好则也是一文不值。同时，密码系统的安全性也很难用理论证明（事实上 证明一个安全系统是安全的很难，但若该系统不安全，证明它是不安全的则很 容易）。如今rsa从提出

55、到现在已经近而是年，经历了各种攻击和考验，逐渐为人 们接受，普遍认为是目前最优秀的公钥密码体制之一。然而在一定环境条件下, rsa实现细节的疏忽会导致对rsa算法的冇效攻击。因此，对rsa体制实现的 各个环节进行个充分的考虑，避免安全性缺陷是相当有必耍的。3.4.1 rsa的参数选择rsa算法的安全性等价于分解n的困难性，但在实际的应用中，在很多吋 候是因为算法实现的细节漏洞导致的，因此，在rsa算法构造密码系统时，为 了保证系统的安全需要仔细地选择使用的参数。根据rsa加解密过程，其屮主 耍的参数有三个：模数n,加密密钥e,解密密钥d。5.模数n的确定rsa模数n = p *§是r

56、sa算法安全性的核心。如果模数n被分解，则rsa 公钥密码体制将立刻被攻击，所以选择合适的n是实现rsa算法的重耍环节。一般來说，模数n的选择可以遵守以下4个原则：（1）n = p%q ,要求p和q为强索数；强素数指存在两个大素数p, %使得川（卩-1），几i （卩-1）;存在4个大素数 厂,环厂2，$2,使得人丨（卩1 一1），$1 1（pl +1），厂2丨（“2 -1）,$2 1（02 +1）；称 rl9sl9r29s2 为三 级素数，卩,卩2为二级素数。（2）和g之差要大，相差儿位以上；（3）p_l与g_l的最大公因子要小；（4）和q要足够大。这是应用rsa算法要遵守的最基本原则，如果rsa算法是安全的，则 n = pq必须足够大，使得因式分解模数n在计算上是不可行的，下面是一般 性使用原则：（1）临时性384bit,经过努力可以破译；(2) 商用性512bit,可由专业组织破译；(3) 军用性1024bit,专家预测十年内不口j破译。jadith moore给出了使用rsa时有关模数的一些限制：(1) 若给定模数的一个加解密密钥指数