ZHQM ZMGM ZMFM ——凱撒（G Julius Caesar）

KXJEY UREBE ZWEHE WRYTU HEYFS KREHE GOYFI WTTTU OLKSY CAJPO BOTEI ZONTX BYBWT GONEY CUZWR GDSON SXBOU YWRHE BAAHY USEDQ ——甘迺迪（John F Kennedy）

為什麼安全工程師必須懂一點密碼學#

密碼學是安全工程與數學交會之處。 它給我們大多數現代安全協定所倚賴的工具，是保護分散式系統的關鍵技術——然而做對它出乎意料地難。第 4 章已經看到，密碼學經常被用來保護錯的東西、或以錯的方式保護對的東西。不幸的是，現成的密碼工具也不總是好用。

作者一位醫生朋友年輕時在某個為了經濟因素而縮短醫學學程、盡快量產專科醫師的國家工作。有一天，一位雙腎已切除、正在等待移植的病人需要重做透析分流管。外科醫師以「病歷上沒有尿液分析」為由把病人退回手術室外——他就是沒想到沒有腎臟的病人根本產不出尿。

正如醫生除了外科還必須懂生理學，安全工程師也必須至少熟悉密碼學的基礎。

密碼學可以在三個層次上切入：

1. 底層的直覺；
2. 釐清這些直覺的數學——在可能時提供安全證明，並整理最令人困惑的構造；
3. 密碼工程——我們常用的工具，以及它們會怎麼出錯的經驗。

你需要一些密碼學知識的一個理由是：許多常見構造令人困惑，而許多工具提供不安全的預設值。

例如微軟的 Crypto API（CAPI）會把工程師推向使用電子密碼本（ECB）模式。讀完本章你應該理解那是什麼、為什麼糟糕、以及你該用什麼取代它。

幾個非數學的定義#

• 密碼學（cryptography）：設計密碼的科學與藝術。
• 密碼分析（cryptanalysis）：破解它們的科學與藝術。
• 密碼學總稱（cryptology，常簡稱 crypto）：兩者的研究。
• 加密過程的輸入通常稱為明文（plaintext / cleartext），輸出稱為密文（ciphertext）。

基本建構區塊包括區塊密碼（block cipher）、串流密碼（stream cipher）與雜湊函數（hash function）。區塊密碼若加解密使用同一把金鑰，稱為共享金鑰（shared-key，又稱秘密金鑰或對稱式）；若加解密使用不同金鑰，稱為公開金鑰（public-key，或非對稱式）。數位簽章方案是一種特殊的非對稱密碼原語。

歷史背景#

蘇埃托尼烏斯記載，凱撒（Julius Caesar）把「A」寫成「D」、「B」寫成「E」來加密快報。奧古斯都（Augustus Caesar）登基後改成「A」寫成「C」——用現代術語說，他把金鑰從「D」改成了「C」。

值得注意的是，據稱是西西里黑手黨教父中的教父的普羅文薩諾（Bernardo Provenzano）用了類似的密碼：「a」寫成「4」、「b」寫成「5」。這直接導致他在 2006 年被義大利警方攔截並解讀訊息後落網。

阿拉伯人把這個想法一般化為單字母替換（monoalphabetic substitution）：用一個關鍵字排列密碼字母表。

abcdefghijklmnopqrstuvwxyz
SECURITYABDFGHJKLMNOPQVWXZ

破解這類密碼是紙筆謎題。訣竅在於某些字母與字母組合遠比其他的常見；英文中最常見的字母依序是 e、t、a、i、o、n、s、h、r、d、l、u。

AI 研究者實驗過解單字母替換的程式：只用字母與雙字母（digram）頻率，通常需要約 600 個密文字母；更聰明的策略（如猜可能的單字）能降到約 150 個；最先進、使用神經網路且接近人類分析師水準的系統，也被拿去測試解讀烏加里特文與線形文字 B 這類古代文字。

要做出更強的密碼，基本上有兩條路：串流密碼（讓加密規則取決於明文符號在明文流中的位置）與區塊密碼（一次加密好幾個明文符號成一個區塊）。

早期串流密碼：維吉尼亞#

這個早期串流密碼通常歸功於法國外交官維吉尼亞（Blaise de Vigenère）。它的做法是用「A = 0、B = 1、…、Z = 25」的約定，把金鑰反覆加進明文，並以模 26 進行加法：

C = P + K mod 26

用重複關鍵字當金鑰的加密看起來像這樣：

明文   tobeornottobethatisthequestion
金鑰   runrunrunrunrunrunrunrunrunrun
密文   KIOVIEEIGKIOVNURNVJNUVKHVMGZIA

第一個公開的解法是 1863 年普魯士步兵軍官卡西斯基（Friedrich Kasiski）提出的。他注意到：只要密文夠長，重複的樣式就會出現在關鍵字長度的倍數處。

上例中我們看到「KIOV」在九個字母後重複、「NU」在六個字母後重複。既然 3 同時整除 6 與 9，我們可以猜關鍵字有三個字母。於是密文的第 1、4、7… 個字母都是用同一個金鑰字母加密的，我們就能用頻率分析猜出這個字母最可能的值，再對金鑰剩下的字母重複這個過程。

一次性密碼本#

要讓這類串流密碼免疫於攻擊，一種方法是讓金鑰序列與明文一樣長、且永不重複。這就是一次性密碼本（one-time pad），由弗南（Gilbert Vernam）在一戰期間提出。

給定任何密文與任何等長的明文，總存在一把金鑰能把該密文解密成該明文。所以不論對手能做多少計算，他們都一無所獲——因為給定任何密文，該長度的所有可能明文都同樣可能。

這個系統因此具有完美保密性（perfect secrecy）。

明文   heilhitler
金鑰   wclnbtdefj
密文   DGTYIBWPJA

密文   DGTYIBWPJA
金鑰   wggsbtdefj
明文   hanghitler

一次性紙帶從二戰後期起被雙方用於最高層級通訊，後來用於北約盟國間的戰略通訊，1963 年起用於美蘇熱線。總共生產了數千台機器，用紙帶作為金鑰材料，直到 1980 年代中期才被電腦取代。

更常見的做法是串流密碼使用偽隨機數產生器把一把短金鑰擴展成長長的金鑰流。而金鑰流光是在通過標準統計隨機性測試的意義上「看起來隨機」是不夠的：它還必須具備「即使對手拿到相當多金鑰流符號，也無法預測更多」的性質。

早期的例子是轉子機（rotor machines）——產生極長偽隨機狀態序列並與明文結合的機械式串流密碼裝置。它們在 1920 年代起被許多人獨立發明，其中不少人試圖賣給銀行業（銀行大體沒興趣）；但二戰交戰各方廣泛用它們加密無線電流量，而盟軍為解讀德軍流量所做的努力（包括圖靈等人在 Colossus 上的工作）在戰後協助啟動了電腦工業。

早期區塊密碼：Playfair#

Playfair 密碼由電報先驅惠斯登（Charles Wheatstone）於 1854 年發明——他也發明了六角手風琴與惠斯登電橋。之所以不叫惠斯登密碼，是因為他把它展示給政治人物普萊費爾男爵（Baron Playfair），而普萊費爾在一次晚宴後又在餐巾上把它展示給亞伯特親王與帕默斯頓子爵（後來的首相）。

這個密碼使用 5×5 的方格，把被關鍵字排列過的字母表填進去，並省略字母「J」：

P  A  L  M  E
R  S  T  O  N
B  C  D  F  G
H  I  K  Q  U
V  W  X  Y  Z

明文先做調整：把「J」都換成「I」，切成字母對，用「x」隔開一對中的重複字母，必要時在最後加「z」補齊。普萊費爾寫在餐巾上的例子是 “Lord Granville’s letter”，變成 lo rd gr an vi lx le sl et te rz。

加密規則（一次兩個字母）：

• 若兩個字母在同一列或同一行，就用後繼字母取代。例如 am 加密成 LE。
• 否則兩個字母位於表中某矩形的兩個角，就用該矩形另外兩個角的字母取代。例如 lo 加密成 MT。

明文   lo rd gr an vi lx le sl et te rz
密文   MT TB BN ES WH TL MP TA LN NL NV

這個密碼的變體被英軍用作一戰的野戰密碼，也被美德雙方用於二戰。它比維吉尼亞大有改進——分析者能蒐集的統計是雙字母組而非單一字母，分佈平坦得多，攻擊需要的密文也更多。

本章開頭的引文，正是甘迺迪（後來的美國總統）年輕時擔任中尉、魚雷快艇與日本驅逐艦相撞沉沒後，與另外十名生還者困在小島上時發出的 Playfair 加密訊息。如果日方攔截到它，他們有可能解開它，歷史或許就不同了。

區塊密碼的輸出光是「直覺上看起來隨機」同樣不夠。Playfair 密文看起來隨機，卻有個性質：如果你改變明文對中的一個字母，往往只有一個密文字母會變。

例如用上面的金鑰，rd 加密成 TB，而 rf 加密成 OB、rg 加密成 NB。後果之一是：只要密文夠多、或有幾個可能的字詞，該表（或一個等價的表）就能被重建出來。

對更強的密碼，我們會希望輸入的微小改變能完全擴散到輸出：改變一個輸入位元，平均應造成一半的輸出位元改變。

區塊密碼的安全性也能靠選擇更長的區塊長度大幅改善。DES 的區塊長度是 64 位元，AES 則是它的兩倍。

如果銀行帳號總是出現在交易中的同一位置，那麼每次用同一把金鑰加密涉及它的交易，很可能都產生相同密文。這可能讓對手剪貼兩份不同密文的片段，產生一筆有效但未經授權的交易。

