《毕业设计（论文）RSA加解密算法的研究与实现.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）RSA加解密算法的研究与实现.doc（50页珍藏版）》请在三一办公上搜索。
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 RSA公钥加密解密概述174.1
2、.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 大素数生成实现2852 密
3、钥对产生实现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 implementationINTRODUCTIONSince 1990,with t
9、he 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 into symmetri
10、cal 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 of the outstand
11、ing 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 which is proposal
12、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 is a research
13、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 important safeguar
14、d 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 Visual C+to implem
15、ent 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 security systemRSA al
16、gorithms 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 cryptography a
17、nd 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. Introduces som
18、e 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 algorithm，which is a
19、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 high security a
20、nd 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和LAdleman三人在文章实现数字签
24、名和公钥密码体制的一种方法中共同提出的，是最具代表性的公钥密码体制。由于算法完善(既可用于数据加密，又可用于数字签名)，安全性良好(据传山东大学信息科学与工程学院的季凯和他的破解团队成员刘强等人宣布己找到可有效破解RSA的方法，并公布了算法，但未经证实)，易于实现和理解，RSA已成为一种应用极广的公钥密码体制，它的提出真正使得互不相识的通信双方在一个不安全的信道上进行安全通信最终成为可能。在广泛的应用中，不仅它的实现技术日趋成熟，而且安全性也逐渐得到事实的证明，因此人们对RSA十分重视。但在实现过程中，由于算法中包含有大数的乘方运算，在计算机上运算时，会耗费大量的时间，严重影响了RSA的加密效
25、率，制约了它的应用，因此人们对其从不同方面进行了改进，并形成了以下实现算法：传统实现算法。由Rivest等人在RSA体制建立时提出，是把乘方后求模的计算改为在边乘方边求模的计算，以减小中间结果的数值，尽量避免大数的乘方计算。该算法在一定程度上改善了RSA的效率。SMM算法。是利用“乘同余对称特性”来减少加密和解密运算中乘法和求模运算量的一种改进算法。其本质是减小求幂运算中的基数的大小，但并没有考虑指数的情况，故只是在一定的程度上改进了原算法的效率。指数2k进制化算法。是通过缩短指数的长度来减少迭代的次数，从而提高计算效率。但是，在求幂运算的过程中，基数的大小也是影响运算速度的重要因素，而该算法
26、只是减小了指数的长度。RSR算法。是将RSA传统算法中的求模运算变成一系列2的乘幂的余数和运算，可以在一定程度上提高计算速度，但是由于在实际实现时，RSR算法要进行对大整数进行字节、比特的不断转换，不适合与其他算法联合使用。此外还有蒙哥马利算法、利用中国剩余定理降指法等。总之，上述各个实现算法分别从不同方面改进了RSA加密算法，使得加密速度有了一定的提高。但是，随着计算机软、硬件的不断发展，数据量也在急剧增大，对加密的速度要求也越来越高，人们需要不断改进加密算法，以提高加密运算的速度。1.3 本文的工作和内容安排在阅读大量国内外研究成果的基础上，讨论了针对 RSA 的各种攻击方法，以及如何作出
27、处理以抵制这些攻击；讨论了RSA 的安全性和RSA 的参数选择详细讨论了大素数的生成和检测；研究了RSA 公钥密码系统中用到的算法；以同余理论为基础，推广了整除性的两个性质；实现了RSA 公钥密码体制大部分算法模块；提出了一种快速模运算算法。本文的工作分一下七章完成：第1章绪论。阐述了课题的研究背景和意义，国内外的研究现状和发展趋势，并介绍了本文研究的主要内容。第2章密码学概述。介绍了密码学的一些基本概念以及密码分析技术，讨论了密码学中的安全性定义，引出了公钥密码体制与私钥密码体制。第3章公钥密码的数论基础。介绍了公钥密码系统中应用到的基本数论知识，为后面相关章节奠定理论基础。第4章RSA算法
28、介绍。对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 密码分析技术密码分析学是密码学的一个重要分支，是研究在不知道密钥的情况下，利用密钥体制的弱点恢复明文的一门学科。对一个密码系统采取截获密文进行分析的这类攻击称为被动攻击(Passive Attack)；
31、另一种是主动攻击(Active Attack)，即非法入侵者主动向系统进行攻击，采取删除、更改、增添、伪造等手段向系统插入假信息，以达到窃取非法信息的目的。密码攻击者攻击密码体制的方法主要有以下三种：1.穷举攻击：密码攻击者通过试遍所有的密钥来进行破译。当然，可以通过增大密钥量来对抗穷举攻击。2.统计分析攻击：密码攻击者通过分析密文和明文的统计规律来破译密码。对抗这种攻击方法是设法使明文的统计特性和密文的统计特性不一样。3.数学分析攻击：密码攻击者针对加密变换的数学基础，通过数学求解的方法来设法找到相应的解密变换。对这种攻击方法，应该选用具有坚实的数学基础和足够复杂的加密算法。根据密码攻击者在
32、密码系统中获得信息的不同，通常可以在下述四种情况下对密码体制进行攻击：1.唯密文攻击(ciphtext-only attack)：密码攻击者仅知道一些密文。2.已知明文攻击(Known-plaintext Attack)：密码攻击者知道一些明文和相应的密文。3.选择明文攻击(Chosen-plaintext Attack)：密码攻击者可以选择一些明文，并得到相应的密文。4.选择密文攻击(Chosen-ciphertext Attack)：密码攻击者可以选择一些密文，并得到相应的明文。以上四种方法中，唯密文攻击的强度最弱，其他情况的攻击强度依次增加。2.3 密码学中的安全性定义荷兰密码学家Ker
33、ckhoff对密码安全性分析做了如下假设：一个信息安全系统的安全性取决于对密钥本身的保护，而不是对系统或者通信硬件的安全保护。对于一个密码体制，如果密码分析者无论获得多少密文以及用什么方法进行攻击都不能破译，则称绝对不可破译的密码体制。绝对不可破译的密码体制在理论上是存在的。但是，只要有足够的资源，那么任何实际的密码体制都是可以破译的。因此，更有实际意义的是在计算上不可破译的密码体制。密码系统只要满足以下两条重则之一就称为计算上不可破译：（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)求x“极为困难，以至于实际
38、上不可能做到。则称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个不同的剩余类；为n所整除的数
39、(即余数为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互素的正整数个数。欧拉定理也有一种等价形式：。定理3.3.2设P和q是两个不同
41、的素数，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=167-166=167-(
43、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，作加密运算：4.1.3 解密
45、对密文分组的解密运算为：由定理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的公钥；输出为待检测的信息组摘要dm，验证过程用算
47、式表示为：由签名和验证的过程可见，用户A对信息签名之后，用户B(或者其他人)就可以确定该签名是A做的(因为只有A的公钥可以验证)。基于RSA算法可以应用在加密，解密，签名，验证方面，因此目前RSA被广泛应用于各种安全或认证领域，如，web服务器和浏览器信息安全、Email的安全和认证、对远程登录的安全保证和各种电子信用卡系统，起着安全的核心的作用。4.2.2 RSA应用举例(1) 保密信息传输这里通过例子来说明用户之间用RSA来进行保密信息的传输，所采用的简单协议仅仅是为了说明问题，在实际应用中，为了安全，所采用的协议要复杂得多。假定每一用户的公钥(e,n)都是公开的，用户A要给用户B发送保密信息m，执行以下步骤，就可以实现从用户A到用户B的保密信息的传输。用户A查到用户B的公钥。用户A计算要保密信息m的密文。用户A通过网络把密文C发送给用户B。用户B接收密文C。用户B 用自己的私钥计算出保密信息。(2) 数字签名在传统世界里，人们用手写签名来证明一个文件出自某人
