在《Hello，密碼學(xué)：第二部分，對稱密碼算法》中講述了對稱密碼的概念，以及DES和AES兩種經(jīng)典的對稱密碼算法原理。既然有對稱密碼的說法，自然也就有非對稱密碼，也叫做公鑰密碼算法。對稱密碼和非對稱密碼兩種算法的本質(zhì)區(qū)別在于，加密密鑰和解密密鑰是否相同：

• 對稱密碼的加解密密鑰相同，用密鑰A加密，也用密鑰B解密。
• 公鑰密碼的加解密密鑰不同，用密鑰A加密，而用密鑰B解密。

非對稱密碼的愛心小鎖

一、公鑰密碼產(chǎn)生的初衷

公鑰密碼產(chǎn)生的初衷就是為了解決 密鑰配送 的問題。

Alice 給遠方的 Bob 寫了一封情意慢慢的信，并使用強悍的 AES-256 進行了加密，但她很快就意識到，光加密內(nèi)容不行，必須要想一個安全的方法將加密密鑰告訴 Bob，如果將密鑰也通過網(wǎng)絡(luò)發(fā)送，很可能被技術(shù)高手+偷窺癖的 Eve 竊聽到。

既要發(fā)送密鑰，又不能發(fā)送密鑰，這就是對稱密碼算法下的“密鑰配送問題”。

解決密鑰配送問題可能有這樣幾種方法：

1. 通過事先約定的共享密鑰解決
2. 通過密鑰分配中心解決
3. 通過公鑰密碼解決

方法一： 事先約定的共享密鑰

這種方法比較高效，但有局限性：

• 只適用于較近的距離。也就是不必通過不信任的網(wǎng)絡(luò)就能通信的情況，比如辦公室內(nèi)的同事之間，完全可以面對面?zhèn)鬟f一下密鑰。一旦距離較遠，無法面對面交互，就出現(xiàn)了問題。
• 只適用于小規(guī)模使用。即使距離較近，但如果通信人數(shù)眾多，比如一個公司有 1000 人，每個員工都可以和另外 999 個人進行加密通信，每個人都需要 999 個密鑰，整個公司需要的密鑰數(shù)量為 1000 × 999 ÷ 2 = 499500 個密鑰，這顯然不現(xiàn)實。

方法二：密鑰分配中心

與方法一不同，密鑰不再由通信個體來保存，而由密鑰分配中心（KDC）負責統(tǒng)一的管理和分配。雙方需要加密通信時，由 KDC 生成一個用于本次通信的通信密鑰交由雙方，通信雙方只要與 KDC 事先共享密鑰即可。這樣就大大減少密鑰的存儲和管理問題。

因此，KDC 涉及兩類密鑰：

• 身份密鑰：代表通信個體身份的密鑰，好比工卡。企業(yè)有 1000 個員工，KDC 中就保存 1000 個身份密鑰，人來人往，身份密鑰也隨之發(fā)生變化。
• 通信密鑰：也叫做會話密鑰，僅在一個通信會話過程中有效。

領(lǐng)略下 KDC 的過程：

1. KDC 事先保存了 Alice 和 Bob 的身份密鑰，分別記為 iKey-Alice 和 iKey-Bob，i 是 identity 的意思；
2. Alice 向 KDC 發(fā)出要與 Bob 通信的請求；
3. KDC 生成一個通信密鑰，記為 cKey，c 是 communication 的意思；
4. KDC 從數(shù)據(jù)庫中調(diào)取 Alice 和 Bob 的身份密鑰，用 iKey-Alice 對 cKey 進行加密后發(fā)送給Alice，用iKey-Bob 對 cKey 加密后發(fā)送給 Bob；
5. Alice 使用 iKey-Alice 解密出 cKey 后，并使用 cKey 對信息進行加密后發(fā)送給 Bob；
6. Bob 使用 iKey-Bob 解密出 cKey 后，并使用 cKey 對來自 Alice 的加密信息進行解密；
7. 本次會話結(jié)束后，Alice 和 Bob 按照公司要求，在本地刪除本次使用通信密鑰 cKey。

