先說清楚：以下方法「不是必要的」（講義 p. 18）
講義 p. 18 開宗明義：要斷定這些歷史密碼不安全，完全不需要暴力搜尋或頻率分析。四個理由，每個都是 Week 2 某個定義的直接應用：
L6.2cmL3.0cmL5.2cm 講義的理由 & 對應的安全概念 & 本教材中的例子
可以挑同長度的 \(m_0,m_1\)，從 \(c_b\) 分辨出哪個被加密 & IND-EAV（單次挑戰、無預言機） & Problem 1 (iii)：\(\ct{aa}\) vs. \(\ct{ab}\)
一對 \((m,c)\) 就洩漏 \(\sk\) 的資訊 & 已知明文攻擊（KPA） & Caesar：\(\sk=c_1-m_1\)
能存取 \(\Enc(\sk,\cdot)\) 就能直接取回 \(\sk\) & IND-CPA 的預言機 & Problem 1 (ii)：查詢
它們都是確定性的 & Week 2 定理 6.1 & 任何重複的明文片段都看得到
反過來說，抵擋這些攻擊只是「最低門檻」：一個方案要有希望達到 IND-EAV／CPA／CCA，至少不能被暴力搜尋或頻率分析打倒，但做到這點遠遠不夠。
L3.4cmL5.6cmL5.0cm 模型 & 敵手拿到什麼 & 本週的對應
唯密文（COA） & 只有密文（與訊息分布的先驗知識） & 頻率分析、Kasiski、trace、Problem 3
已知明文（KPA） & 若干 \((m_i,c_i)\) & 暴力搜尋的「檢查」步驟
選擇明文（CPA） & \(\Enc(\sk,\cdot)\) 預言機 & Problem 1 (ii)、Problem 2 (ii)
選擇密文（CCA） & 另加 \(\Dec(\sk,\cdot)\) 預言機 & OTP 的可塑性（§[sec:otp]）
歷史密碼在最弱的 COA 下就倒了；現代定義要求在 CPA/CCA 下仍安全。
暴力搜尋（講義 p. 19）
就是窮舉某個空間——通常是 \(\calK\)——直到找到「對的」金鑰。講義的虛擬碼：
Input : message, ciphertext pairs (m_i, c_i)_i=1..N for k in K: for i in [N]: if Dec(k, c_i) != m_i: # k is wrong try next k return k # k is consistent with every pair
兩個講義提出的問題：
「is wrong」是什麼意思？
需要二選一：
已知明文對：有 \((m_i,c_i)\) 可以比對，如上方虛擬碼。這時只要密文夠長，錯的金鑰幾乎不可能通過所有檢查。
足夠的「語境」：只有密文（COA）時，改成「\(\Dec(k,c)\) 看起來像英文嗎？」。這需要關於訊息分布的先驗知識——以及夠長的密文，否則會有多把金鑰都給出合理的明文。
Shannon 定義 \(U=H(\calK)/D\)，其中 \(D\) 是語言的冗餘度（英文每字母約 \(\log_226-1.5\approx3.2\) 位元）。粗略地說，密文長度超過 \(U\) 之後，「能解出合理英文」的錯誤金鑰期望數小於 1： \[U_{\text{Caesar}}\approx\frac{4.7}{3.2}\approx1.5,\qquad U_{\text{mono}}\approx\frac{88.4}{3.2}\approx28,\qquad U_{\text{Vigenère},n}\approx\frac{4.7n}{3.2}\approx1.5n .\] Problem 3 的三段密文（46、69、180 個字母）都遠超過各自的 \(U\)，所以解是唯一的——這也是為什麼 (ii) 的 26 種位移只有一種讀得通。
為什麼用 \(\Dec\) 而不是 \(\Enc\)？
唯密文攻擊時根本沒有 \(m_i\) 可以加密：手上只有 \(c\)，唯一能做的是對每把 \(k\) 算 \(\Dec(k,c)\)，再判斷結果是否「像訊息」。
隨機化加密時 \(\Enc\) 不會重現 \(c_i\)：若 \(\Enc\) 使用隨機數（Week 2 的 IND-CPA 方案都必須如此），\(\Enc(k,m_i)\) 即使 \(k\) 正確也幾乎不會等於 \(c_i\)；但 \(\Dec(k,c_i)=m_i\) 對正確的 \(k\) 永遠成立（正確性）。
\(\Dec\) 能一次排除整類金鑰：許多方案的 \(\Dec\) 會先檢查格式／填充／標籤，不合法就立刻拒絕，比較便宜。
對本週的三個確定性密碼，兩者剛好等價（\(\Enc(k,m_i)=c_i\iff\Dec(k,c_i)=m_i\)），但正確的習慣是寫 \(\Dec\)。
Problem 3 (ii) 的密文 ：對 \(\sk=0,1,\dots,25\) 各算一次 \(\Dec\)，只有 \(\sk=8\) 給出英文（§[sec:p3]）。成本：\(26\) 次解密，每次 \(O(\ell)\)。 對替換密碼則是 \(26!\) 次——不可行；但 §[sec:p3] 會示範頻率分析如何在幾十步內完成。
頻率分析（講義 pp. 20–21）
講義 p. 20：假設 (1) 對訊息分布有先驗知識（例如：英文散文），且 (2) 加密沒有消除這個資訊。那麼比較密文的統計量與語言的統計量就是合法的攻擊。 Caesar／替換／換位密碼都滿足 (2)：它們把每個字母送到固定的字母（或固定的位置），統計結構只是被重新標籤。
還有哪些統計量可用（講義 p. 20）？
雙字母（bigram）：th、he、in、er、an、re、on、at、en、nd；三字母（trigram）：the、and、ing、her、ere、ent。
字首頻率：英文單字以 t、a、o、i、s、w 開頭最多（t 約 16%）；字尾：e、s、d、t、n。
雙寫字母：ll、ee、ss、oo、tt、ff。
單字母單字：只有 和 （偶爾 ）——Problem 3 (ii)、(iii) 都靠它。
單字長度與重複單字：題目保留空白，等於多送了一份結構。
講義強調：「需要足夠但出奇地少的密文」——Problem 3 (iii) 只有 69 個字母。
手動頻率分析要「看起來像英文」，寫程式則需要可計算的分數：
重合指數（Friedman 1920）：從文本中隨機抽兩個不同位置，字母相同的機率 \[\IC(x)=\frac{\sum_{a\in\alpha}n_a(n_a-1)}{N(N-1)} ,\] 其中 \(n_a\) 是字母 \(a\) 的出現次數、\(N\) 是總長度。英文約 \(0.0655\)；均勻隨機文字為 \(1/26\approx0.0385\)。Caesar／替換／換位都保持 \(\IC\)（重新標籤不改變 \(\sum n_a(n_a-1)\)），Vigenère 則把它壓向 \(0.0385\)——這正是判斷金鑰長度的依據（§[sec:p3]）。
\(\chi^2\) 統計量：對每個候選位移 \(k\)，把密文平移 \(-k\) 後計算 \[\chi^2_k=\sum_{a\in\alpha}\frac{(n_a-Np_a)^2}{Np_a},\] \(p_a\) 是英文頻率。正確的 \(k\) 給出最小的 \(\chi^2\)，而且通常遠小於其他 25 個——比「最多的字母是 e」穩健得多（§[sec:p3] (iv) 的第二條子密文就是「最多的字母不是 e」的例子）。
內積法：最大化 \(\sum_a p_a\cdot n_{a+k}/N\)，效果類似。
Vigenère 的頻率分析（講義 p. 21）。
給定 \(c=c_1c_2\cdots c_\ell\) 與金鑰長度上限 \(n\)：
對每個候選長度 \(i\in[n]\)，把密文分成 \(i\) 條子密文： \[c_1c_{1+i}c_{1+2i}\cdots,\quad c_2c_{2+i}c_{2+2i}\cdots,\quad\dots,\quad c_ic_{2i}c_{3i}\cdots\] （講義寫成 \(c_{i-1}c_{2i-1}c_{3i-1}\cdots\) 是最後一條的另一種寫法；共 \(i\) 條，每條是一個 Caesar 密碼）。
對每條子密文做頻率分析求出位移；若「沒有一條讀得通」就換下一個 \(i\)。
兩個更快求 \(i\) 的方法：
Kasiski 檢驗（1863）：密文中重複出現的三字母以上片段，多半來自「同一段明文碰到同一段金鑰」，因此它們的距離是金鑰長度的倍數；取所有距離的最大公因數。短密文時雜訊很多（§[sec:p3] (iv) 中 180 個字母只有兩組重複三字母，距離 90 與 16，\(\gcd=2\)，是錯的！）。
Friedman 的 \(\IC\) 檢驗（1920）：對每個 \(i\) 算 \(i\) 條子密文的平均 \(\IC\)；正確的 \(i\)（及其倍數）會跳回 \(\approx0.065\)，其餘留在 \(\approx0.045\)。對短密文更可靠。
總成本：至多 \(n\) 個長度 \(\times\) 每長度 \(26\cdot i\) 個位移 \(=O(26n^2)\)，與 \(26^n\) 天差地遠。
Bonus weakness：trace（講義 p. 22）
講義 p. 22 的標題是「Veni vidi explicavi」（我來、我見、我解釋）。Caesar 密碼「特別糟糕」：相鄰字母之間的間距（gap）完全不變。
對字串 \(w=w_1w_2\cdots w_\ell\in\alpha^\ell\)（視為 \((\Zn{26})^\ell\)），定義 \[\trace(w)=(w_2-w_1,\ w_3-w_2,\ \dots,\ w_\ell-w_{\ell-1})\in(\Zn{26})^{\ell-1}.\] 例：\(\trace(\ct{hello})=(\ct{e}-\ct{h},\ct{l}-\ct{e},\ct{l}-\ct{l},\ct{o}-\ct{l})=(-3,7,0,3)=(23,7,0,3)\)。
對任意 \(\sk\in\Zn{26}\) 與 \(m\in\alpha^\ell\)，\(\trace(\Enc(\sk,m))=\trace(m)\)。
Proof. \(c_{i+1}-c_i=(m_{i+1}+\sk)-(m_i+\sk)=m_{i+1}-m_i\)，金鑰互相抵消。 ◻
講義的例子：\(\sk=1\)，\(\Enc(1,\ct{hello})=\ct{ifmmp}\)，\(\trace(\ct{ifmmp})=(\ct{f}-\ct{i},\ct{m}-\ct{f},\ct{m}-\ct{m},\ct{p}-\ct{m})=(23,7,0,3)\) ✓。
密文 \(c\) 有可能解密成 \(m\)（即存在 \(\sk\) 使 \(\Dec(\sk,c)=m\)）若且唯若 \(\trace(c)=\trace(m)\)（且長度相同）。
Proof. （\(\Rightarrow\)）由引理。 （\(\Leftarrow\)）設 \(\trace(c)=\trace(m)\)。令 \(\sk:=c_1-m_1\)。歸納證明 \(c_i=m_i+\sk\) 對所有 \(i\) 成立：\(i=1\) 由定義；若 \(c_i=m_i+\sk\)，則 \(c_{i+1}=c_i+(c_{i+1}-c_i)=m_i+\sk+(m_{i+1}-m_i)=m_{i+1}+\sk\)，其中第二個等號用了 \(\trace\) 相等。故 \(\Dec(\sk,c)=m\)。 ◻
把常見單字的 trace 背起來或列表：
| 單字 | trace | 單字 | trace |
|---|---|---|---|
| the | (14, 23) | and | (13, 16) |
| hello | (23, 7, 0, 3) | yes | (6, 14) |
| no | (1) | you | (16, 6) |
| blue | (10, 9, 10) | come | (12, 24, 18) |
在密文中找到長度相同、trace 相同的單字，\(\sk=c_1-m_1\) 就出來了。Problem 3 (ii) 的 的 trace 是 \((10,9,10)\)——與 相同；\(\sk=\ct{j}-\ct{b}=9-1=8\)。 這比暴力搜尋更快：不必嘗試 26 把金鑰，只需比對一次。
Vigenère（金鑰長度 \(j\)）：相鄰字母的差不再守恆，但相距 \(j\) 的字母的差守恆：\(c_{i+j}-c_i=m_{i+j}-m_i\)。這是 Kasiski 檢驗的本質——同一段明文在相距 \(j\) 的倍數處會給出相同密文。
替換密碼：差值不守恆，但「哪些位置的字母相同」這個模式守恆：（模式 ABCA）加密後仍是 ABCA。Problem 3 (iii) 中 與 的重複就是這種「同構」（isomorph）資訊。
OTP：\(c_{i+1}-c_i=m_{i+1}-m_i+(\sk_{i+1}-\sk_i)\)，而 \(\sk_{i+1}-\sk_i\) 本身均勻且獨立於訊息——什麼都不守恆。這就是 §[sec:perfect] 的完美保密。
能寫出暴力搜尋虛擬碼，並說明為何用 \(\Dec\)（唯密文時沒有 \(m\)；隨機化加密時 \(\Enc\) 不重現 \(c\)）。
能解釋「is wrong」需要先驗知識或明文對，以及為何密文要夠長（唯一解距離）。
頻率分析的兩個前提；Vigenère 要先分流再逐條分析；知道 Kasiski 與 \(\IC\) 的原理。
trace 的定義、守恆引理、「若且唯若」命題的證明（關鍵：令 \(\sk=c_1-m_1\) 再歸納）。
最重要的：這些攻擊都不是證明不安全的必要手段——IND-EAV 的一對 \(m_0,m_1\) 就夠了。