入門科普 | 從數學到物理學 :「加密演算法Cryptology」的歷史與簡介

是不是只有那些數學頭腦很好的人，才能理解那些在訊息安全中常常用到的技術（密碼學）？如果你要成為密碼學家，那可能是的，畢竟密碼學家的工作就是構造極難破解的加密演算法。但是加密方法在當今世界的用途已經非常普遍了，從保護用戶的信用卡訊息、保護遠程用戶的網路連接，到保護智力產權、防止盜版，密碼學無處不在。本文源自於 The Capital 的部落格觀點文《Understanding Cryptography | From Math to Physics》，由專欄作者以太坊愛好者編譯、撰寫及整理。
（議題背景：針對區塊鏈？習近平表態隔天「全國人大會」通過《密碼法》，預計2020元旦生效）

本文目錄

我這篇文章的目的，就是把令人望而生畏的密碼學轉述成白話，讓大家都能理解這些方法是如何用來加密數據的。

4-1 | 動區動趨-最具影響力的區塊鏈新聞媒體 — 8211 密碼學就是數學和物理學的組合它是訊息安全技術的核心保護我們的數據安全和隱私 8211

1. 密碼學（Cryptology）的歷史

「cryptology」和「cryptography」兩個詞在現代的文獻中常常是無差別混用的，這就把對它們實際意義的混淆延伸到了語義學中。實際上，這幾個不同的詞語最好這樣解釋：

Cryptology（密碼學） —— 對保密技術的藝術性以及 / 或者密碼系統科學性的研究
Cryptography（密碼設計學）—— 設計密碼系統來保密的實用方法
Cryptoanalysis（密碼學分析）—— 致力於發現無需得知密鑰或演算法就能從密文中反推出明文的漏洞

註：正如作者所說，在現代的文獻中，「cryptology」和「cryptography」基本上是沒有差別的了，都是「密碼學」的意思，而且，密碼學雖然脫胎於加密方法研究，但現代的密碼學早已不止於研究加解密，而是延伸到了研究如何保障通信中的「機密性」、「身份同一性」等屬性上。因此，可以說，作者這裡的定義即使不算過時，也至少是窄化了密碼學。不過，出於理解作者原意的需要，對下文中的相應詞語，我們仍沿用此處的翻譯。

本文的絕大部分篇幅是在解釋「Cryptography（密碼設計學）」，也就是今時今日的密碼學實踐，也希望讀者能意識到這幾個詞的含義和區別。

就其本身而言，密碼學作為一種科學的研究已經存在了很多年，已知最早的一個密碼設計學的例子是在一段刻於公元前 1900 年的銘文，是在埃及貴族 Khnumhotep 二世墓地的主墓室裡發現的。那個雕刻者到處使用一些奇怪的符號來代替更常見的符號。不過目的似乎並不是隱藏訊息，只是為了改變其形式，讓它看起來更高貴一些。

在羅馬帝國的鼎盛時期（公元前 100 年），Julius Caesar（凱撒大帝）也因使用加密技術向前線將軍傳送消息而聞名。這種字符替換型加密方法（cipher）被稱為「凱撒密碼」，可能是文獻中最常提到的人類曾用過的加密方法。（所謂」「cipher」，就是用來加密或者解密的算法）。所謂「字符替換型加密方法」，就是把明文（我們想要加密的消息）中的每個字母都換成另一個字母，形成密文（即被編碼過的消息）。凱撒所用的方法是把每個字母位移三位，比如，「A」會被換成「D」，「B」會被換成「E」，以此類推（都是換成該字母后面第三個字母）。相應地，最後的幾個字母會被換成開頭的字母，比如「X」會被換成「A」。

在第二次世界大戰期間，美國海軍從納瓦霍人（Navajo）中招募並訓練了許多熟練使用納瓦霍語的人。從編碼消息的角度來看，這是個絕妙的辦法，因為很少有納瓦霍人以外的人學過怎麼說這種語言，而且當時還沒有用納瓦霍語出版的書。但是除了詞語之外，納瓦霍人的口語並不是十分複雜（按密碼設計學的標準來看），一個母語為納瓦霍語的人再加上一個訓練有素的密碼學家，合作起來完全可以破解這套密碼。日本人曾經有過一次機會，就是在 1942 年「巴丹死亡行軍（Bataan Death March）」期間他們在菲律賓抓住了 Joe Kieyoomia。Joe 是美國海軍的一位納瓦霍中士，但他並不是密語播報員，只負責翻譯無線電消息。只不過，因為他沒有參與過密語訓練，這些詞語是什麼意思他一點也不懂。當他說自己不能解讀這些消息時，日本人就開始嚴刑拷打他。因此，日本陸軍和海軍從來沒有破譯過這些密語。

