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

《毕业设计（论文）RSA加解密算法的研究与实现》由会员分享，可在线阅读，更多相关《毕业设计（论文）RSA加解密算法的研究与实现（51页珍藏版）》请在装配图网上搜索。

1、华北科技学院毕业设计（论文）目录设计总说明3INTRODUCTION51 绪论71.1 研究背景和意义71.2 国内外研究现状与水平81.3 本文的工作和内容安排92 密码学概述102.1 密码学基本概念102.2 密码分析技术102.3 密码学中的安全性定义112.4 密码学的主要任务122.4.1 机密性122.4.2 数据完整性122.4.3 鉴别122.4.4 抗抵赖性122.5 密码体制的分类123 RSA算法的数学理论基础133.1 单向和陷门单向函数133.2 同余及模运算133.3 欧拉函数、欧拉定理和费尔马定理143.4 乘法逆元及其求法154 RSA算法介绍174.1 RS

2、A公钥加密解密概述174.1.1密钥的产生174.1.2 加密174.1.3 解密174.2 RSA算法的应用与举例184.2.1 RSA算法的应用184.2.2 RSA应用举例194.3 RSA算法的攻击与安全性的讨论204.3.1 对RSA的分解模数n攻击204.3.2 对RSA的选择密文攻击214.3.3 对RSA的小指数攻击214.3.4 对RSA共模攻击224.3.5 关于RSA算法的明文部分信息安全性224.3.6 RSA的安全性讨论234.4 RSA参数的选择244.4.1 模数N的确定244.4.2 e的选取原则254.4.3 d的选取原则265 RSA算法的系统及实现2751

3、 大素数生成实现2852 密钥对产生实现315.2.1 加密密钥产生325.2.2 解密密钥产生3453 模幂运算的实现355.4 大数运算处理375.4.1 大整数的进制表示375.4.2大整数的存储与读取395.4.3大整数的基本运算4055加解密整体过程的快速实现425.5.1选定算法的原则435.5.2确定算法与其流程图435.5.3算法的数据结构与源代码455.5.4运行效果与结论466. 总结与展望486.1本文的总结4862展望48参考文献49致谢50RSA加解密算法的研究与实现设计总说明自20世纪90年代以来，随着计算机互联网络的飞速发展，网络技术的应用几乎已经深入到人类社会生

4、活的一切领域。例如网上银行的开通、网上购物的流行以及企业之间的商业机密，银行与银行之间的业务往来，这一切的一切都离不开信息的安全传输。因此在当前的网络环境下，敏感信息的保护已经成为一个很重要的问题，一个安全、健壮的信息系统离不开各种信息安全技术的支持。计算机网络中所采用的核心安全技术中有许多来源于现代密码学，这一技术的研究和发展是计算机技术发展的重要保障。加密技术按照密码使用方法不同可以分为对称密钥算法和非对称密钥算法。对称密钥算法中，加密、解密都使用相同的密钥。非对称密钥算法又称公钥密码算法，即加密、解密使用两个不同的密钥。由于公钥密码算法在保证数据的机密性、完整性以及签名和认可等方面的突出

5、优点，它已经成为当今网络安全中最重要的解决方法。RL.Rivest，ASbamir和LAdleman于1977年提出的RSA公钥密码体制的安全性和性能不断得到人们的肯定，成为最流行的密码体制。RSA密码体制是目前比较成熟的公钥密码体制，可用于数据加解密、数字签名、身份验证等。在各种安全或认证领域，如WEB服务器和浏览器信息安全、Email的安全和认证、对远程登陆的安全保证和各种电子信用卡系统，起着安全核心的作用，而用微电子技术将加密算法转换成硬件实现，不仅加解密速度快，而且抗物理攻击能力强，所以研究如何用硬件快速实现RSA有着重要的现实意义。但是大密钥加解密存在着运算速度缓慢、效率低下的问题，

6、这成为制约它进一步推广的瓶颈。因此，找到一个快速的RSA的实现算法也是当前密码学的一个研究方向。RSA加解密算法的实现主要在大素数的产生，密钥对的生成，模幂运算的实现以及大整数的存储与运算这四方面的问题。本论文根据这几方面的问题一一做了详细的介绍，其中大素数的产生采用Miller-Rabin素数检测法。RSA算法的核心运算是大整数模幂运算，而模幂运算是由一系列的模乘运算构成。因此本文主要针对RSA公钥密码体制中大整数模指数算法进行了深入的研究，将该问题分解为对乘法算法、模乘法算法、模指数算法的研究并使用流行的面向对象软件开发工具Visual C+进行了相应的软件实现。RSA密码算法体制是一种公

7、开密钥算法，其加密密钥和算法本身都可以公开，解密密钥则归用户私人拥有。从诞生那天起，RSA就因为安全强度高、使用方便等卓越性能受到关注，并得到广泛应用。目前，许多密码系统中都嵌有RSA密码算法。本论文的主要工作在于：(1) 简单介绍了一些密码学的基本概念以及密码分析技术，详细的讲述了密码学中的安全性定义，讨论了密码学的主要任务是保障信息的机密性、数据完整性、鉴别、抗抵赖性。简单的介绍了密码体制根据加密算法与解密算法所使用的密钥是否相同可以分为对称密钥体制和非对称密钥体制。对称密钥体制中，加密、解密都使用相同的密钥。非对称密钥算法又称公钥密码体制，即加密、解密使用两个不同的密钥。(2) 对RSA