假設一名在銀行電信商工作的騙子監看到一筆他知道內容是「支付 IBM 一千萬美元」的加密交易。他可以匯 1000 美元給他兄弟，讓銀行電腦插入另一筆「支付 John Smith 1000 美元」的交易，攔截這道指令，再用兩份密文拼出一道解密為「支付 John Smith 一千萬美元」的假指令。

所以除非密碼區塊與訊息一樣大，密文就會含有多個區塊，我們需要某種方法把區塊綁在一起。

雜湊函數#

第三種古典密碼是雜湊函數。它演化出來是為了保護訊息的完整性與真實性——我們不希望有人能以「造成明文可預測改變」的方式操弄密文。

十九世紀中電報發明後，銀行迅速成為它的主要使用者，並發展出電子轉帳系統。由於電報訊息是由人工操作員從一個局中繼到另一個局，操作員有可能操弄付款訊息。

十九世紀時，銀行、電報公司與航運公司發展出碼本（code books），不只保護交易也縮短它們（考慮到當時國際電報的成本）。碼本本質上是把字詞或片語映射到固定長度字母／數字組的區塊密碼。

如果「1000」的碼字是「mauve」而「1,000,000」的碼字是「magenta」，那麼能把編碼流量與已知交易比對的作弊電報員，應該就能看出這件事並把兩者互換。

關鍵創新是：使用碼本，但藉由把碼組相加成一個稱為「測試金鑰（test key）」的數字，讓編碼變成單向的。（現代密碼學家會描述它為雜湊值或訊息認證碼。）

測試金鑰是我們用於認證之代數函數的歷史範例，其現代後裔包括核武指管所用的認證碼，以及與現代區塊密碼搭配使用的機制。想法都一樣：如果你能用一把獨一無二的金鑰認證每一則訊息，簡單的代數就能給你理想的安全性。

假設你有一則任意長度的訊息 M，想算出 128 位元的認證碼（tag）A，而你要的性質是：除非知道金鑰，否則沒人能找到在同一把金鑰下認證碼也是 A 的另一則訊息 M′，除非靠機率 2^-128 的幸運猜測。

你只要選一個 128 位元質數 p，計算 A = k₁M + k₂ (mod p)，其中金鑰由兩個 128 位元數 k₁ 與 k₂ 組成。

這安全的理由與一次性密碼本相同：給定任何其他訊息 M′，你都能找到另一把金鑰 (k₁′, k₂′) 把 M′ 認證成 A。所以在不知道金鑰的情況下，看到 M 與 A 的對手對偽造有效訊息完全沒有任何有用的資訊。由於金鑰有 256 位元而 tag 只有 128 位元，即使對手有無限計算能力這也成立：他能為每對訊息與 tag 找出 2^128 把可能的金鑰，卻無從在其中選擇。

非對稱原語#

有些現代密碼系統是非對稱的：加密與解密使用不同金鑰。例如現今多數網站有一張含公開金鑰的憑證，人們可以用 TLS 協定用它加密自己的工作階段，而網頁擁有者用對應的私鑰解密流量。

電腦之前也有這樣的例子，最好的大概是郵政系統。你可以把訊息寫上我的地址、投入郵筒，就把私密訊息寄給我了；一旦如此，我就是唯一讀得到它的人。

當然，很多事可能出錯：你可能拿到錯的地址（不論是因為錯誤還是被欺騙）；警察可能取得搜索票拆我的信；信可能被不誠實的郵差偷走；詐騙者可能在我不知情下重導我的郵件；或小偷可能從我家門墊上偷走信。

公開金鑰密碼學也會出類似的錯：假的公鑰可以被插入系統、電腦可以被駭、人可以被脅迫，諸如此類。

另一個非對稱應用是數位簽章：我可以用私有簽章金鑰簽署訊息，然後任何人都能用我的公開簽章驗證金鑰檢查它。同樣地，電腦之前的類比是手寫簽名與封印；而同樣地，新舊做法會出錯的清單也驚人地相似。

安全模型#

安全模型試圖把「一個密碼是好的」這個想法形式化。

1. 完美保密性（perfect secrecy）：給定任何密文，該長度的所有可能明文都同樣可能。類似地，只用一次金鑰的認證方案可以設計成最好的偽造攻擊就是隨機猜測，而其成功機率可以靠選夠長的 tag 壓到任意低。

2. 具體安全性（concrete security）：我們想知道對手實際上要做多少工作。

   撰稿時，現存最強大的對手——燒掉的電力大約等於整個丹麥的比特幣礦工社群——要花大約十分鐘解出一個 68 位元的密碼謎題並挖出新區塊。所以一把 80 位元金鑰要花他們 2^12 倍的時間，約一個月；而現代系統預設的 128 位元金鑰又要再難 2^48 倍。所以即使一千年，靠運氣找到正確金鑰的機率也只有 2^-35，即幾十億分之一。

   一般而言，若一個對手工作時間 t 而破解密碼的機率至多為 ε，我們說系統是 (t, ε)-安全的。

3. 標準模型（standard model）：關於不可區分性（indistinguishability）。這讓我們能推理自己在意的特定性質。

   例如多數密碼系統不隱藏訊息長度，所以我們不能只要求「對手無法區分對應兩則訊息的密文」就定義密碼是安全的；我們必須更明確地要求對手無法區分兩則等長訊息 M₁ 與 M₂。這被形式化為密碼學家與密碼分析者玩一場遊戲，分析者若能找到某個她本不該能以超過可忽略機率區分之物的有效區分器，就算贏。

4. 隨機預言機模型（random oracle model）：不如標準模型一般，但常導出更有效率的構造。若一個密碼原語沒有有效的方式能把它與該類型的隨機函數區分開來，我們就稱它是偽隨機的（pseudorandom）。

   要把隨機預言機視覺化，可以想像一個坐在黑盒子裡的精靈，有一個物理隨機源與某種儲存工具（原書圖 5.9 以骰子與卷軸表示）。精靈接受某種類型的輸入，然後查看卷軸看這個查詢是否曾被回答過：若有，就給出它在那裡找到的答案；若無，就擲骰子隨機產生一個答案，並記錄下來以備日後參考。我們進一步假設頻寬有限——精靈每秒只回答這麼多查詢。

隨機函數＝雜湊函數#

第一種隨機預言機是隨機函數：接受任意長度的輸入字串，輸出固定長度（比方說 n 位元）的字串。相同輸入給出相同輸出，但輸出的集合看起來是隨機的。所以精靈只是有一張輸入與輸出的簡單清單，隨著它工作而穩定成長。

隨機函數是我們對密碼雜湊函數的模型。

雜湊函數最早在 1960 年代被用於電腦系統中的密碼單向加密，今天用途更多。例如若警方扣押你的筆電，標準鑑識工具會計算所有檔案的檢核值，以辨識哪些檔案是已知的（如系統檔）、哪些是新的（如使用者資料）。這些雜湊值在檔案被破壞時會改變，因此能向法庭保證警方沒有竄改證據。

而如果我們想證明自己在某個日期前擁有某份電子文件，可以把它提交給線上時戳服務、或讓它被挖進比特幣區塊鏈。但若文件仍是機密的（例如我們想確立優先權日期的發明），我們就不會上傳整份文件，只上傳訊息雜湊——這是虎克字謎的現代等價物。

三個關鍵性質#

1. 單向性（one-wayness）：給定輸入 x 我們可以輕易算出雜湊值 h(x)，但給定 h(x) 要找到 x（若該輸入尚未已知）非常困難。由於輸出是隨機的，攻擊者反轉隨機函數最好的辦法就是不斷餵入更多輸入直到走運；n 位元輸出平均要 2^(n−1) 次猜測。

   這意味著要把 n 選得夠大，讓對手做不到接近 2^n 次計算。若我們宣稱 SHA256 是偽隨機函數，就是在說：除非你早就知道某個輸入並用它算出那個 256 位元值，否則沒有實用方法找到雜湊成該值的輸入。

2. 輸出完全不洩漏輸入的任何資訊（連部分也不）。所以我們可以把值 x 與秘密金鑰 k 串接、計算 h(x, k)，得到 x 的單向加密。

3. 難以找到碰撞（collisions）：不同訊息 M₁ ≠ M₂ 卻有 h(M₁) = h(M₂)。除非對手能找到捷徑攻擊（那就表示該函數不是偽隨機的），否則找碰撞最好的方式是蒐集一大批訊息 Mᵢ 與對應雜湊 h(Mᵢ)、排序後找配對。若雜湊輸出是 n 位元數（有 2^n 個可能雜湊值），敵人需要計算的雜湊數大約是它的平方根，即 2^(n/2)。

生日定理#

生日定理得名自以下問題：數學老師問一班 30 名學生，其中兩人同一天生日的機率有多大？多數學生直覺認為不太可能，然後老師請學生一個接一個報出生日——一旦叫到第 23 名學生，配對的勝算就超過 50%。因為這讓多數人驚訝，它也被稱為「生日悖論」。

生日定理在 1930 年代首次被用來數魚，所以也叫捕捉－再捕捉統計。假設湖裡有 N 條魚，你抓 m 條、標記後放回；當你第一次抓到已標記的魚時，m 大約應該是 N 的平方根。

直覺理由是：一旦你有 √N 個樣本，每一個都可能與其他任一個配對，所以可能的配對數大約是 √N × √N，也就是 N。

這個定理對安全工程師有許多應用：

