課程資訊

L3.2cmL11.6cm 課程 & 6CCS3CIS Cryptography（King’s College London，2025/26）
講師 & Ngoc Khanh Nguyen、Eamonn W. Postlethwaite
本週講義 & Third lecture（2025 年 10 月 9 日，104 張投影片含逐步顯示，實際內容 30 頁）
本週習題 & Problem Set 3（Eamonn W. Postlethwaite，三大題共 16 小題，其中 Problem 3 含三段待破譯的電影台詞密文）
課本 & Katz & Lindell, Introduction to Modern Cryptography, 3rd ed.（簡稱 KL-IMC）
本週對應章節 & KL-IMC §1.3（歷史密碼與其破譯）、第 2 章（完美保密：§2.1 定義、§2.2 一次性密碼本、§2.3 限制、§2.4 Shannon 定理）

本週在整門課的位置

前兩週建立了語言：SKE 的語法與正確性（Week 1–2）、Kerckhoffs 原則、以及用遊戲寫成的安全定義 IND-EAV／IND-CPA／IND-CCA（Week 2）。 第三週第一次把這套語言用在具體的方案上：

  • 先補足數學工具——模算術（\(\Zn{n}\)）與它在 \(n=26\)（字母）和 \(n=2\)（位元，\(\oplus\)）的兩個特例；

  • 把三個歷史密碼（Caesar、單字母替換、Vigenère）寫成正式的 \((\KGen,\Enc,\Dec)\)，並逐一指出它們在 Week 2 的定義下為何立刻不安全——不需要任何「聰明的」破譯；

  • 介紹真正的破譯方法（暴力搜尋、頻率分析、Kasiski／重合指數、trace），這些方法在歷史上花了幾百年才出現，但今天只是「額外的羞辱」；

  • 反思「發現漏洞 \(\to\) 加複雜度 \(\to\) 再被破」的無原則循環，引出現代密碼學「假設 \(\Rightarrow\) 定義」的證明式思維；

  • 最後給出一個真正安全的方案：一次性密碼本（one time pad）與 Shannon 的完美保密，並說明它為什麼「不能讓大家回家」——金鑰必須與訊息等長、只能用一次。

這個「完美但不實用」的結論正是下一階段的出發點：如何用短金鑰得到計算上安全的加密。

學習目標

讀完本教材你應該能夠：

  1. 在 \(\Zn{26}\) 與 \(\Zn{2}\) 中正確計算（含負數與「繞回」），並說明加法群的四條性質為什麼讓「加金鑰／減金鑰」成為一對可逆操作。

  2. 把 Caesar、單字母替換、Vigenère 寫成完整的 SKE（\(\calK,\calM,\calC,\KGen,\Enc,\Dec\)），算出各自的金鑰空間大小，並說明如何均勻抽樣金鑰（拒絕抽樣、Fisher–Yates）。

  3. 對每一個歷史密碼給出：一次 \(\Enc(\sk,\cdot)\) 查詢即可還原金鑰的方法、一對等長訊息 \(m_0,m_1\) 使 IND-EAV 敵手必勝。

  4. 解釋並執行暴力搜尋、頻率分析（含重合指數與 \(\chi^2\) 檢定）、Vigenère 的分流攻擊、以及 Caesar 的 trace 不變量。

  5. 寫出 Shannon 完美保密的定義與其等價形式，證明一次性密碼本是完美保密的，並證明 \(\abs{\calK}\ge\abs{\calM}\)。

  6. 說明一次性密碼本的三個實務限制（金鑰長度、單次使用、金鑰配送），解釋「全零金鑰」為何不是問題、「重複使用金鑰」為何是災難，並舉出歷史實例（VENONA、華盛頓–莫斯科熱線）。

  7. 完整解答 Problem Set 3 的全部 16 小題，包括親手（與用程式）破譯三段電影台詞密文。

教材結構

  • 第一部分（§[sec:modular]–§[sec:otp]）：依講義順序精讀，每節標明對應的講義頁碼（講義右下角頁碼，共 30 頁），並補充 KL-IMC、Shannon 原始論文與歷史文獻的內容。

  • 第二部分（§[sec:p1]–§[sec:p3]）：Problem Set 3 逐題詳解。每題先完整引述原題，再給出可直接寫在作業或考卷上的「標準答案」，最後補充延伸討論。Problem 3 的三段密文附完整的手動破譯步驟與可重現的 Python 程式。

  • 第三部分：一頁重點整理、中英術語對照表、自我測驗與參考資料。

記號慣例

L4.2cmL10.6cm 記號 & 意義
\(\Zn{n}=\{0,1,\dots,n-1\}\) & 模 \(n\) 的整數；\(x \bmod n\) 為 \(x\) 除以 \(n\) 的非負餘數
\(\ct{a}\leftrightarrow0,\ \ct{b}\leftrightarrow1,\dots,\ct{z}\leftrightarrow25\) & 字母與 \(\Zn{26}\) 的對應；字母運算一律指對應數字的模 26 運算
\(\oplus\) & 模 2 加法（XOR），逐位元作用於等長位元串
\(\alpha\)、\(\alpha^n\)、\(\alpha^{\le n}\)、\(\alpha^*\) & 字母表；長度 \(n\) 的字串；長度至多 \(n\) 的字串；任意長度的字串
\([\ell]=\{1,2,\dots,\ell\}\) & 索引集合；\(m=m_1m_2\cdots m_\ell\) 表示逐字元拆解
\(\Perm(\alpha)\) & \(\alpha\) 上所有排列（雙射 \(\alpha\to\alpha\)）的集合，\(\abs{\Perm(\alpha)}=\abs\alpha!\)
\(x\gets X\) & 從有限集合 \(X\) 均勻隨機抽出 \(x\)
\(\Prob[M=m\mid C=c]\) & 看到密文 \(c\) 之後，訊息為 \(m\) 的事後機率（完美保密的核心量）
\(\trace(w)\) & 字串 \(w\) 相鄰字母的差分序列（§[sec:cryptanalysis]）
\(\IC\) & 重合指數（index of coincidence）
& 明文與密文字串一律以等寬字體排印

本週的講義有大量「Sample \(\sk\) and try encrypting and decrypting a short message of your choice」這類動手指令，請真的拿紙筆做一次——Problem 3 (i) 就是這件事。 三段電影台詞的密文（Problem 3 (ii)–(iv)）建議先不看解答，依 §[sec:cryptanalysis] 的方法自己破一次，再對照 §[sec:p3] 的逐步過程；教材附的程式可以用來驗證。