再到 1970 年代，IBM 發現他們的客戶需要某種形式的加密手段，所以他們成立了一個密碼學小組，由Horst-Feistel 領頭。他們設計出了一種加密算法叫「Lucifer」。1973 年，美國國家標準局（現在叫做國家技術與標準局，NIST）放出話來，希望大家能提議一種夠格成為國家標準的數據加密方法。他們顯然已經意識到，自己買了很多並沒有什麼密碼學基礎的商業產品。Lucifer 最終被接受了，因此叫做「DES（數據加密標準）」。1997 年以後，DES 被窮舉式搜索攻擊攻破。DES 的主要問題在於加密密鑰的位數太小。隨著電腦運算力的增加，通過暴力窮舉所有可能的密鑰組合來破解密文慢慢變成了一種可行的辦法。

在 80 年代，大家幾乎只有一個選擇，就是 DES。今天的情形已經大不相同了，有一大堆更健壯、更快，設計也更好的算法可供選擇。問題已經變成了你如何釐清這些選擇。

1997 年，NIST 再次徵求新的加密算法提案，最終收到了 50 份提案。2020 年，NIST 接受了「Rijndael」算法，並命名為「AES」，高級加密標準。

延伸閱讀：觀點｜深度解讀：「密碼學貨幣網路」為什麼是更優越的金融系統？

2. 基本原理

所謂加密，就是一個改變數據，使之變得不可辨識、無授權者無法使用的過程；同時，它還要保證解密過程能成功把改變後的數據恢復成原始形式。安全技術一般都把加密的數學方法和用於加密的參數（叫做「key（密鑰）」）區別開來。被選定的密鑰（通常是一段隨機的字符串）也是加密過程的輸入，對加密過程來說也是必不可少的。同一把密鑰往往也是解密過程的必要輸入。

這個保護過程的原理是，只要密鑰（有時候也叫「口令」，password）沒有暴露、只被得到授權的人所知，那麼原始數據就不會暴露給其他人。只有知道密鑰的人才能解密密文。這個思路，我們叫「私鑰」密碼設計學（註：稱作「對稱密碼學」可能更恰當一些，因為加解密過程是對稱的，都使用同一把密鑰），也是最廣為人知的加密形式。

那麼，加密之所以必要的基本理由如下：

機密性（confidentiality）——在傳輸數據的時候，不希望竊聽者能夠知道被廣播的消息的內容。在保管數據的時候不希望未經授權的人（比如駭客）能夠訪問，也是同理。
身份認證（Authentication）——相當於簽名。收信者希望能確證該訊息是特定的某個人發出的，其他人不能冒充（甚至初始發信方後面想抵賴也不可能）。
完整性（Integrity）——這意味著收信者能夠證實自己得到的數據是完完整整、沒有經第三方改動過的。
不可抵賴性（Non-repudiation）——防止發信方抵賴自己創建過、發送過某條消息。

註：作者在這裡提到的才算是現代密碼學研究的範圍。比如身份認證和不可抵賴性，都是很重要的屬性，但是在實用中幾乎與加解密過程無關，但對數位簽名的研究毫無疑問是密碼學的內容。加解密的安全性跟機密性有關，只是現代密碼學的一部分。

Cipher

密碼設計學是（通過加密）隱藏敏感數據的藝術和科學。它包括加密過程（就是在原始的「原文」上使用加密算法）和解密過程（就是在密文上使用算法，使之恢復到可讀的形式）。

要解釋什麼是 Cipher，最好還是給你看幾個簡單的例子：

波利比烏斯密碼

波利比烏斯密碼（Polibius Cipher）也是一種字符替換型密碼。在我這個示例中，我用的是一個 6×6 的二維矩陣，可以把所有的大寫字母和數字 0 到 9 都包括進去。然後我們可以得出下表：

有了這個矩陣，我們就可以開始代換了。比如，字母「A」可以表示成「1 × 1」，或者「X = 1，Y = 1」，甚至再簡化成 11。再舉例，字幕「N」可以表示成「2 × 3」，或者「X = 2，Y = 3」，簡化後就是23。

來試試加密一條簡單的訊息：

消息（原文）：ENCRYPT ME 2 DAY

