數學中的戰爭，戰爭中的數學——漫談密碼（3）

距離密碼學系列的上一篇文章發出來到現在已經有一段時間了，大家是不是以為說好的本文的作者跑路了呢？好吧其實是因為之前的一段時間本文的作者一直在忙於期末考試和大作業，所以一直沒有動靜 TAT 。好吧，那麼現在我們來進入密碼學系列的第三篇，也是最後一篇。本篇主要介紹非對稱密碼體系。

非對稱密碼體系又稱公鑰密碼體系。他和之前我們講的對稱密碼體系完全是兩種不同的套路。公鑰密碼體系的提出可以說得上是密碼學歷史上最偉大的一次革命（當然了，我們認為也只有這一次能稱得上是革命）。現代各種安全體系中的密鑰交換，數字簽名，用戶認證等都基於公鑰密碼體系。

那麼現在就讓我來帶著大家領略公鑰密碼學的精彩。本篇在原理介紹部分將會涉及到一些數論方面的知識，我會儘可能的將其寫的足夠的易懂。當然如果實在是對此uncomfortable，不妨直接跳過原理部分，無傷大雅。

一、公鑰密碼體系概覽

在之前介紹的對稱密碼體系中，我們知道，對於明文的加密和密文的解密使用的都是相同的密鑰。正是因為這個原因我們把它叫做對稱密碼體系。比如Alice要給Bob發送一條消息，他會使用雙方提前協商好的密鑰對消息進行加密。Bob收到消息後用同樣的密鑰進行解密。這時候，加密和解密互為逆運算。由於密鑰是只在Alice和Bob之間共享的，第三方不能知道密鑰，因此即使有第三方截取了消息（在互聯網上傳播的數據被截取是一件很容易的事情），也不能恢復出原文。

而公鑰密碼體系，在加密和解密的時候使用兩個不同的密鑰，使用一個密鑰加密的數據只能用另一個密鑰來解密。我們稱這樣的兩個密鑰為一個公私密鑰對，其中公鑰可以公開，而私鑰需要被妥善的保管避免泄露。

我們再次考慮Alice要給Bob發送一條消息，Alice需要使用Bob的公鑰對消息進行加密。因為公鑰總是公開的，所以任何人都可以獲取Bob的公鑰並給他發送消息。Bob收到消息之後使用自己的私鑰進行解密。因為其他人都不知道Bob的私鑰，所以都無法讀取消息的原文。

於是，公鑰加密的安全性就取決於以下幾點：

1. 兩個密鑰之一是保密的
2. 知道一個密鑰和若干密文消息是不能確定另一密鑰的（計算上不可行）

為了達到這樣的性質，公鑰加密演算法在設計的時候通常利用了一些數學上難解的問題，例如：

• 大整數的質因數分解
• 大整數的離散對數
• 橢圓曲線上的離散對數

（以上列出幾個名詞僅用於裝逼）

當然了，公鑰密碼體系的作用遠遠不止有加密這麼簡單。這裡我先賣個關子，我們先來以著名的RSA演算法為例，介紹公鑰加密的原理。

二、RSA加密的原理

（前方出現大量數學公式，非戰鬥人員請儘快撤離，跳過到下一部分）

在介紹原理之前我們先來複習一些數論的知識。從我們都很熟悉的帶余整數除法開始。對於任意正整數n和任意非負整數a，我們用a除以n，得到商q和餘數r，他們可以寫為：

其中表示小於等於x的最大整數。

在這個基礎之上我們定義模運算，對於上面的例子，也就是

如果a和b模n的餘數相同，我們就說a和b是同餘的，寫作

如果，也就是a除以n的餘數為0，我們說n整除a，寫作

如果，我們稱b是a的一個因子。定義表示a和b的最大公因子，也就是同時能整除a和b的最大的整數。如果兩個數的最大公因子是1，我們稱這兩個數互素。顯然1與任何整數都互素。

如果對於一個整數，僅有和能夠整除它，我們就說p是一個素數。之後的討論都會主要圍繞素數來進行。

對於任意一個整數，都可以唯一的分解為素數的乘積的形式，即

這個就是算數基本定理。此處略去不證，讀者可以在任何一本數論的教材中找到他的證明。

有了以上的鋪墊之後我們來引入兩個非常重要而且大名鼎鼎的定理（為了節省空間我這裡就都不給出證明了，感興趣的讀者不妨翻閱Wikipedia，有驚喜）。

費馬定理（費馬小定理）

若p是素數，a是正整數且不能被p整除，則

另一種形式為，若p是素數且a是任意正整數，則

歐拉定理

先引入一個非常重要的概念叫做歐拉函數，它指的是小於n且與n互素的正整數的個數。很顯然的（真的很顯然嗎），對於一個素數p，。這很容易理解，因為從1到p-1的整數都與p互素。

