研究生综合应用报告课程名称《高级计算机网络》学院计算机学院年级计算机科学与技术专业班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 algorithms thinking 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: RSA algorithm Fermat's little theorem PKI一、RSA概述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.费马小定理费马小定理：设任意整数a 与素数p 互素，则 ()11mod p a n -≡证明：由a 与素数p 互素，知p 不是a 的素因数，又因为p 也不是1,2,3,...,1p - 的素因数,所以a 乘以此数列各项所得新数列,2,3,...,(1)a a a p a - 各项都不能被整除从而,2,3,...,(1)a a a p a -中的每一项只能和数列1,2,3,...,1p -中的一项模同余又由于,2,3,...,(1)a a a p a -中的任意两项都不能模p 同余（事实上, 如果存在不同的两ra 与sa （不妨设0r s p <<<）模p 同余, 即()mod sa ra p ≡ ， 因a 与p 互素,据同余式的消去律可得()mod s r p ≡ , 与假设r s <矛盾）, 所以,2,3,...,(1)a a a p a -中恰有一项和1,2,3,...,1p -中的1 同余, ,2,3,...,(1)a a a p a -中恰有一项和1,2,3,...,1p -中的2 同余，,2,3,...,(1)a a a p a -中恰有一项和1,2,3,...,1p -中的1p - 同余，从而可以建立1p - 个同余式. 将这1p - 个同余式相乘得：(),2,3,...,(1)123...(1)mod a a a p a p p -≡- .因为，123...(1)p ⋅⋅⋅⋅- 与p 互素，有同余的消去律的()11mod p a n -≡.3.RAS 定理定理 设p 、q 是不同的素数，n pq = ,记()(1)(1)n p q ϕ=-- ,如果e 、d 是与()n ϕ 互素的两个正整数，并满足1(mod ())ed n ϕ≡ ,则对于每个整数x ,都有(mo d )ed x x n ≡. 分析 由同余定义的等价表述, 只要证n 是ed x x - 的因数，但n pq = , 且p 、q都是素数，所以，只要证p 、q 分别是ed x x -的因数, 即只要证对于每个, 都有：(mod )ed x x p ≡ 公式一(mod )ed x x q ≡ 公式二证明：公式一只要证0(mod )ed x x p -≡ . 如果p 是x 的因数，则上式显然成立;如果p 不是x 的因数，即p 与x 互素，由题设 1(mod ())ed n ϕ≡，知()n ϕ是1ed -的因素，故存在整数k 使得1()(1)(1)ed n k p q k ϕ-==-- ，从而1(1)(1)ed p q k =+-- ，1(1)(1)1(1)()ed p q k p q k x x x x +----==⋅ ，因 p 与x 互素，由费马小定律()11mod p a n -≡，可得(1)(1)(mod )ed q k x x x p -≡⋅≡ . 同理可证公式二也成立.因此有：(mod )ed x x p ≡ 三、 RSA 算法原理以下公钥体制实施的步骤, 会帮我们理解它的基本原理（1） 取两个大素数p 和q , 求出n pq = 和()(1)(1)n p q ϕ=-- 的值.（2） 选一个与()n ϕ互素的正整数e ，解同余方程1(mod ())ed n ϕ≡，得到解d ，则{,}e d 是可供一个用户使用的密钥对. 其中e 为公钥，d 为私钥.（3） 构造两个定义域为(0,1,2,...,1)n -的函数:()(mod )e E x x n =为加密函数,()(mod )d D x x n =为解密函数.（4） 根据RSA 定理，()(mod )e e d ed DEx Dx x x x n ===≡ 即在()D x 和()E x 的作用下，经加密和解密后，明文信息x 变换为密文y 后又恢复为明文x ，所以()E x 和()D x 是互逆的.（5） 把供某用户使用的私钥d 交该用户， 并将其公钥e 和n 公开，()n ϕ则由密钥制作者秘密保管.（6） 别的用户要与该用户秘密通信时，先将明文信息x 用该用户的公钥e 建立的加密函数()E x 加密, 得密文()(mod )e y E x x n =≡ , 该用户收到密文y 后, 用自己的私钥d 建立解密函数()D x 解密，得明文()(m o d )()d e d e d x D y y n x x x n=≡≡≡≡ .为什么这里构建的加密函数()(mod )e E x x n ≡是单向函数? 因为n 是素因数为p 与q 很大的整数, 所以即使知道n , 也极难求出p 和q , 从而也无法得到()n ϕ. 因此在能查到公钥e 的情况下, 也不能建立同余方程1(mod ())ed n ϕ≡，不能得到私钥d ,故()(mod )e E x x n ≡为单向函数 四、 RSA 公钥体制进行数字签名和身份认证RSA 公钥体制提出后, 人们立刻发现也能用它来解决数字签名和身份认证问题当甲与乙通信时, 把明文信息x 先用自己的解密函数对它签名:()D x y =甲. 如果信息内容无需保密, 甲就可将经他签名的信息y 发给乙. 乙收到信息就从公钥薄上查到甲的公钥得到加密函数作用于y :()(())E y E D x x ==甲甲甲, 得到明文信息x , 从而确认信息x 是来自甲. 如果信息内容需要保密, 甲在签名后又在公钥薄上查到乙的公钥得到加密函数, 用它对已经签名的信息y 加密:()E y z =乙, 然后把z 发给乙. 乙收到z 后, 先用自己的解密函数作用于z :()()D z D E y y ==乙乙乙, 再从公钥薄上查到甲的公钥得到加密函数作用于y ,==E y E D x x()(())甲甲甲, 得到并确认来自甲的明文信息x.五、PKI体系及运行原理简单概述1.基本概述PKI是“Public Key Infrastructure”的缩写，意为“公钥基础设施”。
简单地说，PKI技术就是利用公钥理论和技术建立的提供信息安全服务的基础设施。
公钥体制是目前应用最广泛的一种加密体制，在这一体制中，加密密钥与解密密钥各不相同，发送信息的人利用接收者的公钥发送加密信息，接收者再利用自己专有的私钥进行解密。
这种方式既保证了信息的机密性，又能保证信息具有不可抵赖性。
目前，公钥体制广泛地用于CA认证、数字签名和密钥交换等领域。
PKI似乎可以解决绝大多数网络安全问题，并初步形成了一套完整的解决方案，它是基于公开密钥理论和技术建立起来的安全体系，是提供信息安全服务的具有普适性的安全基础设施。
该体系在统一的安全认证标准和规范基础上提供在线身份认证，是CA认证、数字证书、数字签名以及相关安全应用组件模块的集合。
作为一种技术体系，PKI可以作为支持认证、完整性、机密性和不可否认性的技术基础，从技术上解决网上身份认证、信息完整性和抗抵赖等安全问题，为网络应用提供可靠的安全保障。