The Caesar cipher is a historical example of an SKE. Let \(\calK=\{0,1,\dots,25\}\) and \(\calM=\calC=\{0,1,\dots,25\}^*\). Encode lowercase letters as \(\mathrm a=0,\mathrm b=1,\dots,\mathrm z=25\). Define \(\SKE=(\KGen,\Enc,\Dec)\) as

  • \(\KGen\): select \(\sk\) uniformly from \(\calK\),

  • \(\Enc(\sk,m)\): parse \(m=m_1m_2\cdots m_\ell\); for \(i\in\{1,\dots,\ell\}\) let \(c_i=m_i+\sk\bmod 26\) and return \(c=c_1c_2\cdots c_\ell\),

  • \(\Dec(\sk,c)\): parse \(c=c_1c_2\cdots c_\ell\); for \(i\in\{1,\dots,\ell\}\) let \(m_i=c_i-\sk\bmod26\) and return \(m=m_1m_2\cdots m_\ell\).

先確認它是合法的 SKE：\(\KGen\) 隨機；\(\Enc\)、\(\Dec\) 確定；正確性 \(\Dec(\sk,\Enc(\sk,m))_i=(m_i+\sk)-\sk\equiv m_i\pmod{26}\) 對所有 \(\sk,m\) 成立。對固定 \(\sk\)，\(\Esk\) 逐字母是 \(\Z_{26}\) 上的雙射（Problem 1 (iv)），對整個 \(\calM=\Z_{26}^*\) 也是長度保持的雙射。金鑰空間只有 26 把——暴力破解（brute force：試遍所有金鑰、看哪個解密結果「像話」）顯然可行。本題問的是：可行的暴力破解一定成功嗎？

(i) 密文 有幾種讀法？

You receive the ciphertext \(c=\mathrm{ck}\). If you allow acronyms and abbreviations, how many human readable messages are there that can encrypt to \(c\) using the Caesar cipher, and what are the respective keys?

\(c=\mathrm{ck}=(2,10)\)。對每把金鑰 \(\sk\in\{0,\dots,25\}\) 計算 \(m=\Dec(\sk,c)=(2-\sk,\ 10-\sk)\bmod26\)，得到下表（ 一般英文單字； 常見縮寫／首字母縮略詞； 難以視為可讀）：

@C0.6cmC0.8cmC0.5cmL4.4cm@C0.6cmC0.8cmC0.5cmL4.4cm@ \(\sk\) & \(m\) & & 說明 & \(\sk\) & \(m\) & & 說明
& & & Calvin Klein；check 的縮寫 & 13 & & & pixel；Post Exchange（美軍福利社）
1 & & & 姓名縮寫（勉強）& 14 & & & 感嘆詞「哎喲」
2 & & & 三趾樹懶；也是 AI & 15 & & & Nevada（州名縮寫）
3 & & & 中文的 ISO 639-1 語言代碼 & 16 & & & 希臘字母 \(\mu\)
4 & & & — & 17 & & & Lt.（lieutenant）
5 & & & 車款（Jaguar XF）；勉強 & 18 & & & Kansas
6 & & & 代名詞 & 19 & & & Jr.（junior）
7 & & & venereal disease & 20 & & & IQ
8 & & & University of California；「you see」& 21 & & & HP；horsepower
9 & & & tuberculosis；terabyte & 22 & & & 動詞
10 & & & South Africa／Australia & 23 & & & function；鍵盤 Fn 鍵
11 & & & — & 24 & & & 印刷單位 em；’em（them）
12 & & & — & 25 & & & download；decilitre

計數：

  • 只算一般英文單字：6 個——（\(\sk=2\)）、（6）、（14）、（16）、（22）、（24）。

  • 題目允許首字母縮略詞與縮寫：再加上 共 17 個，合計 23 個；若剔除最勉強的 、，約 20 個。只有 、、 三個幾乎無法閱讀。（用一份常見網路字彙表機械檢查，26 個候選中有 22 個出現在表中。）

結論：對這麼短的密文，暴力破解列得出全部 26 個候選，卻選不出正確的那一個：幾乎每把金鑰都給出「可讀」的訊息。「人類可讀」的定義愈寬（允許縮寫），存活的金鑰愈多。

(ii) 一則密文一定夠嗎？

Is a single ciphertext always sufficient to mount a brute force attack against an SKE?