再更進一步的，對於兩個素數p，q，，那麼。不妨這裡簡單證明如下。

考慮集合，於n互素且小於n的整數只能在這個集合中。其中，p和q的整數倍一定不和n互素（和n的最大公因子為p或者q），這些數包含和。這兩個集合肯定是沒有重合的元素的，否則，若，也就是。而p和q都是素數，只能是。而我們知道，於是這是不可能的。

所以

那麼歐拉定理表示為，對於任意互素的a和n，有

另一種形式為，對於任意a和n（不要求互素），有

於是，歐拉定理實際上是費馬定理的一種推廣。

有了這些基礎鋪墊之後我們就可以開始介紹RSA加密演算法的原理啦（筆者寫到這裡已經累死了）。

RSA加密演算法將明文，密文，密鑰等當做一個超大的整數來看待。加密之前需要明文分段編碼為超大的整數（一般為1024或2048個二進位位）。以下我們為了簡單就先無視怎麼編碼這個過程，僅用整數的運算來分析RSA的加密過程。這樣也已經能夠清楚的認識到基本的原理了。

RSA首先需要生成公私鑰對，我們就先從密鑰的生成講起。

1. 首先讓我們選擇兩個大素數p和q
2. 計算，可以知道知道。

3. 選擇一個整數e，使得且。

4. 計算d，，使得

以上的各種數的選擇都可以使用隨機生成，然後在進行素數的檢測這樣來進行。第4步中的d可以使用擴展歐幾里得演算法很快的求解。

然後丟棄p和q不再保留（這是安全性的保證）。產生的公鑰為{e, n}，私鑰為{d, n}。

對於一條消息M的加密，我們計算（需要保證）

C就是加密後的密文。

解密的時候我們計算

上面等式的最後一步由歐拉定理保證。由於，於是。那麼

，

而歐拉定理說明，所以。在限制的的條件下，就有。於是我們就從密文解密出了明文。

而RSA加密的安全性的保證在於對於大整數進行質因數分解的困難性。已知了n，無法恢復出p和q。進而就無法從公鑰恢復出私鑰。為了保證這種分解的困難性，需要選擇足夠大的整數。實際的RSA加密標準中使用的整數都長達1024到2048個二進位位。

三、公鑰加密體系的實際應用

好了前面講了很多嚴肅的東西，接下來開始輕鬆一點的模式。

我們說了，公鑰加密（非對稱加密）和對稱加密是兩種不同的模式。那麼既然已經有了對稱加密方式，非對稱的方式又有什麼特別的地方使得其能夠廣泛的應用呢？

我們知道，使用對稱密碼的時候，每需要進行通信的兩個實體都需要共享他們的密鑰。假設總共有N個實體，他們之間要相互通信所需要的密鑰的總量就是

在N比較大（實際中我們也可以想像這有多大）的時候，這個密鑰的總量是一個非常誇張的數字。這給密鑰的保存，分發都帶來了很大的問題。

而在非對稱密碼當中，任何一方只要知道對方的公鑰，就可以發消息給他進行通信。所以N個實體，只需要N個公私鑰對就可以滿足互相通信的需要了。

而且，公鑰體系在其他的方面有更多的應用。我們逐個的來講解。

數字簽名

最開始的時候我們說到，Alice想要給Bob發送消息，只需要使用Bob的公鑰進行加密即可。Bob能解密這條消息，也能確定這條消息不能被發送者之外的其他人知道，但是他卻不能確定發送者的身份是不是就是Alice，因為任何一個人都可以使用Bob的公鑰給其發送消息。

這還了得。這種情況也就意味著任何一個人都可以偽造Alice給Bob發送消息，或者是Alice發送給Bob一條消息後可以否認自己發過該消息！

這種問題在對稱密碼裡面是不存在的，因為只有Alice和Bob能夠知道通信的密鑰，因此Bob如果能正常的解密消息，就能確認消息一定是來自Alice的。

在公鑰加密裡面我們同樣也有一種手段來解決問題。試想Alice要給Bob發送一條消息，如果Alice使用自己的私鑰對消息進行加密，Bob接收到消息後使用Alice的公鑰對消息進行解密。因為Alice的私鑰只有他自己知道，因此如果Bob能夠成功解密消息的話，就一定能確認消息就是來自於Alice的！

不過這裡帶來的問題就是，任何一個人都可以竊聽該消息並用Alice的公鑰進行解密。所以這種方案滿足了認證的需求，卻沒有滿足加密的要求。

當然了聰明的讀者一定想到了，如果既要認證又要加密的話，Alice可以先用自己的私鑰加密消息，然後再用Bob的公鑰加密一遍就可以了。Bob接收到消息之後先用自己的私鑰解密，再用Alice的公鑰解密即可。

