上一篇：零门槛学习https–(1)为什么我们要用https

非对称加密在目前的计算机领域内是非常安全的，主要还是受制于目前的计算能力，或许某天量子计算机的出现会改变这个局面。RSA的本质就是一个数学算法，所以本篇即使你不懂任何计算机知识，也能理解RSA算法的原理，但是其中会涉及到大量的数学知识。

RSA

前面已经介绍过RSA的名称由来，下面来介绍下RSA的安全本质：大整数的因数分解。

举个例子：求77的因数分解，很简单，解是7和11，或许你在高中或者初中就学过这个，很诧异这能成为现代互联网安全的基础？那么你可以看看下面这个数字：

1
2
3
4
5
6
7
8
9
12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

这个就是人类目前破解过的最长的一个整数，在2009年才破解成功，转成二进制就是768位，而现在普遍都是2048位的加密，如果非要破解，那么所需时间是一个天文数字。如果有一天，有人发明了简单的因数分解的方式，那么RSA就很容易被破解了，目前，基本上只有暴力破解，也就是一个数一个数地测试。

RSA的思路

上面那个数等于下面这两个数的乘积，计算这两个数的乘积很简单，计算机在瞬间就可以给出答案，但是只有两个数的乘积，而让你求出其因数，就几乎是不可能了，当然这是基于大整数的情况下，简单的整数，通过暴力破解，还是可以求出来的。

1
2
3
4
5
6
7
8
9
10
11
33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
　　　　×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917

我们把这两个数分别称为p和q，这两个数的乘积称为n，从这个角度出发，只要加密者拥有p和q，很容易算出乘积n，而尝试破解的人，只有n，就没法算出p和q了。

如何生成公私钥？

本质已经知道了，那么我们来生成RSA的公钥和私钥吧，生成公钥和私钥总共分为五步：

1. 随机选择两个质数p和q

质数又称素数，具体的特性和定义请参考这里

比如这里我选择了p=17，q=23

2. 将这个两个数相乘得到n

17 * 23 = 391，391换算成二进制就是110001000，这里的位数就是9位，这就是我们密钥的长度。选择RSA密钥长度的时候，其实就是选择这个n的长度，长度越大，安全性越高，当然加密和解密的时候耗费的计算量也更大。

3. 计算n的欧拉函数φ(n)

欧拉函数的作用是求得大于1小于n的所有质数的个数，例如符合φ(8)的情况是：2, 3, 5, 7，也就是φ(8)的值为：4，具体有关欧拉函数的其他特性请参考这里

我们这里φ(n)可以这么求值：

1
2
3
φ(n) = (p-1)(q-1).

这里，φ(n) = ( 17 -1 ) * ( 23 - 1 ) = 352

4. 随机选择一个整数e, 需要符合条件：1 < e < φ(n)并且e和φ(n)互质

也就是说，e和φ(n)不能有公约数，并且φ(n)不能是e的倍数。

举个例子：φ(n) = 352，所以e可以选的数有3, 5, 7, 11 ....，这里我选择17。

在现实场景中，通常e的选择是65537，为什么要选择这个数呢？请参看这篇文章，解释得非常清楚，总的来说，比65537大的数，在现有的硬件和软件场景下，会造成计算变慢，而比65537小的数，在安全性上会有减弱，所以65537是一个折中的选择。

5. 计算e对于φ(n)的模反元素d

求模

求模操作在大部分计算机语言中操作符都是%，比如：10 % 3 = 1，指的是余数。

同余≡

三横的等号，代表同余，两个整数a，b，若它们除以正整数m所得的余数相等，则称 a， b对于模 m同余，例如：

1
10 ≡ 1 (mod 3)

10 和 1 对于 3 同余。

模反元素

模反元素也成为模逆元

一整数a对同余n之模逆元是指满足以下公式的整数 b

也可以写成以下的式子

整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素，若此模逆元存在，在模数 n 下的除法可以用和对应模逆元的乘法来达成，此概念和实数除法的概念相同。

以上是维基百科对于模反元素的介绍，将e和φ(n)代入公式就变成了：

1
e * d ≡ 1(mod φ(n))

也就是说e * d的结果除以k * φ(n)的余数是1，所以我们的公式就变成了：

1
e * d - 1 = k * φ(n);

将e和φ(n)代入：

1
231 * d - 1 = k * 352

转变一下位置：

1
231x - 352y = 1

就变成了一个二元一次方程，初中时候就求过二元一次方程的解，但是必须得有两个二元一次方程才能求出解，不然就是一个直线方程了，这里我们采用扩展欧几里得算法来进行求解。

欧几里得算法

我们先看看欧几里得算法的定义：欧几里得算法又称为辗转相除法，是一种求最大公约数的方法，其核心思想如下图：

假设我们要求120和76的最大公约数，可以这么计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
首先选择大的数减去小的数

120 - 76 = 44

现在我们剩下76 和 44两个数，继续第一步操作

76 - 44 = 32

44 - 32 = 12

32 - 12  = 20

20 - 12  = 8

12 - 8  = 4

8  - 4  = 4

4  - 4  = 0

所以，我们就可以求出，120和76的最大公约数是4。

扩展欧几里得算法

看名字就可以知道这是欧几里得算法的扩展，其核心思想如下：

已知a和b，求解一组x, y使得ax+by=Gcd(a, b)=d (Gcd(a, b) 表示a和b的最大公约数)。

用类似辗转相除法来求解这个等式17x - 352y = 1：

1
2
3
4
352 = 17 * 20 + 12
17  = 12 * 1 + 5
12  = 5 * 2 + 2
5   = 2 * 2 + 1

改变一下等式两边

