一頁看懂第三週
必背定義與結論
密碼、抽樣與弱點。
L3.4cmL11.0cm 概念 & 一句話版本
\(\Zn{n}\) & \(\{0,\dots,n-1\}\) 配模 \(n\) 加法：封閉、結合、單位元 \(0\)、反元素 \(-a=n-a\)（交換群）
XOR & \(\Zn2\) 的加法；\(a\oplus a=0\)（自反），加密 \(=\) 解密
Caesar & \(\calK=\Zn{26}\)，\(\calM=\calC=\alpha^*\)，\(c_i=m_i+\sk\)、\(m_i=c_i-\sk\)
單字母替換 & \(\calK=\Perm(\alpha)\)，\(c_i=\sk(m_i)\)、\(m_i=\sk^{-1}(c_i)\)；\(\abs\calK=26!\)
Vigenère & \(\calK=\{0..25\}^{\le n}\)，\(c_i=m_i+\sk_{((i-1)\bmod j)+1}\)；\(=j\) 個交錯的 Caesar
均勻抽樣 & 拒絕抽樣（\(26/32\) 接受）；排列用 Fisher–Yates；小心模偏差
五個弱點（Caesar） & 小 \(\calK\)／\((m,c)\) 給 \(\sk\)／間距保留／頻率分析／確定性
密碼分析與完美保密。
L3.4cmL11.0cm 概念 & 一句話版本
暴力搜尋 & 對每個 \(k\in\calK\) 檢查 \(\Dec(k,c_i)=m_i\)；用 \(\Dec\) 因 COA 無 \(m\)、隨機化 \(\Enc\) 不重現 \(c\)
唯一解距離 & \(U\approx\log_2\abs\calK/3.2\)：Caesar 1.5、替換 28、Vigenère \(1.5n\) 個字母
頻率分析 & 前提：訊息分布先驗 + 加密不消除統計；e 12.7、t 9.1、a 8.2、o 7.5、i 7.0
\(\IC\) & \(\sum n_a(n_a-1)/N(N-1)\)；英文 0.0655、隨機 0.0385；Vigenère 分流找週期
trace & \((w_2-w_1,\dots,w_\ell-w_{\ell-1})\)；Caesar 保持；\(c\) 可解成 \(m\iff\trace(c)=\trace(m)\)
完美保密 & \(\forall\) 分布、\(m\)、\(c\)：\(\Pr[M=m\mid C=c]=\Pr[M=m]\) \(\iff\) \(\Pr[\Enc(K,m)=c]\) 與 \(m\) 無關
OTP & \(\calK=\{0,1\}^n\)，\(c=m\oplus\sk_{1..\ell}\)；完美保密因 \(\Pr[\Enc(K,m)=c]=2^{-\ell}\)
\(\abs\calK\ge\abs\calM\) & 否則存在 \(m'\) 不在 \(\{\Dec(k,c)\}\) 中，\(\Pr[M=m'\mid C=c]=0\ne\Pr[M=m']\)
Shannon 定理 & \(\abs\calK=\abs\calM=\abs\calC\) 時：完美 \(\iff\) 金鑰均勻且每對 \((m,c)\) 恰一把金鑰
金鑰重用 & \(c_1\oplus c_2=m_1\oplus m_2\)；有偏訊息時多數決洩漏金鑰；VENONA
限制 & 金鑰 \(\ge\) 訊息、單次使用、金鑰分發 \(\Rightarrow\) 轉向計算安全（PRG）
常見誤區
「金鑰空間夠大就安全」。\(26!\approx2^{88}\) 的替換密碼 69 個字母就被破。大金鑰空間是必要條件。
Vigenère 的區分對寫成 ／。位置 1、2 用不同位移；要用相距 \(n\) 的位置（\(\ct{a}^{n+1}\) vs. \(\ct{a}^n\ct{b}\)）。
Vigenère 的下標寫成 \(\sk_{i\bmod j}\) 而不處理 \(0\)。正確是 \(\sk_{((i-1)\bmod j)+1}\)（或 0 起始下標）。
暴力搜尋用 \(\Enc\)。唯密文時沒有 \(m\)；隨機化加密時 \(\Enc\) 不會重現 \(c\)。
「最多的字母就是 e」當成定理。60 個字母的樣本會失誤（Problem 3 (iv) 子密文 2）；用 \(\chi^2\)／內積。
Kasiski 的 \(\gcd\) 當成金鑰長度。短密文的巧合重複會污染；要搭配 \(\IC\)。
完美保密寫成「密文均勻」。正確敘述是「密文分布與訊息無關」／「後驗 \(=\) 先驗」。均勻是 OTP 的證明手段，不是定義。
「全零金鑰會洩漏明文，所以要拿掉」。拿掉才會洩漏（\(\Pr[\Enc(K,m)=m]=0\)）；KL 習題 2.7、Enigma 反射器。
「OTP 完美保密，所以 IND-CPA」。OTP 確定性，一次 \(\Enc(\sk,0^n)\) 查詢就拿到金鑰；完美保密只談一則訊息。
\(\abs\calK\ge\abs\calM\) 與 \(\calM=\{0,1\}^{\le n}\) 的「矛盾」。完美保密只對固定長度子空間成立；長度本來就洩漏。
忘記 Vigenère 解密時空白不佔金鑰位置。Problem 3 (iv) 計數錯會得到「偶爾對、多數錯」的亂碼。
把 Vigenère 歸給 Vigenère。Bellaso 1553 發明；Vigenère 1586 的是自動金鑰密碼。
與前後週的連結
L2.4cmL12.0cm Week 1 & 保密性 vs. 完整性：OTP 只給保密、完全可塑（翻轉 \(c_i\) 即翻轉 \(m_i\)）；MAC 的必要性。
Week 2 & SKE 語法、\(\Esk\) 單射、Kerckhoffs 六原則、IND-EAV／CPA／CCA、定理 6.1（確定性 \(\Rightarrow\) 非 IND-CPA）、唯一解距離——本週全部用上。
Week 3 & 歷史密碼作為 SKE 的失敗；第一個嚴格定義（完美保密）；OTP 達成它；Shannon 證明代價不可避免。
Week 4+ & 放寬為計算安全：PRG 把短金鑰拉長成「看起來均勻」的金鑰流（串流密碼）；PRF／分組密碼與隨機化模式達成 IND-CPA；安全性依賴明確假設 + 歸約證明——§[sec:reflections] 的三原則。