8、公钥密码体质的原理进行了描述。首先介绍了RSA算法的数学理论基础，其中包括欧拉函数与欧拉定理、费尔马定理，乘法逆元及其求法等。详细描述了加密与解密的原理和RSA算法容易受到的各种攻击以及RSA的参数选择与安全性问题。并且简单介绍了一些RSA算法的典型应用。(3) 对RSA公钥密码算法的原理进行了详细描述，RSA公钥密码系统的实现。详细的讨论了大素数的生成与实现，密钥对的产生，模幂运算的实现以及大整数的四则运算。关键词：RSA；公钥密码系统；大素数；模幂运算RSA encryption algorithm of research and implementationINTRODUCTIONSin

9、ce 1990,with the rapid development of computer and Internet.The network technology has been applied to all the field in peoples daily life.In such an environment,how to protect the sensitive information becomes an important problemAccording to different password use methods encryption can be divided

10、 into symmetrical key algorithms and asymmetric-key algorithm. In Symmetric key algorithms, encryption and decryption are using the same key. While in asymmetric key cryptography algorithm ,which is also called the public-key cryptography,encryption and decryption using two different keys. Because o

11、f the outstanding advantages of public key cryptography algorithms in ensure the data in the confidentiality, integrity, and sign and recognition and other aspects , it has become the most important in todays network security solutions.The security and performance of RSA public key cryptosystem whic

12、h is proposal by RLRiveest.AShamir and LAdleman in 1 977 has been accepted，and it has become the most famous cryptosystemHowever,inefficiency is still a problem in theencryption and decryption processThis disadvantage has become a bottleneck problem of RSAHence,how to implement RSA algorithm faster

13、is a research content of modem cryptographyA secure and robust information system needs all kinds of information security technologyA lot of central security technology which is widely used in computer network derives from modern cryptographyThe research and development of this technology is an impo

14、rtant safeguard of the computer technologyIn this paper we mainly study multipleprecision modular exponentiation algorithm in the implementation of RSA algorithmThis algorithm can be transformed as multiplication，modular multiplication and modular exponentiation algorithmWe can use the software Visu

15、al C+to implement themRSA is mature public-key cryptography at present,it can encrypt，make a scratch of digital and validate degreeIt has been used in many security and identification system，such as we can and explorer security mail,remote loginand smart cards and function as the core of the securit

16、y systemRSA algorithms canoperate with faster speed and has more ability to resist physical attacksSo to developthe RSA security chip is very important to usIn this paper, the main job is:(1)RSA public key password to the principle of the constitution is described. Introduces some basic concepts of

17、cryptography and analysis method, the present situation of the research at home and abroad with level and use of cryptography number theory knowledge.(2) The principle of RSA public key cryptography algorithms is described in detail, and discussed the RSA parameters selection and security problems.

18、Introduces some typical applications of RSA algorithms.(3)RSA public key password system is realized. Detailed discussed the formation of large prime Numbers and implementation, and the realization of the uniform exponent of big integer arithmetic.The research object of this paper is the RSA algorit

19、hm，which is a public-key algorithm with a pair of keys called the publickey and the private keyIn this algorithm，the public-key and algorithm itself are able to be open，with the privatekey possessed by the user himself From the birth on，RSA has always being applied for its excellent performance of h

20、igh security and convenient usage and so onNowadays RSA is employed in lots of cryptogram system.Key words:RSA;public key cryptography;Large prime Numbers;Uniform exponent1 绪论从古至今，人们总有保密通信的需要。特别是随着计算机网络和通信技术的发展，数据的保护、安全与隐私变得越来越重要。密码技术是信息安全的核心，它是实现保密性、完整性不可否认的关键。1.1 研究背景和意义在计算机网络蓬勃发展的今天，信息的交流与传输变得更为便

21、捷与快速。互联网的广泛应用，缩短了人与人之间的距离，淡化了国与国之间的界限。人们可以足不出户，通过网络学习、购物、汇款等活动。计算机网络在方便了人们生活的同时，也提高了人们的工作效率。然而，人与人之间存在着隐私，企业间存在着技术和商业利益的竞争，但网络特有的开放性，使得在网络上传输的信息很容易被拦截。如果通过网络以明文的方式传送不希望第三方知道的保密信息会产生安全上的问题。若把在网络上传送的保密信息以密文的方式传输，使窃听者难以获得有用信息，则可达到安全通信的目的。信息安全技术在计算机和网络通信中占有重要地位。信息安全涉及法律、管理和技术等方面，在此仅讨论技术方面。从技术角度讲，密码技术是使信

22、息系统达到安全的核心手段。密码体制按密钥可以划分为传统密码体制和公钥密码体制两种。传统密码体制中，加密、解密使用相同的密钥。公钥密码体制中加密算法和解密算法是公开的，加密、解密使用两个不同的密钥。传统密码体制不利于密钥管理也不利于数字签名，但速度快。公钥密钥体制证实了从发送端到接收端无密钥传输的保密通信是可行的，从而非常适合于计算机网络的保密通信。公钥密码体制既可用于密钥传递又可用于数字签名，用途十分广泛，但速度较低，可以说，速度是其最显著的缺陷。因此，目前密码系统大多采用混和密码体系，即用公钥密码体制实现密钥管理和数字签名，用传统密码体制实现大量信息的加解密。这样既增强了密码系统的安全性，又

