自我測驗（附解答）

\(+\)\(=24+7=31\equiv5=\)；\(-\)\(=1-3=-2\equiv24=\)；\(-\)\(=-16\equiv10=\)（檢查 \(16+10=26\equiv0\)）。 \(\ct{10110}\oplus\ct{01101}=\ct{11011}\)。 在 \(\Zn2\) 中每個元素是自己的反元素（\(1+1=0\)），所以「加 \(k\)」與「減 \(k\)」相同；在 \(\Zn{26}\) 中 \(-\sk\ne\sk\)（除非 \(\sk\in\{0,13\}\)），所以解密要用 \(-\sk\)。ROT13 是 \(\Zn{26}\) 中唯一「加密 \(=\) 解密」的非平凡位移。

(a) 每輪接受機率 \(26/32\)，期望輪數 \(32/26\approx1.23\)（幾何分布）。 (b) \(0,\dots,5\) 各有兩個原像，機率 \(6\times2/32=12/32=37.5\%\)；均勻時應為 \(6/26\approx23.1\%\)。 (c) 任何以 \(k\) 枚硬幣決定輸出的確定性方法，每個輸出的機率都是（整數）\(/2^k\)；\(1/26\) 不是這種形式，因為 \(26\nmid2^k\)。所以必須允許「重擲」（輪數不固定）。

