毕业设计（论文）RSA加密算法的分析与实现.doc

河 南 科 技 大 学毕 业 设 计（论 文） 题目:RSA加密算法的分析与实现姓 名： 考 号： 院 系： 信系工程系 专 业： 计算机及应用 指导教师： 2011年04月24日摘 要随着信息产业的迅速发展，人们对信息和信息技术的需要不断增加，信息安全也显得越来越重要。基于对网络传输数据安全性的考虑，保障网络信息安全的加密产品具有广泛的应用前景，密码技术则是保障信息安全的一个重要手段。密码学是信息安全技术的核心，现代密码体制分为公钥体制和私钥体制两大类:私钥体制又称单钥体制，其加密密钥和解密密钥相同;公钥体制又称为双钥体制，其加、解密密钥不同，可以公开加密密钥，而仅需保密解密密钥，从而具有数字签名、鉴别等新功能，被广泛应用于金融、商业等社会生活各领域。RSA是目前公认的在理论和实际应用中最为成熟和完善的一种公钥密码体制，不仅可以进行加密，还可以用来进行数字签名和身份验证，是公钥密码体制的代表。大数模幂乘运算是实现RSA等公钥密码的基本运算，该算法存在的问题是在实现时耗时太多，这也是制约其广泛应用的瓶颈。本论文的第一章介绍了国内外密码学和RSA的有关动态以及本论文的意义，第二章介绍密码学的有关知识，第三章对RSA算法进行分析、介绍，第四章是RSA加密与解密的实现的代码和测试，第五章对本课题的结论。最后是致谢和参考文献。关键词:密码学，RSA公钥密码体制，信息安全ABSTRACT With the rapid development of IT technology, people depend on it increasingly, As a result, information security is getting more and more important. Meanwhile, Products that ensure network information show a great prospect due to the importance .Of transmitting data by network safely, and as an important means of information Security, cryptography must be lifted.Cryptography is the core of the information security. Modern cryptograph is, Divided into the public key system and the private key system. The private key system, Is also called the single key system, in which the encryption process is the same as the. Decryption process. The public key system is also called the double key system, Where 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, Many new applications such as the digital signature and authentication, which is. ideally used in every field of the society.Among the various public key cryptosystem, RSA algorithm is the best choice in, Both theory and application, and it is open used in digital signature and identificationSystem. Modular exponentiation and modular multiplication are the basic algorithms. For implementing the public key algorithms such as RSA, etc. However the, Time-consuming modulo exponentiation computation, which has always been the, Bottle-neck of RSA restricts its wider application. The first chapter introduces the domestic and foreign progress of cryptograph; The RSA related tendency as well as the meaning of the research. The second chapter Explains cryptograph. The third chapter describes and analyzes the RSA algorithm. The fourth chapter discusses the improvement of the RSA algorithm including the big, Number restore and operation, and the improvement algorithm of the” Square multiply" algorithm. The fifth chapter reprints an improved algorithm and Comparisons.KEY WORDS: cryptography, RSA, public key cryptosystem, information security目 录摘 要1ABSTRACT2第一章 引 言61.1 研究背景61.2 信息加密技术61.3 密码技术研究现状81.4 研究本课题的意义9第二章 密码学概论112.1 密码学的基本概念112.2 古典密码体制142.3 对称密码体制142.3.1 DES (Data Encryption Standard)162.3.2 AES(Advanced Encryption Standard)182.4 公钥密码体制192.5密码分析技术21第三章 RSA公钥密码体制243.1RSA的数学基础知识243.1.1 因子的概念243.1.2 素数与合数253.1.3 公约数与最大公约数263.14 互质数273.2 RSA算法283.2.1 RSA体制描述283.2.2 RSA工作原理29第四章 RAS的加密与解密技术的实现324.1 RSA加密与解密代码324.2 测试的环境与工具344.3 测试的结果35第五章 结论365.1 结论36致谢37参考文献38第一章 引 言1.1 研究背景自20世纪90年代以来，计算机网络技术得到了空前飞速的发展和广泛的应用，但网络在带给我们方便快捷的同时，也存在着种种安全危机，随着计算机应用的日益广泛和深入，信息交流和资源共享的范围不断扩大，计算机应用环境日趋复杂，计算机的数据安全问题也越来越重要。在计算机网络日益扩大和普及的今天，计算机对安全的要求更高、涉及面更广。其内容主要包括: (1)实体安全。实体安全是指对场地、环境、设施、设备、载体、人员采取的各种安全对策和措施; (2)数据传输网络安全。是指信息、在数据传输网络中传输时，如何保证其安全性的问题，避免在传输途中遭受非法窃取、篡改等; (3)软件安全。它涉及信息在存储和处理状态下的保护问题; (4)信息安全。即数据安全，是指系统有能力抵抗外来非法入侵者对信息的恶意访问、泄漏、修改和破坏等，即:机密性、完整性、可用性。所以，如何实现计算机网络中数据安全传输近年来一直是人们研究的课题之一。1.2 信息加密技术信息加密技术是信息安全技术l2的核心技术，其主要目的是防止恶意攻击者非法破译系统中的机密信息。数据加密技术可以提高信息系统及数据的安全性和保密性，防止秘密数据被外部破译所采用的主要技术手段之一。而密码学是研究通信安全保密的科学，其目的是保护信息在信道上传输过程中不被他人窃取、解读和利用，它主要包括密码编码学和密码分析学两个相互独立又相互促进的分支。前者研究将发送的信息(明文)变换成没有密钥不能解或很难解的密文的方法;而后者则研究分析破译密码的方法。其发展经历了相当长的时期。第一次世界大战之前，密码学的重要进展根本是不为人知的，很少有文献披露这方面的信息。直到1918年由WF.Friendlunn论述了重合指数及其在密码学中的应用以及转轮机专利的发表才引起了人们的重视，但仅仅由军事和秘密部门所控制。第一次世界大战之后到20世纪40年代末期，密码学家们将信息理论、密码学和数学结合起来研究，使信息论成为了研究密码编码学和密码分析学的重要理论基础。完全处于秘密工作状态的研究机构开始在密码学方面取得根本性的进展，最具代表性的有Shannon(香农)的论文保密系统的通信理论和通信的数学理论，他将安全保密的研究引入了科学的轨道，从而创立了信息论的一个新学科。从20世纪50年代初期到60年代末期的20年中，在密码学的研究方面公开发表的论文极少，但David Kahn于1967年出版的著作破译者使密码学的研究涉及到了相当广泛的领域，使不知道密码学的人了解了密码学，因此密码学的研究有了新的进展。自20世纪70年代初期到现在，随着计算机科学与技术的发展，促进了密码学研究的兴起和发展，人们使用密码学技术来保护计算机系统中信息的安全。因此，在密码学的研究和应用等方面取得了许多惊人的成果和理论。具有代表性的有:(l)由Daffier和Hellman于1976年发表的“密码学的新方向”一文提出了公开密钥密码学(即公开密钥或双密钥体制)，打破了长期沿用单密钥体制的束缚，提出了一种新的密码体制。公开密钥体制可使收、发信息的双方无须事先交换密钥就可秘密通信。(2)由Horst Festal研究小组于20世纪70年代初着手研究美国数据加密标准(Data Encryption standard，DES)，并于1973年发表了“密码学与计算机保密”等有价值的论文，该文论述了他们的研究成果并被美国标准局伽BS)采纳，于1977年正式公布实施为美因数据加密标准并被简称为Desk标准。上述密码学的发展可粗略的划分为三个阶段:第一阶段(194·9年之前)的密码学可以说不是什么学科，仅为一门艺术;第二阶段(1949年到1975年)可以说是密码学研究的“冬天”，成果和论文少且为单密钥体制，但在这一阶段有如Shaman的理论和Dave记Kahn的著作并为密码学奠定了坚实的理论基础;第三阶段(1976年到现在)可以说是密码学研究的“春天”，密码学的各种理论和观点百花齐放，应用成果累累。1.3 密码技术研究现状密码技术是信息安全技术的核心，它主要由密码编码技术和密码分析技术两大分支组成。密码编码技术的主要任务是寻求产生安全性高的有效密码算法和协议，以满足对消息进行加密或认证的要求。密码分析技术的主要任务是破译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏话动。这两个分支既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展。目前人们将密码理论与技术分成两大类，一类是基于数学的密码理论与技术，包括公钥密码、分组密码、序列密码、认证码、数字签名、Hash函数、身份识别、密钥管理、PKI技术、VPN技术等;另一类是非数学的密码理论与技术，包括信息隐藏、量子密码、基于生物特征的识别理论与技术等。现在世界上的一些大国都非常重视密码学研究I3jI4。在美国国家安全局(Nast)和国家标准技术研究所(Mist)的共同推动下，20世纪70年代以来陆续建立了国家数据加密标准(DES)和数字签名标准(D55)，2001年又确定了高级加密标准算法(AES)以作为21世纪的应用基础。美国政府为了适应信息社会发展的需要，加强政府司法机构的社会管理执法的高技术支撑能力和情报部门的对抗信息战的能力，正通过Nast提出并推动着密钥托管、密钥恢复、证书授权认证、公开密钥基础设施、公开密钥管理基础设施等一系列技术手段、技术标准和相关理论基础的研究。国际上对在分组密码和序列密码设计和分析的理论和技术已经比较成熟。除了算法的设计之外，美国、欧洲、日本发达国家在加密算法的标准化方面做了大量的工作。我们国内的学者也设计了很多对称加密算法，但是目前的问题是，国内还没有一个统一的加密标准。可喜的是，目前有关部门正在组织对加密标准的讨论和征集。1.4 研究本课题的意义加密技术按照密码使用方法不同可以分为对称密钥算法和非对称密钥算法。对称密钥算法中，加密、解密都使用相同的密钥。非对称密钥算法又称公钥密码算法，即加密、解密使用两个不同的密钥。由于公钥密码算法在保证数据的机密性、完整性以及签名和认可等方面的突出优点，它已经成为当今网络安全中最重要的解决方法。在众多的公钥密码体制中，1978年由Rivets，Shamir和Adelman在美国MIT提出的Rosa算法156被公认为是目前理论和实际应用中最为成热和完善的一种公钥密码体制，可以用来进行数字签名和身份验证。该算法的安全性依赖于大整数的素数因子分解的困难性，其最基本最核心的算术操作是模乘运算，再由一系列的模乘来完成模幂运算。RSA体制算法完善(既可用于数据加密，又可用于数字签名)，安全性良好，易于实现和理解。使用RSA体制作为课题算法和方案的实现基础，我们可以有效地利用RSA体制的优点。同时，关于RSA体制的大量的研究工作的文献和成果为本文研究工作的开展提供了良好的基础。RSA体制是最具代表性的公钥密码体制。RSA体制的特点使得它成为公钥密码体制研究的一个标准模板。同时，由于RSA算法发展至今，在实现技术上己经相当成熟，因此本文算法的实现在许多方面都可以利用己有的技术，这对增强算法的实用性是非常有益的。RSA算法计算复杂，实现的难度大。软件实现主要问题是加密、解密操作要计算位数达十进制百位以上的模幂乘函数。执行的时间长，难以满足实际使用要求。在实际应用中，其加密和解密的速度是主要的问题，所以研究RSA的快速算法具有非常重要的现实意义。本论文主要研究了密码学尤其是RSA的发展历程，及目前RSA在应用中面临的问题。在大量阅读国内外重要文献资料的基础上，深入剖析了RSA算法的精要。第二章 密码学概论密码学7的历史极为久远，其起源可以追溯到远古时代，人类有记载的通信密码始于公元前400年。虽然密码是一门古老的技术，但自密码诞生直至第二次世界大战结束，对于公众而言，密码始终处于一种未知的黑暗当中，常常与军事、机要、间谍等工作联系在一起，让人在感到神秘之余，又有几分畏惧。信息技术的发展迅速改变了这一切。随着计算机和通信技术的迅猛发展，大量的敏感信息常常通过公共通信设施或计算机网络进行交换，特别是intermit的广泛应用、电子商务和电子政务的迅速发展，越来越多的个人信息需要严格保密，如:银行账号、个人隐私等。正是这种对信息的秘密性与真实性的需求，密码学才逐渐揭去了神秘的面纱，走进公众的日常生活当中。本章回顾了密码学的基础知识，包括密码学的基本概念、密码理论与技术基础、认证理论与技术基础以及密码分析学基础。这些基础概念和知识是本课题研究工作的理论与技术基础。2.1 密码学的基本概念首先我们明确一下本文所使用的密码学的一些基本概念。它们将贯穿本文的由始至终。定义1密码学 (Cryptology)是研究信息系统安全保密的科学。它包括两个分支，即密码编码学和密码分析学。定义2密码编码学(Cryptography)是对信息进行编码实现信息隐蔽的技术和科学。定义3密码分析学(Cryptanalysis)是研究分析破译密码的技术与科学。定义4明文(Plaintext)是指发送方想要发送给接受方的消息。定义5密文(Cipher text)是指明文被加密后的消息。定义6加密(Encryption)将明文变换为密文的过程。定义7解密(Decryptions)将密文恢复为明文的过程。定义1.8一个密码体制是满足以下条件的五元组(P，C，K，E，D):1.P表示所有可能的明文组成的有限集。2.C表示所有可能的密文组成的有限集。3.K代表密钥空间，是由所有可能的密钥组成的有限集。4.对任意的，都存在一个加密法则和相应的解密法则。并且对每一:和:对任意的明文，均有。通常人们用香农(Salmon)的密码模型来说明密码体制。Shalom提出的保密系统的模型8如图2-1所示:它由以下几部分组成:明文空间P，密文空间C，密钥空间K1和k2单钥体制下K1=k2=k3密钥K需通过安全的密钥通道由发送方传给接密变换EK1:，由加密器完成，其中;解密变换DK2:密器完成，其中。称五元组(P，c，K，E，D)为一保密系统。 如果一个密码体制的，或由其中一个很容易推出另一个，钥密码体制或对称密码体制或传统密码体制(one- key Cryptosystem，其是美国的数据加密标准Desk(Data Encryption Standard): 其中 （3.2）否则，称为双体制或非对称密码体制。进而，如果在计算上K2不能由K1推出，这公开也不会损害K2的安全，于是便可以将K1公开。这种密码体制称码体制(public一key Cryptosystem)，其典型代表是Rosa密码体制。根据对明文的划分与密钥的使用方法的不同可将密码体制分为分序列密码体制。分组密码是将明文M划分为一系列明文块M1，M2，Mn，通常若干字符，并且对每一块Mi都用同一个密钥Kill进行加密，即C=(C1,C2,Cn)。序列密码将M划分为一系列的字符或位m1，m2，mn，并且对于这每一个mi用密钥序列KI=(Kl1，Kl2，Kln)的第I个分量Kli来加密，即C=(C1，C2，Cn)，其中Ci=E(mi，kli)，i=l，2，n分组密码一次加密一个明文块，而序列密码一次加密一个字符或一个位。两种密码在计算机系统中都有广泛应用。为了实现信息的保密性，抗击密码分析，保密系统应当满足下述要求:即使达不到理论上是不可破解的，也应当是实际上是不可破解的。也就是说，从截获的密文或某些己知明文密文对，要确定密钥或任意明文在计算上是不可行的;保密系统的安全性应依赖于密钥，而不是依赖于密码体制或算法本身的细节的安全性;加密解密算法实用于所有密钥空间中的元素;系统应该易于实现和使用方便。2.2 古典密码体制古典密码是密码学的渊源，这些密码都是由基于字符的密码算法构成的，可用手工或机械操作实现加解密。不同的密码算法是字符之间互相代换或者是互相置换，好的密码算法是结合这两种方法，每次进行多次运算。虽然现在己经很少采用了，但原理还是没变。重要的变化是算法对位而不是对字符进行变换，实质上这只是字母表长度的改变。古典密码的基本运算有两种代替(substitution)和换位(Transposition)。代替是指每一个或一组字符被另一个或另一个或一组字符所取代;换位是不改变明文字符，而按一定规则重新安排字符次序。实际的密码算法是执行一系列这两种基本运算的不同组合，即得到所谓的乘积密码。比较有名的古典密码包括J恺撒(Kaiser)密码、维吉利亚(viewers)密码、维尔南(Velma)、普莱费厄(pl即fair)密码和希尔(Hill)密码等。2.3 对称密码体制对称密码体制10又叫私钥密码算法，是指能够从解密密钥中推算出加密密钥，反过来也成立。在大多数的对称密码体制中，加密密钥和解密密钥的，它要求发送者和接收者在通信之前协商一个安全的密钥，因此有时码也称为单钥密码。单钥密码体制的安全性主要取决于算法和密钥的长漏密钥就意味着任何人都能对消息进行加、解密。对称密码体制不仅可以用于数据加密，也可以用于消息认、证。但是码体制存在着严重的缺陷:在进行安全通信之前，通信的双方必须通过道商定和传送密钥，而在实际的通讯网中，通信双方很难确定一条合理通道;另外一个问题就是密钥的管理。在拥有大量用户的计算机通信网个相互进行保密通信的用户需要N(N一1)/2个密钥;当N值比较大的钥管理的开销极大，密钥只能记录在计算机内存或外存上，这.本身就是全的。分组密码一般的设计原则包括:分组长度n要足够大，使分组代替字母表中的元素个数2n足够大明文穷举攻击法奏效。密钥量要足够大(即置换子集中的元素足够多)，尽可能消除弱密钥有密钥无特殊性可分析，以防止密钥穷举攻击奏效。但密钥又不能过长于密钥的管理。由密钥确定代替的算法要足够复杂，充分实现明文和密文的扩散没有简单的关系可循，要能抗击各种己知的攻击，如差分攻击和线性攻加密和解密运算简单，易于软件和硬件的快速实现。数据扩展。一般无数据扩散，在采用同态置换和随机化加密技术入数据扩展。差错传播尽可能地小。为了抗击统计分析破译法，需要实现三条要求，Shannon曾建议采用扩散 (Diffusion)和混淆(confusedly)法。所谓扩散，就是将明文及密钥的每一位数字的影响尽可能迅速地扩散到输出密文的较多个数字中，以便隐蔽明文数字的统计特性。在理想情况下，明文的每一位bit和密钥的每一bit应影响密文的每一bit即实现所谓的“完备性”。Sharman提出的“混淆”概念目的在于使作用于文明的密钥和密文之间的关系复杂化，使明文和密文之间、密文和密钥之间的统计相关性极小化，从而使统计分析攻击法不能奏效。扩散和混淆原则是设计分组密码的基本准则，到达良好的扩散和混淆效果是分组密码设计的核心问题Shannon还提出了“乘积”的方法，所谓“乘积密码”，是将若干个密码复合。例如，设有两个子密码T和S，我们先以T对明文进行加密，然后再以S对所得的结果进行加密，则乘积密码可表示为F二ST。利用这种方法常可将简单易于实现的密码组合成复杂的更为安全的密码。分组密码的特点是将明文消息编码后的数字序列在密钥的控制下变换成等长的数字序列。分组密码的输入输出序列长度预先己确定(一般二者相等)，故从本质上看，这种密码可看作是字长为分组长度的数字序列的代换密码。著名的数据加密标准(Data Encryption Standard，DES)是分组密码家族的一个成员，它作为世界范围的标准己经有20多年的历史了。其他比较有名的分组密码算法还有国际数据加密算法(IDEA)Ghost算法等。2.3.1 DES (Data Encryption Standard)数据加密标准DES(Data Encryption standard)算法由IBM公司开发，并被美国国家标准局困（NIST)于1977年2月采纳作为“非密级”应用的一个标准，此后， DES成为全世界使用最广泛的加密标准。DES是迄今为止最为广泛应用的一种加密算法，也是最具代表性的一种分组密码体制。DES对于推动密码理论的发展和应用起了重大作用，掌握和了解这一算法的基本原理、设计思想、安全性分析等问题，对于研究分组密码理论和其实际应用具有重要意义。DES是一种对二元数据进行加密的方法，数据分组长度为64位，密文分组长度也是64位，没有数据扩展。其算法的基本思想是:通过循环或迭代，将简单的基本运算(例如左移、右移、模2加法等)和变换(选择函数、置换函数)构造成数据流的非线性变换(加密变换或解密变换)。DES算法的数据流程的基本框架是固定的，通过密钥分解将一个实际上是56位 (二进制)(64位密钥去掉奇偶校验位，刚好是56位)的密钥分解成16个48位(二进制)的子密钥，每个子密钥控制一次循环或迭代。加密与解密的密钥和流程是完全相同的，区别仅仅是加密与解密使用子密钥序列的操作顺序刚好相反。DES算法在历史上曾发挥重要作用，但也存在以下问题:DES密钥空间的规模256对实际安全而言太小。DES的密钥存在弱密钥、半弱密钥和互补密钥。DES里的所有计算，除去S盒，全是线性的。S盒的设计对密码算法的安全性至关重要。然而，美国国家安全局并没有公布S盒的设计原则，因此，有人怀疑S盒里隐藏了“陷门(trapdoors)”，如果是这样，美国国家安全局就能轻易地解密消息。由于DES的密钥空间小，针对DES算法进行穷举攻击就可以取得成1998年7月，电子前沿基金会(EFF)使用一台25万美元的电脑在56小时了DES密钥。1999年1月RSA数据安全会议期间，EFF通过遍布全世万台计算机的协同工作，用22小时巧分钟就宣告破解了一个DES的密外，关于DES的攻击还有差分密码分析方法和线性密码分析方法。2.3.2 AES(Advanced Encryption Standard)从各方面来看，DES已走到了它生命的尽头，为了替代己经超龄服役DES算法，Nils于1997年1月开始了公开筛选DES替代者高级加密标准（AES）的工作。其目的是为了确定一个非保密的、全球免费使用的分组密码算法，用于保护下一世纪政府的敏感信息，并希望成为秘密和公开部门的数据加密标准.最终，2000年10月2日，NIST宣布比利时的密码学家Joan Diemen 和Vincent Rijmen设计的“Roundel算法”最终获胜。Roundel之所为能当选AES，主要是因为:运算速度快。在无论有无反馈模式的计算环境下的软硬件中，Rijndael表现出非常好的性能。对内存的需求非常低，使它很适合用于受限制的环境。算法可靠。使用非线性结构的S一盒，表现出有足够的安全余地。Irondale算法的设计策略是宽轨迹策略(Wide Trail Strategy)，这种策略会有效抵抗差分分析和线性分析攻击。Irondale是一个分组迭代密码，被设计成128/192/256比特三种密匙标准可用于加密长度为128/192/256比特的分组，相应的轮数为10/12/14，分组长度和密钥长度设计灵活。密钥安装的时间很好，也具有很高的灵活性。操作简单，并可抵御时间和能量攻击，此外，它还有许多未被特的防御性能。由上可见，助deal汇聚了安全性能、效率、可实现性和灵活性等。2.4 公钥密码体制对称密码体制的特点是解密密钥与加密密钥相同或者很容易从加密密钥导出解密密钥。在对称密码体制中，加密密钥的暴露会使系统变得不安全。对称密码系统的一个严重缺陷是在任何密文传输之前，发送者和接收者必须使用一个安全信道预先商定和传送密钥。在实际的通讯网中，通信双方则很难确定一条合理的安全通道。由Dime和Hellman首先引入的公钥密码体制克服了对称密码体制的缺点。它的出现是密码学研究中的一项重大突破，也是现代密码学诞生的标志之一。在公钥密码体制中，解密密钥和加密密钥不同，从一个难以计算出另一个，解密运算和加密运算可以分离。通信双方无须事先交换密钥就可建立起保密通信。公钥密码体制克服了对称密码体制的缺点，特别适用于计算机网络中的多用户通信，它大大减少了多用户通信所需的密钥量，节省了系统资源，也便于密钥管理。1978年Rivets，Shamir:和Adelman提出了第一个比较完善的公钥密码算法，这就是著名的RSA算法。自从那时起，人们基于不同的计算问题，提出了大量的公钥密码算法。比较重要的有RSA算法、Mermen- Hellman背包算法、Mealier算法、Enigmas算法和椭圆曲线密码算法等。设计公钥密码体制的关键是先要寻找一个合适的单向函数，大多数的公钥密码体制都是基于计算单向函数的逆的困难性建立的。例如，RSA体制就是典型的基于单向函数模型的实现。这类密码的强度取决于它所依据的问题的计算复杂性。值得注意的是，公钥密码体制的安全性是指计算安全性，而绝不是无条件安全性，这是由它的安全性理论基础即复杂性理论决定的。单向函数在密码学中起一个中心作用。它对公钥密码体制的构造的研究是非常重要的。虽然目前许多函数(包括RSA算法的加密函数)的被认为或被相信是单向26的，但目前还没有一个函数能被证明是单向的。目前己经问世的公钥密码算法主要有三大类:第一类是基于有限域范围内计算离散对数的难度而提出的算法。比如，世界上第一个公钥算法Defile一Hellman算法就属此类，但是，它只可用于密钥发，不能用于加密解密信息。此外，比较著名的还有Enigma算法和1991年NIST提出的数字签名算法-Digital signature Algorithm(DSA)。第二类是20世纪90年代后期才得到重视的椭圆曲线密码体制。1985年，美国Washington大学的Neal Koblenz和IBM Watson认研究中心的Victor Miller各自独立的提出:一个称为椭圈曲线的不引人注目的数学分支可以用于实现密码学。他们没有设计出用椭圆曲线的新的密码算法，但他们在有限域上用椭圆曲线实现了己有的公钥算法，如Dine-Henlman.lGamal和Schonn一算法等。第三类就是本课题研究要涉及的RSA公钥密码算法。1977年，MIT的Ronald L.Rivest.Adi Shamir Leonard和Madmen教授对Defies和Hellman的公约密码学的思想进行了深入的研究，开发出了一个能够真正加密数据的算法。众所周知的用他们三个名字首字母命名的RSA算法问世。由于Whiff和Martin Hellman提供的ME背包算法于1984年被破译，失去了实际意义，因而RSA算法是真正有生命力的公开密钥加密系统算法，也是第一个既能用于数据加密也能用于数字签名的算法，在过去数年中提出的所有公钥算法是最易于理解和实现的，也是最流行的，自提出后已经经过了多密码分析，至今还没有发现其中的严重缺陷，仍然在发挥的及其重要的作用。本文将在下一章对该算法作比较详细的介绍。另外，还有由Remark。和Elhanan设计出的第一个广义的公钥加密算法-背包算法，Rabin算法，细胞自动机算法等许许多多的算法。1988年，daffier总结了己经出现的所有公钥密码算法，提出大多数公钥算法都基于三个难问题之一:背包问题、离散对数和因子分解。所以说，公钥密码学的数学基础是很狭窄的，设计出全新的公钥密码算法的难度相当大，而且无论是数学上对因子分解还是计一算离散对数问题的突破都会使现在看起来安全的所有么:钥算法变得不安全。2.5密码分析技术密码分析学是密码学的一个重要分支，同密码编码学并列。一般说来密码分析学是研究是在不掌握密钥的情况下，利用密码体制的弱点来恢复明文的一门学科。对一个密码系统采取截获密文进行分析的这类攻击称作被动攻击 (passive attack)。密码系统可能遭受的另一种攻击是主动攻击口、evilest。既非法入侵者主动向系统窜扰，采用删除、更改、增添、重放、伪造等手段向系统插入假消息，以达到窃取非法信息的目的。如果能够根据密文确定出明文或密钥，或者能够根据明文一密文对确定出密钥，则我们说这个密码是可破译的。否则，我们说这个密码是不可破译的。密码分析者攻击密码的方法主要有以下三种:穷举攻击:是指密码分析者用试遍所有密钥的方法来破译密码。穷举攻击所花费的时间等于尝试次数乘以一次解密(加密)所需的时间。显然可以通过增大密钥量或加大解密(加密)算法的复杂性来对抗穷举攻击。当密钥量增大时，尝试的次数必然增大。当解密(加密)算法的复杂性增大时，完成一次解密(加密)所需的时间增大。从而使穷举攻击在实际上不能实现。统计分析攻击:是指密码分析者通过分析密文和明文的统计规律来破译密码。统计分析攻击在历史上为破译密码做出过极大的贡献。许多古典密码都可以通过分析明文字母和字母组的频率而破译。对抗统计分析攻击的方法是设法使明文的统计特性不带入密文。这样，密文不带有明文的痕迹，从而使统计分析成为不可能。数学分析攻击:是指密码分析者针对加密算法的数学依据通过数学求解的方法来破译密码。为了对抗这种数学分析攻击，应选用具有坚实数学基础和足够复杂的加密算法。此外，攻击密码分析者可利用的数据来分类，可将破译密码的类型分为下三种:仅知密文攻击:即密码分析者仅根据截获的密文来破译密码;己知明文攻击:即密码分析者根据己经知道的某些明文一密文对来破译密码。例如，密码分析者可能知道从用户终端送到计算机的密文数据以一个标准词“Login”开头。又例如，加密成密文的计算机源程序特别容易受到这种攻击，这是因为诸如“begin”、“。nd”、“if”、“then”、“else”等词有规律的在密文中出现，密码分析者可以合理的猜测它们。近代密码学认为，一个密码仅当它能够经得起己知明文攻击时才是可取的。选择明文攻击:即密码分析者能够选择明文并获得相应的密文。这是对密码分析者最有利的情况。计算机文件系统和数据库特别容易受到这种攻击，因为用户可随意选择明文，并得到相应的密文文件和密文数据库。密码编制学的任务是寻求生成高强度密码的有效算法，满足对消息进行加密或认证的要求。密码分析学的任务是破译密码或伪造认证密码，窃取机密信息或进行诈骗破坏活动。对一个保密系统采取截获密文进行分析的方法进行进攻，称为被动进攻;非法入侵者采用删除、更改、添加、重放、伪造等手段向系统注入假消息的进攻是主动进攻。进攻与反进攻、破译与反破译是永无止境的矛与盾的竞技。一个密码，如果无论密码分析者截获了多少密文和用什么方法进行不能被攻破，则称为是绝对不可破译的。绝对不可破译的密码在理论上的。但是，如果能够利用足够的资源，那么任何实际的密码都是可破译此，对我们更有实际意义的是在计算上不可破译的密码，如果一个密码仅当它能够密码分析者根据可利用的资源所破译，则称为在计算上是不可破译的。 通常假定密码分析者或攻击者知道所使用的密码系统或算法，这种攻击作Kirchhoff假设。当然，如果密码分析者或攻击者不知道所使用的密码算法，那么破译密码会更困难，但是密码系统的安全性应依赖于密钥，依赖于加密体制或算法本身的细节的安全性。因此，在设计一个密码体我们的目标是在Kirchhoff假设下达到安全性。第三章 RSA公钥密码体制著名的Rosa公钥密码体制是在1975年由R.L.Rivest，A.Shamir和L.Adlemen三人共同提出。Rash是最具代表性的公钥密码体制。由于算法完善(既可用于数据加密，又可用于数字签名)，安全性良好，易于实现和理解，Rosa己成为一种应用极广的公钥密码体制