23、可以比较快速地进行加解密，效果非常好。RSA 是公钥密码体制中最成熟、最典型的代表，已成为数据加密事实上的标准。其安全性也是基于数学上的一个难题：将两个大素数相乘比较容易，反之，将一个大数分解为素因子的乘积则比较困难。RSA 加解密可归结为对Mx (modN)的运算。由于目前计算机的处理速度的不断提高，分解大整数的能力日益增强，为了保证安全，目前模数N及密钥X的二进制位数为1024:2048，所以RSA算法运算量极大。因而，对RSA 公钥密码系统算法中的大整数运算进行研究具有显著的现实价值。1.2 国内外研究现状与水平RSA公钥密码体制是在1978年由RLRivest，AShamir和LAdl

24、eman三人在文章实现数字签名和公钥密码体制的一种方法中共同提出的，是最具代表性的公钥密码体制。由于算法完善(既可用于数据加密，又可用于数字签名)，安全性良好(据传山东大学信息科学与工程学院的季凯和他的破解团队成员刘强等人宣布己找到可有效破解RSA的方法，并公布了算法，但未经证实)，易于实现和理解，RSA已成为一种应用极广的公钥密码体制，它的提出真正使得互不相识的通信双方在一个不安全的信道上进行安全通信最终成为可能。在广泛的应用中，不仅它的实现技术日趋成熟，而且安全性也逐渐得到事实的证明，因此人们对RSA十分重视。但在实现过程中，由于算法中包含有大数的乘方运算，在计算机上运算时，会耗费大量的时

25、间，严重影响了RSA的加密效率，制约了它的应用，因此人们对其从不同方面进行了改进，并形成了以下实现算法：传统实现算法。由Rivest等人在RSA体制建立时提出，是把乘方后求模的计算改为在边乘方边求模的计算，以减小中间结果的数值，尽量避免大数的乘方计算。该算法在一定程度上改善了RSA的效率。SMM算法。是利用“乘同余对称特性”来减少加密和解密运算中乘法和求模运算量的一种改进算法。其本质是减小求幂运算中的基数的大小，但并没有考虑指数的情况，故只是在一定的程度上改进了原算法的效率。指数2k进制化算法。是通过缩短指数的长度来减少迭代的次数，从而提高计算效率。但是，在求幂运算的过程中，基数的大小也是影响

26、运算速度的重要因素，而该算法只是减小了指数的长度。RSR算法。是将RSA传统算法中的求模运算变成一系列2的乘幂的余数和运算，可以在一定程度上提高计算速度，但是由于在实际实现时，RSR算法要进行对大整数进行字节、比特的不断转换，不适合与其他算法联合使用。此外还有蒙哥马利算法、利用中国剩余定理降指法等。总之，上述各个实现算法分别从不同方面改进了RSA加密算法，使得加密速度有了一定的提高。但是，随着计算机软、硬件的不断发展，数据量也在急剧增大，对加密的速度要求也越来越高，人们需要不断改进加密算法，以提高加密运算的速度。1.3 本文的工作和内容安排在阅读大量国内外研究成果的基础上，讨论了针对 RSA

27、的各种攻击方法，以及如何作出处理以抵制这些攻击；讨论了RSA 的安全性和RSA 的参数选择详细讨论了大素数的生成和检测；研究了RSA 公钥密码系统中用到的算法；以同余理论为基础，推广了整除性的两个性质；实现了RSA 公钥密码体制大部分算法模块；提出了一种快速模运算算法。本文的工作分一下七章完成：第1章绪论。阐述了课题的研究背景和意义，国内外的研究现状和发展趋势，并介绍了本文研究的主要内容。第2章密码学概述。介绍了密码学的一些基本概念以及密码分析技术，讨论了密码学中的安全性定义，引出了公钥密码体制与私钥密码体制。第3章公钥密码的数论基础。介绍了公钥密码系统中应用到的基本数论知识，为后面相关章节奠

28、定理论基础。第4章RSA算法介绍。对RSA公钥密码系统进行了详细的研究，包括安全性的讨论，常用攻击方法及其对策的介绍，RSA算法的典型应用及举例。第5章RSA公钥密码系统的算法研究与实现。这一章是本文的重点。介绍了大素数的生成与检测，模幂运算的实现，大整数的四则运算等。并研究了密钥对的生成实现以及加解密过程的整体实现。第6章总结与展望。总结了全文的研究工作，指明了下一步的研究方向。2 密码学概述密码学的历史极为久远，其起源可以追溯到远古时代，人类有记载的通信密码始于公元前400年。密码学是研究信息系统安全保密的科学，它包括两个分支，密码编码学和密码分析学；密码编码学是对信息进行编码实现信息隐蔽

29、的技术和科学；密码分析学是研究分析破译密码的技术和科学。密码是实现秘密通讯的主要手段，是隐蔽语言、文字、图像的特种符号。凡是用特种符号按照通讯双方约定的方法把电文的原形隐蔽起来，不为第三者所识别的通讯方式称为密码通讯。在计算机通讯中，采用密码技术将信息隐蔽起来，再将隐蔽后的信息传输出去，使信息在传输过程中即使被窃取或截获，窃取者也不能了解信息的内容，从而保证信息传输的安全。2.1 密码学基本概念（1）明文(plaintext)：也就是消息(message)。明文一般用m表示，指待加密信息。（2）密文(ciphertext)：就是加密后的消息，一般用c表示。（3）密码算法(algorithm)：

