數學中的戰爭，戰爭中的數學——漫談密碼（3）
作者：@何欽堯
距離密碼學系列的上一篇文章發出來到現在已經有一段時間了，大家是不是以為說好的本文的作者跑路了呢？好吧其實是因為之前的一段時間本文的作者一直在忙於期末考試和大作業，所以一直沒有動靜 TAT 。好吧，那麼現在我們來進入密碼學系列的第三篇，也是最後一篇。本篇主要介紹非對稱密碼體系。
非對稱密碼體系又稱公鑰密碼體系。他和之前我們講的對稱密碼體系完全是兩種不同的套路。公鑰密碼體系的提出可以說得上是密碼學歷史上最偉大的一次革命（當然了，我們認為也只有這一次能稱得上是革命）。現代各種安全體系中的金鑰交換，數字簽名，使用者認證等都基於公鑰密碼體系。
那麼現在就讓我來帶著大家領略公鑰密碼學的精彩。本篇在原理介紹部分將會涉及到一些數論方面的知識，我會盡可能的將其寫的足夠的易懂。當然如果實在是對此uncomfortable，不妨直接跳過原理部分，無傷大雅。
一、公鑰密碼體系概覽
在之前介紹的對稱密碼體系中，我們知道，對於明文的加密和密文的解密使用的都是相同的金鑰。正是因為這個原因我們把它叫做
對稱密碼體系
。比如Alice要給Bob傳送一條訊息，他會使用雙方提前協商好的金鑰對訊息進行加密。Bob收到訊息後用同樣的金鑰進行解密。這時候，加密和解密互為逆運算。由於金鑰是隻在Alice和Bob之間共享的，第三方不能知道金鑰，因此即使有第三方截取了訊息（在網際網路上傳播的資料被擷取是一件很容易的事情），也不能恢復出原文。
而公鑰密碼體系，在加密和解密的時候使用兩個不同的金鑰，使用一個金鑰加密的資料只能用另一個金鑰來解密。我們稱這樣的兩個金鑰為一個
公私金鑰對
，其中公鑰可以公開，而私鑰需要被妥善的保管避免洩露。
我們再次考慮Alice要給Bob傳送一條訊息，Alice需要使用Bob的公鑰對訊息進行加密。因為公鑰總是公開的，所以任何人都可以獲取Bob的公鑰並給他傳送訊息。Bob收到訊息之後使用自己的私鑰進行解密。因為其他人都不知道Bob的私鑰，所以都無法讀取訊息的原文。
於是，公鑰加密的安全性就取決於以下幾點：
兩個金鑰之一是保密的
知道一個金鑰和若干密文訊息是不能確定另一金鑰的（計算上不可行）
為了達到這樣的性質，公鑰加密演算法在設計的時候通常利用了一些數學上難解的問題，例如：
大整數的質因數分解
大整數的離散對數
橢圓曲線上的離散對數
（以上列出幾個名詞僅用於裝逼）
當然了，公鑰密碼體系的作用遠遠不止有加密這麼簡單。這裡我先賣個關子，我們先來以著名的
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首先需要生成公私鑰對，我們就先從金鑰的生成講起。
首先讓我們選擇兩個大素數p和q
計算
，可以知道知道
。
選擇一個整數e，使得
且
。
計算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的公鑰解密即可。
講到這裡我們就涉及到了一個重要的概念叫做
數字簽名。
當密碼被應用在商業和個人目的中的時候，如同重要的檔案需要手寫簽名一樣，重要的電子檔案也需要簽名。密碼學裡面我們就做出這樣的考慮，能否設計一種方法，能夠確保數字簽名一定是出自某個特定的人，並且雙方都對此沒有異議呢？（也就是這個簽名的結果不能被任何一方否認）
一般來說，數字簽名必須要滿足：
能夠驗證簽名者，簽名日期和時間
能夠驗證簽名內容
能由第三方進行仲裁
（背景音：說人話）
好吧其實也就是接受方收到這條訊息之後，可以確認這條訊息一定是傳送方傳送的，且訊息的內容沒有被篡改過。傳送方也不能抵賴這一個事實。
上面說到的將整個訊息用傳送方的私鑰進行加密是一種可能的數字簽名手段。但是由於公鑰加密一般來說的運算量都太大，對整個訊息完整的進行加密太費時。而為了解決這個問題，先讓我們引入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的證書（也就是公鑰）是被廣泛接受，並內建在作業系統，瀏覽器等當中的。我們通常在系統裡遇到的『受信賴的根證書頒發機構』，就是這種東西。
好了，雖然公鑰密碼學還有很多有意思的東西，但是貪大求全不如做小而精，而且篇幅太長實在難讀。本篇僅在於介紹一些基本的概念，為大家入個門。如果能激起一些同學深入探索密碼學的興趣的話，那便是足夠了。
好了，水木看山密碼學部分的三篇到這裡就全部結束了。請大家期待水木看山未來更多精彩的作品~