講到這裡我們就涉及到了一個重要的概念叫做數字簽名。當密碼被應用在商業和個人目的中的時候，如同重要的文件需要手寫簽名一樣，重要的電子文件也需要簽名。密碼學裡面我們就做出這樣的考慮，能否設計一種方法，能夠確保數字簽名一定是出自某個特定的人，並且雙方都對此沒有異議呢？（也就是這個簽名的結果不能被任何一方否認）

一般來說，數字簽名必須要滿足：

1. 能夠驗證簽名者，簽名日期和時間
2. 能夠驗證簽名內容
3. 能由第三方進行仲裁

（背景音：說人話）

好吧其實也就是接受方收到這條消息之後，可以確認這條消息一定是發送方發送的，且消息的內容沒有被篡改過。發送方也不能抵賴這一個事實。

上面說到的將整個消息用發送方的私鑰進行加密是一種可能的數字簽名手段。但是由於公鑰加密一般來說的運算量都太大，對整個消息完整的進行加密太費時。而為了解決這個問題，先讓我們引入Hash函數的概念。

有些時候我們需要快速的判斷兩個消息（文檔）的內容是否相同，但是如果文件過大的話，比對兩個文檔的每一個位元組耗時太多。數字簽名的場景下，加密整個文檔耗時過大。這種情況下，我們使用一種折中，對於整個文檔計算一個定長的Hash值，用來代表文件的內容。這種Hash值由於長度是定的，所以一定會存在重複（即兩個相同的文檔對應了一個Hash值）。但是密碼學中的構造方法保證，很難通過一個Hash值來反推出一個文檔來。這樣就可以讓我們放心的使用Hash來作為文檔完整性的檢驗。

因此在數字簽名中一般採用的手段是，Hash函數計算出原消息的一個Hash值，然後對這個Hash值用發送方的私鑰進行加密，並將加密後的消息拼接在原本的消息之後作為一個簽名，發送出去（發送中仍然可以使用其他的加密手段來保證通信的保密性）。接收方收到消息之後，可以同樣的計算消息的Hash值，然後和簽名解密出來的值進行比對，如果相同，就完成了這個對發送方的認證。

實際的數字簽名方案當然要複雜的多，也採用了很多除了RSA以外的公鑰演算法。不過上面這樣的簡化的講法，依然是對理解整個的框架是有益的。

證書體系

在講完上面的各種公鑰加密和數字簽名之後，相信大家都一定知道了，對於公鑰密碼體系來說，公私鑰是非常重要的。首先私鑰必須要被妥善的保管而不能被竊取，否則就會威脅該個體的通信安全。而對於公鑰，我們也必須要有能力確認，某個公鑰確實是屬於某個人的。否則可以有一個第三方聲稱自己是Alice並公布自己的公鑰，而在Alice發現這一點之前，冒充者都可以獲取本應發送給Alice的消息。要解決這個問題，我們需要研究公鑰如何分發。

我們可以設想有一個可信的第三方來保存所有人的公鑰，用戶在需要的時候向其獲取某個用戶的公鑰。這個第三方有義務去認證在這裡存放公鑰的每個人的身份。但是這樣就導致這個中心化的證書存儲成為了一個瓶頸，如果被攻擊者攻破，就可以修改任何人的公鑰達到偽造的目的。而現在廣泛使用的證書體系則是對於這個問題的一種解決。

在這種體系當中，需要一個可信的第三方，我們叫做CA（certificate authority），但是不需要中心化的證書存儲。Alice需要將自己的公鑰交給CA，CA在對Alice本人認證之後，會使用CA自己的私鑰對Alice的公鑰進行簽名，並將Alice的公鑰和簽名合在一起作為證書。之後Alice就可以將證書發送給任何需要和自己通信的實體，比如Bob。

Bob收到證書之後，使用CA的公鑰對簽名進行解密，就可以判斷該證書是否是由CA簽發的。如果能夠確認證書是由CA簽發的，Bob就可以確認這個公鑰一定是屬於Alice的而不是冒充的（因為CA需要驗證身份）。

在實際的使用中不會只有一個CA，而是很多個CA組成一個樹狀的結構，處於最頂端的叫做根CA。二級或者三級的CA也可以頒發證書，而他們自己的公鑰是由上一級的CA簽發的證書。這樣我們就可以一級一級的向上驗證證書的合法性。通常，處於最頂端的根CA的證書（也就是公鑰）是被廣泛接受，並內置在操作系統，瀏覽器等當中的。我們通常在系統里遇到的『受信賴的根證書頒發機構』，就是這種東西。

好了，雖然公鑰密碼學還有很多有意思的東西，但是貪大求全不如做小而精，而且篇幅太長實在難讀。本篇僅在於介紹一些基本的概念，為大家入個門。如果能激起一些同學深入探索密碼學的興趣的話，那便是足夠了。

好了，水木看山密碼學部分的三篇到這裡就全部結束了。請大家期待水木看山未來更多精彩的作品~