RSA算法的历史

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

但实际上，在1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。

所以谁是RSA算法的发明人呢？不好说，就好像贝尔并不是第一个发明电话的人但大家都记住的是贝尔一样，这个地方我们作为旁观者倒不用较真，重要的是这个算法的内容：

RSA算法的过程

RSA算法用到的数学知识特别多，所以在中间介绍这个算法生成私钥和公钥的过程中会穿插一些数学知识。生成步骤如下：

1. 寻找两个不相同的质数

随意选择两个大的质数p和q，p不等于q，计算N=p*q;

什么是质数?我想可能会有一部分人已经忘记了，定义如下：

除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1该数本身两个正因数]的数）。

比如2，3，5，7这些都是质数，9就不是了，因为3*3=9了

2. 根据欧拉函数获取r

r = φ(N) = φ(p)φ(q) = (p-1)(q-1)。

这里的数学概念就是什么是欧拉函数了，什么是欧拉函数呢？

欧拉函数的定义：

欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目。

互质的定义：

如果两个或两个以上的整数的最大公约数是 1，则称它们为互质

例如：φ(8) = 4，因为1,3,5,7均和8互质。

推导欧拉函数:

（1）如果n = 1, φ(1) = 1；(小于等于1的正整数中唯一和1互质的数就是1本身)；

（2）如果n为质数，φ(n) = n - 1；因为质数和每一个比它小的数字都互质。比如5，比它小的正整数1,2,3,4都和他互质；

(3) 如果n是a的k次幂，则 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1)；

(4) 若m,n互质，则φ(mn) = φ(m)φ(n)

证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理(经常看数学典故的童鞋应该了解，剩余定理又叫韩信点兵，也叫孙子定理)，A*B和C可建立双射一一对应)的关系。（或者也可以从初等代数角度给出欧拉函数积性的简单证明） 因此的φ(n)值使用算术基本定理便知。（来自维基百科）

3. 选择一个小于r并与r互质的整数e

选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为d（ed = 1(mod r)模反元素存在，当且仅当e与r互质），e我们通常取65537。

模反元素：

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

比如3和5互质，3关于5的模反元素就可能是2，因为32-1=5可以被5整除。所以很明显模反元素不止一个，2加减5的整数倍都是3关于5的模反元素{...-3, 2,7,12…} 放在公式里就是3*2 = 1 (mod 5)*

上面所提到的欧拉函数用处实际上在于欧拉定理：

欧拉定理：

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

a^φ(n) = 1(mod n)

由此可得：a的φ(n - 1)次方肯定是a关于n的模反元素。

欧拉定理就可以用来证明模反元素必然存在。

由模反元素的定义和欧拉定理我们知道，a的φ(n)次方减去1，可以被n整除。比如，3和5互质，而5的欧拉函数φ(5)等于4，所以3的4次方(81)减去1，可以被5整除（80/5=16）。

小费马定理：

假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成

a^(p-1) = 1 (mod p)

这其实是欧拉定理的一个特例。

4. 销毁p和q

此时我们的(N , e)是公钥，(N, d)为私钥，爱丽丝会把公钥(N, e)传给鲍勃，然后将(N, d)自己藏起来。一对公钥和私钥就产生了，然后具体的使用方法呢？请看：SSL协议之数据加密过程详解

RSA算法的安全性

我们知道像RSA这种非对称加密算法很安全，那么到底为啥子安全呢？
我们来看看上面这几个过程产生的几个数字：

• p,q：我们随机挑选的两个大质数；
• N：是由两个大质数p和q相乘得到的。N = p * q；
• r：由欧拉函数得到的N的值，r = φ(N) = φ(p)φ(q) = (p-1)(q-1)。
• e：随机选择和和r互质的数字，实际中通常选择65537；
• d： d是以欧拉定理为基础求得的e关于r的模反元素，ed = 1 (mod r)；

N和e我们都会公开使用，最为重要的就是私钥中的d，d一旦泄露，加密也就失去了意义。那么得到d的过程是如何的呢？如下:

1. 比如知道e和r，因为d是e关于r的模反元素；r是φ(N) 的值
2. 而φ(N)=(p-1)(q-1)，所以知道p和q我们就能得到d;
3. N = pq，从公开的数据中我们只知道N和e，所以问题的关键就是对N做因式分解能不能得出p和q

所以得出了在上篇博客说到的结论，非对称加密的原理：

将a和b相乘得出乘积c很容易，但要是想要通过乘积c推导出a和b极难。即对一个大数进行因式分解极难

目前公开破译的位数是768位，实际使用一般是1024位或是2048位，所以理论上特别的安全。

后记

RSA算法的核心就是欧拉定理，根据它我们才能得到私钥，从而保证整个通信的安全。