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

研究生综合应用报告

课程名称《高级计算机网络》

学院计算机学院年级计算机科学与技术专业班6班

学生姓名唐洪奎学号20141402021

开课时间2014 至2015 学年第 1 学期

RSA原理学习与PKI简述

摘要

随着计算机网络的发展，计算机网络所能提供的服务也越来越丰富。特别是一些和银行、电子商务、军事通信相关的网络服务，对应计算机网络上信息通信安全提出了严苛的要求；密码学也在这种情况下得以发展；RSA作为重要的公钥加密算法，其应用和算法思想应信息安全都有很重要的意义，本文再述了RSA的证明、原理，并简单介绍了PKI系统，并在结尾处进行一定程度的反思。

关键字：RSA算法费马小定理PKI

Abstract

With 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 为私钥.