假設我們有一個生物辨識系統，兩位隨機選出的受測者被誤認為同一人的機率只有百萬分之一。這不表示我們能把它當作在一所有兩萬名教職員與學生的大學裡可靠的識別手段——因為那裡有將近兩億個可能的配對。

事實上，一旦註冊人數超過一千多人，你就預期會找到第一個碰撞——第一對會被系統誤認為同一人的人。不過拿它來驗證一個聲稱的身分，可能還可以。

有些應用中碰撞搜尋不是問題，例如挑戰－回應協定（攻擊者必須找到剛發出之挑戰的答案，而你可以防止挑戰重複）。在 IFF 系統中，常見設備的回應長度是 48 到 80 位元——你負擔不起更長，因為那會犧牲雷達精度。

但另一些應用中碰撞不可接受：

設計數位簽章系統時，我們通常先把訊息 M 通過密碼雜湊函數，再簽 h(M)。這種應用中，如果能找到 h(M₁) = h(M₂) 但 M₁ ≠ M₂ 的碰撞，那麼黑手黨開的書店網站可能預先算好合適的一對 M₁、M₂，讓你簽下 M₁——「本人在此訂購一本《橡膠戀物癖》第 7 卷，售價 32.95 美元」，然後把簽章連同 M₂ 一起出示——「本人在此以 75,000 美元抵押我的房子，並請將款項匯至百慕達的黑手黨控股公司。」

但如果你只需要確保沒人能為一個既存的、外部給定的雜湊找到第二原像（second preimage），或許可以將就少一點。

隨機產生器＝串流密碼#

第二個基本密碼原語是隨機產生器，也稱為金鑰流產生器或串流密碼。它也是隨機函數，但與雜湊函數相反：輸入短、輸出長。

它可以用來保護備份資料的機密性：去金鑰流產生器輸入一把金鑰，得到一長串隨機位元檔案，與明文資料互斥或得到密文，再送到雲端備份服務。（因為互斥或就是模 2 加法，這也叫加法式串流密碼。）

注意這不保證檔案完整性。如同一次性密碼本的討論，把金鑰流加到明文能保護機密性，卻無法偵測檔案被修改。為此我們可能要對檔案做雜湊並把它存在安全的地方——保護一個雜湊值不被修改，可能比保護整個檔案容易。

金鑰流產生器的真正問題是防止同一段金鑰流被使用超過一次。

隨機排列＝區塊密碼#

第三種原語，也是現代密碼學中最重要的，是區塊密碼——我們把它建模為隨機排列（random permutation）。這裡函數是可逆的，而輸入明文與輸出密文大小固定。

我們可以這樣視覺化：同樣是黑盒子裡有骰子與卷軸的精靈，卷軸左邊是明文欄、右邊是密文欄。

• 加密：精靈在左欄查看是否有紀錄。若無，就擲骰子產生一個適當大小、且尚未出現在右欄的隨機密文，然後把明文／密文對寫進卷軸；若有，就給出右欄對應的密文。
• 解密：反過來做。

直覺是：密碼機在給定明文與金鑰時應輸出密文、給定密文與金鑰時應輸出明文，但只給明文與密文時它應該什麼也不輸出。此外，沒有人應該能推論出關於它尚未產生之明文或密文的任何資訊。

隨機排列模型也讓我們能定義對區塊密碼的不同攻擊類型：

而攻擊者的目標可能是推出他尚未提過之查詢的答案（偽造攻擊），或回復金鑰（金鑰回復攻擊）。

例如針對 DES 演算法宣布的第一個重大攻擊（差分密碼分析）需要 2^47 個選擇明文才能回復金鑰，而下一個重大攻擊（線性密碼分析）改善到 2^43 個已知明文。雖然這些攻擊有巨大的科學重要性，其實際工程效果是零——沒有實用系統會把那麼多已知文本（更別說選擇文本）交給攻擊者。

這類不實用的攻擊常被稱為**認證性（certificational）**攻擊，因為它們影響的是密碼的安全認證而非提供實用的攻擊途徑。但它們仍可能有商業效果：對 DES 的攻擊削弱了信心，開始把人們推向其他密碼。

公開金鑰加密與陷門單向排列#

公開金鑰加密演算法是一種特殊的區塊密碼：精靈會為任何提出請求的人執行對應某把特定金鑰的加密，但只為金鑰的擁有者執行解密操作。

延續我們的比喻：使用者可以給卷軸取一個只有她與精靈知道的秘密名稱，用精靈的公開單向函數算出這個秘密名稱的雜湊，把雜湊公布出來，並指示精靈為任何引用該雜湊的人執行加密操作。

這意味著 Alice 可以公布一把金鑰，而 Bob 想要的話現在就能加密訊息寄給她——即使他們素未謀面。唯一必要的是他們都能存取那個預言機。

最簡單的變體是陷門單向排列（trapdoor one-way permutation）：任何人都能執行、但只有知道陷門（例如秘密金鑰）的人才能反轉的運算。形式上，公開金鑰加密原語由一個函數構成，給定隨機輸入 R 會回傳兩把金鑰 KR（公開加密金鑰）與 KR⁻¹（私有解密金鑰），並具備以下性質：

1. 給定 KR，計算 KR⁻¹ 是不可行的（所以也不可能算出 R）；
2. 存在加密函數 { … }，對訊息 M 用加密金鑰 KR 產生密文 C = {M}KR；
3. 存在解密函數，對密文 C 用解密金鑰 KR⁻¹ 產生原訊息 M。

在多數真實系統中，加密是隨機化的，所以每次用同一把公鑰加密同一則訊息，答案都不同。

這對語意安全是必要的，否則對手就能檢查對某個密文的明文猜測是否正確。

數位簽章#

最後一個密碼原語是數位簽章。基本想法是：一則訊息上的簽章只能由一個主體產生，卻能被任何人檢查。應用包括簽署軟體更新，讓 PC 能分辨 Windows 的更新是真的由微軟產出，而非某個外國情報機關。

簽章方案也可以是確定性或隨機化的：

• 確定性：對某則訊息計算簽章總是給出相同結果。
• 隨機化：每次給出不同結果。（後者更像手寫簽名：沒有兩個完全一樣，但銀行有辦法判定某個樣本是真是偽。）

簽章方案也可能支援或不支援訊息回復（message recovery）：若支援，則給定簽章任何人都能回復產生它的訊息；若不支援，驗證者就必須先知道或猜出訊息才能驗證。

形式上，簽章方案有一個金鑰對產生函數，給定隨機輸入 R 回傳 σR（私有簽章金鑰）與 VR（公開簽章驗證金鑰）：

1. 給定 VR，計算 σR 不可行；
2. 存在數位簽章函數，給定訊息 M 與 σR 產生簽章 Sig_σR{M}；
3. 存在驗證函數，給定 Sig_σR{M} 與 VR，若簽章是用 σR 正確計算的則輸出 TRUE，否則輸出 FALSE。

一個使用訊息回復的應用是機器印製的郵資戳（indicia）：郵戳由一個二維條碼構成，含郵資機做的數位簽章，並包含面額、日期、寄件與收件郵遞區號等資訊。

在一般情況下我們不需要訊息回復；待簽訊息可能任意長，所以先把它通過雜湊函數再簽雜湊值。我們需要該雜湊函數不只單向，還要抗碰撞。

對稱式密碼演算法#

SP 網路#

向農在 1940 年代提出：反覆結合替換與換位可以建造出強密碼。他把密碼的性質描述為混淆（confusion）與擴散（diffusion）——加入未知的金鑰值會讓攻擊者對明文符號的值感到混淆，而擴散意味著把明文資訊散佈到整個密文中。

最早的區塊密碼是結合替換與排列電路的簡單網路，因此稱為 SP 網路。原書圖 5.10 顯示一個有 16 個輸入、兩層 4 位元可逆替換盒（S-box）的 SP 網路，每個 S-box 可視為含有 0 到 15 某種排列的查表。

要讓這種設計安全，三件事必須做到：

1. 密碼必須夠「寬」
2. 必須有足夠的輪數
3. S-box 必須適當選擇

一、區塊大小#

只作用於 16 位元區塊的區塊密碼相當受限，因為對手可以在觀察到明文與密文區塊時直接建字典。

所以實用的區塊密碼通常處理 64 位元、128 位元甚至更多的明文與密文。若使用 4 位元到 4 位元的 S-box，我們可能有 16 個（64 位元區塊）或 32 個（128 位元區塊）。

二、輪數#

原書圖 5.10 的兩輪完全不夠，因為對手可以用合適的模式撥動輸入位元來推出 S-box 的值。

例如他可以固定最右邊 12 個位元、撥動最左邊 4 個，來推出左上角 S-box 的值。（實際攻擊稍微複雜些，因為有時撥動 S-box 的一個輸入位元不會使任何輸出位元改變，這時我們必須改變它的另一個輸入再撥一次。但這仍是基本的學生習題。）

需要的輪數取決於資料擴散通過密碼的速度。在簡單例子中，擴散非常慢，因為一輪 S-box 的每個輸出位元只連到下一輪的一個輸入位元。

與其只做導線的簡單排列，更有效率的做法是用線性變換：讓一輪中的每個輸入位元都是前一輪數個輸出位元的互斥或。若區塊密碼要同時用於加密與解密，這個線性變換必須是可逆的。

三、S-box 的選擇與兩大密碼分析法#

S-box 的設計也影響安全所需的輪數，而研究糟糕的選擇正是我們進入區塊密碼深層理論的入口。

