6CCS3CIS Cryptography Week 1：密碼學導論、保密性與完整性 完全學習教材
第一部分講義精讀與延伸什麼是密碼學 SkyBlue 思想實驗 SkyBlue SKE 與正確性 SkyBlue 安全定義 SkyBlue 完整性與 MAC SkyBlue 其他攻擊 SkyBlue 歷史插曲 SkyBlue 敵手模型
閱讀文章 →導讀：如何使用本教材
第一週用故事（Francis 與 Henry 的羊皮紙）建立直覺：語法 → 正確性 → 安全性三層分開、保密不等於完整、安全定義要同時說清「敵手不能做什麼」與「敵手能做什麼」。 第二週把這些直覺全部寫成數學： 下週開始的歷史密碼（Caesar、Vigenère 等）會不斷回到這些定義：它們為什麼不安全？用哪一個遊戲可以精確說明？
閱讀文章 →SKE 的正式定義（講義 pp. 2–4）
注意量詞：是所有金鑰、所有訊息，不是「大部分」。這條性質講的是「用同一把 加密再解密會回到原訊息」；它完全沒有提到敵手。
閱讀文章 →MAC 的正式定義（講義 pp. 5–7）
與 SKE 對照： 產生東西、 檢查東西；差別在 不需要「還原」什麼，只需判決。注意 MAC 的輸出 是附加在 m 旁邊傳送的，訊息本身不被隱藏。
閱讀文章 →空間 , , , 到底是什麼？（講義 pp. 8–9）
定義裡的「空間」在數學上就是集合（set）：一堆沒有重複的東西。貓的照片、位元字串、一顆超新星——什麼都可以（講義 p. 8）。這種抽象有好處（定理對任何集合都成立），但常常不夠具體。密碼學裡，這些集合幾乎總是某個字母表上的字串。
閱讀文章 →把 與 當成函數（講義 pp. 10–11）
固定一把金鑰 之後，加密就是一個普通的數學函數。這一節複習函數的三個性質，並算一算「有多少個這樣的函數」——這是 Problem 1 的全部數學工具。
閱讀文章 →Kerckhoffs 原則（講義 p. 12）
今天說「Kerckhoffs 原則」（單數）幾乎都指 2：系統的安全只能依賴金鑰的保密，不能依賴演算法的保密。Shannon 在 1949 年〈Communication Theory of Secrecy Systems〉把它濃縮成一句Shannon 格言Shannon's maxim：「the enemy knows the system」——假設敵人知道系統。
閱讀文章 →SKE 的形式化安全：IND-EAV、IND-CPA、IND-CCA（講義 pp. 13–18）
直覺：不知道 的敵手，不應該能「學到」任何關於訊息的「有意義」資訊，即使它能 問題是「學到」與「有意義」都不是數學。Week 1 的教訓是：安全定義必須同時說清（ ）敵手不能做什麼與（ ）敵手能做什麼。本週的工具是密碼學遊戲cryptographic game：一個挑戰者challenger 依規則與敵手adversary 互動，最後判定 是否「獲勝」。（ ）由 可用的預言機oracle決定，（ ）由獲勝條件決定。
閱讀文章 →MAC 的形式化安全：EUF-CMA（講義 pp. 19–22）
不知道 的敵手，不應該能替一個它沒看過標籤的訊息偽造出合法標籤，即使它可以要求對任意自選的訊息產生標籤。 講義註明：像 IND-EAV／CPA／CCA 一樣，MAC 也有不同強度的定義（KL-IMC 4.2「Strong unforgeability」），本課程只用其中一個。Week 1 的 Problem 1 其實已經把整個光譜走過一遍——1 金鑰不可恢復（太弱）、2 任何訊息不可偽造（不可能）、3 新訊息不可偽造（標準）、3^+ 強
閱讀文章 →哪些敵手？PPT 與可忽略函數（講義 p. 23）
所有安全定義都長這樣：「沒有有效率的敵手能以明顯異於 12（或 0）的機率獲勝」。講義 p. 23 把兩個關鍵詞翻譯成術語：有效率 = PPT，明顯異於 = 不可忽略。講義說本課程不要求形式定義，但理解它們能避免許多誤解。
閱讀文章 →Problem 1：On message and ciphertext spaces（函數與無歧義解密）
（1）單射 。考慮 f(x_1),f(x_2),…,f(x_s) Y。因為 f 單射，x_a x_b f(x_a) f(x_b)，所以這 s 個元素兩兩相異。Y 至少包含這 s 個相異元素，故 t=Y s=X。 （等價說法：f 把 X 一一對應到它的像 f(X)，所以 f(X)=X；又 f(X) Y，所以 X=f(X) 。）
閱讀文章 →Problem 2：On brute force attacks（暴力破解的極限）
先確認它是合法的 SKE： 隨機； 、 確定；正確性 ( , ( ,m))_i=(m_i+ )- m_i26 對所有 ,m 成立。對固定 ， 逐字母是 _26 上的雙射（Problem 1 (iv)），對整個 = _26^* 也是長度保持的雙射。金鑰空間只有 26 把——暴力破解（brute force：試遍所有金鑰、看哪個解密結果「像話」）顯然可行。本題問的是：可行的暴力破解一定成功嗎？
閱讀文章 →Problem 3：On Kerckhoffs' principles（碼書與 Kerckhoffs 原則）
本質上這是以單字為字母的單字母替換密碼（monoalphabetic substitution over a huge alphabet）：確定性、逐符號、金鑰空間巨大。下週分析替換密碼的所有結論（頻率分析）都適用。
閱讀文章 →本週重點整理
本週重點整理 L3.4cmL11.0cm 概念 & 一句話定義 SKE 語法 & ；c ( ,m)（或 =）；m/ = ( ,c)；空間 , , 隨機化演算法 & 確定性演算法 + 隨機輸入 = ^r： ( ,m; ) SKE 正確性 & , m ： ( , ( ,m))=m MAC 語法／正確性 & ； = ( ,m)； ( ,m, ) 0,1； ( ,m, ( ,m))=1 典範驗證 & 重算 '= ( ,m) 並比對；需要確定性
閱讀文章 →中英術語對照表
中英術語對照表 L4.6cmL3.0cmL7.0cm English & 中文 & 說明 firsthead English & 中文 & 說明 head 3r size（續下頁） foot lastfoot secret key encryption (SKE) & 秘密金鑰加密 & ( , , ) 與 , , message authentication code (MAC) & 訊息鑑別碼 & ( , , ) 與 , , rand
閱讀文章 →自我測驗（附解答）
自我測驗 建議先不看解答，每題寫下自己的答案再比對。 在 , , , , 五個演算法中，哪些一定隨機、哪些可以隨機、哪些一定確定？為什麼 不能隨機？ 在定義裡扮演什麼角色？ 一定隨機（否則人人算得出同一把金鑰）； 、 可以隨機（本課的 取確定性）； 、 一定確定。 若隨機，正確性只能是機率性的且毫無好處——可把隨機帶固定而不失正確性；收件人需要明確答案。 讓 能對像集之外、格式錯誤或驗證失敗的密文給出「非法」判決，使 不必滿射（Prob
閱讀文章 →參考資料
N. K. Nguyen, E. W. Postlethwaite, 6CCS3CIS Cryptography, second lecture, King's College London, 9 October 2025. E. W. Postlethwaite, Problem Set 2, 6CCS3CIS Cryptography, 6 October 2025. J. Katz, Y. Lindell, Introductio
閱讀文章 →6CCS3CIS Cryptography Week 2：形式化定義、Kerckhoffs 原則與安全遊戲 完全學習教材
第一部分講義精讀與延伸對應講義 pp. 2–23：SKE 與 MAC 的正式定義、空間與函數、Kerckhoffs 原則、IND 與 EUF-CMA 安全遊戲、PPT 與可忽略函數
閱讀文章 →導讀：如何使用本教材
前兩週建立了語言：SKE 的語法與正確性（Week 1–2）、Kerckhoffs 原則、以及用遊戲寫成的安全定義 IND-EAV／IND-CPA／IND-CCA（Week 2）。 第三週第一次把這套語言用在具體的方案上： 這個「完美但不實用」的結論正是下一階段的出發點：如何用短金鑰得到計算上安全的加密。
閱讀文章 →模算術（講義 pp. 2–6）
講義的例子（n=5）：1-4=-3 2、2+2=4、3+4=7 2 5。 要點是負數也要繞回：-3 加上 5 得 2。一般地，x n 永遠取 0,…,n-1 中的那個代表。
閱讀文章 →Caesar 密碼（講義 pp. 7–8）
若 =N，均勻抽樣指每把金鑰被選中的機率恰為 1/N。 講義的提示「擲五枚硬幣」：五個公平位元給出 2^5=32 個等機率結果，但我們只要 26 個。
閱讀文章 →單字母替換密碼（講義 pp. 9–12）
金鑰最方便的寫法是兩列表（講義 p. 9）：上列是 的自然順序，下列是它們的像；加密「由上往下」查，解密「由下往上」查——這就是 ^-1。
閱讀文章 →Vigenère 密碼（講義 pp. 13–15）
這個觀察（講義：「four ‘distinct’ Caesar ciphers」）就是全部破譯方法的基礎：只要知道 j，把密文依位置 j 分成 j 條子密文，每條都是普通的 Caesar，各自用頻率分析解決（ ）。 攻擊成本是 26· j，不是 26^j——金鑰可以被「分而治之」地逐段攻擊，這是金鑰空間大小不等於安全性的又一個例子。
閱讀文章 →反思：從「設計—破解」循環到定義（講義 pp. 16–17）
講義稱這是「不講原則的」（unprincipled）： 每一次「修補」都只針對上一個攻擊，沒有人問「我們到底想抵擋哪一類敵手？」。 在這種循環裡，一個方案「安全」的唯一證據是「目前還沒有人破解它」——Vigenère 頂著「不可破解」的名號三百年，就是這種證據有多薄弱的最佳示範。
閱讀文章 →