《從數學到物理學：加密演算法簡介》作者：George Moraetes，翻譯&校對：閔敏 & 阿劍
是不是隻有那些數學頭腦很好的人，才能理解那些在資訊保安中常常用到的技術（密碼學）？如果你要成為密碼學家，那可能是的，畢竟密碼學家的工作就是構造極難破解的加密演算法。但是加密方法在當今世界的用途已經非常普遍了，從保護使用者的信用卡資訊、保護遠端使用者的網路連線，到保護智力產權、防止盜版，密碼學無處不在。
我這篇文章的目的，就是把令人望而生畏的密碼學轉述成大白話，讓大家都能理解這些方法是如何用來加密資料的。
- 密碼學就是數學和物理學的組合；它是資訊保安技術的核心，保護我們的資料安全和隱私 -
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 密碼也是用同樣的原理設計出來的。但是解密起來就很麻煩，因此每個字母都代表一個位移值。
維吉尼亞密碼錶
在理解密碼設計學之前，我們先要了解加密演算法的工作原理，因為它們是所有加密過程的基礎。速記是一種記錄隱藏資訊的方法，實際上可以歸為古典密碼設計學一類，因為現代密碼設計學已經成了 “電腦保安” 的代名詞。
多型性
多型性是密碼設計學中較為高階的部分，在計算機加密技術中最為常見。多型性指的是，一種加密方法在每次使用時都會產生不同的結果，而且在每次使用過後都會發生改變。多型性常見於計算機加密演算法。也就是說，如果我們將相同的資料加密兩次，每次都會得到一個不同的加密結果。
我們用汽車鑰匙來打個比方。現在，我們只需要在一個小巧的電子遙控裝置上輕輕一按，就可以解鎖汽車了。當你解鎖車門時，你或許從來沒思考過其中的原理 —— 你按下按鈕的那一刻，會有一段特定的資料傳送到你的車上，一旦匹配成功，車門就解鎖了。要實現這點，最簡單的方法是為每個遙控裝置設定不同的頻率。但是，這樣管理起來會很麻煩。因此，所有遙控裝置都採用了同樣的波長，但是使用不同的演算法（滾動碼）來生成傳送給汽車的資料。這些就是多型性演算法。
由於這些演算法每次使用過後都會發生改變，很難對其進行逆向工程。即使有駭客破解了演算法（首先，破解多型性演算法本身難度就很大），他還得找到與該演算法匹配的汽車/鑰匙（這又是一項複雜的任務）。
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 演算法所用的金鑰大小會相應決定轉換操作的重複輪數。對應關係如下：
128 位金鑰對應 10 輪重複
192 位金鑰對應 12 輪重複
256 位金鑰對應 14 輪重複
每一輪都包含幾個處理步驟，而每個步驟都包含 4 個相似但不同的階段，其中包括取決於加密金鑰本身的一個階段。在解密的時候，需要用同一把金鑰來反向重複操作、將密文恢復成原文。
量子密碼學
上面這個圖示說明了量子金鑰分發方案（BB84 協議），它實現了一種包含量子力學的密碼學協議，能夠保證安全通訊。它讓通訊雙方可以生成一個共享的隨機金鑰（是個對稱金鑰），這個金鑰只有他們雙方才知道，因此可以用於加解密訊息。量子力學是一組描述組成宇宙的光子、電子和其它粒子運動規律的科學定律。
業界一直在盡最大努力尋找能夠抵抗駭客攻擊的最高安全手段，而新一代的密碼設計學已經從數學轉向物理學。量子力學科學家已經進入密碼學的世界了，這些科學家希望利用量子力學的原理來傳送無法被黑的訊息。這就是 “量子密碼學” 的大概，它是在過去這幾十年裡才成長起來的。
量子密碼學將自己的根紮在量子物理學中。組成我們這個宇宙的基本粒子具有內在的不確定性，可能同時存在於此處或彼處，也可以有不止一種狀態。只有在撞上一個物體或者被測量時，它們才會顯現出運動現象。
密碼設計學是資訊保安的一個迷人領域，也是最複雜的學科之一。不過，我們從簡單的凱撒密碼和波利比烏斯密碼介紹到多輪加密的DES和AES演算法，相信讀者會覺得理解起密碼演算法概念就不那麼複雜了。
對於密碼學這門科學，我們已經瞭解其歷史、從最簡單到最複雜的加密演算法的基本概念。
原文連結:https://medium.com/the-capital/understanding-cryptography-from-math-to-physics-8c2000c8e7e7
宣告：本文內容為作者獨立觀點，不代表碳鏈價值立場，且不構成任何投資理財建議。