30、是用于加密和解密的数学函数，通常有两个相关函数：一为加密，一为解密。（4）加密(encryption)：用某种方法伪装信息以隐藏它的内容的过程。加密函数E(m)作用于明文而得到密文，公式表示为E(m)=C。（5）解密(decryption)：把密文转变为明文的过程。解密函数D(c)作用于密文来恢复明文，公式表示为D(c)=m。（6）密钥(key)：包括加密密钥和解密密钥。加密密钥用于加密运算，解密密钥用于解密运算。2.2 密码分析技术密码分析学是密码学的一个重要分支，是研究在不知道密钥的情况下，利用密钥体制的弱点恢复明文的一门学科。对一个密码系统采取截获密文进行分析的这类攻击称为被动攻击(Pa

31、ssive Attack)；另一种是主动攻击(Active Attack)，即非法入侵者主动向系统进行攻击，采取删除、更改、增添、伪造等手段向系统插入假信息，以达到窃取非法信息的目的。密码攻击者攻击密码体制的方法主要有以下三种：1.穷举攻击：密码攻击者通过试遍所有的密钥来进行破译。当然，可以通过增大密钥量来对抗穷举攻击。2.统计分析攻击：密码攻击者通过分析密文和明文的统计规律来破译密码。对抗这种攻击方法是设法使明文的统计特性和密文的统计特性不一样。3.数学分析攻击：密码攻击者针对加密变换的数学基础，通过数学求解的方法来设法找到相应的解密变换。对这种攻击方法，应该选用具有坚实的数学基础和足够复杂

32、的加密算法。根据密码攻击者在密码系统中获得信息的不同，通常可以在下述四种情况下对密码体制进行攻击：1.唯密文攻击(ciphtext-only attack)：密码攻击者仅知道一些密文。2.已知明文攻击(Known-plaintext Attack)：密码攻击者知道一些明文和相应的密文。3.选择明文攻击(Chosen-plaintext Attack)：密码攻击者可以选择一些明文，并得到相应的密文。4.选择密文攻击(Chosen-ciphertext Attack)：密码攻击者可以选择一些密文，并得到相应的明文。以上四种方法中，唯密文攻击的强度最弱，其他情况的攻击强度依次增加。2.3 密码学中的

33、安全性定义荷兰密码学家Kerckhoff对密码安全性分析做了如下假设：一个信息安全系统的安全性取决于对密钥本身的保护，而不是对系统或者通信硬件的安全保护。对于一个密码体制，如果密码分析者无论获得多少密文以及用什么方法进行攻击都不能破译，则称绝对不可破译的密码体制。绝对不可破译的密码体制在理论上是存在的。但是，只要有足够的资源，那么任何实际的密码体制都是可以破译的。因此，更有实际意义的是在计算上不可破译的密码体制。密码系统只要满足以下两条重则之一就称为计算上不可破译：（1） 破译密文的代价超过被加密信息的价值；（2） 破译密文的时间超过信息的有用期。2.4 密码学的主要任务经典的密码学主要是关于

34、加密和解密的理论，主要用于通信保密。但今天，密码学已得到了更加神术广泛的发展。总的来说，在信息安全的诸多涉及方面中，密码学主要为存储和传输中的数字信息提供如下几个方面的安全保护。2.4.1 机密性是一种允许特定用户访问和阅读信息，而非授权用户对信息内容不可理解的安全属性。在密码学中，信息的机密性通过加密技术来实现。2.4.2 数据完整性数据完整性即用于确保数据在存储和传输过程中不被非授权修改的安全属性。为提供这种安全属性用户必须有检测非授权修改的能力。非授权修改包括数据的篡改，删除，插入和重放等。密码学可通过采用数据加密，报文鉴别和数字签名等技术实现数据的完整性保护。2.4.3 鉴别这是一种与

35、数据来源和身份鉴别有关的安全服务。鉴别服务包括对身份的鉴别和对数据源的鉴别。密码学可通过密码数据，数字签名和鉴别协议等技术来提供这种真实性服务。2.4.4 抗抵赖性这是一种用于阻止通信实体抵赖先前的通信行为及相关内容的安全特性。密码学通过对称加密或非对称加密，以及数字签名等技术，并借助可信机构或证书机构的辅助来提供这种服务。2.5 密码体制的分类密码体制根据加密算法与解密算法所使用的密钥是否相同可以分为对称密钥体制和非对称密钥体制。对称密钥体制中，加密、解密都使用相同的密钥。非对称密钥算法又称公钥密码体制，即加密、解密使用两个不同的密钥。由于公钥密码体制在保证数据的机密性、完整性以及签名和认可