KDC 通過中心化的手段，確實能夠有效的解決方法一的密鑰管理和分配問題，安全性也還不錯。但也存在兩個顯著的問題：

• 性能問題：由于所有的加密通信，都要和 KDC 發(fā)生交互，KDC 的負荷會隨著通信會話的增加而陡增，一旦癱瘓，整個組織的加密通信都將癱瘓。
• 安全問題：KDC 也是軟件，也存在漏洞，黑客 Mallory 可能直接對 KDC 下手。一旦 KDC 的密鑰數(shù)據(jù)庫被破解，整個組織的加密通信都將被破譯。

方法三：公鑰密碼

使用公鑰密碼，加密密鑰和解密密鑰不同，只要擁有加密密鑰，所有人都能進行加密，但只有擁有解密密鑰的人才能進行解密。于是就出現(xiàn)了這個過程：

• 信息接收者事先將加密密鑰通過普通途徑發(fā)送給信息發(fā)送者即可，不必擔心加密密鑰被竊聽；
• 信息發(fā)送者使用加密密鑰對信息進行加密并發(fā)送給信息接收者；
• 信息接收者使用解密密鑰對加密信息進行解密。

密鑰配送的問題天然被解決了。當然，解密密鑰丟失而導(dǎo)致信息泄密，這不屬于密鑰配送的問題。

下面，再詳細看下這個過程。

二、公鑰密碼的基本流程

公鑰密碼流程的核心，可以用如下四句話來概述：

1. 發(fā)送者只需要加密密鑰
2. 接收者只需要解密密鑰
3. 解密密鑰須妥善保管，不能被竊聽者獲取
4. 加密密鑰無所謂，被竊聽者獲取也沒關(guān)系

既然加密密鑰是公開的，因此也叫做 “公鑰（Public Key）”。
既然解密密鑰是私有的，因此也叫做 “私鑰（Private Key）。

公鑰和私鑰是一一對應(yīng)的，稱為 “密鑰對”，他們好比相互糾纏的量子對，彼此之間通過嚴密的數(shù)學(xué)計算關(guān)系進行關(guān)聯(lián)，不能分別單獨生成。

在公鑰密碼體系下，再看看 Alice 如何同 Bob 進行通信。

公鑰密碼體系的通信

在公鑰密碼體系下，通信過程是由 Bob 開始啟動的：

1. Bob 生成公私鑰對，妥善保管私鑰；
2. Bob 將公鑰發(fā)送給 Alice，公鑰被 Eve 竊聽也沒關(guān)系；
3. Alice 使用 Bob 的公鑰對消息進行加密；
4. Alice 將加密后的消息發(fā)送給 Bob，密文被 Eve 截取也沒關(guān)系；
5. Bob 使用私鑰對密文進行解密。

過程看起來非常簡單，但為什么即使公鑰被竊取也沒有關(guān)系？這就涉及了上文提到的嚴密的數(shù)學(xué)計算關(guān)系了。如果上一篇文章對稱密鑰的 DES 和 AES 算法進行概述，下面一節(jié)也會對公鑰體系的數(shù)學(xué)原理進行簡要說明。

三、RSA算法背后的數(shù)學(xué)原理

自從 Diffie 和 Hellman 在1976年提出公鑰密碼的設(shè)計思想后，1978年，Ron Rivest、Adi Shamir 和 Reonard Adleman 共同發(fā)表了一種公鑰密碼算法，就是大名鼎鼎的 RSA，這也是當今公鑰密碼算法事實上的標準。其實，公鑰密碼算法還包括ElGamal、Rabin、橢圓曲線等多種算法，這一節(jié)主要講述 RSA 算法的基本數(shù)學(xué)原理。

• RSA 加密公式：密文 = 明文 ^ E mod N
• RSA 解密公式：明文 = 密文 ^ D mod N
• RSA 公鑰：{E, N}
• RSA 私鑰：{D, N}

一堆符號，解釋下，E 代表 Encryption，D 代表 Decryption，N 代表 Number。