假設 S-box 是把輸入 (0,1,2,…,15) 映射到輸出 (5,7,0,2,4,3,1,6,8,10,15,12,9,11,14,13) 的排列。那麼輸入的最高有效位元會原封不動地通過，成為輸出的最高有效位元。若同一個 S-box 用在上述密碼的兩輪，輸入的最高有效位元就會一路通到輸出的最高有效位元——我們當然不能宣稱這個密碼是偽隨機的。

線性密碼分析（linear cryptanalysis）：

真實區塊密碼上的攻擊通常較難察覺，但用的是同樣的想法。可能 S-box 有「輸入的位元 1 等於輸出的位元 2 加位元 4」這種性質；更常見的是存在以某種機率成立的線性近似。

線性密碼分析的做法是蒐集一批這樣的關係（如「第一個 S-box 輸入的位元 2 加位元 5，等於輸出的位元 1 加位元 8，機率 13/16」），然後尋找把它們黏合成「輸入位元、輸出位元與金鑰位元之間、機率不等於 1/2 的代數關係」的方法。

若我們能找到一個在整個密碼上以機率 p = 0.5 + 1/M 成立的線性關係，那麼依機率論的抽樣定理，我們預期在有大約 M² 個已知文本後開始回復金鑰位元。

若最佳線性關係的 M² 值大於可能的已知文本總數（即輸入輸出為 n 位元寬時的 2^n），我們就認為該密碼對線性密碼分析是安全的。

差分密碼分析（differential cryptanalysis）：

類似，但基於「輸入 S-box 的某個給定改變會造成輸出某個給定改變」的機率。對 8 位元 S-box 的典型觀察可能是：「若我們同時翻轉輸入位元 2、3、7，則以 11/16 的機率，唯一會翻轉的輸出位元是 0 與 1。」

事實上，對任何非線性布林函數，撥動某個輸入位元組合都會使某個輸出位元組合以不等於 1/2 的機率改變。分析程序是檢視所有可能的輸入差異樣式，尋找「輸入改變 δᵢ 會以特別高（或低）機率產生輸出改變 δₒ」的那些值。

還有一個變體叫不可能密碼分析（impossible cryptanalysis）：不找高機率差異，而找不可能發生（或極少發生）的差異。名字很有魅力，但它對許多系統確實可能奏效。（這也許最早用於二戰的布萊切利園——破解德軍 Enigma 的一個關鍵洞見，就是沒有任何字母會被加密成它自己。）

我們可以靠仔細設計每一輪來降低每輪的資訊洩漏、從而降低所需輪數。但複雜的設計在軟體中可能很慢、或在硬體中需要很多閘，所以用簡單的輪、但用更多輪，也許更好；簡單的輪也可能更容易分析。

謹慎的設計者還會用比擋下今日已知攻擊所嚴格需要更多的輪數，以留下安全餘裕——因為攻擊只會越來越好。

AES#

**進階加密標準（AES）**原名 Rijndael，取自其發明者 Vincent Rijmen 與 Joan Daemen。它作用於 128 位元區塊，金鑰長度可為 128、192 或 256 位元，是一個 SP 網路。

• S-box：AES 使用單一個 byte 進 byte 出的 S-box。實作上可視為 256 byte 的查表，但實際上由方程式 S(x) = M(1/x) + b 定義於體 GF(2^8) 上，其中 M 是適當選擇的矩陣、b 是常數。這個構造給出緊緻的差分與線性界限。

• 線性變換：把被加密值的 16 個 byte 排成方陣，做 byte 層級的洗牌與混合。第一步是洗牌——第一列的四個 byte 不動，第二列左移一位、第三列兩位、第四列三位。第二步是行混合——用矩陣乘法混合一行中的四個 byte。

  這個組合的效果是：輸入的改變在僅僅兩輪後就可能影響全部輸出——這種**雪崩效應（avalanche effect）**讓線性與差分攻擊都變得更難。

• 金鑰加入：金鑰材料在線性變換後逐 byte 加入，每輪需要 16 byte 金鑰材料，由使用者提供的金鑰經遞迴關係衍生。

• 輪數：128 位元金鑰用 10 輪、192 位元用 12 輪、256 位元用 14 輪。

這些輪數足以給出實用但非認證性的安全性——這在 AES 競賽時就已預期。第一批金鑰回復攻擊使用稱為 biclique 密碼分析的技術，2009 年被發現；它們只給出非常小的優勢，複雜度現估為 128 位元 AES 的 2^126 與 256 位元 AES 的 2^254.3，相對於暴力搜尋的 2^127 與 2^255。這些攻擊在實務上毫無差別，因為它們需要不可行的大量文本或非常特殊的相關金鑰組合。

Feistel 密碼與 DES#

許多區塊密碼使用更複雜的結構，由 Feistel 及其團隊在 1950 年代末、60 年代初開發 Mark XII IFF 時發明。Feistel 後來轉往 IBM，成立了產出 DES 演算法的研究團隊——該演算法至今仍是支付系統安全的中流砥柱。

Feistel 密碼有梯狀結構（原書圖 5.12）：輸入被切成左右兩半。先計算左半的輪函數 f₁，用互斥或與右半結合；接著計算右半的函數 f₂ 與左半結合，依此類推。最後（若輪數為偶數）左右半交換。

讓我們能解密 Feistel 密碼的基本結果——也正是這個設計的整個重點——是：

ψ⁻¹(f₁, f₂, …, f_{2k−1}, f_{2k}) = ψ(f_{2k}, f_{2k−1}, …, f₂, f₁)

換言之，要解密，我們只要以相反順序使用輪函數。

因此輪函數 fᵢ 不必可逆，而 Feistel 結構讓我們能把任何單向函數變成區塊密碼。這意味著我們在選擇兼具良好擴散、混淆性質，又滿足程式碼大小、軟體速度或硬體閘數等其他設計限制的輪函數時，受到的約束較少。

Luby-Rackoff 結果#

Luby 與 Rackoff 在 1988 年證明的關鍵理論結果是：若 fᵢ 是隨機函數，則 ψ(f₁, f₂, f₃) 在選擇明文攻擊下與隨機排列不可區分；這個結果很快被擴展為 ψ(f₁, f₂, f₃, f₄) 在選擇明文／密文攻擊下不可區分——換言之，它是一個偽隨機排列。

用工程語言說：給定一個真正好的輪函數，四輪 Feistel 就夠了。

所以如果我們有一個信得過的雜湊函數，要從它建構區塊密碼很直接：在 Feistel 網路中用四輪帶金鑰的雜湊。

DES 的設計與其金鑰長度問題#

DES 在銀行與其他支付應用中廣泛使用。讓它被廣泛部署的「殺手級應用」是 ATM 網路，並從那裡擴散到預付電表、交通票券等。經典形式的它是 Feistel 密碼，區塊 64 位元、金鑰 56 位元。其輪函數作用於 32 位元半區塊，包含四個操作：

1. 區塊從 32 位元擴展到 48 位元；
2. 48 位元輪金鑰用互斥或混入；
3. 結果通過一排八個 S-box，每個接受 6 位元輸入、提供 4 位元輸出；
4. 輸出的位元依固定樣式排列。

輪金鑰由使用者提供的金鑰衍生，依一個略不規則的樣式，讓每個使用者金鑰位元在十二個不同的輪中被使用。

DES 於 1974 年推出並立即引發爭議。最有力的批評是金鑰太短。

想用暴力（即試遍所有可能金鑰）找出 56 位元金鑰的人，總耗盡時間是 2^56 次加密，平均解出時間是其一半即 2^55 次。Diffie 與 Hellman 在 1977 年主張：可以用一百萬顆晶片、每顆每秒測一百萬把金鑰來建一台 DES 金鑰搜尋機；由於一百萬約為 2^20，這平均要 2^15 秒即九個多小時就能找到金鑰。他們主張這種機器 1977 年可用兩千萬美元造出。發明 DES 的 IBM 反駁說，他們會向美國政府收兩億美元來造這種機器。（事後看來，兩邊都對。）

3DES(k0, k1, k2; M) = DES(k2; DES⁻¹(k1; DES(k0; M)))

DESX(k0, k1, k2; M) = DES(k0; M ⊕ k1) ⊕ k2

操作模式#

一個常見的失敗是密碼函式庫允許、甚至鼓勵開發者使用不恰當的操作模式。 操作模式指定了固定區塊大小的區塊密碼（DES 8 byte、AES 16 byte）如何被擴展以處理任意長度的訊息。

理解這些模式極為重要，好讓你為工作挑對的那個——尤其因為有些常用工具預設提供弱的那個。

不該怎麼用區塊密碼：ECB#

在**電子密碼本（ECB）**模式中，我們只是用區塊密碼加密每一個接續的明文區塊得到密文。這對使用單一區塊的協定（如挑戰－回應與某些金鑰管理任務）是足夠的，也被用來在提款機系統中加密 PIN。

原書圖 5.14 顯示一張卡通圖片用 DES ECB 模式加密後的樣子：重複的明文區塊全部加密成相同的密文，讓圖像仍然清晰可辨。（那是知名的 Linux 企鵝圖。）

CBC：密碼區塊鏈結#

多數加密超過一個區塊的商業應用過去使用**密碼區塊鏈結（CBC）**模式：加密前把前一個密文區塊與當前明文區塊互斥或。

這個模式掩蓋了明文中的樣式：每個區塊的加密都取決於所有之前的區塊。輸入的初始化向量（IV）確保刻板的明文訊息標頭不會因加密成相同密文而洩漏資訊。

更微妙的事情也可能出錯：

系統必須把明文填補（pad）到區塊大小的倍數。若某個伺服器解密訊息、發現填補不正確時把這件事發出訊號——不論是回傳「無效填補」訊息，還是單純回應得比較慢——這就開啟了填補預言機攻擊（padding oracle attack）。