36、等方面的突出优点，它已经成为当今网络安全中最重要的解决方法。在公钥密码体制中最典型的就是RSA公钥加密算法，下面主要研究其原理与实现。3 RSA算法的数学理论基础在密码学中需要使用到许多数学理论，例如数论、信息论、复杂度理论等，它们是设计密码系统及协议不可或缺的工具，其中数论是密码学中(尤其是公开密钥密码系统中)最重要的数学基础，因此有必要对有关数论理论做一介绍。下面介绍RSA算法的数学基础知识。3.1 单向和陷门单向函数RSA的安全性主要取决于构造其加密算法的数学函数的求逆困难性，这同大多数公钥密码系统一样(譬如EIGamal算法就是基于离散对数问题的困难性），我们称这样的函数为单向函数。单

37、向函数不能直接用作密码体制，因为如果用单向函数文进行加密，即使是合法的接收者也不能还原出明文，因为单向函数的逆运算是难的。与密码体制关系更为密切的陷门单向函数，即函数及其逆函数的计算都存在有效的算法，而且可以将计算函数的方法公开。单向和陷门单向函数的概念是公钥密码学的核心，它对公钥密码系统的构造非常重要，甚至可以说公钥密码体制的设计就是陷门单向函数的设计。定义a：令函数f是集合A到集合B的映射，以f：AB表示。若对任意X1X2，X1,X2A，有f(X1)f(X2)，则称f为1一l映射，或可逆函数。定义b：一个可逆函数f，若它满足：1. 对所有XA，易于计算f(x)；2对“几乎所有xA，由f(X

38、)求x“极为困难，以至于实际上不可能做到。则称f为单向函数(One-way function)上述定义中的“极为困难”是对现有计算机能力和算法而言的，Massey称此为视在困难性，相应的函数称之为视在单向函数。以此来和本质上的困难性相区分。目前，还没有人能够从理论上证明单向函数是存在的。3.2 同余及模运算同余：假定有三个整数a，b，n(nO)，当我们称a在模n时与b同余，是指当且仅当a与b的差为n的整数倍，即a-b=Kn，其中k为任一整数。若a与b在模n中同余，我们可写为ab(modn)或n|(a-b)。剩余类(Residue Class)：很明显地，利用同余概念，所有整数在模n中被分成n个

39、不同的剩余类；为n所整除的数(即余数为O)为一剩余类，被n所除余数为1的数为另一剩余类，余2的数又为一剩余类，以此类推。完全剩余系(Complete Set of Residues)：若将每一剩余类中取一数为代表，形成一个集合，则此集合称为模n的完全剩余系，以Zn表示。很明显地，集合0，l，2，n-1为模n的一完全剩余系。从O到n-1的整数组成的集合构成了模n的“完全剩余系”。这意味着，对每一个整数a，它的模n剩余是从0到n-1之间的某个整数。所谓运算a mod n表示求a被n除的余数，成为模运算。既约剩余系(Reduced Set of Residues)：在模n的完全剩余系中，若将所有与n

40、互素的剩余类形成一个集合，则称此集合为模n的既约剩余系，以表示。例如n=10时，O，1，2，3，4，5，6，7，8，9为模10的完全剩余系；而1，3，7，9)为模lO的既约剩余系。3.3 欧拉函数、欧拉定理和费尔马定理欧拉函数：是一个定义在正整数上的函数，其值等于0，1，2，3，.n-1中与n互素的数的个数。即为模n既约剩余系中所有元素的个数。由定义知，当P是素数时，=P-1。定理3.3.1欧拉定理：若m，a为正整数，有gcd(a，m)=l(gcd，Greatest CommonDivisor，最大公约数)，则。其中为欧拉函数，它是比m小但与m互素的正整数个数。欧拉定理也有一种等价形式：。定理

41、3.3.2设P和q是两个不同的素数，n=pq，则=(P1)(q-1)，对任意的X。及任意的非负整数k，有。定理3.3.3费尔马定理：如果P是素数，且gcd(m，P)=l(可表示为(m，P)=1)，则，费尔马定理还存在另一种等价形式：如果P是素数，m是任意正整数，则。对于素数P来说，所以费尔马定理实际是欧拉定理的一个推论。费尔马定理和欧拉定理及其推论在构成了RSA算法的主要理论基础。3.4 乘法逆元及其求法乘法逆元的定义：若，则称b为a在模n的乘法逆元，b可表示为。利用Euclid(欧几里德)算法(辗转相除法)求乘法逆元：己知a及n且(a,n)=1，求。欧几里德算法是古希腊数学家欧几里德给出的求

42、两个自然数的最大公约数的方法，如果(a，n)=1，则b一定存在。首先介绍利用欧几里德算法求gcd(a，n)的方法，再介绍求乘法逆元的方法。令=n，=a，利用辗转相除法可得 . . . 则为a及n的最大公因子。(欧几里德算法求gcd的主要概念在于：若c=dg+r，则(c，d)=(d，r)。因此在上述算法中，(a，n)=(，)=(，)=。=。可以通过举例说明利用欧几里德算法求逆元的方法，如：求1001b-lmod 3837，b是1001关于模3837的乘法逆元。因为(1001，3837)=l，而3837=31001+8341001=1834+167834=4167+166167=1166+1所以l

43、=167-166=167-(834-4167)=5167834=5(1001834)一834=51001-6834=51001-6(383731001)=231001-63837因此231001l(mod3837)，故1001关于模3837的乘法逆元为23。一般求乘法逆元以欧几里德算法为佳。4 RSA算法介绍1978年美国麻省理工学院(MIT)的研究小组成员李维斯特(RL.Rivest)，沙米尔(AShamir)和艾德勒曼(L.Adleman)在杂志IEEE上发表论文，提出了一种以模幂函数为密码算法的公钥体制，通称为RSA公钥密码体制。RSA的理论基础是数论中的欧拉定理,它的的安全性依赖于大数

44、的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。4.1 RSA公钥加密解密概述RSA密码体制采用下述加密解密变换。4.1.1密钥的产生1) 取两个大素数p和q(保密)；2) 计算模N=pq(公开)，以及欧拉函数=(p一1)(q-1)(保密)，其中是N的欧拉函数值；3) 随机选取整数e(公开)，满足1e,且gcd(e，)=1；4) 计算d(保密)，满足保密de1(),d是e在模下的乘法逆元；5) 以（e,N）为公钥，（d,N）为私钥，销毁p,q,。4.1.2 加密加密时首先将明文比特串进行分组，使得每个分组对应得串在数值上小于，即分组的二进制长度小于。然后，对每个明文分组M，