從公式種能夠看出來，RSA的加解密數(shù)學(xué)公式非常簡單（即非常美妙）。RSA 最復(fù)雜的并非加解密運算，而是如何生成密鑰對，這和對稱密鑰算法是不太一樣的。而所謂的嚴密的數(shù)學(xué)計算關(guān)系，就是指 E 和 D 不是隨便選擇的。

RSA加密和解密

RSA的核心問題：生成密鑰對

密鑰對的生成，是 RSA 最核心的問題，RSA 的美妙與奧秘也藏在這里面。

• 求 N
• 求 L（L是生成密鑰對過程種一個關(guān)鍵的中間變量）
• 求 E
• 求 D

接下來是一點點數(shù)學(xué)介紹了！

1. 求N

求 N 公式：N = p × q

其中，p 和 q 是兩個質(zhì)數(shù)，而且應(yīng)該是很大又不是極大的質(zhì)數(shù)。如果太小的話，密碼就容易被破解；如果極大的話，計算時間就會很長。比如 512 比特的長度（155 位的十進制數(shù)字）就比較合適。

這樣的質(zhì)數(shù)是如何找出來的呢？需要通過 “偽隨機數(shù)生成器（PRNG）” 進行生成，然后再判斷其是否為質(zhì)數(shù)。如果不是，就需要重新生成，重新判斷。

判斷一個數(shù)是否為質(zhì)數(shù)，并不是看其能不能分解質(zhì)因數(shù)，而是通過數(shù)學(xué)的判斷方法來完成，比如費馬測試和米勒·拉賓測試等。（描述復(fù)雜數(shù)學(xué)算法的念頭還是算了吧）

2. 求L

求 L 公式：L = lcm(p-1, q-1)

lcm 代表 “最小公倍數(shù)（least common multiple）” 。注意，L 在加解密時都不需要，僅出現(xiàn)在生成密鑰對的過程中。

3. 求E

E 要滿足兩個條件：
1）1 < E < L
2）gcd(E,L) = 1

gcd 代表 “最大公約數(shù)（greatest common divisor）”。gcd(E,L) = 1 就代表 “E 和 L 的最大公約數(shù)為1，也就是說，E 和 L 互質(zhì)”。

L 在第二步已經(jīng)計算出來，而為了找到滿足條件的 E，第二次用到 “偽隨機數(shù)生成器（PRNG）”，在 1 和 L 之間生成 E 的候選，判斷其是否滿足 “gcd(E,L) = 1” 的條件。

可以使用“歐幾里得輾轉(zhuǎn)相除法”計算最大公約數(shù)。（描述復(fù)雜數(shù)學(xué)算法的念頭還是算了吧）

經(jīng)過前三步，已經(jīng)能夠得到密鑰對種的 “公鑰：{E, N}” 了。

4. 求D

D 要滿足兩個條件：
1）1 < D < L
2）E × D mod L = 1

只要 D 滿足上面的兩個條件，使用 {E, N} 進行加密的報文，就能夠使用 {D, N} 進行解密。

"E × D mod L = 1" 在數(shù)學(xué)上的表述方式為：在以 L 為模的世界中，E 和 D 互為倒數(shù)。我們平時說的乘法中的倒數(shù)（比如 3 和 1/3），只是 L 為 1 的特殊情況。

至此，N、L、E、D 都已經(jīng)計算出來，再整理一下

RSA密鑰對

RSA 模擬實踐

模擬實踐的過程包括兩部分，第一部分是生成密鑰對，第二部分是對數(shù)據(jù)進行加解密。為了方便計算，都使用了較小的數(shù)字。

第一部分：生成密鑰對

1. 求N
準備兩個質(zhì)數(shù)，p = 5，q = 7，N = 5 × 7 = 35

2. 求L
L = lcm(p-1, q-1) = lcm (4, 6) = 12

3. 求E
gcd(E, L) = 1，即 E 和 L 互質(zhì)，而且 1 < E < L，滿足條件的 E 有多個備選：5、7、11，選擇最小的 5 即可。于是，公鑰 = {E, N} = {5, 35}