攻擊者一次撥動一個 byte 的輸入密文、觀察錯誤訊息，最後就能解密整則訊息。這由 Serge Vaudenay 在 2002 年發現，其變體晚至 2016 年仍被用來攻擊 SSL、IPSEC 與 TLS。

計數器模式加密#

回饋式的區塊密碼加密模式正在退流行，不只因為密碼學上的問題，也因為它們難以平行化。使用 CBC 時，每個區塊輸入與每個區塊輸出之間必須計算完整一輪密碼，這對保護骨幹鏈路流量這類高速應用很不方便。

既然矽很便宜，我們寧願把加密晶片管線化，讓它在盡可能少的時脈週期內加密新區塊（或產生新區塊的金鑰流）。

最簡單的解法是把 AES 當串流密碼用：從初始化向量開始加密一個計數器來產生金鑰流：Kᵢ = {IV + i}K，把金鑰 K 擴展成長串的金鑰流區塊 Kᵢ，再典型地用互斥或與訊息區塊結合：Cᵢ = Mᵢ ⊕ Kᵢ。

加法式串流密碼有兩個系統性漏洞：

1. 深度攻擊（attack in depth）：若同一段金鑰流被用兩次，兩份密文的互斥或就是兩份明文的互斥或，往往能從中推出明文（如 Venona）。
2. 無法保護訊息完整性。

假設用串流密碼加密資金轉帳訊息。這類訊息高度結構化；你可能知道位元組 37–42 含轉帳金額。你可以（例如用 SS7 漏洞）讓某家分行的資料流量經過你的電腦，然後走進銀行匯 500 美元給共犯。密文 Cᵢ = Mᵢ ⊕ Kᵢ 抵達你的機器；你知道位元組 37–42 的 Mᵢ，所以可以回復 Kᵢ 並構造一則修改過的訊息，指示收款銀行支付的不是 500 美元而是 500,000 美元！

處理這件事的通常做法是加上認證碼，最常見的標準使用伽羅瓦計數器模式（GCM）。

訊息認證碼（MAC）#

區塊密碼另一個官方操作模式不是用來加密資料，而是保護其完整性與真實性：訊息認證碼（MAC）。

用區塊密碼對訊息計算 MAC 的做法是：用 CBC 模式加密它，然後丟掉除了最後一個以外的所有輸出密文區塊；最後這個區塊就是 MAC。（中間結果保密以防剪貼攻擊。）

這個構造讓 MAC 取決於所有明文區塊以及金鑰。只要訊息長度固定，它就是安全的——Bellare、Kilian 與 Rogaway 證明了在這些情況下對 MAC 的任何攻擊都會給出對底層區塊密碼的攻擊。

若訊息長度可變，你必須確保對某個字串算出的 MAC 不能被當作計算另一個字串之 MAC 的 IV，否則對手就能靠取得兩字串串接後的 MAC 來作弊。為了修正這個問題，NIST 標準化了 CMAC，在最後一次加密前把金鑰的一個變體互斥或進去。

MAC 還有其他可能的構造，最常見的是 HMAC——用帶金鑰的雜湊函數。

伽羅瓦計數器模式（GCM）#

上述模式都是 1970、80 年代為 DES 開發的。它們對「同時需要保護完整性與機密性的大量加密」並不有效率：若你用 CBC 或計數器模式加密資料，再用 CBC-MAC 或 CMAC 保護完整性，那你對每個處理的資料區塊都要呼叫兩次區塊密碼，而且無法平行化。

它每個文本區塊只呼叫一次區塊密碼，而且可平行化，因此能在快速資料鏈路上以低成本、低延遲取得高吞吐量。

• 加密以計數器模式的變體進行；
• 產生的密文同時被用作某個多項式的係數，該多項式在一個 2^128 元素的伽羅瓦體上、於一個取決於金鑰的點求值，得到認證 tag；
• tag 的計算是前述那種通用雜湊函數，只要金鑰永不重用就是可證明安全的。
• 提供的金鑰與一個隨機 IV 一起用來產生獨一無二的訊息金鑰與認證金鑰。輸出因此是與明文等長的密文，加上通常各 128 位元的 IV 與 tag。

GCM 還有個有趣的增量性質：新的認證碼與密文可以用與「被改變之位元數」成正比的工作量算出。

它是大量內容認證加密的合理預設值。（另有一個較早的複合模式 CCM，用於藍牙 4.0 之後——它結合計數器模式與 CBC-MAC，所以計算成本約兩倍，且無法平行化或增量重算。）

XTS#

GCM 與其他認證加密模式會加入訊息金鑰與認證 tag，因而擴展明文。這在硬碟加密這類我們偏好保持明文長度的應用中很不方便。

磁碟加密系統過去用 CBC 加上磁區編號當 IV，但自 Windows 10 起，微軟改用受 GCM 啟發、2007 年標準化的新模式 XTS-AES。

這是一個密碼本模式，但明文被一把從磁碟磁區衍生的**調校金鑰（tweak key）**漂白。形式上，在區塊 j 用金鑰 K 加密的訊息 Mᵢ 是：

AESX(KTj, K, KTj; M)

其中調校金鑰 KTj 由用另一把金鑰加密 IV、再反覆與適當常數相乘而得，以便為每個區塊給出不同的漂白值。

這意味著若攻擊者交換兩個加密區塊，全部 256 個位元都會解密成隨機的錯誤值。你仍需要更高層的機制來偵測密文操弄，但簡單的檢核值就足夠了。

雜湊函數的建構與應用#

前面說過 Luby-Rackoff 定理讓我們能從雜湊函數建構區塊密碼；反過來也可以從區塊密碼建構雜湊函數。訣竅是把訊息區塊一次一個餵給區塊密碼的金鑰輸入，用它更新一個雜湊值（起始為 H₀ = 0）。為了讓這個操作不可逆，我們加上前饋（feedforward）：第 (i−1) 個雜湊值與第 i 輪的輸出互斥或。這個 Davies-Meyer 構造給出區塊密碼的最後一個操作模式（原書圖 5.16）。

所以 64 位元區塊密碼不夠——偽造一則訊息只要 2^32 則訊息的量級，太容易了。

常見雜湊函數與它們的淪陷#

1990 與 2000 年代最常用的雜湊函數，演化自一個金鑰 512 位元、區塊大小從 128 增至 512 位元的區塊密碼。前兩個由 Ron Rivest 設計，其餘由 NSA 設計：

• MD5 被王小雲（Xiaoyun Wang）與同僚在 2004 年攻破；碰撞現在可以輕易找到，甚至能在含有有意義文字、且符合數位憑證等訊息格式的字串之間找到。
• 王小雲隔年與 Yiqun Lisa Yin、Hongbo Yu 合作，提出只需 2^69 步找到 SHA-1 碰撞的演算法，嚴重打擊了 SHA-1；現在約需 2^60 次計算。
• 2017 年 2 月，阿姆斯特丹與 Google 的科學家發表了這樣一個碰撞，以證明論點並協助說服人們轉向更強的雜湊函數。
• 2020 年，Leurent 與 Peyrin 開發出改良攻擊，能計算選定前綴碰撞，使憑證偽造的成本降到數萬美元等級。

2007 年 NIST 舉辦競賽尋找替代的雜湊函數族。優勝者 Keccak 有相當不同的內部結構，2015 年被標準化為 SHA-3。所以我們現在有 SHA-2 與 SHA-3 兩個標準雜湊函數的選擇。

雜湊函數的其他應用#

• HMAC：計算 MAC 的公認做法。天真的方法是 MACk(M) = h(k, M)，但公認做法多一個步驟——把這個計算的結果再雜湊一次，且兩次雜湊使用金鑰的變體（分別與兩個不同常數互斥或）：

  HMACk(M) = h(k ⊕ B, h(k ⊕ A, M))

  A 是把位元組 0x36 重複所需次數構成，B 同樣由 0x5C 構成。若雜湊函數偏弱，這個構造能讓可利用的碰撞更難找。 HMAC 現在是 FIPS 198-1。

• 承諾（commitments）：稍後才揭露。例如我想為某份數位文件加時戳以確立智慧財產優先權，但還不想揭露內容。我可以公布文件的雜湊、或送給商業時戳服務、或讓它被挖進比特幣區塊鏈。產生碰撞對的演算法破壞不了這件事，因為你做時戳時就得手上有那一對。

• Merkle 樹：把大量輸入雜湊成單一輸出。輸入被雜湊成樹的葉節點值；每個非葉節點含其所有子節點雜湊的雜湊，所以根的雜湊就是所有葉值的雜湊。

  這是雜湊大型資料結構的快速方法，用於程式碼簽章（你可能不想等到應用程式所有檔案都檢查完簽章才開啟它）。它也在區塊鏈應用中廣泛使用——事實上，區塊鏈就是一棵 Merkle 樹。

  它由 Ralph Merkle 發明，最初是為了計算一大批公鑰檔案的短雜湊，特別針對公鑰只用一次的系統。例如 Lamport 數位簽章可以從雜湊函數建構：你建立一把由 512 個隨機 256 位元值 kᵢ 構成的私鑰，並把它們的 Merkle 樹雜湊公布為驗證金鑰 V。然後要簽 h = SHA256(M) 時，若 h 的第 i 個位元為 0 就揭露 k₂ᵢ，否則揭露 k₂ᵢ₊₁。只要雜湊函數安全這就安全，但缺點是每把金鑰只能用一次。