45、作加密运算：4.1.3 解密对密文分组的解密运算为：由定理1和定理2可以证明解密运算能恢复明文M。图4.1给出RSA算法的加解密的系统框图私钥S=(d,n)公钥P=(e,n)明文M密文C明文M加密解密图4.1 RSA加解密系统框图4.2 RSA算法的应用与举例RSA在应用中包括加密，解密，签名，验证四种。然而，它们的运算核心相同，均为大数的模幂运算，差别仅在于输入输出的不同，下面以数学表达式说明这四种处理过程。假设用户A的公钥为，私钥为，用户B的公钥为，私钥为。我们要完成的任务是，用户A将信息m传给用户B(A加密，B解密)，以及用户A对信息dm签名(A签名，B验证)。4.2.1 RSA算法的应

46、用加密：输入的待处理消息为信息组明文m，使用的密钥为用户B的公钥，输出为密文c。加密过程用计算式表示为解密：输入的待处理消息为密文c，使用的密钥为用B的私钥；输出为解密后的信息组明文m。解密过程用计算式表示为由加密和解密的过程可见，用户A将信息传给用户B的时候，只需要知道B的公钥即可，也就是说，RSA公钥密码系统中，任何人都可以利用该公钥给B传送消息，但是只有拥有解密密钥的用户B才能将信息解密，还原为明文了。签名：输入的待处理消息为信息dm，使用的密钥为用户A的私钥；输出为签名后的签名文本dc，签名过程用算式表示为：验证：输入的待处理消息为签名文本dc，使用的密钥为用户A的公钥；输出为待检测的

47、信息组摘要dm，验证过程用算式表示为：由签名和验证的过程可见，用户A对信息签名之后，用户B(或者其他人)就可以确定该签名是A做的(因为只有A的公钥可以验证)。基于RSA算法可以应用在加密，解密，签名，验证方面，因此目前RSA被广泛应用于各种安全或认证领域，如，web服务器和浏览器信息安全、Email的安全和认证、对远程登录的安全保证和各种电子信用卡系统，起着安全的核心的作用。4.2.2 RSA应用举例(1) 保密信息传输这里通过例子来说明用户之间用RSA来进行保密信息的传输，所采用的简单协议仅仅是为了说明问题，在实际应用中，为了安全，所采用的协议要复杂得多。假定每一用户的公钥(e,n)都是公开

48、的，用户A要给用户B发送保密信息m，执行以下步骤，就可以实现从用户A到用户B的保密信息的传输。用户A查到用户B的公钥。用户A计算要保密信息m的密文。用户A通过网络把密文C发送给用户B。用户B接收密文C。用户B 用自己的私钥计算出保密信息。(2) 数字签名在传统世界里，人们用手写签名来证明一个文件出自某人，或是经他同意的。在数字化世界里，则需要数字签名和验证来取代手写签名功能，RSA就提供了这种数字签名和验证机制。下面以用户A通过网络从银行的账户上支取500元钱来说明如何通过RSA来实现这一功能，具体过程如下：用户A 对数字帐单m用自己的私钥进行加密，即计算用户A 把数字帐单和数字签名s发送给银

49、行。银行则按下列步骤验证用户A的数字帐单m和数字签名s。查到A的公钥。计算。如果m=则完成签名认证，给用户A500元钱；否则，不是数字帐单m就是数字签名s被篡改了，签名无效。因为A的私钥只有A才拥有，因此A在以后不能否认他支取了500元钱，银行也不能诬赖A支取的不是500元钱。4.3 RSA算法的攻击与安全性的讨论理论上，RSA的安全性取决于因式分解模数N的困难性。从严格的技术角度上来说这是不正确的，在数学上至今还未证明分解模数就是攻击RSA的最佳方法，也未证明分解大整数就是NP问题(表示那些能在多项式时间内利用“不确定性图灵机可以求解的问题)。事实情况是，大整数因子分解问题过去数百年来一直是

50、令数学家头疼而未能有效解决的世界性难题。人们设想了一些非因子分解的途径来攻击RSA体制，但这些方法都不比分解n来得容易。因此，严格地说，RSA的安全性基于求解其单向函数的逆的困难性。RSA单向函数求逆的安全性没有真正因式分解模数的安全性高，而且目前人们也无法证明这两者等价。许多研究人员都试图改进RSA体制使它的安全性等价于因式分解模数。对RSA算法的攻击主要有以下几种：4.3.1 对RSA的分解模数n攻击分解模数n是最直接的攻击方法，也足最困难的方法。攻击者可以抉得公开密钥e和模数N；如果模数N=pq被因式分解，则攻击者通过P和q便可计算出=(p-1)(q-1)，进而由ed1(mod)而得到解