4. 求D
E × D mod L = 1，即 5 × D mod 12 = 1，滿足條件的 D 也有多個備選：5、17、41，選擇 17 作為 D（如果選擇 5 恰好公私鑰一致了，這樣不太直觀），于是，私鑰 = {D, N} = {17, 35}

至此，我們得到了公私鑰對：

• 公鑰 = {5, 35}
• 私鑰 = {17, 35}

第二部分：模擬加解密

明文我們也使用一個比較小的數(shù)字 -- 4，利用 RSA 的加密公式：

密文 = 明文 ^ E mod N = 4 ^ 5 mod 35 = 9
明文 = 密文 ^ D mod N = 9 ^ 17 mod 35 = 4

尼瑪，好大啊

從這個模擬的小例子能夠看出，即使我們用了很小的數(shù)字，計算的中間結(jié)果也是超級大。如果再加上偽隨機數(shù)生成器生成一個數(shù)字，判斷其是否為質(zhì)數(shù)等，這個過程想想腦仁兒就疼。還好，現(xiàn)代芯片技術(shù)，讓計算機有了足夠的運算速度。然而，相對于普通的邏輯運算，這類數(shù)學(xué)運算仍然是相當緩慢的。這也是一些非對稱密碼卡/套件中，很關(guān)鍵的性能規(guī)格就是密鑰對的生成速度

網(wǎng)上搜索到的某密碼卡性能參數(shù)

四、針對 RSA 的攻擊

公鑰密碼體系中，用公鑰加密，用私鑰解密，公鑰公開，私鑰隱藏。因此：

• 黑客能夠拿到的信息：1）密文；2）公鑰（即 E 和 N）
• 黑客無法拿到的信息：1）明文；2）私鑰（即 D 和 N）；3）中間計算過程的信息（即 p、q、L）。當然，私鑰中的 N 其實能夠拿到，和明文的 N 是一樣的。

攻擊方式一：直接破解明文

加密公式為：密文 = 明文 ^ E mod N

破譯的過程就是對該公式進行逆運算。由于除了對明文進行冪次運算外，還加上了“模運算”，因此在數(shù)學(xué)上，該逆運算就不再是簡單的對數(shù)問題，而是求離散對數(shù)問題，目前已經(jīng)在數(shù)學(xué)領(lǐng)域達成共識，尚未發(fā)現(xiàn)求離散對數(shù)的高效算法。

攻擊方式二：通過暴力破解求 D

暴力破解的本質(zhì)就是逐個嘗試。當前主流的 RSA 算法中，使用的 p 和 q 都是 1024 位以上，這樣 N 的長度就是 2048 位以上。而 E 和 D 的長度和 N 差不多，因此要找出 D，就需要進行 2048 位以上的暴力破解。即使上文那個簡單的例子，算出（蒙出） “9 ^ D mod 35 = 4” 中的 D 也要好久吧。

攻擊方式三：通過 E 和 N 求出 D

因為 E 和 N 是已知的，而 D 和 E 在數(shù)學(xué)上又緊密相關(guān)（通過中間數(shù) L），能否通過一種反向的算法來求解 D 呢？

• E × D mod L = 1
• L = lcm(p-1, q-1)

從這個地方能夠看出，p 和 q 是極為關(guān)鍵的，這兩個數(shù)字不泄密，幾乎無法通過公式反向計算出 D。也就是說，對于 RSA 算法，質(zhì)數(shù) p 和 q 絕不能被黑客獲取，否則等價于交出私鑰。

既然不能靠搶，N = p × q，N是已知的，能不能通過 “質(zhì)因數(shù)分解” 來推導(dǎo) p 和 q 呢？或者說，一旦找到一種高效的 “質(zhì)因數(shù)分解” 算法，就能夠破解 RSA 算法了。

