Problem 2：On the one time pad

\[\calK=\{0,1\}^n,\qquad \calM=\calC=\{0,1\}^{\le n}=\bigcup_{\ell=0}^{n}\{0,1\}^\ell .\]

• \(\KGen()\)：輸出均勻的 \(\sk\gets\{0,1\}^n\)（每把金鑰機率 \(2^{-n}\)）。

• \(\Enc(\sk,m)\)：令 \(\ell=\abs m\)；輸出 \(c=m\oplus(\sk_1\sk_2\cdots\sk_\ell)\)，即 \(c_i=m_i\oplus\sk_i\)，\(i\in[\ell]\)。

• \(\Dec(\sk,c)\)：令 \(\ell=\abs c\)；輸出 \(m=c\oplus(\sk_1\cdots\sk_\ell)\)。

正確性：\(\Dec(\sk,\Enc(\sk,m))=(m\oplus\sk_{1..\ell})\oplus\sk_{1..\ell}=m\oplus0^\ell=m\)。 完美保密（對每個固定長度 \(\ell\)）：\(\Pr[\Enc(K,m)=c]=\Pr[K_{1..\ell}=m\oplus c]=2^{-\ell}\)，與 \(m\) 無關（§[sec:otp]）。

• 密文與明文等長，所以長度會洩漏；這是定義允許的（Week 2 的 IND 遊戲要求 \(\abs{m_0}=\abs{m_1}\)）。

• 數一數：\(\abs\calM=\sum_{\ell=0}^n2^\ell=2^{n+1}-1>2^n=\abs\calK\)。這不違反 \(\abs\calK\ge\abs\calM\) 的定理——該定理針對的是「完美保密」成立的訊息空間，而這裡完美保密只對每個固定長度的子空間 \(\{0,1\}^\ell\) 成立（\(\abs{\{0,1\}^\ell}=2^\ell\le2^n\)）。

• 若只要加密恰好 \(n\) 位元的訊息，就是 KL-IMC Construction 2.8：\(\calK=\calM=\calC=\{0,1\}^n\)。

查詢 \(m=0^n\)：\(\Enc(\sk,0^n)=0^n\oplus\sk=\sk\)。一次查詢、密文就是金鑰。 更一般地，查詢任何 \(n\) 位元的 \(m\)，得 \(c=m\oplus\sk\)，則 \(\sk=c\oplus m\)——這就是 XOR 的自反性：知道三個量中的任兩個就知道第三個。 即使只允許查詢較短的訊息，查 \(0^\ell\) 得到前 \(\ell\) 位金鑰，拼起來即可。

因為 (ii) 的敵手違反了 OTP 的使用條件：每把金鑰（的每個位元）只能用一次。

• 完美保密的定義（KL-IMC Def. 2.3／Lemma 2.4）只談一則訊息的一個密文：\(\Pr[M=m\mid C=c]=\Pr[M=m]\)。定義裡沒有加密預言機；敵手看到的就只有那一個 \(c\)。OTP 對這個定義的證明完全正確，(ii) 沒有推翻它。

• 在 (ii) 中，敵手拿到 \(\Enc(\sk,0^n)\) 之後，\(\sk\) 已經「用掉」了。正確操作的 OTP 此時應該銷毀 \(\sk\)，之後的任何訊息都要用新的金鑰加密；敵手知道一把已經不會再用的金鑰，毫無價值。若之後仍然用同一把 \(\sk\) 加密真正的訊息，那就不是 OTP，而是「一次性密碼本用兩次」——完美保密從沒對它做任何承諾。

• 用 Week 2 的語言：(ii) 是 IND-CPA 攻擊（有 \(\Enc(\sk,\cdot)\) 預言機）。OTP 是完美保密／IND-EAV 安全，但不是 IND-CPA 安全——這兩個定義不同，一個方案滿足前者而不滿足後者沒有任何矛盾（Week 2 的定義層級）。而且由 Week 2 定理 6.1，任何確定性方案都不可能 IND-CPA，OTP 當然也不例外。

題目提示的「proper operation 對 \(\sk\) 的條件」就是：均勻、至少與訊息一樣長、只用一次。(ii) 破壞了第三條。

\(\calK\) 有 \(2^n\) 個元素，均勻抽樣每個機率 \(1/2^n\)，所以 \[\Pr[\sk=0^n]=2^{-n}.\] 這與任何其他特定金鑰（例如 \(1^n\)、\(0101\cdots\)）的機率完全相同——全零金鑰沒有任何特殊地位。

直覺上「全零金鑰把明文原封不動送出去」聽起來很糟。但完美保密問的不是「密文是否等於明文」，而是「敵手看到密文後，能否縮小明文的可能範圍」。

