125      阿裏雲  技術社區[雲棲]

零門檻學習https--(2)https中s的秘密

上一篇：零門檻學習https--(1)為什麼我們要用https

非對稱加密在目前的計算機領域內是非常安全的，主要還是受製於目前的計算能力，或許某天量子計算機的出現會改變這個局麵。RSA的本質就是一個數學算法，所以本篇即使你不懂任何計算機知識，也能理解RSA算法的原理，但是其中會涉及到大量的數學知識。

RSA

前麵已經介紹過RSA的名稱由來，下麵來介紹下RSA的安全本質：大整數的因數分解。

舉個例子：求77的因數分解，很簡單，解是7和11，或許你在高中或者初中就學過這個，很詫異這能成為現代互聯網安全的基礎？那麼你可以看看下麵這個數字：

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

這個就是人類目前破解過的最長的一個整數，在2009年才破解成功，轉成二進製就是768位，而現在普遍都是2048位的加密，如果非要破解，那麼所需時間是一個天文數字。如果有一天，有人發明了簡單的因數分解的方式，那麼RSA就很容易被破解了，目前，基本上隻有暴力破解，也就是一個數一個數地測試。

RSA的思路

上麵那個數等於下麵這兩個數的乘積，計算這兩個數的乘積很簡單，計算機在瞬間就可以給出答案，但是隻有兩個數的乘積，而讓你求出其因數，就幾乎是不可能了，當然這是基於大整數的情況下，簡單的整數，通過暴力破解，還是可以求出來的。

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)可以這麼求值：

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

這裏，φ(n) = ( 17 -1 ) * ( 23 - 1 ) = 352

4. 隨機選擇一個整數e, 需要符合條件：1 < e < φ(n)並且e和φ(n)互質

也就是說，e和φ(n)不能有公約數，並且φ(n)不能是e的倍數。

舉個例子：φ(n) = 12，所以e可以選的數有3, 5, 7, 11 ....，這裏我選擇**17**。

在現實場景中，通常e的選擇是65537，為什麼要選擇這個數呢？請參看這篇文章，解釋得非常清楚，總的來說，比65537大的數，在現有的硬件和軟件場景下，會造成計算變慢，而比65537小的數，在安全性上會有減弱，所以65537是一個折中的選擇。

5. 計算e對於φ(n)的模反元素d

求模

求模操作在大部分計算機語言中操作符都是%，比如：10 % 3 = 1，指的是餘數。

同餘≡

三橫的等號，代表同餘，兩個整數a，b，若它們除以正整數m所得的餘數相等，則稱 a， b對於模 m同餘，例如：

10 ≡ 1 (mod 3)

10 和 1 對於 3 同餘。

模反元素

模反元素也成為模逆元

一整數a對同餘n之模逆元是指滿足以下公式的整數 b

也可以寫成以下的式子

整數 a 對模數 n 之模逆元存在的充分必要條件是 a 和 n 互素，若此模逆元存在，在模數 n 下的除法可以用和對應模逆元的乘法來達成，此概念和實數除法的概念相同。

以上是維基百科對於模反元素的介紹，將e和φ(n)代入公式就變成了：

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

也就是說e * d的結果除以k * φ(n)的餘數是1，所以我們的公式就變成了：

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

將e和φ(n)代入：

231 * d - 1 = k * 352

轉變一下位置：

231x - 352y = 1

就變成了一個二元一次方程，初中時候就求過二元一次方程的解，但是必須得有兩個二元一次方程才能求出解，不然就是一個直線方程了，這裏我們采用擴展歐幾裏得算法來進行求解。

歐幾裏得算法

我們先看看歐幾裏得算法的定義：歐幾裏得算法又稱為輾轉相除法，是一種求最大公約數的方法，其核心思想如下圖：

假設我們要求120和76的最大公約數，可以這麼計算：

首先選擇大的數減去小的數

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：

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

改變一下等式兩邊

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

把等式代入上一個等式

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

加密公式

m^e ≡ c (mod n)

這裏的c就是我們的密文。

上麵我們計算的n是：391，e是：17， 那假設我們要加密的內容是：11，所以我們的密文就是：198。

這裏非常需要注意的一點就是，需要使用一些大數計算的方式，而不能使用普通的double之類的類型，因為double類型，還有js等語言的默認的數字類型尾數位隻有52位，無法精確表達比2的53次更大的數字

解密公式

c^d ≡ m (mod n)

c是：198，d是：145，n是：391，解出我們的明文是：11，至此，我們的整個加密和解密過程就結束了。也許你會好奇，為什麼這麼算就能算出相等的結果，下麵就來證明一下。

公式證明

我們的加密公式是：

m^e ≡ c (mod n)

我們的解密公式是：

c^d ≡ m (mod n)

根據上麵的規則，c可以這麼表達：

c = m^e - kn***

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

(m^e - kn)^d ≡ m (mod n)

因為這是一個同餘等式，等號左邊加減n都不會影響等式，所以我們可以把等式簡化為

m^ed ≡ m (mod n)

當我們在求d的時候有同餘等式：

ed ≡ 1 (mod φ(n))

這個等式也可以寫成這個樣子：

ed = h \ φ(n) + 1*

代入剛剛簡化後的等式：

m^hφ(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*

代入剛剛的式子：

kp^ed ≡ kp (mod q)

假設有t，使得求模運算可以寫成：

kp^ed = t \ q + k * p*

轉換一下等式：

kp^{ed - 1} = t \ q*

因為p和q是互質關係，所以k * p隻有當k等於q或者其倍數的時候，才能整除q，但是m = q * k，而且m < n，所以k * p必然是不能整除q的，由此可得p必然能夠整除t才能使得等式成立，也就是有：t = t<sup>'</sup> * p，由此可得如下等式：

kp^ed = t^' pq + kp

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

m^ed = t^'n + m

寫成同餘等式可得：

m^ed ≡ m (mod n)

這裏就證明了我們剛剛橫線中的等式。

結論

到這裏，我們已經證明了兩種情況下等式都是成立了，也就是明文通過公鑰加密之後，使用私鑰也必然能夠得到原本的結果，RSA算法也就成立了。

RSA中的對稱性

其實你會發現，RSA裏麵，公鑰加密的東西私鑰能夠解密，同樣的，從公式中發現，私鑰加密的東西公鑰也能解密，這也是非常重要的一個特性。那麼，為什麼不能把({n, d})作為公鑰給用戶呢？因為({n, e})中，n是公開的，e基本都使用常數65537，所以很容易就被猜到了，因此，雖然在算法上都能加密和解密，但是隻把({n, e})作為公鑰，公鑰和私鑰有非常嚴格的區分。

總結

有了這麼安全的加密方式，那麼我們就可以開始給HTTP加密了，那麼https究竟是怎麼做的呢，一起來看看：

零門檻學習https--(3)https的安全策略

最後更新：2017-05-31 19:35:01

  上一篇：  人工智能開啟客戶服務新時代

  下一篇：  就是要你懂 TCP-- 最經典的TCP性能問題