加密後的數據（密文）：51–23–31–63–15–43–24 13–51 55 41–11–15

納入生僻字符後，這張表可以變得很大很複雜。而且，定期地隨機改變字符的位置也會讓暴力破解無從下手。這很像我們今天在高級計算型加密方法所用的多態性（polymorphism）。

凱撒密碼

歷史最悠久的加密算法之一就是以其創造者凱撒而聞名的凱撒密碼（Caeser Cipher）。他用這套方法來保證跟羅馬將軍們的安全通信，這樣羅馬帝國的敵人們就算拿到信也沒有辦法讀懂。凱撒密碼是加密的一種初級形式，很容易被破解，所以今天已經基本不會用在任何安全用途中了。

從原理上來說，凱撒密碼就是重排字母表，不同的位移值也會使得編碼後的數據完全不同。位移值，顧名思義，就是通過讓字母左移或者右移一定位數來生成密文的數值。（註：所以，在這裡，大家可以把凱撒密碼理解成一種根據字母表順序的位移來加密的算法（cipher），而位移值就是那個 Key，密鑰。）

這裡我們用右移 3 位的做法來看一個實際的例子：

英文原文：ENCRYPT ME

密文：HQFUBSW PH （解密時候要相應左移3 位才能解密）

上面這條消息可以通過嘗試所有可能的位移值來暴力破解：不斷嘗試新的位移值，直到解出來的原文看起來像樣子。更加複雜的密碼比如 Vigenere 密碼和 Gronsfeld 密碼也是用同樣的原理設計出來的。但是解密起來就很麻煩，因此每個字母都代表一個位移值。

維吉尼亞密碼表

在理解密碼設計學之前，我們先要了解加密算法的工作原理，因為它們是所有加密過程的基礎。速記是一種記錄隱藏訊息的方法，實際上可以歸為古典密碼設計學一類，因為現代密碼設計學已經成了「計算機安全」的代名詞。

多態性

多態性是密碼設計學中較為高級的部分，在計算機加密技術中最為常見。多態性指的是，一種加密方法在每次使用時都會產生不同的結果，而且在每次使用過後都會發生改變。多態性常見於計算機加密算法。也就是說，如果我們將相同的數據加密兩次，每次都會得到一個不同的加密結果。

我們用汽車鑰匙來打個比方。現在，我們只需要在一個小巧的電子遙控設備上輕輕一按，就可以解鎖汽車了。當你解鎖車門時，你或許從來沒思考過其中的原理 —— 你按下按鈕的那一刻，會有一段特定的數據發送到你的車上，一旦匹配成功，車門就解鎖了。要實現這點，最簡單的方法是為每個遙控設備設定不同的頻率。但是，這樣管理起來會很麻煩。因此，所有遙控設備都採用了同樣的波長，但是使用不同的算法（滾動碼）來生成發送給汽車的數據。這些就是多態性算法。

由於這些算法每次使用過後都會發生改變，很難對其進行逆向工程。即使有駭客破解了算法（首先，破解多態性算法本身難度就很大），他還得找到與該算法匹配的汽車 / 鑰匙（這又是一項複雜的任務）。

延伸閱讀：以太坊顛覆了以太坊！「分佈式系統 + 密碼學」實現 2.0 性能突破

3. 常用算法

現如今，常用的加密算法不外乎私鑰加密方法和公鑰加密方法。私鑰加密方法可以用來保護關鍵 / 敏感數據。密鑰密文只需一把鑰匙（由通信雙方共享）破解，因此被稱為對稱性密碼設計學。

1949 年，貝爾實驗室的 Claude Shannon 公佈了私鑰加密方法的基本理論。數十年來的演化已經孕育出了很多高質量的私鑰加密算法。然而，直到 1975 年，一個名為 DES 的強大私鑰加密方法才得到了廣泛使用。

公鑰/非對稱性密碼設計學誕生於 20 世紀 70 年代中期。公鑰加密方法需要用到一對密鑰，分別是對外公開的公鑰和相對應的由個人持有的私鑰。例如，接收方可以創建一對密鑰，並將公鑰分享給任何想要向 ta 發送密文的人。發送方可以使用公鑰加密發送給接收方的信件，接收方可以用私鑰來解密。

加密算法的強大程度取決於三個主要因素：