• 金鑰更新（key updating）與自動金鑰（autokeying）：

  • 金鑰更新：共享金鑰的兩個或更多主體在約定時間把它通過單向雜湊函數：Kᵢ = h(Kᵢ₋₁)。重點是若攻擊者攻陷其中一個系統並竊得金鑰，他只拿到當前金鑰，無法解密過去的流量。這個性質稱為向後安全（backward security）。
  • 自動金鑰：主體用「金鑰與上次換金鑰以來交換過的訊息」一起雜湊來更新金鑰：Kᵢ₊₁ = h(Kᵢ, Mᵢ₁, Mᵢ₂, …)。若攻擊者攻陷其中一個系統竊得金鑰，那麼一旦雙方交換一則他無法觀察或猜測的訊息，安全性就恢復了。這個性質稱為前向安全（forward security），最早用於澳洲的銀行 EFT 支付終端機。

非對稱密碼原語#

非對稱密碼學（公開金鑰加密與數位簽章）常用的建構區塊都基於數論。基本想法是讓密碼的安全性取決於一個已知很難的數學問題——難的意思是很多人努力嘗試過而失敗。幾乎所有真實系統使用的兩個問題是因數分解與離散對數。

基於因數分解的密碼學#

質數是沒有真因數的正整數。算術基本定理說：每個大於 1 的自然數都能分解成質數，且在因數順序上唯一。

2020 年被分解的最大「兩個大隨機質數之積」是 RSA-250，一個 829 位元（250 個十進位數字）的數。這相當於單一 2.2GHz 核心 2,700 年的工作量；先前 2019 年的紀錄 RSA-240 花了相當於 900 年。

因數分解也可能被偷偷地進行（也許用殭屍網路）：2001 年當時最先進的水準是分解 512 位元數，Simon Singh 的《碼書》中出了這樣一道挑戰，被五名瑞典學生用他們能取用的數百台電腦解開。

至於 1024 位元數，作者預期 NSA 已經能分解了。想讓金鑰維持多年安全的組織，現在至少該用 2048 位元的數。

RSA#

用於基於因數分解之公開金鑰加密與數位簽章的常用演算法是 RSA，以發明者 Rivest、Shamir 與 Adleman 命名。它使用費馬小定理：對所有不整除 a 的質數 p，a^(p−1) ≡ 1 (mod p)。對一般整數 n，a^φ(n) ≡ 1 (mod n)，其中歐拉函數 φ(n) 是小於 n 且與它互質的正整數個數。所以若 n 是兩質數 pq 之積，則 φ(n) = (p−1)(q−1)。

在 RSA 中：

• 加密金鑰是一個難以分解的模數 N（取 N = pq，p、q 為隨機選取的大質數，比方說各 1024 位元），加上一個與 p−1 及 q−1 都沒有共同因數的公開指數 e。
• 私鑰是保密的因數 p 與 q。
• 加密：C ≡ M^e (mod N)
• 解密：知道私鑰的人可以找到 d 使得 de ≡ 1 (mod φ(N))，於是計算 M ≡ C^d (mod N)。

私鑰擁有者同樣可以對訊息運算產生簽章 Sig_d(M) ≡ M^d (mod N)，而此簽章可藉由對它取 e 次方 mod N 並檢查是否回復訊息 M 來驗證。

原因是加密是代數過程，會保留某些代數性質。例如若明文之間有 M₁M₂ = M₃ 這樣的關係，那麼密文之間也會有 C₁C₂ = C₃、簽章之間也會有 Sig₁Sig₂ = Sig₃。這個性質稱為乘法同態（multiplicative homomorphism）。

裸 RSA 的同態性質意味著它不符合隨機預言機模型對公開金鑰加密或簽章的定義。

公開金鑰加密還有另一個一般性問題：若明文取自一個小集合（例如「進攻」或「撤退」），而加密過程是確定性的（RSA 就是），那麼攻擊者可以直接預先算出可能的密文，等它們出現時認出來。

要擋掉猜測攻擊、低指數攻擊與基於同態的攻擊，明智的做法是在加密明文區塊前加入一些隨機性與一些冗餘。

每次我們加密同一則短訊息（如「進攻」），都想得到完全不同的密文，而且它們彼此之間、以及與「撤退」的密文之間都無法區分。而做這件事有好方法也有壞方法。

實務上的通常解法是最佳非對稱加密填補（OAEP）：把訊息 M 與隨機 nonce N 串接，用雜湊函數 h 結合它們：

C1 = M ⊕ h(N)
C2 = N ⊕ h(C1)

這實際上是一個以 h 為輪函數的兩輪 Feistel 密碼。結果 C1、C2 的組合再用 RSA 加密送出，接收者計算 N = C2 ⊕ h(C1) 並回復 M = C1 ⊕ h(N)。這最終被證明是安全的。

這擋掉了 20 世紀發現的一大批攻擊，例如「對手能偵測你是否用兩把不同 RSA 金鑰加密了同一則訊息」。事實上 1990 年代我們學到的一件事是：隨機化有助於讓密碼協定對各式各樣的攻擊更穩健，不只是數學攻擊——旁通道攻擊甚至對裝置的物理探測都要多花很多工夫。

基於離散對數的密碼學#

雖然 RSA 是第一個部署在 SSL 與 SSH 協定中的公開金鑰加密演算法，現在最流行的公鑰演算法是基於離散對數的。有幾種風味，有些用一般模數算術，有些用橢圓曲線。

**模 p 的原根（primitive root）**是其冪次能生成所有非零模 p 數的數。例如模 7 運算時：

5^1 = 5   (mod 7)
5^2 = 25 ≡ 4   (mod 7)
5^3 ≡ 4×5 ≡ 6  (mod 7)
5^4 ≡ 6×5 ≡ 2  (mod 7)
5^5 ≡ 2×5 ≡ 3  (mod 7)
5^6 ≡ 3×5 ≡ 1  (mod 7)

所以 5 是模 7 的原根。這意味著給定任何 y，我們總能解方程 y = 5^x (mod 7)；x 就稱為 y 模 7 的離散對數。

小例子可以靠檢視解出，但對一個大的隨機質數 p，我們不知道怎麼有效率地做這件事。

所以映射 f: x → g^x (mod p) 是一個單向函數，並具備 f(x+y) = f(x)f(y) 與 f(nx) = f(x)^n 的額外性質。換言之，它是一個單向同態——因此可以用來建構數位簽章與公開金鑰加密演算法。

Diffie-Hellman 金鑰建立#

第一個公開發表的公開金鑰加密方案，由 Diffie 與 Hellman 於 1976 年提出，使用固定的原根 g，並把 g^(xA·xB) 模 p 當作共享金鑰加密系統的金鑰。

A → B :  g^RA (mod p)
B → A :  g^RB (mod p)
A → B :  {M} g^(RA·RB)

質數 p 與生成元 g 是所有使用者共有的。Alice 選隨機數 RA、算出 g^RA 送給 Bob；Bob 同樣選 RB 送 g^RB；兩人接著都形成 g^(RA·RB)，用作工作階段金鑰。

如果他們用的是**暫時金鑰（transient keys）**而非長期金鑰，他們就成功地「無中生有」創造出一個共享秘密。

即使對手在這個協定開始前就檢查過他們兩人的機器、知道所有儲存的私鑰，只要滿足一些基本條件（例如亂數產生器不可預測、沒有留下惡意程式），對手仍然無法竊聽他們的流量。這是前向安全的強版本：對手無法從已知的舊金鑰往前推。

而只要 Alice 與 Bob 用完後都銷毀共享秘密，他們也會有向後安全：日後取得他們設備的對手無法往回破解舊流量。

回到掛鎖協定：假設凱撒直接命令奴隸把盒子帶給他，在安東尼的鎖旁邊扣上自己的鎖。奴隸把盒子帶回安東尼，安東尼取下自己的鎖，盒子回到凱撒手中，凱撒就打開了它。凱撒甚至可以跑兩份協定實例，對安東尼假裝自己是布魯圖斯、對布魯圖斯假裝自己是安東尼。

在 Diffie-Hellman 中，同樣的想法導致中間人攻擊：Charlie 攔截 Alice 給 Bob 的訊息並回覆；同時他假裝是 Alice 與 Bob 發起金鑰交換。他最後有一把與 Alice 共享的金鑰 DH(RA, RC)，以及一把與 Bob 共享的 DH(RB, RC)。只要他繼續坐在網路中間翻譯兩人之間的訊息，他們可能很難察覺通訊已被攻陷。

通常的解法是認證暫時金鑰，有多種可能：

如果你在實作公開金鑰密碼學，你必須參考最新標準、使用經正式認可的工具包，並找懂行的人評估你做了什麼。

而且請不要自己寫實際的密碼程式碼——把它做好需要一大堆不同技能，從計算數論到旁通道分析與形式方法。即使使用好的密碼函式庫，你也還有很多機會把自己的腳射穿。

ElGamal 簽章與 DSA#

假設底數 p 與生成元 g 是以某種合適方式選定的公開值，每個想簽訊息的使用者有一把私有簽章金鑰 X 與公開簽章驗證金鑰 Y = g^X。

ElGamal 簽章方案：隨機選一把訊息金鑰 k，形成 r = g^k (mod p)。然後用 k、r、訊息 M 與私鑰 X 的線性方程形成簽章 s。ElGamal 簽章用的方程是：

rX + sk = M

所以 s 算成 s = (M − rX)/k，這是模 φ(p) 做的。兩邊都通過單向同態 f(x) = g^x mod p 後得到 Y^r · r^s ≡ g^M。ElGamal 對訊息 M 的簽章由 r 與 s 構成，接收者可用上式驗證。