不一定。暴力破解的流程是「對每把 \(\sk\in\calK\) 計算 \(\Dec(\sk,c)\)，保留看起來正確的」。它要成功，需要同時滿足幾個條件，而單一密文可能讓任何一個失敗：

  1. 金鑰空間可枚舉。\(\abs{\calK}=26\) 當然可以；\(2^{128}\) 則不行。這是計算上的限制（§[sec:adversaries]）。

  2. 要有辦法認出正確的明文。若明文沒有結構（隨機位元、已壓縮資料、另一層加密的密文、金鑰材料），每把金鑰解出來都一樣「像話」，攻擊者無從判斷。這就是為什麼暴力破解通常搭配已知明文（知道某段 \(m\)）或明文的冗餘（語言、檔頭、格式）。

  3. 密文要夠長。即使明文是英文，太短的密文會讓多把金鑰都解出可讀結果——(i) 就是例子。所需長度由 Shannon 的刻畫（下方觀念框）。

  4. 金鑰空間不能大到「什麼明文都可能」。極端情形是一次性密碼本：\(\abs{\calK}\ge\abs{\calM}\)，對任何 \(c\)，每一個同長度的 \(m\) 都對應某把金鑰。暴力破解會列出全部可能的明文——等於什麼都沒學到。這是完美保密（Week 1）的另一種說法。

反過來，當密文夠長、明文有冗餘、金鑰空間小，單一密文就足夠：Caesar 密文只要約 2–3 個以上的英文字母，通常就只剩一個可讀解。

設語言每個字母的為 \(D=\log_2\abs{\alpha}-r\) 位元，其中 \(r\) 是語言的熵率（英文約 \(1.5\) 位元／字母，\(\log_2 26\approx4.7\)，故 \(D\approx3.2\)）。對長度 \(L\) 的密文，錯誤金鑰解出「像英文」的明文的期望個數約為 \[\bar s\ \approx\ (\abs{\calK}-1)\cdot 2^{-D\,L},\] 而使 \(\bar s\approx 1\) 的長度 \(U=\dfrac{\log_2\abs{\calK}}{D}\) 稱為唯一解距離：超過 \(U\) 之後，解通常唯一。

L3.4cmC3.2cmC2.4cmL4.3cm 密碼 & \(\log_2\abs{\calK}\) & \(U\)（字母）& 備註
Caesar & \(\log_2 26\approx4.7\) & \(\approx1.5\) & 2 個字母理論上就該唯一——但見下文
單字母替換 & \(\log_2 26!\approx88.4\) & \(\approx28\) & 下週：約 30 字母以上才能唯一決定
AES-128（英文明文）& \(128\) & \(\approx40\) & 單一區塊（16 字母）不夠；三個區塊有餘
一次性密碼本 & \(\ge L\log_2 26\) & \(\infty\) & 永遠不唯一：完美保密

為什麼 (i) 的結果（6 到 23 個候選）遠多於公式的 \(\bar s\approx25\cdot2^{-6.4}\approx0.3\)？因為 \(D\approx3.2\) 是長文本的平均冗餘；極短字串的冗餘低得多——676 個雙字母組合中約 100 個是英文單字（密度 \(\approx0.15\)，對應 \(D\approx1.4\)），而若允許縮寫，幾乎任何兩個字母都「可讀」（密度 \(\to1\)，\(D\to0\)，\(U\to\infty\)）。冗餘愈低，暴力破解愈無力。

(iii) 最長的「雙解」Caesar 密文

What is the longest ciphertext you can find that can decrypt to at least two human readable messages using the Caesar cipher?

這是一個可以用程式窮舉的問題：兩個訊息 \(m,m'\) 能加密成同一個密文，若且唯若 \(m'\) 是 \(m\) 的某個位移 \(k\in\{1,\dots,25\}\)（此時密文可以取 \(m\) 本身，金鑰 \(0\) 與 \(26-k\) 都給出可讀解）。所以只要在字典裡找「互為 Caesar 位移」的單字對，取最長者。