基礎設施 ——如果相關密碼設計主要由軟體實現，那麼底層基礎將是最薄弱的環節。如果你總是會加密某些訊息，那麼對駭客來說，最好的做法是駭進你的電腦，在訊息被加密前將其偷到手。相比破解密鑰來說，入侵系統或者使用病毒感染系統要容易得多。很多情況下，破解密鑰最簡單的方法是竊聽用戶，並在密鑰被傳入加密程式時進行攔截。
密鑰長度 ——在密碼設計學中，密鑰長度很重要。如果攻擊者無法安裝按鍵監視器（keystroke monitor），那麼破解密文的最佳方法就是通過不斷的試錯來暴力破解。實用的加密算法必須將密鑰長度設定得足夠長，來杜絕暴力破解的可能性。但是，隨著電腦運算速度一年比一年快，密鑰長度的安全閾值也需要一直提高。專家們承認，小於等於 64 位的密鑰，包括 DES 密鑰在內，都很容易被暴力破解。在 1999 年，電子前線基金會（Electronic Frontier Foundation）資助開發了一種叫做「Deep Crack」的設備，可以在三天以內破解一個 DES 加密密鑰。所以現在加密算法的密鑰長度一般都在 100 位以上，少數算法支持 256 位的密鑰。
算法質量 ——算法質量本身是很難評價的，基於一個現有算法去構造一個看似可行的算法是很容易的，但只有經驗老道的專家仔細檢查才能發現其中的微妙漏洞。算法中的漏洞會產生「捷徑」，讓攻擊者可以在暴力搜索攻擊時候跳過大批密鑰。舉個例子，流行的壓縮程序 PKZIP 以前繼承了一個定制的的加密功能，使用 64 位的密鑰。理論上來說，應該要 264 嘗試才能試完所有的密鑰。但實際上，有捷徑可走，所以攻擊 PKZIP 加密算法只需 227 次嘗試就能破解密文。發現這樣漏洞的唯一辦法就是嘗試破解算法，一般來說就是使用對付其它算法的技巧。只有在經過這樣的分析和攻擊之後，算法的質量才會展現出來，所以，還沒有找出這樣的漏洞，並不代表這個算法永遠不被發現有漏洞。

算法的類型

DES —— DES 已經經受住了時間的考驗，多來年出版的研究都證明了其質量。經過四分之一世紀的研究之後，研究員也只能找出一些猜測式的攻擊方法，而且實用性還不如暴力破解。DES 算法的唯一真實弱點就是它過短的密鑰長度（56位）。

三重 DES —— 使用 112位或者 168位的密鑰連續三次使用 DES算法。最終這個算法會比其它有類似強度的算法慢得多，而且，因為電腦還是強大到了能破解這個算法，這一方法已經過時了。

AES —— 高級加密標準（AES）支持三種密鑰大小，128 位的、192 位的和 256 位的，而數據則按 128 位為一個組。現在 AES 被當成標準，全世界都在使用。

Rijndael 密碼表

DES 是明確設計為內置在硬體中的，從沒考慮過怎麼讓它在軟體層面實現。後來，NIST 評估了執行效率和存儲需求，保證 AES 能在 C 語言和 Java 語言中工作，既能在工作站中運行，也能在資源更有限的環境比如嵌入式 ARM 處理器和智能卡中運行。

雖然荷蘭研究院 Vincent Rijman 和 Joan Daemen 發明的 Rijndael 算法贏得了NIST 精算，但所有進入 AES 決賽的算法相對比 DES 和 DES 的替代品都顯現出了巨大的進步。所有這些算法都是分組加密（block cipher）算法並且支持 128 位乃至更大的密鑰；沒有一種算法有嚴重的漏洞；最終選擇其實是密碼設計強度和性能的權衡。

AES 基於一種叫做「置換-排列」的設計原理，在計算中既有置換，又有排列，無論在軟體層還是硬體層，計算起來都很快。不像其前輩 DES，AES 不使用費斯托密碼（Feistel）原理，AES 是 Rijndael 密碼的一種變種，使用固定的 128 位大小作為輸入，而且支持 128 位、192 位和 256 位的臨界維數（critical dimension）。相反，Rijndael 設計規範僅指定了輸入組和密鑰的大小都是 32 的倍數，最小是 128 位，最大是 256 位。

AES 在一個 4×4 的字節矩陣上操作，這些舉證叫做「狀態」。但是 Rijndael 算法的某些版本的輸入組更大，因此矩陣更大。大部分 AES 計算都是在一個特定的有限域內完成的。

AES 算法所用的密鑰大小會相應決定轉換操作的重複輪數。對應關係如下：