實際的數位簽章方案還需要補幾個細節：糟糕的 p 與 g 選擇會削弱演算法；我們也會想先用雜湊函數雜湊訊息 M，好能簽任意長度的訊息，並防止對手利用演算法的代數結構在從未被簽的訊息上偽造簽章。處理好這些細節並做一兩項最佳化後，就得到美國標準、在政府應用中廣泛使用的數位簽章演算法（DSA）。

DSA 假設一個典型 2048 位元的質數 p、一個整除 (p−1) 的 256 位元質數 q、模 p 整數中階為 q 的元素 g、秘密簽章金鑰 x 與公開驗證金鑰 y = g^x。對訊息 M 的簽章 Sig_x(M) 是 (r, s)：

r ≡ (g^k (mod p)) (mod q)
s ≡ (h(M) − xr)/k (mod q)

預設使用的雜湊函數是 SHA256。

p 與 q 的預設大小之所以選成 2048 與 256 位元，是為了讓兩個已知最佳密碼分析攻擊的工作因子相等：**數體篩法（number field sieve）**的速度取決於 p 的大小，而 Pollard’s rho 取決於 q 的大小。

DSA 是「無訊息回復之隨機化數位簽章方案」的經典例子。 現今最常用的版本是基於橢圓曲線的變體 ECDSA——它是加密貨幣的標準，也日益成為銀行智慧卡憑證的標準。

橢圓曲線密碼學#

離散對數及其類比存在於許多其他數學結構中。橢圓曲線密碼學使用橢圓曲線上的離散對數——曲線由 y² = x³ + ax + b 這樣的方程給出。這些曲線的性質是你可以在其上定義加法運算，而產生的 Mordell 群可用於密碼學。

橢圓曲線密碼系統至少因兩個理由而有趣：

1. 效能：它們給出 Diffie-Hellman 金鑰交換與 DSA 這類熟悉原語的版本，使用較少計算、變數也較短——這在受限環境中都是好事。橢圓曲線密碼學被用於從最新版 EMV 支付卡到比特幣的各種應用。
2. 雙線性配對（bilinear pairing）：某些橢圓曲線具備它，Boneh 與 Franklin 用它建構出「你的公鑰就是你的名字」的密碼系統。

回想在 RSA 與 Diffie-Hellman 中，使用者選擇自己的私鑰再算出對應的公鑰。在所謂的**身分基密碼系統（identity-based cryptosystem）**中，你選擇自己的身分，然後去中央機構取得對應該身分的私鑰。有一把全域公鑰，任何人都能用它加密訊息給你的身分；你用你的私鑰解密它。

更早，Shamir 已發現身分基簽章方案，讓你能用私鑰簽訊息，任何人都能對照你的名字驗證簽章。兩種情況下，你的私鑰都是由中央機構用只有它自己知道的系統級私鑰算出的。

身分基原語只被用在少數專門系統中：Zcash 的支付隱私機制，以及英國政府一個叫 Mikey-Sakke 的金鑰管理協定。

從人們的郵件地址或其他識別符算出他們的私鑰，看起來像個俐落的技巧，但當政府部門重組或改名時，代價可能很高。

多數組織與應用使用帶有公鑰認證的普通公開金鑰系統。

憑證機構#

現在我們能做公開金鑰加密與數位簽章了，我們需要某種機制把使用者與金鑰綁定。

Diffie 與 Hellman 發明數位簽章時提出的做法，是有一本像電話簿一樣的系統授權使用者公鑰目錄。更常見的解法（歸功於 Loren Kohnfelder）是由憑證機構（CA）簽署使用者的公開加密金鑰或簽章驗證金鑰，給出含使用者名稱、一或多把公鑰、以及授權等屬性的憑證。

憑證可以符號化描述為：

CA = Sig_KS (TS, L, A, KA, VA)

其中 TS 是憑證的起始日期時間、L 是有效期長度、A 是使用者名稱、KA 是她的公開加密金鑰、VA 是她的公開簽章驗證金鑰。

• 命名就很難（見分散式系統那一章）。
• 而且往往名字並不是協定真正要建立的東西——現實世界中它常常關乎授權而非認證。政府系統常關心的不只是使用者的名字或角色，而是他們的安全查核等級；銀行系統關心的是你的餘額、可用信用額度與動用它的權限；商業系統常關心的是把遠端使用者連到角色基存取控制。
• 在面向使用者的系統中，有把盡可能多的合規成本傾倒給客戶的傾向。
• 政治層面：典型瀏覽器中有數百個憑證機構，它們或多或少被同等信任，而許多民族國家能脅迫其中至少一個。（少數不能脅迫的就試圖作弊：2011 年伊朗駭入 CA Diginotar；2019 年哈薩克強迫公民把本國警方憑證加進瀏覽器。兩次瀏覽器廠商都快速強力地反擊——Diginotar 被列入黑名單後倒閉，而哈薩克的憑證即使公民手動安裝也被封鎖。這當然也引出主權問題。）
• 糟糕憑證的撤銷通常很不牢靠，如果它真的有效的話。

TLS#

伺服器可以公布公鑰 KS，任何瀏覽器就能用 KS 加密含信用卡號的訊息 M 送給它：{M}KS。這本質上就是 TLS 協定（當時稱 SSL）在電子商務伊始被設計來做的事。

它由 Paul Kocher 與 Taher ElGamal 於 1995 年開發，支援雙向的加密與認證，讓 http 請求與回應都能防範竊聽與操弄。它就是你在瀏覽器工具列看到掛鎖時被啟動的那個協定。

TLS v1 基本版本的簡化描述：

1. 客戶端送出 client hello，含其名稱 C、交易序號 C# 與隨機 nonce N_C。
2. 伺服器回覆 server hello，含其名稱 S、交易序號 S#、隨機 nonce N_S，以及含其公鑰 KS 的憑證 CS。客戶端現在檢查憑證 CS，必要時檢查簽署它的金鑰（在另一張憑證中），一路回溯到儲存在瀏覽器中、由 Verisign 這類公司簽發的根憑證。
3. 客戶端送出 key exchange 訊息，含用伺服器公鑰 KS 加密的預主秘密金鑰 K₀。它也送出 finished 訊息，含對迄今所有訊息計算的 MAC；該 MAC 的金鑰是主秘密 K₁，由預主秘密與客戶端及伺服器送出的 nonce 一起雜湊而得：K₁ = h(K₀, N_C, N_S)。從這一點開始所有流量都被加密。
4. 伺服器也送出含迄今所有訊息之 MAC 的 finished 訊息，然後才終於開始送資料。

C → S :  C, C#, NC
S → C :  S, S#, NS, CS
C → S :  {K0}KS
C → S :  {finished, MAC(K1, 迄今全部)}KCS
S → C :  {finished, MAC(K1, 迄今全部)}KSC , {data}KSC

一旦客戶端與伺服器建立了預主秘密，就不再需要公鑰運算，因為進一步的主秘密可以靠把它與新 nonce 一起雜湊得到。

TLS 的用途與安全性#

完整協定比這複雜，並經歷了多個版本。它支援過多種密碼套件（ciphersuites），最初是為了讓軟體的出口版本能被限制在 40 位元金鑰——那是美國政府多年來施加的出口許可條件。

這導致降級攻擊（downgrade attacks）——中間人可以強制使用弱金鑰。

其他密碼套件支援針對暫時金鑰的簽署式 Diffie-Hellman 金鑰交換，以提供前向與向後保密。TLS 也有雙向認證的選項。除了加密網頁流量，TLS 自 Windows 2000 起也是 Windows 的認證選項之一——你可以用它取代 Kerberos 在企業網路上做認證。

雖然早期版本的 SSL 有若干臭蟲，SSL 3.0 之後看來是健全的（SSL 3.0 之後的版本被改名為 TLS 1.0）。Larry Paulson 在 1998 年對它做了形式驗證，所以我們知道理想化版本的協定沒有臭蟲。

然而在此後二十多年間，出現了超過十幾次嚴重攻擊。 早在 1998 年 Bleichenbacher 就提出了第一個基於「量測伺服器解密所花時間、或它對精心設計之協定回應所回傳之錯誤訊息」的攻擊。

• TLS 1.1（2006）加入了對 CBC 加密與填補錯誤利用的防護。
• TLS 1.2（兩年後）把雜湊函數升級到 SHA256 並支援認證加密。
• 期間還有一批處理各種浮現攻擊的修補。

這件事的處理方式是大型服務公司改變自家瀏覽器以拒絕過時的密碼套件，並加入**嚴格傳輸安全（STS）**這類功能——網站可以指示瀏覽器未來只用 https 與它互動（以防降級攻擊）。瀏覽器廠商還強制推行了一系列其他配套措施，從縮短憑證壽命到憑證透明化。

TLS 1.3#

最近一次核心協定的大升級 TLS 1.3 在兩年討論後於 2019 年 1 月獲 IETF 批准。它放棄了向後相容性以終止對許多舊密碼的支援，並規定必須在每個工作階段開始時透過 Diffie-Hellman 金鑰交換建立端對端前向保密。

這在銀行業引起爭議，因為銀行例行攔截加密工作階段以進行合規監控。這將不再可能，所以銀行必須承擔「使用過時加密的法律不適」或「重新開發系統以改在端點監控合規」的財務成本。

其他公開金鑰協定#