幸運的是，這和上述的“離散對數(shù)求解”一樣，當下在數(shù)學(xué)上還沒有找到這種算法，當然，也無法證明“質(zhì)因數(shù)分解”是否真的是一個困難問題。因此只能靠硬算，只是當前的算力無法在可現(xiàn)實的時間內(nèi)完成。這也是很多人都提到過的，“量子時代來臨，當前的加密體系就會崩潰”，從算力的角度看，或許如此吧。

既不能搶，也不能算，能不能猜呢？也就是通過 “推測 p 和 q 進行破解”。

p 和 q 是通過 PRNG（偽隨機數(shù)生成器）生成的，于是，又一個關(guān)鍵因素，就是采用的偽隨機數(shù)生成器算法要足夠隨機。

隨機數(shù)對于密碼學(xué)極為重要，后面會專門寫一篇筆記。

攻擊方式四：中間人攻擊（最常見的 RSA 攻擊手段）

前三種攻擊方式，都是基于 “硬碰硬” 的思路，而 “中間人攻擊” 則換了一種迂回的思路，不去嘗試破解密碼算法，而是欺騙通信雙方，從而獲取明文。具體來說，就是：主動攻擊者 Mallory 混入發(fā)送者和接收者之間，面對發(fā)送者偽裝成接收者，面對接收者偽裝成發(fā)送者。

中間人攻擊

這個過程可以重復(fù)多次。需要注意的是，中間人攻擊方式不僅能夠針對 RSA，還可以針對任何公鑰密碼。能夠看到，整個過程中，公鑰密碼并沒有被破譯，密碼體系也在正常運轉(zhuǎn)，但機密性卻出現(xiàn)了問題，即 Alice 和 Bob 之間失去了機密性，卻在 Alice 和 Mallory 以及 Mallory 和 Bob 之間保持了機密性。即使公鑰密碼強度再強大 N 倍也無濟于事。也就是說，僅僅依靠密碼算法本身，無法防御中間人攻擊。

而能夠抵御中間人攻擊的，就需要用到密碼工具箱的另一種武器 -- 認證。在下面一篇筆記中，就將涉及這個話題。

好了，以上就是公鑰密碼的基本知識了。

五、混合密碼體系

公鑰密碼體系能夠完美的解決對稱密碼體系中 “密鑰配送” 這個關(guān)鍵問題，但是拋開 “中間人攻擊” 問題不談，公鑰密碼自己也有個嚴重的問題：

公鑰密碼處理速度遠遠低于對稱密碼。不僅體現(xiàn)在密鑰對的生成上，也體現(xiàn)在加解密運算處理上。

因此，在實際應(yīng)用場景下，往往會將對稱密碼和公鑰密碼的優(yōu)勢相結(jié)合，構(gòu)建一個 “混合密碼體系”。簡單來說：首先用相對高效的對稱密碼對消息進行加密，保證消息的機密性；然后用公鑰密碼加密對稱密碼的密鑰，保證密鑰的機密性。

下面是混合密碼體系的加解密流程圖。整個體系分為左右兩個部分：左半部分加密會話密鑰的過程，右半部分是加密原始消息的過程。原始消息一般較長，使用對稱密碼算法會比較高效；會話密鑰一般比較短（十幾個到幾十個字節(jié)），即使公鑰密碼算法運算效率較低，對會話密鑰的加解密處理也不會非常耗時。

著名的密碼軟件 PGP、SSL/TLS、視頻監(jiān)控公共聯(lián)網(wǎng)安全建設(shè)規(guī)范（GB35114） 等應(yīng)用，都運用了混合密碼系統(tǒng)。

1. 混合密碼體系-加密流程

混合密碼體系-加密流程

2. 混合密碼體系-解密流程

混合密碼體系-解密流程

好了，以上就是公鑰密碼算法的全部內(nèi)容了，拖更了很久，以后還要更加勤奮一些。

為了避免被傻啦吧唧的審核機器人處理，后面就不再附漂亮姑娘的照片（也是為了你們的健康），改成我的攝影作品，希望不要對收視率產(chǎn)生影響，雖然很多小伙兒就是沖著姑娘來的。

就從喀納斯之旅開始吧。

喀納斯-月亮灣