import string AL = string.ascii_lowercase def shift(w, k): return "".join(AL[(AL.index(ch) + k)

words = w.strip().lower() for w in open("/usr/share/dict/words") if w.strip().isalpha() and w.strip().islower() pairs = set() for w in words: for k in range(1, 26): v = shift(w, k) if v in words and v != w: pairs.add((len(w),) + tuple(sorted((w, v))) + (k,)) for p in sorted(pairs, reverse=True)[:12]: print(p)

結果（macOS 內建的 Webster’s Second 字典，約 23.5 萬字）——最長為 7 個字母：

C1.1cmL3.6cmC2.0cmL6.6cm 長度 & 單字對 & 位移 & 備註
& \(\leftrightarrow\) & 13（ROT13）& 最著名的 ROT13 單字對；兩者皆為一般英文字
7 & \(\leftrightarrow\) & 3 & primero 是一種紙牌遊戲（OED 有收）
7 & \(\leftrightarrow\) & 7 & 兩者皆罕見
6 & \(\leftrightarrow\) & 6 & 兩者皆為日常用字
6 & \(\leftrightarrow\) & 13 & purrel 罕見
6 & \(\leftrightarrow\) & 13 & becuna（一種魚）罕見
5 & \(\leftrightarrow\) & 9 & 日常用字
5 & \(\leftrightarrow\) & 9 & 日常用字
5 & \(\leftrightarrow\) & 7 & 日常用字
5 & \(\leftrightarrow\) & 7 & 日常用字
5 & \(\leftrightarrow\) & 13 & —
4 & \(\leftrightarrow\) ； \(\leftrightarrow\) ； \(\leftrightarrow\) & 3；11；10 & 日常用字

若只用一份 2 萬字的常用字表，最長是 6 字母的 ／，其次是上表的 5 字母對。還有一個三解的例子：密文 可解成 （\(\sk=0\)）、（\(\sk=7\)）與口語的 （\(\sk=6\)）。

建議的作答：「以單一英文單字而言，最長的雙解密文是 7 個字母，例如 \(c=\mathrm{nowhere}\) 可解為 （\(\sk=0\)）或 （\(\sk=13\)）；若限制為日常用字，則為 6 個字母的 \(c=\mathrm{layout}\)，可解為 （\(\sk=0\)）或 （\(\sk=6\)）。」

兩點討論：

  • 多字訊息可以無限延長。若允許多個單字，只要把同一位移的單字對串起來即可：位移 9 的「」\(\leftrightarrow\)「」（11 個字母）、ROT13 的「」\(\leftrightarrow\)「」……只是語句愈長愈不像「人類會寫的訊息」。這說明「人類可讀」沒有精確定義，暴力破解的成敗取決於攻擊者對明文的語言模型有多準。

  • 為什麼不會更長？依唯一解距離的估計，長度 \(L\) 的英文字串有一個 Caesar 位移也是英文字的機率約 \(25\cdot2^{-3.2L}\)：\(L=7\) 時約 \(5\times10^{-6}\)，而英文單字只有幾十萬個，所以 7 字母的例子已屬鳳毛麟角，8 字母以上的單字對預期不存在（在這份字典中確實沒有）。

(iv) 有加密預言機：一次查詢就夠

If an adversary has access to \(\Enc(\sk,\cdot)\) describe a (non brute force) attack against the Caesar cipher that does not need any ciphertexts.

敵手向預言機查詢 \(\Enc(\sk,\mathrm a)\)。因為 \(\mathrm a=0\)， \[c=\Enc(\sk,\mathrm a)=0+\sk\bmod 26=\sk .\] 一次查詢，直接讀出金鑰，之後所有密文都能解。更一般地，查詢任何已知的 \(m\)（哪怕只有一個字母）得 \(c\)，則 \(\sk=c_1-m_1\bmod26\)——不必嘗試 26 把金鑰，一步算出。

這是一個，而且是最強的那種結果：金鑰恢復（Week 1 的 ）。它甚至不需要「選擇」：任何一對已知的 \((m,c)\)（known plaintext）都夠，所以就算沒有預言機，只要猜中一個字（例如電報開頭的日期），Caesar 也立刻瓦解。

  • Caesar 的 \(\Enc\) 是確定性的，由定理 [thm:det-not-cpa] 它不可能 IND-CPA 安全；(iv) 給出的攻擊比定理的通用攻擊更強——不只分辨，還恢復金鑰。

  • Caesar 甚至不是 IND-EAV 安全的（§[sec:ind] 的例子：\(m_0=\mathrm{aa}\)、\(m_1=\mathrm{ab}\)，看密文兩字母是否相同）。注意這個攻擊不需要預言機也不需要暴力破解——這就是為什麼安全定義不以「金鑰不可恢復」為標準：Caesar 在 (i) 的情境下金鑰確實恢復不了，但它仍然處處洩漏。

  • 對任何確定性加密，加密預言機都讓敵手建立一本「碼書」（明文 \(\to\) 密文對照表）。Caesar 特別慘是因為它對金鑰是線性的：一個對照就決定全部。現代加密用隨機化（nonce）與非線性避免這兩點。

  1. 暴力破解需要：可枚舉的金鑰空間、可辨認的明文（冗餘或已知明文）、超過唯一解距離的密文長度。

  2. 冗餘愈低（縮寫、壓縮、隨機資料）暴力破解愈無力；一次性密碼本是極限（任何明文皆可能）。

  3. 有加密預言機時，確定性密碼可被建碼書；對 Caesar 一次查詢即恢復金鑰。