51、密密钥d。大整数分解研究一直足数论与密码理论研究的重要课题。4.3.2 对RSA的选择密文攻击选择密文攻击足攻击者对RSA等公钥算法最常用的攻击，也是最有效的攻击手段之一。选择密文攻击通常是由RSA加密变换的性质诱发的，常见的对RSA的选择密文攻击有三种：明文破译。攻击者获得某用户A使用公钥e加密的密文Y=(modN)，并试图恢复出消息X。随机选取rn，计算，这意味。计算。令，则，现在攻击者请A对消息进行签名,得到。攻击者计算，得到了明文。骗取仲裁签名。在有仲裁情况下，若某用户A有一个文件要求仲裁，可先将其送给仲裁T，T使用RSA的解密密钥进行签名后送给A。攻击者有一个消息想要T签名，但T并不

52、想给他签，因为可能有伪造的消息，也可能是来自非法使用者的消息。但攻击者可用下述方法骗取T的签名。令攻击者的消息为X，他首先任取一个数N，计算(e是T的公钥)，然后计算M=yx，送给T，T将签名的结果送给攻击者，则有：攻击者成功骗取T对x的签名。伪造合法签名。攻击者利用自己伪造两个消息和来拼凑出所需要的。攻击者如果得到用户A对和的签名和，就可以计算的签名4.3.3 对RSA的小指数攻击这类攻击专门针对RSA算法的实现的细节。采用小的e、d可以加快加密和验证签名的速度，而且所需的存储空间小，但是如果e、d太小，则容易受到小指数攻击，包括低加密指数攻击和低解密指数攻击。通过独立随机数字对明文消息X进

53、行填充，这样使得，可以有效地抗击小指数攻击。4.3.4 对RSA共模攻击在RSA公钥密码的实现中，为简化问题，可能会采用给每个人相同的刀值，但不同的指数值e和d。这样做的问题是，如果同一信息用两个不同的指数加密，这两个指数是互素的，则不需要任何解密密钥就能恢复明文。设m是明文，两个加密密钥分别为和，共同的模数为n，两个密文为：由于和是互素的，由扩展的欧几里德算法可以找到r和s，使之满足假设r是负数(其中必有一个为负数)，再次使用欧几里德算法可以求得对模数n的逆元，故可以得到即密码分析者知道n,和，则可以恢复出明文m。4.3.5 关于RSA算法的明文部分信息安全性同RSA算法一样，大多数的公钥密

54、码体制的安全性是建立在单向函数之上的，即所谓的单向函数模型密码体制。RSA算法使用的单向函数的安全性是基于大数分解的困难性，即攻击者在多项式时间内不能分解模数n。但这并不能保证攻击者很难使用概率方法来推算明文的某些特征或用二进制表示某个或某些比特的值(即明文的部分信息)。攻击者通过获取明文消息的部分信息，进而可以破译或恢复整个明文信息。这就是RSA安全性的另一个重要方面，可以称之为比特安全性，即RSA算法中密文所泄漏的有关明文二进制表示的某些有效位的部分安全性。关于RSA体制部分信息安全性的最好结果是由W.Aiexi等人得出的。他们证明了任何由密文E(x)(E为加密函数)以不小于的正确概率猜对

55、最末有效位的算法F，都可诱导出一种由密文E(石)破译出石的相对于算法F的非确定多项式算法，即所谓的最末有效位安全性。4.3.6 RSA的安全性讨论判断一个密码系统是否安全，不能从算法设计角度分析，而应该看其能否抵抗各种攻击。密码界有句格言：只有密码分析者能评判密码体制的安全性。因此，在分析RSA的安全性时，必须讨论其攻击方法，看其是否足够强劲以抵御这些攻击。RSA公钥密码系统就是基于这样的一个事实：给定两个大素数p和q，要获得他们的乘积n=pq很容易，但是如果给定一个刚好是两个大素数乘积的台数n，要找出这个合数的两个素因子非常困难。分解大整数模n是最显而易见的攻击方法。虽然无法证明，RSA密码

56、算法的强度等同于大数模n的因子分解，但目前还没有找到比分解模n更快的攻击方法。如果击者分解了模n，得到其因子p和q，那么结合公开的加密指数e，找到对应的解密指数d就轻而易举，解密密文自然也不成问题。在正常情况下，攻击RsA算法的方法就是求合数的素因子分解。RSA公钥密码体制的公开密钥是目前最难分解的一类合数，专用的分解方法和数域筛的方法都不会对这类数构成危险。对于在100位至200位之间的数，每增加3位，则分解时间将增加一倍。由此推算，每秒10亿次的计算机在一天内最多也就分解一个不到100位的合数；而分解一个200位的合数，用通用的方法，大概需要天的时间。现在，无论计算机的速度，还是数量，都不