1
2
3
4
12  = 352 - 17 * 20
5   = 17 - 12
2   = 12 - 5 * 2
1   = 5 - 2 * 2

把等式代入上一个等式

1
2
3
4
5
6
7
8
9
10
1  = 5 - 2 * 2
1  = 5 -（ 12 - 5 * 2 ）* 2 // 代入等式：2 = 12 - 5 * 2
1  = 5 - 12 * 2 + 5 * 4
1  = 5 * 5 - 12 * 2
1  = ( 17 - 12 ) * 5 - 12 * 2 // 代入等式：5 = 17 - 12
1  = 17 * 5 - 12 * 5 - 12 * 2
1  = 17 * 5 - 12 * 7
1  = 17 * 5 - ( 352 - 17 * 20 ) * 7 // 代入等式：12 = 352 - 17 * 20
1  = 17 * 5 - 352 * 7 + 17 * 140
1  = 17 * 145 - 352 * 7

即可得出：x = 145, y = 7

结果

在第五步中我们想要的d就是这里的x，所以，d = 145。

作为一个直线方程，这里理论上这里会有无数个整数解，的确，尝试一下就发现，所有整数解都是能计算的，只是数字越大，计算量越大，但是要注意，这里的d不能小于0。

组合公钥和私钥

到这里，公钥和私钥所需要的东西都齐全了，({n, e})就是公钥，而({n, d})就是私钥，一般会使用ASN.1来表达。

加密

首先，我们用公钥加密。

要加密的数据m

m需要满足以下条件：

  1. m必须是正整数(字符串之类的可以取arcii)
  2. m必须小于n

加密公式

me ≡ c (mod n)

这里的c就是我们的密文。

上面我们计算的n是：391，e是：17， 那假设我们要加密的内容是：11，所以我们的密文就是：198。

这里非常需要注意的一点就是，需要使用一些大数计算的方式，而不能使用普通的double之类的类型，因为double类型，还有js等语言的默认的数字类型尾数位只有52位，无法精确表达比2的53次更大的数字

解密公式

cd ≡ m (mod n)

c是：198，d是：145，n是：391，解出我们的明文是：11，至此，我们的整个加密和解密过程就结束了。也许你会好奇，为什么这么算就能算出相等的结果，下面就来证明一下。

公式证明

我们的加密公式是：

me ≡ c (mod n)

我们的解密公式是：

cd ≡ m (mod n)

根据上面的规则，c可以这么表达：

c = me - kn

把c代入我们的解密方程：

(me - kn)d ≡ m (mod n)

因为这是一个同余等式，等号左边加减n都不会影响等式，所以我们可以把等式简化为

med ≡ m (mod n)

当我们在求d的时候有同余等式：

ed ≡ 1 (mod φ(n))

这个等式也可以写成这个样子：

ed = h * φ(n) + 1

代入刚刚简化后的等式：

mhφ(n)+1 ≡ m (mod n)

到这里，只要我们能够证明这个等式是成立的，那么就能够证明我们的加密和解密公式是成立的，这里就有两种情况了：

m和n是互质的关系

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

aφ(n) ≡ 1 (mod n)

我们把m和n代入公式可以得到：

mφ(n) ≡ 1 (mod n)

因为m和n互质，那么以下等式依然成立：

(mφ(n))h * m ≡ m (mod n)

对指数稍微换算一下就能得到我们之前的等式了，m和n互质的情况下，我们很容易就能证明之前的等式成立。

m和n不是互质的关系

首先我们有n = p * q，因为m和n不是互质的，而因为n是两个质数相乘的结果，也就是说p或者q就是m和n的一个公约数，所以有m = p * k，或者m = q * k。假设p是m和n的公约数，那么就有m = p * k。

然后因为p和q都是质数，质数和除了是自己倍数之外的数都互质，又因为m必须小于n，所以这里k取值必然不能是q或者更大的数，所以我们有一个结论是：k必然和q互质。

k * p必然和q互质，把k * p和q代入，所以我们能够得出以下同余等式：

(kp)φ(q) ≡ 1 (mod q)

因为k * p和q互质，所以可以有：

(kp)h * φ(q) + 1 ≡ kp (mod q)

而我们之前已经求出：

ed = h * φ(n) + 1

代入刚刚的式子：

kped ≡ kp (mod q)

假设有t，使得求模运算可以写成：

kped = t q + k p

转换一下等式：

kped - 1 = t * q

先假设k * p和t互质，也就是说k * p能够整除q，因为p和q是互质关系，而上面我们也得出k必然和q互质，所以我们的假设k * p和t互质不成立，上方我们得出k必然和q互质，由此可得p必然能够整除t才能使得等式成立，也就是有：t = t‘ * p，由此可得如下等式：

kped = t‘ pq + kp

因为m = kp，而n = pq，所以：

med = t‘n + m

写成同余等式可得：

med ≡ m (mod n)

这里就得出了我们刚刚求出的等式。

结论

到这里，我们已经证明了两种情况下等式都是成立了，也就是明文通过公钥加密之后，使用私钥也必然能够得到原本的结果，RSA算法也就成立了。

RSA中的对称性

其实你会发现，RSA里面，公钥加密的东西私钥能够解密，同样的，从公式中发现，私钥加密的东西公钥也能解密，这也是非常重要的一个特性。那么，为什么不能把({n, d})作为公钥给用户呢？因为({n, e})中，n是公开的，e基本都使用常数65537，所以很容易就被猜到了，因此，虽然在算法上都能加密和解密，但是只把({n, e})作为公钥，公钥和私钥有非常严格的区分。

总结

有了这么安全的加密方式，那么我们就可以开始给HTTP加密了，那么https究竟是怎么做的呢，一起来看看：

零门槛学习https–(3)https的安全策略