毕业设计（论文）-RSA算法的软件实现.doc

毕 业 设 计题 目 RSA算法的软件实现 姓 名 学号 所在院(系) 数学与计算机科学学院 专业班级 信息与计算科学1101班 指导教师 完成地点 陕西理工学院 2015年 5 月10日陕西理工学院毕业设计RSA算法的软件实现作者：（陕西理工学院数学与计算机科学学院信息与计算科学专业1101班，陕西 汉中 723000）指导教师： 摘要 随着计算机网络的快速发展，计算机网络资源的共享程度变得越来越强，网络管理的重要性变得越来越突出，网络的安全问题也就接踵而来。如何有效的利用网络资源，提高网络的经济效益，控制网络的风险，为用户提供有效、可靠、安全、综合开放的便携式服务；以及随后发展起来的一些新兴技术，如网络安全技术，加密与认证技术，防火墙技术与网络安全的入侵检测，计算机病毒的入侵与防护等，均是目前网络安全研究的一个热点。RSA 作为一种重要的公钥加密算法，它是由罗纳德李维斯特（Ron Rivest）、阿迪萨莫尔（Adi Shamir）和伦纳德阿德曼（Leonard Adleman）在1977年一起提出的。此算法是目前非常具有影响力的公开密码算法，虽然它的可靠性一直未能得到理论上的证明，但是它可以阻挡目前为止已经为人所熟知的绝大多数密码攻击 ，已经被国际化标准组织（ISO）推荐为公钥数据加密标准。它是继背包加密算法之后的一个比较完备的公开加密算法，它不仅可以用于对接收方和发送方的消息进行加密和解密，而且可以用于数字签名。本毕设的主要简介了RSA加密算法的基本原理，及其研究背景与意义和国内外的发展趋势，并且着重讨论了RSA算法的安全性，最后探讨了RSA算法的软件实现及效率，并用C语言进行实现。关键词 公钥加密算法；RSA; C语言RSA algorithm is implemented in softwareAuthor: Shang Xun Chao(Grade11,Class 01, Major in Information and computing science, Mathematics and computer science Dept. Shaanxi University of Technology, Hanzhong 723000,Shaanxi)Tutor:Pan PingAbstract：As computing into the fast development of the network, the extent of the shared computer network resources to further strengthen the importance of network management has become more and more prominent, network security issues will follow. How efficient use of network resources and improve economic efficiency of the network, network control risk, to provide users with efficient, reliable, secure, integrated open mobile services. Then some of the emergence of new technologies, such as network security, encryption and authentication technologies, network security, intrusion detection and firewall technology, computer virus harm and protection. As an important RSA public key cryptography algorithm, it is by Ronald Rivest (Ron Rivest), Adi Shamir (Adi Shamir) and Leonard Adleman (Leonard Adleman) together in 1977It raised. This algorithm is the most influential public key encryption algorithm, although its safety has not been proved theoretically, but it can stop the already well known so far the vast majority of password attacks, has been the international standard group (ISO) recommended as public key encryption standard. It is the knapsack encryption algorithm (MH) Following is a more complete public encryption algorithm, it can not only be used for the message recipient and sender encryption and decryption, and can be used for digital signatures. The main work of this paper is to briefly describe the basic principles of RSA encryption algorithm, the research background and significance of domestic and international trends, and focuses on what its safety, discuss RSA algorithm software implementation and efficiency, and using C language .Key words: Public key encryption algorithm; RSA; C language目录1.绪论11.1 引言11.2 研究的背景及意义11.3 RSA的国内外发展趋势及研究现状11.4 论文章节结构22.RSA公钥加密算法22.1 RSA加密算法的概念22.2 RSA加密算法原理32.3 RSA设计流程43.RSA的安全性分析53.1 RSA的安全性53.2 RSA的攻击方法63.2.1 因子分解法63.2.2 模数攻击73.2.3选择密文攻击74.RSA 算法的一种快速软件实现84.1BR算法84.2改进的乘幂算法85.RSA的C语言实现95.1 RSA的硬件与软件实现95.2 算法加密结果95.2.1 加密算法的C代码95.2.2加密所得结果14结论14参考文献15致谢161.绪论1.1 引言计算机网络是20世纪的一项重大发明和创造，它极大地丰富和方便了我们的生活，尤其是近几十年来，计算机网络技术不断提高并且其应用领域不断扩大，使得其越来越成为人们生活的重要工具和手段，同时人们也必将日益依赖于计算机来处理和存储工作中的各种事务。这样，网络安全就不能不成为人们研究的热点话题。在这其中RSA加密技术就受到了人们的高度关注，它是一种积极主动的安全保护方案，它不但能对内部攻击、外部攻击和误操作进行实时防护，而且在计算机网络和系统受到危害前进行有效阻断，在保证网络性能的情况下能对网络进行有效保护。密码技术尤其是公钥加密技术是信息安全技术中的关键技术，国家核心基础建设中不可能引进或利用别国的加密技术，只能自主研发自己的加密体系。我们只有自主的开发自己的加密解密技术，才能保障我们自己信息的安全性。RSA是目前最具有影响力的公开密码算法，它可以阻挡到目前为止被人们已知的绝大多数密码攻击，已被国际化标准组织推荐为公钥数据加密标准。由于RSA加密算法在保证数据的安全性、有效性、完整性以及数字签名和认证等方面的突出特点，它已经成为当今网络安全中最有效的解决方法。1.2 研究的背景及意义 由于计算机网络在各个领域的深入应用，很多部门或个人都会将一些重要的信息存储到网络当中，因此人们就对网络信息安全产生怀疑。特别是近几十年来计算机技术的快速发展和广泛普及，网络攻击的手段和途径呈现出多样化的特点，而现有的一些安全防御措施诸如防火墙、安全审计、数据加密、访问控制等，都会多多少少存在一些不足之处，而且它们的功能过于单一，很难构成一个完整的安全防御系统，使得网络安全问题变得越来越突出。当今，网络犯罪日益猖獗，保障网络信息的安全，如何给广大用户提供一个安全的网络环境已是人们日益关注的问题。网络信息安全已成为国家与国防安全的重要组成分支，社会信息化需要建立在网络安全的基础之上。如何实现在信息战中取得主动权，如何保护国家信息安全是迫在眉睫的研讨话题，它也是在未来信息社会中能够生存的必由之路。目前非常常见的网络安全技术主要有加密技术、访问控制技术、认证技术和身份鉴别、入侵检测技术和防火墙技术等。实验室研究虽然提出了各种新措施来检测新类型攻击行为，但离实际应用还有很大的距离。当前研究机构和工业界的入侵检测系统普遍存在的最突出的共同问题是：系统只能检测到已知类型的攻击行为而对新类型的攻击行为往往会误报漏报，因此失去应有的性能，系统在检测攻击行为时实时性不是很好，除此之外，系统操作非常麻烦，配置繁琐也是所面临的重要问题之一。因此，致力于RSA加密算法的研究具有重要的社会意义和现实意义。考虑RSA加密算法的优势和提出的有效方法，期望获得更好的防御效果。1.3 RSA的国内外发展趋势及研究现状密码技术是信息安全的核心技术，它主要分为密码编码技术和密码分析技术两大部分。密码编码技术的主要任务是寻求产生安全性高的有效密码算法和协议，可以实现对消息进行加密或认证的要求。密码分析技术的主要任务是破译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏话动。这两个分支既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展。当前人们将密码理论与技术分成两大类，一类是以数学的密码理论与技术为基础，包括身份识别、PKI技术、VPN技术、数字签名、Hash函数、公钥密码、密钥管理、分组密码、认证码、序列密码等；另一类是非数学的密码理论与技术，包括量子密码、信息隐藏、基于生物特征的识别理论与技术等。现在世界上的一些大的国家都很重视密码学研究。在美国国家安全局(NSA)和国家标准技术研究所(NIST)的共同推动下，20世纪80年代以来陆续建立了国家数据加密标准(DES)和数字签名标准(DSS)，2001年又确定了高级加密标准算法(AES)以作为21世纪的应用基础。美国政府为了适应信息社会发展的需要，加强政府司法机构的社会管理执法的高技术支撑能力和情报部门的对抗信息战的能力，正通过NIST提出并推动着密钥托管、密钥恢复、证书授权认证、公开密钥基础设施、公开密钥管理基础设施等一系列技术手段、技术标准和相关理论基础的研究。国际上对序列密码和分组密码设计以及分析的理论与技术已经比较成熟。除此之外，美国、欧洲、日本发达国家在实现加密算法的标准化方面都做了很大的努力。我们国家的一些研究者虽然也设计了很多对称加密算法，可惜的是，目前还没有一个统一的加密标准，加密标准还处于讨论与征集阶段。在美国旧金山举行的RSA信息安全大会上，云安全，网络安全仍是目前最为热点的研讨话题。其中云安全是最耀眼的新星，围绕着云安全与网络安全提出了许多问题以及解决方法，比如：云安全需要急迫解决的安全隐患，云安全将成为2015年安全领域趋势，即新的安全威胁面前需要新的安全架构。另外，一些学者针对RSA所做的一些研究，包括：RSA算法的改进；基于AES与RSA混合加密策略的分区加密技术；一种基于RSA的加密算法；RSA密码算法的研究与改进实现；RSA加密算法的研究及应用等等。随着全球信息化步伐的加快，网络安全变得日益重要。网络安全从其本质上讲就是网络上的信息安全。再加上科学经济和信息时代的到来，网络与信息安全问题易发与经济发展和社会稳定密切相关，研究和开发高效实用的信息安全技术产品已成为当务之急。1.4 论文章节结构本论文总共分为五章，给章节内容安排如下：第1章 ，介绍了RSA加密算法研究的背景、意义和国内外研究现状；第2章 ，RSA公钥加算法，主要介绍其算法的由来，算法的原理以及加解密的实现；第3章 ，RSA运行速度的讨论；第4章 ，安全性分析，主要介绍了各种RSA的攻击方法以及在设计RSA中应该注意的一些问题。第5章 ，RSA的C语言的具体实现，主要介绍用C语言实现RSA的部分代码和加密所得到的结果。2.RSA公钥加密算法2.1 RSA加密算法的概念RSA加密算法是第一个即能同时用于数字加密也能用于数字签名的算法，而且容易理解和操作。此算法是一个被研究得非常广泛的公钥加密算法，自从1977年罗纳德李维斯特（Ron Rivest）、阿迪萨莫尔（Adi Shamir）和伦纳德阿德曼（Leonard Adleman）在麻省理工学院一起提出到现在已将近四十年，经历了各种攻击的考验，逐渐被人们接受，普遍认为是目前最优秀的公钥加密算法之一。RSA的安全性依赖于对大整数作因数分解，但它的安全性一直未能得到理论上的证明。即此算法的重大遗憾是无法从理论上把握它的保密性能如何，而且密码学界人士更多倾向于因子分解不是NPC问题。RSA的缺点主要有：1)产生密钥很麻烦，由于受到素数产生技术的影响，所以很难做到一次一密。2) 为保证安全性，RSA密钥长度至少也要600bits以上，一般推荐使用1024位。这就使得运算量很大，进而导致运算速度较慢，和对称密码算法相比慢几个数量级；而且伴随着大数分解技术的持续发展，这个长度还在快速增加，因而不易于数据格式的标准化。目前，国际公认的RSA算法密钥的安全长度为1024位。3)随着保密级别提高，RSA密钥长度增加很快。下表列出了对同一安全级别所对应的密钥长度。保密级别对称密钥长度（bit）RSA密钥长度（bit）ECC密钥长度（bit）保密年限808010241602010112112204822420301281283072256204019219276803842080256256153605122120在此算法出现之前，早在1973年，英国国家通信总局的数学家Clifford Cocks就发现了类似的算法。由于他的发现被称作为绝密，直到1998年才被人们熟知。RSA算法是一种非对称密码算法，所谓非对称，就是指该发送方和接收方需要一对密钥，使用其中一个用作数据加密，另一个用作数据解密。e和d是一对相关的值，d可以任意取，但要求d与(p-1) (q-1)互质；再选择e，要求(ed) mod (p-1) (q-1) = 1。(n,e), (n,d)就是密钥对。RSA加解密的算法完全一样,设M为明文，C为密文，则：；e和d可以互换使用，即: ；。2.2 RSA加密算法原理 RSA是用一个单向陷门函数构造的公钥加密算法，如图所示私钥公钥图2.1 RSA利用单向陷门函数的原理RSA密钥对的生成假设接收方想要通过一个不可靠的媒体接收发送方的一条私人消息。她可以用以下的方式来产生一个公钥和一个私钥：1.随意找两个大素数q和p，,并且为获得最大程度的安全性，要让q与p长度相同。接着计算n =；2.根据欧拉函数；3.选择一个小于r的整数e，求得e关于r的模反元素，命名为d。（模反元素存在，当且仅当e与r互质）4. q和p的记录销毁。其中是公钥，是私钥。接收方将他的公钥传给发送方，而将他的私钥藏起来。加密过程假设发送方想给接收方送一个消息m，他知道接收方产生的。他使用起先与接收方约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面的公式他可以将n加密为c：。计算c并不复杂。发送方算出c后就可以将它传递给接送方。解密过程接收方得到发送方的消息c后就可以利用她的私钥d来解码。她可以用以下这个公式来将c转换为n：，得到n后，她可以将原来的信息m重新复原。解码的原理是：，以及和。由Euclid定理（因为q和p是质数），和。这说明（因为q和p是不同的质数，所以p和q互质），故。发送者加密系统密文明文明文解密系统接收者图2.2 加解密流程图2.3 RSA设计流程如下图所示：信息输入模块素数产生模块素数测试模块产生密钥模块加密模块解密模块信息输出模块图2.3 RSA设计流程小结本章首先介绍了RSA加密算法的概念，指出了RSA的用途和目的；其次，通过介绍RSA加密与解密过程，指出了RSA加密算法的基本原理与工作方法；最后，通过作出RSA设计流程图对此算法做了总结。3.RSA的安全性分析3.1 RSA的安全性伴随着计算机网络技术的快速发展,人们日益重视对信息安全的要求,而且信息加密技术也需进一步的提高。为了提高数据在计算机网络传输过程中的安全性,本设计中介绍了RSA非对称加密算法,该算法可以进一步提高数据在网络传输过程中的安全性。RSA的安全性依赖于大数分解，假设偷听者乙获得了甲的公钥N和e以及丙的加密消息c，但他无法直接获得甲的密钥d。要获得d，最简单的方法是将N分解为q和p，这样她可以得到同余方程并解出d，然后代入解密公式导出n（破密）。但是到现在为止还没有人能够找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在。今天也没有人能够证明对N进行因数分解是唯一的从c推导出N的方法，但今天依然没有找到比它更简单的方法。（至少没有公开的方法。）因此今天一般认为只要模数足够大，那么攻击者就没有办法了。假如模数的长度小于或等于256位，那么只用一台个人电脑就可以在几个小时内分解它的因子了。1999年，数百台电脑合作分解了一个512位长的模数。今天对模数的要求是它至少要1024位长。1994年Shor证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的办法的话，那么Shor的算法可以淘汰RSA和相关的派生算法。（即依赖于分解大整数困难性的加密算法）假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。目前，RSA的一些变种算法已被证实等同于大数的分解。分解模数是最显然的攻击方法。作为一个密码分析者，他有可能尝试每一种可能的私钥，直到获得正确的一个。但是这种穷举攻击和试图分解模数相比就差很远。如今，人们可以分解出多个十进制位的大素数。所以为了保障RSA算法的安全性，模数n只有选得大一点的，视具体适用情况而定。当然攻击者也可以通过猜测欧拉函数加密的值来攻击RSA。但这种攻击和分解n相比就困难的多了。他们不攻击的基本算法，只是攻击加密协议。如果我们仅仅会使用RSA而忽略它的实现是不够的。实现的具体过程也很重要。这就是RSA的选择密文攻击。RSA在选择密文攻击面前有很大的缺陷。一般情况下入侵者是先将自己的某一个信息作一下伪装，让拥有私钥的实体对此信息进行签名。然后，通过计算就可获得他所想要的东西。实际上，入侵者利用的都是共同的一个弱点，即由于这样一个事实：乘幂保留了输入的乘法结构：。这个固有问题的根源就是公钥密码系统的最有用的特征：每个人都可以使用公钥。但是从算法的角度上讲是无法解决这一问题的，主要措施有两个：一个是采用比较好的公钥协议，确保工作过程中实体不对其他实体产生的任意信息解密，不对自己不了解的信息进行签名；另一个是绝不能对陌生人的随机文档签名，签名时先要使用单向函数对文档作哈希处理，或着同时使用不同的签名算法。随着时间的推移，人们宣称自己已经找到了破译RSA的简单方法，但是到目前为止这些宣称还是站不住脚的。比如1993年Willian Payne在他的的论文草案中曾经提到了一种基于费尔马小定理的方法。但是很不幸，它的运算速度和分解模数相比还是要慢得很多。3.2 RSA的攻击方法攻击RSA加密算法的方法有很多，主要有因子分解法，模数攻击，RSA的小指数攻击，选择密文攻击，RSA的边信道攻击，低加密指数攻击,低解密指数攻击，时间攻击。下面对因子分解法, 模数攻击，选择密文攻击进行简要说明。3.2.1 因子分解法RSA加密体制的安全性主要依赖于大整数因子分解的问题，那么，攻击者尝试分解模数n所以的素因子就是攻击RSA最直接的方案。试除法是出现的比较早的因子分解法，它的基本思想与穷举攻击基本一样：密码攻击者完全尝试小于n的所有素数，直到找到他想要的结果。我们根据素数理论知道，尝试的次数上限是。虽然试除法非常有效，但是对于非常大的数n，这种方法对资源的消耗在现实之中几乎是难以实现的。后来也出现了一些比较重要的因子分解法，比如：Pollard在1974年提出的p-1因子分解法，Williams提出的p+1因子分解法，二次筛因子分解法，椭圆曲线因子分解法，数域筛因子分解法等常用方法。除了因子分解法的持续发展之外，并行计算和网络上分布式计算也加快了因子分解的速度，如下表：表3-1 不同时间段因子分解位数年度位数（十进制）1984711994129199915520031742005200虽然因子分解的速度加快了，但是随着因子分解位数的增加，人们可能会置疑因子分解是不是计算上的难题。但是由于银子分解的时间复杂性并没有降为多项式时间，所以，因子分解仅仅只是计算上的难题，如果我们只需要考虑使用较大的位数来确保此算法无法在短时间内被攻破就可以了。3.2.2 模数攻击如果在一个系统中共享一个模数，只是不同的人拥有各自的密钥对，那么系统将是很危险的。最普遍的情况就是同一明文通过不同的公钥加密获得密文，而且公钥共模且互质，那么该密文无需私钥就可得到恢复。设m为信息明文，两个加密密钥为和，公共模数是n，则：如果密码分析者知道n、和，就能得到m。因为和互质，故用欧拉算法就能找到r和s，使其满足：我们假设r为负数，需再用欧拉算法计算，则除此之外，还有其它几种利用公共模数攻击的方案。总而言之，如果攻击者知道给定模数的一对密钥，一方面有利于他们分解模数，另一方面有利于他们计算出其它成对的密钥对，而无需分解模数。解决这个问题的措施只有一个，那就是我们只需要不共享模数n。RSA的小指数攻击。如果我们让公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。但这样做是不安全的，解决方法就是e和d都取较大的值。3.2.3选择密文攻击RSA在选择密文攻击面前很脆弱。攻击者可以将某一信息作一下伪装，让拥有私钥的实体签名。获得签署后，通过计算就可以获得到他所想要的信息。实际上，攻击者利用的都是相同的一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：这个固有的问题根源于公钥密码系统的最有用的特征：每个人都能采用公钥加密。但是我们从算法这个角度无法解决这一问题，主要措施有两个：一个是采用较好的公钥协议，保障工作过程中实体不对其他莫名实体产生的任意信息解密，不对自己不了解的信息签名；另一个是我们绝不能对陌生人送来的随机文档签名，签名时首先要对文档作哈希处理，或者同时使用不同的签名算法。下面我们通过例子说明。实例1：甲在乙通信的过程中进行窃听，甲想办法成功的获取了一个乙的公开密钥加密的密文c。甲想从中读出消息，我们从数学上讲，也就是甲想得到明文m，这里：为了恢复出完整的m，甲先选取了一个随机数r，而且r小于n。甲得到了乙的公开密钥e，然后进行计算：如果成立，那么就成立现在，甲让乙用他的私人密钥对y签名，便于解密y（注意，乙以前从未见过y）。则乙发送给甲：甲计算如下内容:甲就获得了m。实例2：甲想让乙对签名。甲先生成两份消息，而且满足如下要求：如果，他也能让乙对和进行签名，就能计算：因此，我们应该谨记，绝对不能对陌生人发送的随机消息进行签名，并且我们要先利用单向散列函数对消息进行散列运算。ISO9796分组格式可以防止这种攻击。4.RSA 算法的一种快速软件实现RSA 算法是基于数论的公开密钥密码算法。 此算法已经成为当下十分流行的公钥加密算法与数字签名算法之一。由于 RSA算法的加密、解密操作时要进行的十进制位数不是很小，所以它的实现难度大和运算时间很长。而影响其运算速度的主要因素是大数乘幂算法。4.1BR算法RSA公钥密码体制在密码学中占有相当重要的地位。由于它不仅保密性强，密钥管理方便，而且具有数字签名、认证和鉴别等多种功能，所以特别适合于现代保密通讯的需要。但是由于它所采用的幂剩余计算耗时太多，一直是它广泛应用的瓶颈问题。几乎所有的快速 RSA 算法都是建立在 BR算法的基础上，下面对 BR 算法进行简要的介绍。BR 算法是将指数 e先转化成二进制化来实现的，即将指数 e表示成二进制形式： 再进行一系列迭代运算。1) 设，2) 置变量 c =13) 对于 i=k-1, k -2, , 1, 0重复计算，若, 则c =，4) c 即为所求。上述算法中，影响运算速度的主要因素有两个：一是平方运算的次数，二是乘法运算的次数。 如果假设指数e的长度为 k bit, 则此算法只需 k次平方运算和 k次乘法运算。若假设的概率为 1/2则该算法的平均运算量为:平方次数: k；乘法次数: k/2。4.2改进的乘幂算法上述算法中将指数e二进制化后，e的比特序列长度变得很长(实际中往往超过400位)，在计算过程中需要进行多次迭代，因此导致了其计算效率下降，为了减少迭代的次数，可用缩短指数位数的方法来实现。基于上述思想，改进的算法是将指数e先进行进制化(k =0, 1, )，即将指数e转化为:其中。这样指数序列的长度减少，从而使迭代次数减少，算法效率就会提高。因此可表示成:其中 n为加密指数 e被 2 k 进制化后的序列长度, (*) M 表示括号中值取模。如取k =3 时算法如下:1. 设 ，其中，2. 求出，3. 置变量 c =1，4. 对于 i =n-1, n-2, , 1, 0重复计算： 若, 则, 式中。5. c即为所求。上述算法的平均时间复杂度为:平方次数：k；乘法次数 ：7 n /24+14。5.RSA的C语言实现5.1 RSA的硬件与软件实现在硬件实现时，对称加密算法比RSA加密算法将近快1000倍。在512位模数的硬件情况下，最快的是VLSI硬件，它可实现的吞吐量为64位/秒。除此之外还有一些可实现1024位的RSA的加密芯片。到1995年，拥有512位模数的芯片其吞吐量可达到1M/秒。在实际应用中，智能卡中已经大量采用了RSA，不幸的是它们的实现速度大多都较慢。虽然随着技术的发展RSA与DES两者运算速度的差距会变小，但是有这样一个事实，RSA的运算速度不可能也不会达到对称加密算法的速度。下表给出了具有8位公开密钥的RSA对于不同长度模数的加密速度。512位768位1024位加密0.03秒0.05秒0.08秒解密0.16秒0.48秒0.93秒签名0,16秒0.52秒0.97秒验证0.02秒0.07秒0.08秒表5-1 具有8位公开密钥的RSA对于不同长度模数的加密速度5.2 算法加密结果5.2.1 加密算法的C代码（1）小素数的实现#include int candp ( int a, int b, int c ) / /数据处理函数，实现幂的取余运 int r = 1;B = b+1;while ( b! = 1 )R = r*a;R = r%c;B -;printf( %dn, r );return r;int fun ( int x, int y ) / / 公钥 e与 t 的互素判断int t;while ( y )t = x;x = y;y = t%y;if ( x = 1 )return 0; / / x 与 y互素时返回 0elsereturn 1; / / x 与 y不互素时返回 1void main ( )int p, q, e, d, m, n, t, c, r;printf( 请输入两个素数 p,q: );scanf( %d%d,&p, &q );n = p*q;printf( 计算得 n 为 %3dn,n );t = ( p-1 )*( q-1 ); / 求 n 的欧拉数printf ( 计算得 t 为 %3dn, t );printf ( 请输入公钥 e: );scanf( %d,&e );if ( et|fun(e,t) )printf( e 不合要求， 请重新输入: ); / / et 或 e 与 t 不互素时，重新输入scanf( %d,&e );d = 1;while ( ( ( e*d ) %t )! = 1 ) d+; / / 由公钥 e 求出私钥dprintf ( 经计算 d 为 %dn,d );printf ( 加密请输入 1n ); / / 加密或解密选择printf ( 解密请输入 2n );scanf ( %d,&r );switch ( r )case 1: printf ( 请输入明文 m: ); / / 输入要加密的明文数字scanf ( %d, &m );c = candp ( m, e, n );printf( 密文为 %dn, c );case 2: printf ( 请输入密文 c: ); / / 输入要解密的密文数字scanf ( %d, &c );m = candp ( c, d, n );printf ( 明文为 %dn ,m );（ 2 ）函数说明/ / ! MAX是数组的最大个数，LEN为结构体slink的占用内存空间大小 * / # define MAX 100 # define LEN sizeof ( struct slink ) / /! #能够进行动态链接库编译的RSA类 / *! see class _declspec ( dllexport ) RSA 将RSA算法写成动态链接库的形式方便调用，其中有公钥，私钥和明文 就可以进行明文的加密和解密 * / class _declspec ( dllexport ) RSA public: / /! # 新定义的数据结构slink / *! see struct slink 数据结构中，bignum存储的是随机生成的大数，next是指向后面的指针 see int bignum MAX * / typedef struct slink int bignum MAX ;/ * ! bignum 98 用来标记正负号，1正，0负bignum 99 来标记实际长度*/ struct slink * next; slink; public: / / ! #RSA 的构造函数 / * ! see RSA( ) 其中应该对RSA类中的一些变量进行相应的初始化 * / RSA( ); / /! #RSA的析构函数 / * ! see RSA( ) 释放内存 * / RSA( ); public: / / ! #RSA的大数运算函数库 /* 大数比较函数 see int cmp ( int, int ) * / int cmp ( int a1 MAX , int a2 MAX ); / * 大数类型转换函数 see void mov ( int a MAX , int *b ); * / void mov ( int a MAX , int *b ); / * 大数乘积函数 see void mul ( int a1 MAX , int a2 MAX , int *c ); * / void mul ( int a1 MAX , int a2 MAX , int *c ); / * 大数相加函数 see void add ( int a1MAX, int a2MAX, int *c ); * / void add ( int a1 MAX , int a2 MAX , int *c ); / * 大数大数相减函数 see void sub ( int a1 MAX , int a2 MAX , int *c ); * / void sub ( int a1 MAX , int a2 MAX , int *c ); / *! 大数取模函数 see void mod ( int a MAX , int b MAX , int *c ); attention /c = a mod b/ /注意：经检验知道此处A和C的数组都改变了。 * / void mod ( int a MAX , int b MAX , int *c ); /*! 大数相除函数 see void divt ( int t MAX , int b MAX , int *c , int *w ); attention / /试商法/调用以后w为a mod b, C为a div b; * / void divt ( int t MAX ,int b MAX , int *c ,int *w ); / *! 解决 了 m = a*b mod n; / *! see void mulmod ( int a MAX , int b MAX , int n MAX, int *m ); * / void mulmod ( int a MAX ,int b MAX ,int n MAX ,int *m ); / *! 解决 m = ap mod n的函数问题 / *! see void expmod ( int a MAX , int p MAX , int n MAX , int *m ); * / void expmod ( int a MAX , int p MAX , int n MAX , int *m ); / *! 判断是否为素数 see int is_prime_san ( int p MAX ); * / int is_prime_san ( int p MAX ); / *! 判断两个大数之间是否互质 see int coprime (int eM AX , int s MAX ); * / int coprime ( int e MAX , int s MAX ); / *! 随机产生素数 see void prime_random ( int *p, int *q ); * / void prime_random ( int *p, int *q ); / *! 产生素数e see void errand ( int e MAX , int m MAX ); * / void errand (int e MAX ,int m MAX ); / *! 根据规则产生其他的数 see void rsad ( int e MAX , int g MAX , int *d ); * / void rsad ( int e MAX , int g MAX , int *d ); / *! 求解密密钥d的函数( 根据Euclid算法 ) see unsigned long rsa( unsigned long p, unsigned long q, unsigned long e ); * / unsigned long rsa( unsigned long p,unsigned long q,unsigned long e ); / /! #RSA的产生大数的公钥和私钥的函数 / *! see bool RSAKey( ); param 没有任何输入， param 随机产生e，d，n的函数，其运行时间比较长，需要等待 return bool 成功返回true，失败返回false * / bool RSAKey( ); / /! #RSA的进行文件加密的函数 / *! see string tencrypto ( int e MAX , int nMAX, char* text ); param int e，n为随机产生的公钥，利用公钥进行加密 param char* text为明文，明文以char*的格式存储 return string 返回值为加密成功之后的密文，采用string类型进行存储 * / string tencrypto ( int e MAX , int n MAX , char* text ); / /! #RSA的进行文件解密的函数 / *! see string tdecrypto( int d MAX , int n MAX , string text ); param int d, n为私钥，由函数RSAKey( )产生 param string text为密文，对应加密函数，密文的格式为string return string 解密之后的明文采用string进行存储 * / string tdecrypto ( int d MAX , int n MAX , string text ); public: / * brief 定义的全局变量，存储密钥 * / int p MAX , q MAX , n MAX , d MAX , e MAX , m MAX , p1 MAX , q1 MAX ; privat