• 程式碼簽章（code signing）：1990 年代人們開始下載軟體而非用磁片取得時導入，現在被廣泛用來確保軟體的來源。

  你可能以為在軟體中放一把公開簽章驗證金鑰、讓版本 N 能驗證到版本 N+1 的更新，是公開金鑰密碼學的簡單應用——遠非如此。

  許多平台簽署作業系統程式碼（含更新）以防止持久性惡意程式，機制通常涉及 TPM 這類可信硬體。有些平台（如 iPhone）只跑簽署過的程式碼，這不只確保軟體來源，也讓平台擁有者能把 app 貨幣化；遊戲主機類似。由於有些使用者會不擇手段越獄自己的裝置，這類平台通常有可信硬體存放驗證金鑰。若無可信硬體，驗證可能用混淆過的程式碼，讓惡意程式（或客戶）更難竄改它——這是一場持續的軍備競賽。

  至於簽章金鑰，開發者可能把它放在昂貴且會以微妙方式故障的硬體安全模組中；可能有一條回溯到商業 CA 的信任鏈，但那又要擔心政府機關的法律脅迫；你甚至可能為求心安自己實作一個 CA。簡言之，程式碼簽章不像看起來那麼容易，尤其當使用者就是敵人時。

• PGP/GPG：1990 年代「密碼戰爭」期間，網路行動者為加密郵件的權利與政府對抗。密碼行動者 Phil Zimmermann 寫了開源加密產品 PGP，並藉由把原始碼印成紙本書出版（可以郵寄、掃描再編譯）規避美國出口管制。

  PGP 及後來相容的 GPG 在技術宅之間相當普及。系統管理員、電腦緊急應變小組（CERT）與惡意程式研究者用它分享攻擊與漏洞資訊。它也被內建進賣給犯罪集團、支援訊息傳遞的客製化手機中。

  最基本形式下，每位使用者手動產生私鑰／公鑰對並與聯絡人分享公鑰。手動金鑰管理避免了「CA 可能被駭或被脅迫」的需要。

  但正如第 3 章所述，Whitten 與 Tygar 那篇資安可用性的開山論文評估「有動機但密碼學不精的使用者」能否理解 PGP 到足以安全駕馭它：十二名受試者中只有四人能正確地寄出加密郵件給其他受試者，而每一位受試者都至少犯了一個重大錯誤。

• QUIC：Google 設計的新 UDP 協定，被推廣為 TLS 的替代方案，允許更快的工作階段建立、並縮短頁面載入時廣告競價的延遲；工作階段能在人們移動於不同接入點時持續。這靠一個保存客戶端最後 IP 位址、由伺服器加密的 cookie 達成。它 2013 年出現在 Chrome 中，現在約佔網際網路流量的 7%。

  Google 宣稱它把搜尋延遲降低 8%、YouTube 緩衝時間降低 18%。獨立評估顯示好處主要在桌面而非行動裝置，而且有隱私顧慮——伺服器可以對每個客戶端使用個別的公鑰，並用它來追蹤。

  作為一般原則，應該對企業以專有標準取代開放標準的企圖保持警惕：不論是 1950 年代 IBM 的 EBCDIC 編碼標準與 1970 年代的 SNA、1990 年代起微軟「擁抱並延伸」郵件標準與安全協定的嘗試，還是 Facebook 在非洲推廣的、把使用者大體留在自家圍牆花園內的網際網路接取。

特殊用途原語#

研究者發明了大量具特殊性質的公鑰與簽章原語，其中兩個已出現在真實產品中：

• 門檻密碼學（threshold crypto）：把一把簽章或解密金鑰分給 n 個主體，使得 n 中任 k 個就能簽署（或解密）。k = n 時構造很容易（例如 RSA 可以把私鑰 d 拆成 d = d₁ + d₂ + … + dₙ）；k < n 時稍複雜（但也不難——用拉格朗日插值公式）。

  門檻簽章最早用於「多台伺服器獨立處理交易並獨立對結果投票」的系統；近來被用來在加密貨幣錢包上實作商業規則，例如「一筆付款必須由七位公司董事中任兩位授權」。

• 盲簽章（blind signatures）：在不知道訊息內容的情況下對它簽章。例如用 RSA，我可以取一個隨機數 R，形成 R^e·M (mod n) 交給簽署者，他算出 (R^e·M)^d = R·M^d (mod n)。他把它還我時，我可以除掉 R 得到簽章 M^d。

  盲簽章的用途：數位現金與匿名憑證

  你可能會問，為什麼有人會想在不知道文件內容的情況下簽署它？但確實有些應用。

  第一個是數位現金。 你可能想能夠發行匿名的付款代幣給客戶，而 David Chaum 最早的想法是在不知道序號的情況下簽署「數位硬幣」。銀行可能同意對任何具有唯一序號與指定形式冗餘、並帶有可用公鑰 (e, n) 正確驗證之簽章的字串 M 兌現 10 美元。盲簽章協定確保客戶能讓銀行簽一枚硬幣而銀行不知道其序號，它曾被用於原型道路收費系統。效果是數位現金對付款者可以是匿名的。

  數位現金的主要問題是偵測重複花用同一枚硬幣的人，這最終靠區塊鏈或其他帳本機制解決。

  匿名數位憑證現在被用於證明（attestation）：你 PC 主機板上的 TPM 晶片可以在不識別你的情況下，證明關於你機器上執行之軟體的某件事。

  不幸的是，這導致 SGX（及其 AMD 對應物）中的證明設計，使得一台被攻陷的裝置就會破壞整個生態系。

  匿名簽章也出現在進行電子選舉的原型系統中。

非對稱原語有多強？#

要提供與對稱區塊密碼相同等級的保護，非對稱密碼原語一般至少需要兩倍的區塊長度。

橢圓曲線系統看來達到了這個界限：256 位元的橢圓方案破解難度大約等同於帶 128 位元金鑰的 128 位元區塊密碼；NSA Suite B 軍用演算法中唯一使用的公開金鑰加密方案是 384 位元橢圓曲線系統。

基於因數分解與離散對數的傳統方案，現在需要 3072 位元金鑰才能保護 Top Secret 等級材料，因為有數體篩法這類捷徑攻擊演算法。結果是橢圓曲線密碼系統比較快。

歷史進展：

• 2000 年（第一版）：數體篩法被用來攻擊到 512 位元的金鑰，難度可比擬對 56 位元 DES 金鑰的搜尋。
• 2007 年（第二版）：64 位元對稱金鑰已被暴力破解，663 位元挑戰數 RSA-200 已被分解。
• 2019 年（第三版）：比特幣礦工每十分鐘找到 68 位元雜湊碰撞，RSA-768 已被分解，而史諾登差不多告訴了我們 NSA 能對 1024 位元質數模數做離散對數。

現實中還會出什麼錯#

針對 20 世紀設計之系統的攻擊確實存在，多半涉及因出口管制規則、笨拙設計或兩者而過短的金鑰。前面已談過弱密碼如何促成一波偷車潮；後面章節會舉出密碼戰爭及其出口管制規則如何導致對門鎖、手機與著作權執行的攻擊。

現今多數攻擊利用的是實作。

• 第 2 章提過 NIST 標準化一個基於橢圓曲線、含 NSA 後門的複雜亂數產生器的醜聞。
• 糟糕的亂數產生器導致許多其他失敗：有共同因數的 RSA 金鑰、離散對數可預測的種子等等。這些漏洞持續存在；拜物聯網所賜，你能在網際網路上找到的、與其他 RSA 金鑰共享共同因數的 RSA 憑證比例，在 2012 到 2020 年間實際上是上升的——每 172 張 IoT 憑證中就有 1 張是微不足道地脆弱的。
• 過去 20 年間迫使重大改變的許多實用攻擊，利用的是計時與功耗分析這類旁通道。

小結#

許多密碼失敗是因為被用得很糟，所以安全工程師必須對不同類型的密碼各做什麼有清楚的概念。這可以在不同層次上處理：

• 密碼理論層次：隨機預言機模型、具體模型與語意安全模型，希望藉此避免使用弱的操作模式與其他構造。
• 個別密碼設計層次：AES，或支撐公開金鑰密碼系統與數位簽章機制的數論機制。它們也有各自的專門數學領域——區塊密碼密碼分析與計算數論。
• 實作糟糕的層次：這一層難處理得多也髒亂得多。它涉及計時、錯誤處理、耗電量與各種其他齷齪細節，而這正是現代密碼系統在實務上崩壞的地方。

除非你真的理解自己在做什麼，否則永遠不要使用 ECB 模式。

不要設計自己的協定、不要設計自己的密碼；除非萬不得已，也不要自己寫密碼程式碼。如果你非做不可，那麼你不只要讀這本書（然後再仔細讀一遍），還要讀相關的專門材料、與專家交談，並讓有能力又有動機的人去試著攻破它。至少，你需要讓自己的工作接受同儕檢視。

設計密碼有點像玩電鋸雜耍——犯下致命錯誤實在太容易了。

研究問題#

密碼學研究有許多活躍的線索，許多是密碼學與某個數學分支（數論、代數幾何、複雜度理論、組合學、圖論、資訊理論）交會之處。經驗性的一端關注設計加密、簽章與複合操作的原語，並讓它們在可用平台上有合理效能。兩端在密碼分析、以及「尋找兼具可證明安全性質與良好效能之原語」的研究中相遇。

要感受理論端正在發生什麼，最好的方式是讀最近幾年 Crypto、Eurocrypt 與 Asiacrypt 等研究會議的論文集；密碼設計的工作出現在 Fast Software Encryption；對實作的攻擊常出現在 CHES；而對「密碼如何在系統中被使用」的攻擊，可以在 IEEE Security and Privacy、CCS 與 Usenix 等系統安全會議中找到。