《RSA算法原理以及PKI系统简介.docxVIP

研究生综合应用报告课程名称《高级计算机网络》学院计算机学院年级计算机科学与技术专业班 6班学生姓名唐洪奎学号 20141402021 开课时间 2014 至 2015 学年第 1 学期RSA原理学习与PKI简述摘要随着计算机网络的发展，计算机网络所能提供的服务也越来越丰富。特别是一些和银行、电子商务、军事通信相关的网络服务，对应计算机网络上信息通信安全提出了严苛的要求；密码学也在这种情况下得以发展；RSA作为重要的公钥加密算法，其应用和算法思想应信息安全都有很重要的意义，本文再述了RSA的证明、原理，并简单介绍了PKI系统，并在结尾处进行一定程度的反思。关键字：RSA算法费马小定理PKIAbstractWith the development of Internet, Internet provides more and more services to public. Some services referring to Bank Transient, E-Commercials needs a safer communication on the Internet.Cryptography was developed in this case. As an important public key encryption algorithm, RSA’s applications and algorithmsthinking has a very important significance to Information Security. This paper describes the proof of RSA, principles, and briefly describes the PKI system, and a certain degree of rethinking about RSA and PKI at the end.Keywords: RSAalgorithm Fermats little theoremPKIRSA概述RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。本文简单探头了RSA的证明原理，以及用类似RSA这样的算法构建的PKI系统的运作方式。RSA数学基础1.概述RSA的数学基础来自离散数学的分支—数论。数论，也可以看成是高等代数中的一部分，通过用多项式的方式，定义素数或者是互素关系、整除、辗转相除法、最大公约数、最小公倍数等等，并且在此基础上讨论数论的定理证明。一般的信息安全数学教材利用整数进行讨论。RSA算法基于“大数难分解”，理论基础是模数运算。在证明，过程用到了素数、互素、同余、同余方程的概念，这些可以再一般的信息安全书籍中找到。证明中比较重要的是费马小定理、RSA定理，我们再述其证明过程。2.费马小定理费马小定理：设任意整数与素数互素，则证明：由与素数互素，知不是的素因数，又因为也不是的素因数,所以乘以此数列各项所得新数列各项都不能被整除从而中的每一项只能和数列中的一项模同余又由于中的任意两项都不能模同余（事实上, 如果存在不同的两与（不妨设）模同余, 即，因与互素, 据同余式的消去律可得, 与假设矛盾）, 所以中恰有一项和中的同余,中恰有一项和中的同余，中恰有一项和中的同余，从而可以建立个同余式. 将这个同余式相乘得： .因为，与互素，有同余的消去律的.3.RAS定理定理设、是不同的素数， ,记 ,如果、是与互素的两个正整数，并满足 ,则对于每个整数 ,都有.分析由同余定义的等价表述, 只要证是的因数，但, 且、都是素数，所以，只要证、分别是的因数, 即只要证对于每个, 都有：公式一公式二证明：公式一只要证 .如果是的因数，则上式显然成立;如果不是的因数，即与互素，由题设，知是的因素，故存在整数使得，从而，，因与互素，由费马小定律，可得 .同理可证公式二也成立.因此有