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

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

RSA

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

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

1
12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

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

RSA的思路

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

1
33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
    ×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917

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

如何生成公私钥?

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

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

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

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

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

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

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

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

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

1
φ(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,指的是余数。

同余

三横的等号,代表同余,两个整数ab,若它们除以正整数m所得的余数相等,则称 ab对于模 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

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

欧几里得算法

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

假设我们要求12076的最大公约数,可以这么计算:

1
首先选择大的数减去小的数

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

所以,我们就可以求出,12076的最大公约数是4

扩展欧几里得算法

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

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

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

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

改变一下等式两边

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

把等式代入上一个等式

1
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)

我们把mn代入公式可以得到:

mφ(n) ≡ 1 (mod n)

因为mn互质,那么以下等式依然成立:

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

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

m和n不是互质的关系

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

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

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

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

因为k * pq互质,所以可以有:

(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

因为pq是互质关系,所以k * p只有当k等于q或者其倍数的时候,才能整除q,但是m = q * k,而且m < n,所以k * p必然是不能整除q的,由此可得p必然能够整除t才能使得等式成立,也就是有:t = t<sup>'</sup> * p,由此可得如下等式:

kped = t pq + kp

因为m = kp,而n = pq,所以:

med = tn + m

写成同余等式可得:

med ≡ m (mod n)

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

结论

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

RSA中的对称性

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

总结

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

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