(a) 固定 ，其餘 25 個字母任意排列：\(25!\approx1.55\times10^{25}\)，佔全部的 \(1/26\)。 (b) ／ 的精神：有效金鑰空間從 \(26!\) 縮成「英文單字數」（\(\sim10^5\)），敵手知道系統（含「金鑰來自單字」）後就能窮舉；也與 的初衷（好記）互相拉扯。 (c) \(m_0=\ct{aa}\)、\(m_1=\ct{ab}\)；收到 \(c=c_1c_2\)，若 \(c_1=c_2\) 輸出 0，否則 1。任何排列都是單射：\(\sk(\ct{a})=\sk(\ct{a})\) 恆成立、\(\sk(\ct{a})\ne\sk(\ct{b})\) 恆成立，故 \(\Pr[b'=b]=1\)。

(a) \(m_0=\ct{aaaaa}\)、\(m_1=\ct{aaaab}\)：位置 1 與 5 都用 \(\sk_1\)，\(b=0\) 時 \(c_1=c_5\)，\(b=1\) 時 \(c_5=c_1+1\)。長度 \(\le4\) 的訊息每個位置用獨立均勻的位移且各用一次，是完美保密的（§[sec:perfect]），任何 \(m_0,m_1\) 都無法區分。 (b) \(c_{i+4}-c_i=(m_{i+4}+\sk_{r})-(m_i+\sk_{r})=m_{i+4}-m_i\)，其中 \(r=((i-1)\bmod4)+1=((i+3)\bmod4)+1\)。 (c) \(L=\operatorname{lcm}(1,2,3,4)=12\)：\(m_0=\ct{a}^{13}\)、\(m_1=\ct{a}^{12}\ct{b}\)，位置 1 與 13 對任何 \(j\in\{1,2,3,4\}\) 都用 \(\sk_1\)。

(a) \(\trace(\ct{yes})=(\ct{e}-\ct{y},\ct{s}-\ct{e})=(4-24,18-4)=(6,14)\)。 (b) \(\trace(\ct{ekx})=(10-4,23-10)=(6,13)\ne(6,14)\)，不可能。\(\trace(\ct{eky})=(6,14)\) ✓，\(\sk=\ct{e}-\ct{y}=4-24\equiv6\)；檢查 \(\ct{y}+6=30\equiv4=\ct{e}\)、\(\ct{e}+6=\ct{k}\)、\(\ct{s}+6=24=\ct{y}\) ✓。 (c) 相鄰差不再守恆（\(\sk_{i+1}-\sk_i\) 混進來），但相距 \(j\) 的差守恆（第 4 題 (b)）；替換密碼則只保留「相同字母的位置模式」。

(a) 即使 \(k=\sk\)，\(\Enc(k,m)\) 用新的隨機數，與 \(c\) 相等的機率約 \(2^{-128}\)；正確金鑰會被誤判為錯，搜尋失敗。 (b) 正確性保證 \(\Dec(\sk,c)=m\) 對任何曾被用的 \(\rho\) 都成立，所以正確金鑰必通過檢查；錯誤金鑰通過的機率由密文長度控制。 (c) 唯一解距離 \(U\approx88.4/3.2\approx28\) 個字母；少於此長度會有多把金鑰都給出「合理英文」。（但 \(26!\) 次嘗試本身不可行——這題的重點是「檢查」的邏輯，不是可行性。）

(a) 對任意 \(m,c\in\alpha\)，\(\Enc(K,m)=c\iff K=c-m\)，機率 \(1/26\)，與 \(m\) 無關；由 Lemma 2.4 得證。亦可用 Shannon 定理：\(\abs\calK=\abs\calM=\abs\calC=26\)、金鑰均勻、每對 \((m,c)\) 恰一把金鑰。 (b) \(m=\ct{aa}\)、\(m'=\ct{ab}\)、\(c=\ct{bb}\)：\(\Pr[\Enc(K,\ct{aa})=\ct{bb}]=\Pr[K=1]=1/26\)，但 \(\Pr[\Enc(K,\ct{ab})=\ct{bb}]=0\)（需要 \(K=1\) 且 \(K=0\)）。兩個字母就不完美——金鑰被用了兩次。

不完美。\(\Pr[\Enc(K,m)=m]=\Pr[K=0^n]=\tfrac12\)，而對 \(m'\ne m\)，\(\Pr[\Enc(K,m')=m]=\tfrac12\cdot\tfrac1{2^n-1}\)。 敵手：送 \(m_0\ne m_1\)；若 \(c=m_0\) 猜 0、若 \(c=m_1\) 猜 1、否則擲硬幣。\(b=0\) 時：\(c=m_0\) 機率 \(\tfrac12\)（猜對）、\(c=m_1\) 機率 \(\tfrac1{2(2^n-1)}\)（猜錯）、其餘擲硬幣。 \(\Pr[\text{贏}]=\tfrac12\cdot1+\tfrac1{2(2^n-1)}\cdot0+\bigl(1-\tfrac12-\tfrac1{2(2^n-1)}\bigr)\tfrac12=\tfrac34-\tfrac1{4(2^n-1)}\)，對 \(n\ge2\) 嚴格大於 \(\tfrac12\)（\(n=8\)：約 \(0.749\)；\(n=1\) 時這個 \(\KGen\) 恰好是均勻的，獲勝機率正是 \(\tfrac12\)）。 Shannon 定理的條件 (1)「金鑰均勻」被破壞。

\(\sk=c_1\oplus m_1=\ct{00010010}\oplus\ct{01001000}=\ct{01011010}\)；\(m_2=c_2\oplus\sk=\ct{00010011}\oplus\ct{01011010}=\ct{01001001}\)（ASCII ）。 或直接 \(m_2=c_1\oplus c_2\oplus m_1=\ct{00000001}\oplus\ct{01001000}=\ct{01001001}\)。 未知 \(m_1\) 時，\(c_1\oplus c_2=\ct{00000001}\) 告訴敵手「兩則訊息只差最低位元」——若訊息是 ASCII 大寫字母，就是相鄰的兩個字母（H/I、J/K…）。

\(\abs\calK=2^n<2^{n+1}=\abs\calM\)，違反定理「完美保密 \(\Rightarrow\abs\calK\ge\abs\calM\)」。 攻擊：取任一 \(\Pr[C=c]>0\) 的密文 \(c\)，計算 \(\calM(c)=\{\Dec(k,c):k\in\calK\}\)，至多 \(2^n\) 個訊息；至少有 \(2^n\) 個訊息不在其中。敵手看到 \(c\) 後就知道這些訊息不可能是明文——後驗與先驗不同。IND-EAV 版本：挑 \(m_0\in\calM(c)\)、\(m_1\notin\calM(c)\)……更簡單地，隨機挑 \(m_0,m_1\)，收到 \(c\) 後檢查哪一個在 \(\calM(c)\) 裡（需要無限算力，但完美保密正是對這種敵手的承諾）。

(a) 距離 \(24,24\)，\(\gcd=24\)，候選長度為 24 的因數：\(2,3,4,6,8,12,24\)。 (b) \(p=4\) 第一次跳回英文水準（0.063），8 與 12 也高是因為它們是 4 的倍數（分流更細仍是單一 Caesar，只是樣本變少）；\(p=2,3,6\) 低，排除。取最小的高 \(\IC\) 週期：\(4\)。確認方式：分成 4 條子密文各做 \(\chi^2\)，若都能得到明確的位移且合起來讀得通，即為答案。

重用給出 \(c_1-c_2=m_1-m_2\pmod{10}\)，其中 \(m_i\) 是代碼組序列。代碼組的分布高度不均（常用詞、固定格式、流水號），所以「差」的分布也不均，可用 crib dragging 逐段還原兩則代碼組序列，再重建代碼簿（Meredith Gardner 的工作）。代碼簿只是另一個確定性替換，並不提供額外的隨機性。 啟示：完美保密的證明是條件式的——「若金鑰均勻、等長、只用一次，則……」。證明沒有錯，錯的是操作違反了前提；安全性論證的前提與實際部署之間的落差，正是講義 p. 29「完美但脆弱」的意思。