RSA加密课程设计.doc

武汉工程大学 计算机科学与工程学院综合设计报告设计名称： 软件应用综合设计 设计题目： RSA非对称密码算法的设计与实现 学生学号： 0 7 0 5 0 5 0 1 1 4 专业班级：计算机科学与技术（信息安全方向）01班学生姓名： 学生成绩： 指导教师（职称）： 肖 利 芳（讲师） 课题工作时间： 2010.12.27 至 2011.1.7 说明：1、报告中的第一、二、三项由指导教师在综合设计开始前填写并发给每个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、指导教师评语一栏由指导教师就学生在整个设计期间的平时表现、设计完成情况、报告的质量及答辩情况，给出客观、全面的评价。4、所有学生必须参加综合设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩小组成员应由2人及以上教师组成。5、报告正文字数一般应不少于5000字，也可由指导教师根据本门综合设计的情况另行规定。6、平时表现成绩低于6分的学生，其综合设计成绩按不及格处理。7、此表格式为武汉工程大学计算机科学与工程学院提供的基本格式（适用于学院各类综合设计），各教研室可根据本门综合设计的特点及内容做适当的调整，并上报学院批准。成绩评定表学生姓名： 李 志 学号： 0705050114 班级： 07信息安全01班 类别合计分值各项分值评分标准实际得分合计得分备注平时表现1010按时参加综合设计，无旷课、迟到、早退、违反实验室纪律等情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在3篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩： 分 补充说明： 指导教师： （签字）日 期： 年 月 日答辩记录表学生姓名： 李 志 学号： 0705050114 班级： 07信息安全01班 答辩地点： 计算机大楼 答辩内容记录：答辩成绩合计分值各项分值评分标准实际得分合计得分备注2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。答辩小组成员（签字）： 年 月 日指导教师评语指导教师： （签字）日 期： 年 月 日一、综合设计目的、条件、任务和内容要求：目的：课程设计是课程教学中的一项重要内容，是完成教学计划达到教学目标的重要环节，是教学计划中综合性较强的实践教学环节，它对帮助学生全面牢固地掌握课堂教学内容、培养学生的实践和实际动手能力、提高学生全面素质具有很重要的意义，让我们更加了解各种加密算法的实现，把所学过的知识更加融会贯通。密码学是一门理论性和实用性都很强的课程，也是密码学课程设计环节应占有重要的地位，密码技术为现代电子商务、网络安全等必修之工具。本课程设计还应达到以下教学目的：1使学生对于密码学算法如何实现加密与解密有更加深入的理解； 2提高学生在应用C语言、数据结构编写大型算法的能力；任务：实现RSA非对称公钥密码算法的设计和实现，并能够在Visual C+6.0版的软件开发环境中运行并得到正确的结果内容要求：密码学课程设计是一个实践环节，它使学生自己能够实现出可以加密和解密的编码，并能够正确的理解源代码的含义和一些主要函数的作用和用法，在理解的基础上正确完整的编写出程序代码并在编写环境中正常的运行出正确的结果，编写环境为Visual C+6.0版。要求学生按教师的要求，认真编写出RSA非对称算法的程序代码，并运行出结果，完成课程设计的报告及设计论文。 指导教师签字： 年 月 日二、进度安排：本次课程设计安排时间为2周：18周的周一至周五，安排学生自主查询相关资料，借助课外资料书，理解RSA非对称加密算法实现的基本原理，并且编写出正确实现RSA非对称加密算法的源程序代码。19周一至周四：查资料，并按要求撰写课程设计报告论文，周五进行课程设计的答辩并提交课程设计论文和报告。三、应收集资料及主要参考文献：应收集的资料：密码学一些基本知识，有关RSA非对称公钥密码学算法编码用到的一些函数知识如：加密函数，解密函数，还有一些有关RSA非对称密码算法的工作原理的资料参考文献：1张福泰.密码学教程.武汉：武汉大学出版社,20062Michael Welschenbach.编码密码学加密方法的C与C+实现. 北京：电子工业出版社,20033杨波.现代密码学.北京：清华大学出版社，20074王育民.通信网的安全理论与技术.西安：西安电子科技大学出版社，1999 5冯登国.密码学导引北京：科学出版社，1999年6对称密码学及其应用. 北京：北京邮电大学出版社，2009年7. 卢开澄计算机密码学北京：清华大学出版社，20038 何明星，林昊RSA算法原理及其实现重庆：重庆师范大学学报，2003武汉工程大学计算机科学与工程学院 综合设计报告目 录摘 要 Abstract .第一章 绪论. 11.1 课题背景 .11.2 课题意义 .1第二章RSA应用及文件加密分析 . 32.1 设计原理 .3 2.1.1 RSA非对称密码算法实现 .32.1.2 RSA非对称密码算法分析 .4 2.2 文件加密使用RSA的意义 .4第三章RSA加密软件的设计与实现 . 63.1 需求分析与总体设计 .6 3.2 各部分的设计与开发 . 73.2.1 实现RSA算法的C+核心类库. 73.2.2封装C+核心类库的DLL组件. 14第四章软件整体测试与分析改进 .154.1 软件数据测试 .15 4.1.1 密钥生成测试 . 154.1.2 数据输入输出测试 . 164.1.3 加密解密测试 . 174.2 性能分析与改进优化 .19总 结 .20致 谢 .21 参考文献 .22附录 主要程序代码 .23摘 要分析RSA算法的应用现状，论证文件加密应用RSA算法的可行性和意义。设计一套完整实用的RSA文件加密解决方案，具体编码实现。对RSA算法进行研究，从常规RSA算法出发，用C+实现RSA加密算法类库，并在32位windows平台封装成组件。在.Net平台引用此组件，实现可以对任意文件进行RSA加密操作的窗体应用程序。经过加密的文件以及密钥文件都是文本文件。给出关键类类图、整个应用程序的结构描述文档、关键模块流程图、较详细的接口文档、所有源代码。对应用程序进行测试，对测试结果进行分析研究，进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在windows运行的可以用指定密钥对任意文件进行RSA加密并可解密的完整应用程序，和一些相关的可移植组件。关键词： RSA； RSA算法； 文件加密； 加密成文本AbstractDo research about the application area of RSA encryption and reason that RSA can be used for file encryption. Design a RSA file-encrypt solution and complete an application on Microsoft Windows. Design a C+ class based on normal RSA algorithm. And make a DLL module based on the class. Then complete a .Net Framework window-application using that DLL. The application can encrypt any file and decrypt them. The file after encryption can be saved as a text file. And the encryption-keys also can be saved as text.Provide pivotal classes chart, project description, core algorithm flowchart, all source code, and module interfaces document. Do application performance test and record the performance data. Analyze the result then optimize core algorithm and improve the application. Finally, create a practical application using RSA algorithm that can encrypt and decrypt any file. And several modules in the project can be reuse by other applications. For instance, the C+ class can be cross-compiled for handheld devices, the DLL can be referenced by other win32 applications, and the .Net class can be easily referenced by web server applications or web services.Keywords：RSA； RSA algorithm； File encryption； Encrypt to text 第一章 绪论1.1 课题背景随着计算机信息技术的蓬勃发展，作为信息采集、存储、处理和传输的媒体，计算机及网络应用逐步延伸到社会生活的方方面面。当人类越来越感受到计算机系统功能的强大，不得不感叹于信息技术带来的方便快捷的同时，各种忧虑也渐渐产生：已经习惯性依赖于计算机的人们离开它还能生存吗？信息战将对国防安全、军事领域产生什么影响?信息诈骗和其他信息犯罪将如何改变人们的日常生活? 这些问题都属于计算机信息安全的范畴。起初，计算机系统的安全主要是指硬件的安全保护。随着信息所发挥的价值日益为人们所了解，人们的目光转移到在计算机系统中存储、传输的信息的安全，包括防止信息泄漏和非法慕改等。数据库集中存放和管理大量信息，其安全性对于整个计算机信息系统至关重要。为了保证数据安全，人们在不同层面运用了各种安全措施，这些防范措施分别可以在一定程度上防止某种安全威胁。但是，在操作系统、数据库和网络的层层防护之下，仍然无法保证数据库数据的安全。因为通常数据库中的数据最终是以文件形式存储在计算机上的，这些文件大部分是多个用户可读可写的，一旦网上黑客通过某种途径进入系统就可以直接读取数据文件或存储介质，从中窃取数据或利用非法软件篡改数据库文件内容。信息的传输则通过公共信道。这些计算机系统和公共信道是不设防的，是很脆弱的，容易受到攻击和破坏，信息的丢失不容易被发现，而后果是极其严重的。如何保护信息的安全已不仅仅是军事和政府部门感兴趣的问题，各企事业单位也愈感迫切。而密码是有效而且可行的保护信息安全的办法，有效是指密码能够做到使信息不被非法窃取，不被篡改或破坏，可行是说它需要付出的代价是可以接受的。因此密码学的研究就成为一个重要的来解决信息安全问题的一种手段了，而且有着重要的地位1.2课题意义：信息是一种资源，也是一种财富。在现代社会中，信息处理和通信技术日益发展保护信息的安全，特别是保护重要信息的安全，已成为国际社会普遍关注的重大问题。但前由于信息保护措施的不力或失误，世界各国所遭受的损失是巨大的，在商业，交通，工业，科学技术，国防，外交等部门的大量事例已充分说明了这一点。因此，对于信息的加密保护就显的尤其重要。数据加密技术已随着计算机技术的迅猛发展，由早期的军事和外交领域，逐步伸展到交通、工业经济、科学技术、社会安全和公共生活的各个领域，成为现代社会中保护信息的重要手段和工具。信息保护的现实需要，使得数据加密算法和技术迅速进入了现代社会，了解并有效使用数据加密算法技术已成为计算机技术和通信领域的专业技术人员和广大用户的迫切需求，这是信息化社会发展阶段的重要标志，数据库加密也是信息安全必不可少的安全手段。从六十年代数据库技术的产生到广泛的应用，人类对数据库安全的研究历经了三十多年，已经研究出很多的数据库安全及保密技术，数据库安全及其数据安全日益被重视。可是又一个问题显现出来，对于数据及信息本身来讲自然是安全级别越高越好，但是过高的安全级别势必会给数据及信息资源的共享和使用带来不便。RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman。虽然自1978年提出以来，RSA的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今（2006年）未被完全攻破。随着越来越多的商业应用和标准化工作，RSA已经成为最具代表性的公钥加密技术。VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。当今公钥加密更广泛应用于互联网身份认证，本课题将公钥加密算法RSA应用于小型文件加密。将任意文件加密成文本的解决方案，使其使用更加灵活。整个工程的分层设计，给引用移植和后续开发带来便利。如果我们想通过Internet上的公众论坛或邮件发送重要保密信息给某人。例如发送一个银行帐号和密码给某人。这种情况要保证安全，在当今互联网络上是比较棘手的。如果用公众论坛直接留言给指定用户，论坛管理员和服务器管理员通常有方法看到数据。如果发送邮件，虽然传送过程是加密的，但是密码毕竟是由邮件服务器维护，所以系统管理员通常也有办法看到内容。问题的关键在于我们所有的数据包括密钥保存在服务器之上。在这种情况下，我们需要使用公开密钥方式，并自己维护私有密钥。RSA文件加密可以灵活的解决这些问题。例如，我们可以将任意一个文件用某人的公开密钥加密变换成一段可以复制粘贴的文本，然后粘贴在公众互联网上，对方只需把需要解密的文本复制保存成一个文本文件，在本地机用自己的私有密钥解密即可。第2章 RSA应用及文件加密分析2.1 设计原理2.1.1 RSA非对称密码算法实现RSA算法可以简单叙述如下：取素数p，q，令n=pq.取与(p-1)(q-1)互素的整数e，由方程de=1 (mod (p-1)(q-1)解出d，二元组(e,n)作为公开密钥，二元组(d,n)作为私有密钥b=ae mod n，c=bd mod n.附录中给出了证明a=c (mod n).RSA公开密钥加密算法自20世纪70年代提出以来，已经得到了广泛认可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规范。RSA作为最重要的公开密钥算法，在各领域的应用数不胜数。RSA在硬件方面，以技术成熟的IC应用于各种消费类电子产品。RSA在软件方面的应用，主要集中在Internet上。加密连接、数字签名和数字证书的核心算法广泛使用RSA。日常应用中，有比较著名的工具包Open SSL(SSL，Security Socket Layer,是一个安全传输协议，在Internet上进行数据保护和身份确认。Open SSL是一个开放源代码的实现了SSL及相关加密技术的软件包，由加拿大的Eric Yang等发起编写的)。Open SSL应用RSA实现签名和密钥交换，已经在各种操作系统得到非常广泛的应用。另外，家喻户晓的IE浏览器，自然也实现了SSL协议，集成了使用RSA技术的加密功能，结合MD5和SHA1，主要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎都在使用RSA技术。RSA更出现在要求高度安全稳定的企业级商务应用中。在当今的企业级商务应用中，不得不提及使用最广泛的平台j2ee。事实上，在j2se的标准库中，就为安全和加密服务提供了两组API：JCA和JCE。 JCA (Java Cryptography Architecture)提供基本的加密框架，如证书、数字签名、报文摘要和密钥对产生器； JCA由几个实现了基本的加密技术功能的类和接口组成，其中最主要的是java.security包，此软件包包含的是一组核心的类和接口，Java中数字签名的方法就集中在此软件包中。JCE(Java Cryptography Extension) 在JCA的基础上作了扩展，JCE也是由几个软件包组成，其中最主要的是javax.crypto包，此软件包提供了JCE加密技术操作API。用户程序可以直接使用java标准库中提供的API进行数字签名和证书的各种操作。单机应用程序使用RSA加密尚比较少见，例如使用RSA加密任意一个文件。2.1.2 RSA非对称密码算分析通过1.2节的论述，不难看出RSA当今的应用多在于数字签名和证书等方面。之所以只应用于这些短小数据的加密解密，是因为RSA算法加密极慢，速度是DES对称密钥加密速度的千分之一左右。正是因为这样，把RSA应用于普通文件加密的想法一直被忽略。通常文件被想象成大数据块，但是实际上在日常应用中，有些极其重要的文本资料是并不太大的，比如因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。虽然RSA加密运算的速度十分慢，但是在PC性能越来越好的今天，对于几千字节的数据进行一次几百位密钥的RSA加密，所消耗的时间应该是可以接受的。下面结合大数运算程序的调试，从理论上简单的分析消耗时间。其实从一个简单的角度来说，既然RSA用于数字签名可行，那就完全可以用于同样大小的普通文件。对于较大的文件，如果分成与数字签名同样大小的段(这里假设数字签名较短，不分段一次计算加密完成)，分开的各段逐一进行加密运算，那所需要的时间也只是按文件大小线性的增长。通常数字签名为几十字节，加密运算并不需要很长的等待，这就说明对于几百字节或一两K字节大小的文件来说，如果进行RSA加密，并不会是非常漫长的工作。当然，如果文件更大，加密就显得十分漫长了。比如按前面叙述的45毫秒大数运算程序推理，加密1M字节大小的文件需要约1天的时间。所以，要在普通PC用几百位以上的长密钥RSA加密文件，文件不能过大，一般可以接受的上限是几KB。如果要在较短时间内加密大文件，需要缩短密钥长度以减小运算量，这将带来安全性隐患。2.2 文件加密使用RSA的意义如之前所述，小型文件加密可以使用RSA。比如，因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。可行的方法未必是必要的，本小节讨论何种文件适合用非对称密钥加密，即RSA加密文件的意义所在。对于前面叙述的带有重要信息的小型文本和二进制数据的维护，如果不加密，将无法放心的保存在计算机上，尤其是连网的或机房里的公共计算机。如果借助功能强大的大型多用户数据保护程序维护几个小型文件，显得十分烦琐，好比杀鸡用牛刀。如果采用对称密钥加密，即加密解密的密钥相同，只适合部分情况。在某些情况下，使用对称密钥加密文件，交流使用不够方便。比如，张三由于某种原因，需要将自己的某个文件在公共计算机上留给李四，而不希望别人看到内容。如果采用对称密钥加密，张三和李四提前约好一个密码就可以。但是如果张三想要在同一台公共计算机上再留一个秘密文件给王五，而不希望别人看到，就要和王五另外约定一个密码。如果需要在这台公共计算机上留十个文件给不同的人，自己就要记和十个人约定好的密码，这样以来交流起来不够方便，因为对于张三，要自己维护太多的密钥。非对称密钥(公开密钥方式)恰好解决这样的问题。只要大家都在这台计算机或这台计算机可以访问到的地方，留下自己的公开密钥，一切就变的容易解决了。张三要留给李四的文件，就用李四的公开密钥加密，要留给王五的文件，就用王五的公开密钥加密。李四和王五只要把留给自己的文件用自己的私有密钥解密，就可以得到留给自己的文件了。显然，非对称密钥体制更适合多用户交流，而将这种加密方式直接应用于文件加密，使我们在公开场合的交流更加灵活方便。我们可以将自己的私有密钥通过DES加密后保存在自己的移动磁盘上，使用的时候只要将其解密读取即可，用完后立即从当前操作环境清除。这样，我们自己维护自己的私有密钥，利用简单并且公开的方式，可以安全传送任意小型数据，包括一切二进制文件。所以，对于使用小型文件进行数据交换的情况，更好的方案是通过一个小型应用程序对这些文件进行非对称密钥加密。为了适合前面叙述的在公共BBS与特定的某人交流重要保密信息的情况，加密生成的数据应该是文本，这样可以方便复制粘贴。综上所述，使用前面叙述的方式加密文件有两点重要意义：应用非对称密钥加密任意文件，使非对称密钥的应用不仅仅局限于互联网络。非对称加密后的数据变换成文本，使得我们可以通过几乎任何方式安全传递任意文件，比如在只有http的环境使用xml方式。第3章 RSA加密软件的设计与实现概要：运用C+编写出一个加密和解密的密钥对一段明文进行加密和解密来达到隐秘的传送信息的目的，运用RSA非对称密码算法和系统来完成整个设计要求3.1 需求分析与总体设计经过2.1.1节的论述，我们可以将对软件的要求总结如下：可以按要求的位数生成非对称密钥。可以保存密钥和装载密钥，密钥保存为纯文本。可以用指定密钥以RSA算法加密任意一个文件，加密生成的数据为纯文本。可以装载加密过的文件，并用指定的密钥解密还原出原文件。提示信息完整、操作舒适、图形界面雅观按上述描述，给出Use Case和Statechart如图3-1。图3-1 本项目的 Use Case和Statechart根据以上分析，一般来说，需要进行编码的程序有 RSA密钥生成 RSA加密解密 任意文件的读取和保存操作 各环节必要的数据编码转换 图形操作界面。3.2各部分的设计与开发3.2.1 实现RSA算法的C+核心类库1.大数存储和四则运算根据RSA算法的要求，为了实现大数的各种复杂运算，需要首先实现大数存储和基本四则运算的功能。当今开源的大数运算C+类有很多，多用于数学分析、天文计算等，本文选用了一个流行的大数类型，并针对RSA算法和本项目的具体需要对其进行了扩充和改进。下面简单介绍大数存储和四则运算的实现原理。最先完成的功能是大数的存储，存储功能由flex_unit类提供。和普通的类型一样，每一个大数对应一个flex_unit的实例。类flex_unit中，用一个无符号整数指针unsigned * a指向一块内存空间的首地址，这块内存空间用来存储一个大数，所以可以说，大数是被存储在一个以unsigned为单元的线性组中。在方法void reserve( unsigned x )中通过C+的new来给a开辟空间，当flex_unit的实例中被存入比当前存储的数更大的数时，就会调用reserve来增加存储空间，但是当flex_unit的实例中被存入比当前存储的数更小的数时，存储空间并不会自动紧缩，这是为了在运算的时候提高执行效率。结合指针a，有两个重要的无符号整数来控制存储，unsigned z和unsigned n，z是被分配空间的单元数，随数字变大不断增大，不会自己紧缩，而n是当前存储的大数所占的单元数，组成一个大数的各unsigned单元的存入和读出由set、get方法完成，变量n是只读的。类型unsigned在32位机是32位的，所以对于flex_unit这个大数类来说，每个大数最大可以达到 个字节长，这已经超过了32位机通常的最大内存容量，所以是足够进行RSA所需要的各种运算的。图3-2形象的说明了大数存储类flex_unit对大数的管理。 *a unsigned类型的指针大数占n个单元开辟了z个单元大的内存内存空间图3-2 flex_unit对大数的管理在flex_unit的存储功能基础上，将其派生，得到vlong_value，在vlong_value中实现四则运算函数，并实现强制转换运算符unsigned，以方便大数类型和普通整数的互相赋值。当大数被强制转换为unsigned时，将取其最低四字节的值。四则运算实现的原理十分简单，都是按最基本的算术原理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加，就是低位单元对齐，逐单元相加并进位，减法同理。而乘除法和取余也都是按照竖式运算的原理实现，并进行了必要的优化。虽然实现了四则运算函数，但是若是程序里的运算都要调用函数，显得烦琐而且看起来不美观，所以我们另写一个类vlong，关联(Associate，即使用vlong_value类型的对象或其指针作为成员)vlong_value，在vlong重载运算符。这样，当我们操作vlong大数对象的时候，就可以像使用一个简单类型一样使用各种运算符号了。之所以将vlong_value的指针作为成员而不是直接构造的对象，也是为了提高执行效率，因为大型对象的拷贝要消耗不少机器时间。2.大数幂模与乘模运算Montgomery幂模算法在实现了vlong类型后，大数的存储和四则运算的功能都完成了。考虑到RSA算法需要进行幂模运算，需要准备实现这些运算的方法。所以写一个vlong的友元，完成幂模运算功能。幂模运算是RSA 算法中比重最大的计算，最直接地决定了RSA 算法的性能，针对快速幂模运算这一课题，西方现代数学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模的性质，先将幂模运算化简为乘模运算。通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变成偶数，然后再对半分，例如求D=，E=15，可分解为如下6个乘模运算。 归纳分析以上方法，对于任意指数E，可采用如图3-3的算法流程计算 。开始D=1;P=C mod nE0?E为奇数?E=E-1E为偶数?E=E/2YesNoResult=D结束YesYesNoNo图3-3 幂模运算分解为乘模运算的一种流程按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。求的值开始D = 1P = 2 mod 17 = 2E = 15E奇数D = DP mod n = 2P = PP mod n = 4E = (E-1)/2 =7E奇数D = DP mod n = 8P = PP mod n = 16E = (E-1)/2 =3E奇数D = DP mod n = 9P = PP mod n = 1E = (E-1)/2 =1E奇数D = DP mod n = 9P = PP mod n = 1E = (E-1)/2 =0最终D = 9 即为所求。求的值开始D = 1P = 2 mod 17 = 2E = 8E偶数D = 1P = PP mod n = 4E = E/2 =4E偶数D = 1P = PP mod n = 3E = E/2 =2E偶数D = 1P = PP mod n = 9E = E/2 =1E奇数D = DP mod n = 9P = 不需要计算E = (E-1)/2 =0最终D = 9 即为所求。观察上述算法，发现E根据奇偶除以二或减一除以二实际就是二进制的移位操作，所以要知道需要如何乘模变量，并不需要反复对E 进行除以二或减一除以二的操作，只需要验证E 的二进制各位是0 还是1 就可以了。同样是计算，下面给出从右到左扫描二进制位进行的幂模算法描述，设中间变量D,P,E的二进制各位下标从左到右为u,u-1,u-2,0。Powmod(C,E,n) D=1; P=C mod n; for i=0 to u do if(Ei=1)D=D*P(mod n); P=P*P(mod n); return D;选择与模数n互素的基数R=2k，n满足2k1n2k， n应为奇数。并且选择R-1及n，满足0 R-1n, 0 nn,使得 RR-1-nn1。对于0mRn的任意整数,Montgomery给出求模乘法mR-1 mod n 的快速算法M(m):M(m) if (tn) return (t-n); else return t;因为，故t为整数；同时，得。由于，M(m) 中t结果范围是0t=n) x -= n;return x;exp(C,E,n) D=R-n; P=C*R mod n;i=0; while(true) if(E的当前二进制位Ei=1)D=M(D*P); /从低位到高位检测二进制位i+=1;if(i=E的二进制位数)break; P=M(P*P);return D*R-1 (mod n);在具体的实现中，对应monty类的mul和exp方法。全局函数modexp初始化monty对象并调用其exp方法，使用的时候直接调用modexp即可。3.寻找素数Eratosthenes筛选与Fermat素数测试首先在需要寻找素数的整数范围内对整数进行筛选，把所有确知为合数的整数排除出去。程序中构造了一个数组b，大小为一轮素数搜索的范围，记搜索范围大小为SS。b0到bSS分别对应大数start到start+SS。b中所有元素先初始化为1，如果对应的大数确定为合数，就将b中对应的元素置为0。最后，只需对那些b中为1的元素对应的大数进行比较确切的素数测试即可，只要被测试的数是素数概率达到一定门限，就判这个数为素数。这样做既保证了这段程序可以在短时间内执行完，又保证了可以以比较高的准确度得到素数。函数find_prime先把b的所有元素赋值为1，然后按参数start给标记数组b的各元素赋0值。下面描述标记数组b的赋0值算法。首先，在类Prime_factory_san被构造的时候，构造函数中从2开始搜寻一些小素数，记录在数组pl中，共记录NP个。这些小素数用来当作因子，他们的倍数将被从大素数搜索范围内剔除(即把数组b的对应元素标记为0)，剔除的程序代码如下。 for (i=0;inp;i+) unsigned p = pli; unsigned r = start % vlong(p); if (r) r = p - r; while ( r 0 x=r图3-4 在素数搜索范围内剔除小素数因子p的倍数接下来，对可能为素数的数(即标记数组b中值为1的元素对应的数)进行素数测试。取一个与p互素的整数A，对于大素数p来说应该满足Ap-1mod p=1，但是我们把p代入一个大整数，满足这个关系的数不一定是素数。这时我们改变A，进行多次测试，如果多次测试都通过，这个数是素数的概率就比较大。按这种原理，我们编写素数测试函数如下。int is_probable_prime_san( const vlong &p ) const rep = 4; /测试次数 const unsigned anyrep = 2,3,5,7 ; /测试用的底数 for ( unsigned i=0; irep; i+=1 )if ( modexp( anyi, p-vlong(1), p ) != vlong(1) ) return 0; /modexp是幂模函数，按上一小节叙述的算法编码。/这里modexp计算anyip-1mod p。 return 1;测试通过，程序就判定这个数为找到的素数，将找到的素数返回给上层程序使用。在这里其实有一个不可忽视的问题，就是得到一个测试通过的合数。对于这种情况，RSA算法加密解密是否还可以实现，是一个需要从数学角度论证的问题。因为得到素数的概率很高，经过一整天的生成密钥和加密操作，没有发现失败的密钥， 所以本文暂没有对这个问题进行讨论。综上所述，总结素数寻找的流程，如图3-5所示。 开始按start参数初始化标记数组bSS ; i=0计数iSS?bi=1?判定为素数?start+=1;i+=1结束返回素数寻找结果startYesYesYesNoNoNo图3-5 函数find_prime寻找素数的流程框图得到了大素数，即RSA算法中的p、q，我们就可以计算出密钥，进行加密等操作了。4.按常规RSA算法实现加密与解密最后，类RSA_san基于前面的准备工作，实现RSA密钥生成和加解密的功能为了方便阅读，整个类的源程序中，所使用的变量字母均和RSA算法协议中一致。在类RSA_san的构造函数里，执行准备一对随机密钥的操作。之后可以直接使用类的其他成员进行RSA加解密操作，也可以载入以前保存的密钥或再次随机生成密钥。类中各成员频繁的用到字符串和vlong类型的转换，因为大数是用字符串置入的，而把大数读出，也是保存在字符指针指向的一段内存空间里，所以也是字符串。所以，需要实现一系列的编码转换函数，比如将unsigned指针指向的一段空间里保存的一个大数，表示成十六进制形式的字符串文本。编码转换通常是用C风格的指针操作和sprintf函数来完成。需要加密和解密的数据也是通过字符串参数置入的。由于字符串的结尾字符“0”实际上也可能是需要加密的数据，所以置入的串长度并不能以“0”来决定，程序里引入一个unsigned类型的参数来决定置入的串长度，这样就解决了加密连0数据时候被截断的问题。因为是对文件加密的软件，需要加密的数据通常并不止几字节，这时由上层程序将数据按用户的设置分块，分别加密或解密。本软件默认的分块大小是1字节，即逐个字节作为参数，调用C+核心模块中的方法。3.2.2 封装C+核心类库的DLL组件在Visual Studio当前的解决方案中以VC+创建一个win32dll工程，将测试好的实现RSA加密算法的C+核心类库中的所有文件加入到此工程下，新建一对cpp和h文件，把可能用到的功能全部规划为新文件中的全局函数，并以C接口导出，即_declspec(dllexport)。由于核心类库的对外功能都使由RSA_san类提供的，所以在新cpp文件中全局的声明一个RSA_san类的对象指针(RSA_san *WRSA)，全局函数int start_RSA_san()初始化*WRSA对象，在初始化成功后，其他全局函数通过调用*WRSA对象的公开方法实现各种功能，如加密、读取密钥等。在关闭上层引用程序以前，应执行int finish_RSA_san()来释放WRSA，该函数执行delete WRSA的操作。其他接口函数的使用见DLL接口文档。另外，DLL组件可以自己在全局函数中实现一些