57、可能有超过倍的增长。目前，十进制129位的数也被分解，因此，n要大于这些数。为了使模n的分解难以实现，要求：1）模n足够大。这是为了防止采用穷举搜索来寻找n的因子。至于究竟需要多大，和当前的因子分解技术和具体密码系统的应用背景有关。只要满足使因子分解的代价大于解密获取的利益即可。2)大素数p和q应该足够大，若p或q是小素数，穷举搜索小素数集合，也会很快找到p，q。另外p和q相差不能太小，因为若p和q大小相若，则可通过对模n取平方根，较快地找到p、q。3)大素数p和q应为随机产生，不能具有特殊形式或取自某个素数表，显然，具有特殊形式的素数首先是因子分解的尝试对象。基于以上的分析来考虑，本文选取模

58、为二进制1024位的RSA算法，采用随机数产生函数结合Miller-Rabin素数检测来产生大素数，且p和q的位数不相同，从一定程度上保证了算法的安全性。这些重要函数的实现将会在后续章节给出详细的实现方案。4.4 RSA参数的选择RSA遭受攻击的很多情况是因为算法实现的一些细节上的漏洞所导致的，所以在使用RSA算法构造密码系统时，为保证安全，在生成大素数的基础上，还必须认真仔细选择参数，防止漏洞的形成。根据RSA加解密过程，其主要参数有三个：模数N，加密密钥e，解密密钥d。4.4.1 模数N的确定虽然迄今人们无法证明，破解RSA系统等于对N因子分解，但一般相信RSA系统的安全性等同于因子分解，

59、即：若能分解因子N，即能攻破RSA系统，若能攻破RSA系统，即能分解因子。因此，在使用RSA系统时，对于模数N的选择非常重要。在RSA算法中，通过产生的两个大素数P和q相乘得到模数，而后分别通过对它们的数学运算得到密钥对。由此，分解模数得到P和q是最显然的攻击方法，当然也是最困难的方法，如果模数n被分解，攻击者利用得到的P和q便可计算出=(P-1)x(q-1)，进而通过公开密钥由解密密钥d，则RSA体制立刻被攻破。相当一部分的对RSA的攻击就是试图分解模数N，选择合适的是实现RSA算法并防止漏洞的重要环节。一般地，模数N的确定可以遵循以下几个原则：P和之差要大。当p和q相差很小时，在已知n的情

60、况下，可假定二者的平均值为，然后利用，若等式右边可开方，则得到及，即N被分解。Pl和q一1的最大公因子应很小。P和q必须为强素数。一素数P如果满足:条件一：存在两个大素数，使得|p-1且|p+1；条件二：存在四个大素数使得。则此素数为强素数。其中称为3级的素数，称为2级的素数，P则称为1级的素数，很明显地，任何素数均为3级的素数。只有两个强素数的积所构成的n，其因子分解才是较难的数学问题。P和q应大到使得因子分解N为计算上不可能。RSA的安全性依赖于大数的因子分解，若能因子分解模数N，则RSA即被攻破，因此模数N必须足够大直至因子分解N在计算上不可行。因子分解问题为密码学最基本的难题之一，如今

61、，因子分解的算法已有长足的进步，但仍不足以说明RSA可破解。为保证安全性，实际应用中所选择的素数P和拿至少应该为300位以上的二进制数，相应的模数将是600位以上的二进制数。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。随着计算能力的提高和分布式运算的发展，安全密钥的长度将是动态增长的。Jadith Moore给出了使用RSA时有关模数的一些限制：若给定模数的一个加/解密密钥指数对已知，攻击者就能分解这个模数。若给定模数的一个加/解密密钥指数对已知，攻击者无需分解模数就可以计算出别的加/解密密钥

62、指数对。在通信网络中，利用RSA的协议不应该使用公共模数。消息应该用随机数填充以避免对加密指数的攻击。4.4.2 e的选取原则在RSA算法中，e和矽()互质的条件容易满足，如果选择较小的e，则加、解密的速度加快，也便于存储，但会导致安全问题。一般地，e的选取有如下原则：e不能够太小。在RSA系统中，每人的公开密钥P只要满足即可，也即e可以任意选择，为了减少加密运算时间，很多人采用尽可能小的e值，如3。但是已经证明低指数将会导致安全问题，故此，一般选择e为16位的素数，可以有效防止攻击，又有较快速度。e应选择使其在的阶为最大。即存在i，使得，可以有效抗击攻击。4.4.3 d的选取原则一般地，私密

63、密钥d要大于。在许多应用场合，常希望使用位数较短的密钥以降低解密或签名的时间。例如IC卡应用中，IC卡CPU的计算能力远低于计算机主机。长度较短的d可以减少IC卡的解密或签名时间，而让较复杂的加密或验证预算(e长度较长)由快速的计算机主机运行。一个直接的问题就是：解密密钥d的长度减少是否会造成安全性的降低?很明显地，若d的长度太小，则可以利用已知明文M加密后得，再直接猜测d，求出是否等于M。若是，则猜测J下确，否则继续猜测。若d的长度过小，则猜测的空间变小，猜中的可能性加大，已有证明当d时，可以由连分式算法在多项式时间内求出d值。因此其长度不能过小。5 RSA算法的系统及实现由前面的分析知道，RSA算法的实现都是基于大数的运算，RSA算法实现主要包括大素数的产生、密钥对的产生和消息处理。大素数的产生是指大素数p和q的产生，这是RSA算法的基础，没有合适的p，q，RSA就成了空话；密钥对的产生，就是指公钥和私钥的产生，现代密码系统的安全性几乎完全等价于密钥的安全性，因此，必须寻求合适的密钥对