為什麼不洩漏。

假設敵手看到 \(c\)。對每一個可能的明文 \(m\in\{0,1\}^\ell\)，恰有一把金鑰 \(k=m\oplus c\) 會把 \(m\) 送到 \(c\)，而每把金鑰機率相同。 特別地，「\(m=c\)（金鑰全零）」只是 \(2^\ell\) 個同樣可能的解釋中的一個——敵手無法知道發生的是這一個，還是 \(m=c\oplus k\)（\(k\ne0\)）中的某一個。 形式上，完美保密的證明 \(\Pr[\Enc(K,m)=c]=2^{-\ell}\) 對所有 \(m\) 成立，包括 \(m=c\)；全零金鑰的存在正是讓「\(m=c\)」這個可能性與其他可能性一樣可能所必需的。

反過來：把全零金鑰拿掉才會出問題（KL-IMC 習題 2.7）。

令 \(\calK'=\{0,1\}^n\setminus\{0^n\}\)，均勻抽樣。則對任何 \(m\)： \[\begin{gather*} \Pr[\Enc(K,m)=m]=\Pr[K=0^n]=0,\\ \Pr[\Enc(K,m')=m]=\Pr[K=m\oplus m']=\tfrac1{2^n-1}\quad(m'\ne m). \end{gather*}\] 兩者不等，Lemma 2.4 失敗：敵手看到 \(c\) 後確定 \(m\ne c\)，排除了一個可能的明文。 具體的 IND-EAV 敵手：送出 \(m_0,m_1\)；收到 \(c\)，若 \(c=m_0\) 輸出 \(1\)，若 \(c=m_1\) 輸出 \(0\)，否則擲硬幣。計算： \[\Pr[\text{贏}]=\tfrac12+\tfrac1{2(2^n-1)},\qquad \Adv=\Bigl|\Pr[\text{贏}]-\tfrac12\Bigr|=\tfrac1{2(2^n-1)}>0 .\] \(n=1\) 時 \(\Pr[\text{贏}]=1\)（金鑰只能是 \(1\)，\(c=\bar m\)，敵手必勝）；\(n\) 很大時優勢雖小，但完美保密要求的是恰好 \(0\)。 Shannon 定理（§[sec:perfect]）的角度：\(\abs{\calK'}=2^n-1<2^n=\abs\calM\)，條件 (2)「每對 \((m,c)\) 恰有一把金鑰」對 \(c=m\) 這一對失敗。

分析密文的分布。

\(c_i=m_i\oplus\sk\)，且各 \(m_i\) 獨立同分布。

• 若 \(\sk=0\)：\(c_i=m_i\)，所以 \(\Pr[c_i=1]=2/3\)——密文中 1 偏多。

• 若 \(\sk=1\)：\(c_i=\bar m_i\)，所以 \(\Pr[c_i=1]=1/3\)——密文中 0 偏多。

猜測規則（多數決）。

令 \(N_1=\#\{i:c_i=1\}\)、\(N_0=\ell-N_1\)。 \[\text{若 }N_1>N_0\text{ 猜 }\sk=0;\qquad \text{若 }N_1<N_0\text{ 猜 }\sk=1;\qquad \text{平手則擲硬幣。}\] 猜到 \(\sk\) 之後，\(m_i=c_i\oplus\sk\) 把所有訊息一次解開。

為什麼這是最佳的（最大概似）。

\[\frac{\Pr[c_1\cdots c_\ell\mid\sk=0]}{\Pr[c_1\cdots c_\ell\mid\sk=1]} =\frac{(2/3)^{N_1}(1/3)^{N_0}}{(1/3)^{N_1}(2/3)^{N_0}}=2^{\,N_1-N_0}.\] 概似比只取決於 \(d=N_1-N_0\)；\(d>0\) 時 \(\sk=0\) 更可能。若對 \(\sk\) 的先驗是均勻的（\(\KGen\) 確實如此），後驗為 \[\Pr[\sk=0\mid c]=\frac{2^d}{1+2^d},\] 例如 \(d=1\colon0.667\)、\(d=2\colon0.8\)、\(d=3\colon0.889\)、\(d=5\colon0.970\)、\(d=10\colon0.999\)。 每多一個「多數票」，信心就多一倍的賠率。

錯誤機率隨 \(\ell\) 下降。

多數決猜錯的機率（\(\sk=0\) 但 \(N_1\le N_0\)，平手算一半；\(\sk=1\) 對稱）：

（由二項分布 \(N_1\sim\mathrm{Bin}(\ell,2/3)\) 直接計算；Hoeffding 不等式給出 \(\Pr[\text{錯}]\le e^{-\ell/18}\) 的指數衰減。） 只要 \(\ell\) 約 30，金鑰就幾乎確定；\(\ell=1\) 時 \(1/3\) 的錯誤率等於「永遠猜 \(\sk=0\)」——單一訊息下 OTP 的確什麼都沒洩漏。

教訓。

完美保密的證明用到了「金鑰只與一則訊息 XOR」。一旦同一位元金鑰被用在多則非均勻的訊息上，密文的統計分布就會把金鑰「投票」出來——這是 VENONA 攻擊的一位元縮影。注意若訊息是均勻的（\(\Pr[m=0]=1/2\)），多數決無效；但重用仍洩漏 \(c_i\oplus c_j=m_i\oplus m_j\)，即「哪些訊息相同」。

不可以。名字裡的「one time」就是使用說明。理由（由弱到強）：

1. (vi)：訊息分布有偏時，重用直接洩漏金鑰。

2. 講義 p. 26／§[sec:otp]：\(c_1\oplus c_2=m_1\oplus m_2\)，即使訊息分布未知也洩漏兩則訊息的關係；已知其中一則就得到另一則；crib dragging 可同時還原兩則。

3. (ii)：若敵手能影響被加密的內容（選擇明文），一則已知訊息就給出金鑰，之後所有訊息全部暴露。

4. 形式上：重用金鑰的 OTP 是確定性方案，由 Week 2 定理 6.1 不可能 IND-CPA；更強地，任何確定性方案都不可能達到「多則訊息的完美保密」（KL-IMC §2.2 的討論／習題 2.3）。

正確做法：每則訊息用金鑰帶上新的一段，用過即銷毀（VENONA 的失敗正是來自重複印製密碼本）。

Kerckhoffs（1883）的六條原則（Week 2 §5）逐條檢查：

總結：OTP 完美滿足 、、，明確違反 ，、 視規模而定。Kerckhoffs 的原則本來就是為了「野戰可用」而寫；OTP 在安全性上無可挑剔，卻在可用性上失分，這與講義 p. 29「完美但脆弱、只有邊緣用例」的結論一致。

最著名、也最能說明「違反條件就崩潰」的案例是蘇聯的外交／情報密碼本與美國的 VENONA 計畫。

系統。

1930 年代起，蘇聯 NKVD／GRU 與外交部的電報採兩層加密：先用代碼簿把字詞換成 4 位數的代碼組，再把代碼組逐位加上一次性密碼本上的隨機 5 位數字（模 10 不進位加法——§[sec:modular] 的元素級運算）。密碼本每頁只用一次、用後銷毀。只要密碼本真隨機且不重用，這就是 \(\Zn{10}\) 上的完美保密方案。

錯誤。

1941–1942 年德軍入侵造成的壓力下，密碼本製造單位為了趕工，把同一批約 35,000 頁的金鑰印了兩份，分發給不同的使用單位（例如紐約的貿易代表團與華府的大使館）。重複的頁面在 1942–1948 年間被用掉。

攻擊。

• 1943 年 2 月 1 日，美國陸軍信號情報局（Arlington Hall）的 Gene Grabeel 開始系統性檢視蘇聯電報。1943 年 10 月，Richard Hallock 發現貿易電報中金鑰重用的統計證據；1944 年 11 月，Cecil Phillips 與 Genevieve Feinstein 找到剝離金鑰的方法；1946 年起語言學家 Meredith Gardner 開始還原代碼簿。

• 原理就是 §[sec:otp] 的 \(c_1-c_2=m_1-m_2\)（模 10），再對「代碼組的差」做 crib dragging：已知的固定格式（電報開頭、常見代碼組、公開文件的譯文）給出突破口。

• 成果：約 3,000 份電報被（至少部分）翻譯（1995 年解密時公布的數字是 2,200，之後持續重工）；紐約 KGB 站發往莫斯科的電報中，1944 年約 49% 可讀，1943 年 15%，1942 年只有 1.8%——重複頁面越多的年份越容易破。揭露了 Rosenberg 夫婦、Klaus Fuchs、Cambridge Five 等間諜網；計畫一直持續到 1980 年，1995 年解密。

它示範了什麼。

(1) OTP 的安全性證明沒有錯——被攻破的電報全都是金鑰重用的那一部分，一次使用的部分至今未破； (2) 兩層加密（代碼簿 + OTP）沒有拯救它，因為重用讓敵手拿到 \(m_1-m_2\)，而代碼組的分布高度非均勻（(vi) 的放大版）； (3) 金鑰分發與管理的操作失誤才是真正的弱點——這正是講義 p. 29 的結論。

其他歷史用例（簡述）。