(i) 用三個密碼加密與解密
For each cipher in HISTORICAL-CIPHERS use it to encrypt and decrypt a message of your choice.
三個例子已分別在 §[sec:caesar]、§[sec:mono]、§[sec:vigenere] 逐字母算過，這裡彙整並附上可直接執行的程式。
L1.5cmL3.4cmL4.1cmL4.1cm & 金鑰 & 明文 \(\to\) 密文 & 解密檢查
Caesar & \(\sk=3\) & \(\to\) & 每字母 \(-3\)：\(\to\)、\(\to\)…
替換 & \(\sk=\)
（ 的像） & \(\to\) & 查反表 \(\sk^{-1}\)：\(\to\)、\(\to\)、\(\to\)…
Vigenère & \(\sk=\) \(=(10,2,11)\) & \(\to\) & 第 \(i\) 個字母減 \(\sk_{((i-1)\bmod3)+1}\)
import string A = string.ascii_lowercase def num(ch): return A.index(ch)
def caesar(text, k, dec=False): s = -k if dec else k return "".join(A[(num(ch)+s)
def mono(text, key, dec=False): # key: 26-letter string, image of a..z table = dict(zip(key, A)) if dec else dict(zip(A, key)) return "".join(table.get(ch, ch) for ch in text)
def vigenere(text, key, dec=False): # spaces are kept as-is and do NOT consume key letters ks = [num(ch) for ch in key]; out = []; j = 0 for ch in text: if ch in A: s = -ks[j out.append(A[(num(ch)+s) else: out.append(ch) return "".join(out)
c = caesar("veni vidi vici", 3) # -> yhql ylgl ylfl assert caesar(c, 3, dec=True) == "veni vidi vici"
k = "xiwvesjkndztbogyhmlaqfpucr" c = mono("the quick brown fox jumps over the lazy dog", k) assert mono(c, k, dec=True).startswith("the quick")
c = vigenere("kings college london", "kcl") # -> ukyqu nynwoip vqynqy assert vigenere(c, "kcl", dec=True) == "kings college london"
(ii) Caesar 密文
46 個字母、13 個單字。三種方法都能在一分鐘內解開，依「越省力越前面」排列：
方法 A：單字母單字。
單獨成字出現四次。英文的單字母單字只有 、（詩句中偶有 ），所以 \[\sk=\ct{w}-\ct{a}=22,\qquad \sk=\ct{w}-\ct{i}=22-8=14,\qquad \sk=\ct{w}-\ct{o}=22-14=8 .\] 只需試三把金鑰。\(\sk=22\) 給 、\(\sk=14\) 給 ，都不是英文；\(\sk=8\) 給出答案。
方法 B：trace（講義 p. 22）。
出現四次，是最值得攻擊的單字。\(\trace(\ct{jtcm})=(\ct{t}-\ct{j},\ct{c}-\ct{t},\ct{m}-\ct{c})=(10,-17,10)=(10,9,10)\)。 在常見四字母單字中找 trace \((10,9,10)\)： 的 trace 是 \((\ct{l}-\ct{b},\ct{u}-\ct{l},\ct{e}-\ct{u})=(10,9,-16)=(10,9,10)\) ✓。於是 \(\sk=\ct{j}-\ct{b}=9-1=8\)，一次比對就得到金鑰。
方法 C：暴力搜尋（講義 p. 19）。
26 把金鑰全試，用「像不像英文」當 \(\Dec\) 的檢查：
| \(\sk\) | \(\Dec(\sk,c)\) | \(\sk\) | \(\Dec(\sk,c)\) |
|---|---|---|---|
| 0 | w jtcm kwum nwzbp w jtcm izqam … | 13 | j wgpz xjhz ajmoc j wgpz vmdnz … |
| 1 | v isbl jvtl mvyao v isbl hypzl … | 14 | i vfoy wigy zilnb i vfoy ulcmy … |
| 2 | u hrak iusk luxzn u hrak gxoyk … | 15 | h uenx vhfx yhkma h uenx tkblx … |
| 3 | t gqzj htrj ktwym t gqzj fwnxj … | 16 | g tdmw ugew xgjlz g tdmw sjakw … |
| 4 | s fpyi gsqi jsvxl s fpyi evmwi … | 17 | f sclv tfdv wfiky f sclv rizjv … |
| 5 | r eoxh frph iruwk r eoxh dulvh … | 18 | e rbku secu vehjx e rbku qhyiu … |
| 6 | q dnwg eqog hqtvj q dnwg ctkug … | 19 | d qajt rdbt udgiw d qajt pgxht … |
| 7 | p cmvf dpnf gpsui p cmvf bsjtf … | 20 | c pzis qcas tcfhv c pzis ofwgs … |
| 8 | o blue come forth o blue arise … | 21 | b oyhr pbzr sbegu b oyhr nevfr … |
| 9 | n aktd bnld enqsg n aktd zqhrd … | 22 | a nxgq oayq radft a nxgq mdueq … |
| 10 | m zjsc amkc dmprf m zjsc ypgqc … | 23 | z mwfp nzxp qzces z mwfp lctdp … |
| 11 | l yirb zljb cloqe l yirb xofpb … | 24 | y lveo mywo pybdr y lveo kbsco … |
| 12 | k xhqa ykia bknpd k xhqa wneoa … | 25 | x kudn lxvn oxacq x kudn jarbn … |
只有一列讀得通——46 個字母遠超過 Caesar 的唯一解距離（約 1.5 個字母）。
答案。
\(\sk=8\)（字母 ），明文：
出自 Derek Jarman 的電影《Blue》（1993）——全片畫面只有一片 International Klein Blue，旁白是 Jarman 失明前寫下的文字；這句是開場的吟誦「O Blue come forth / O Blue arise / O Blue ascend / O Blue come in」。
(iii) 單字母替換密文
69 個字母、16 個單字、14 個不同的密文字母。暴力搜尋 \(26!\) 不可行，用講義 p. 20 的頻率分析，一步一步來。
第 0 步：統計。
| 密文字母 | ||||||||||||||
| 次數 | 13 | 10 | 9 | 7 | 7 | 6 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 |
| % | 18.8 | 14.5 | 13.0 | 10.1 | 10.1 | 8.7 | 4.3 | 4.3 | 4.3 | 2.9 | 2.9 | 2.9 | 1.4 | 1.4 |
單字長度：\(4,3,5,4,1,8,3,8,7,4,3,5,4,2,3,5\)。重複的單字：（\(\times2\)）、（\(\times2\)）、（\(\times2\)）、（\(\times2\)）、（\(\times2\)）。
第 1 步：最多的字母是 。
佔 18.8%，遠高於其他，猜 \(\ct{t}\mapsto\ct{e}\)。
第 2 步：單字母單字。
單獨成字，而且是第二高頻（14.5%）：\(\ct{q}\mapsto\ct{a}\)（ 是最常見的單字母單字且頻率 8.2%； 也可能，先記著）。
第 3 步：三字母單字 。
出現兩次、結尾是 \(=\)：最常見的三字母單字 完全吻合 \(\Rightarrow\) \(\ct{z}\mapsto\ct{t}\)、\(\ct{i}\mapsto\ct{h}\)。檢查頻率： 10.1%、 10.1% 與 t、h 的高頻一致。
第 4 步：用已知字母擴散。
現在密文變成（大寫為已知）：
HEqr qfr Hqfrl fEEr A dEroAToK THE dEroAToK wETvEEf HEqr qfr Hqfrl dxlT wE THE HEAkT
\(=\) ：只能是 \(\Rightarrow\) \(\ct{k}\mapsto\ct{r}\)。
\(=\) ，出現兩次且夾在兩個同樣的單字之間： \(\Rightarrow\) \(\ct{f}\mapsto\ct{n}\)、\(\ct{r}\mapsto\ct{d}\)。頻率檢查： 13%、 8.7%—— 在這段文字裡偏高，但短文本本來就會偏離平均（見下方警告）。
\(=\) ✓（兩次）； \(=\) \(\Rightarrow\) ，\(\ct{l}\mapsto\ct{s}\)； \(=\) ✓。
\(=\) （ 介於 、 之間， 介於 、 之間）： \(\Rightarrow\) \(\ct{d}\mapsto\ct{m}\)、\(\ct{o}\mapsto\ct{i}\)、\(\ct{g}\mapsto\ct{o}\)。
\(=\) ： \(\Rightarrow\) \(\ct{w}\mapsto\ct{b}\)、\(\ct{v}\mapsto\ct{w}\)。 \(=\) ✓。
\(=\) ： \(\Rightarrow\) \(\ct{x}\mapsto\ct{u}\)。
答案。
出自 Fritz Lang 的《Metropolis》（大都會，1927）的題詞與結尾字幕：「Mittler zwischen Hirn und Händen muss das Herz sein」——「頭腦與雙手之間的中介必須是心」。
還原的金鑰（部分）。
r|*26@ c@ 明文 & a&b&c&d&e&f&g&h&i&j&k&l&m&n&o&p&q&r&s&t&u&v&w&x&y&z
密文 & q&w&?&r&t&?&?&i&o&?&?&?&d&f&g&?&?&k&l&z&x&?&v&?&?&?
只確定了 \(14/26\) 格。其餘 12 個明文字母 \(\{\ct{c,f,g,j,k,l,p,q,v,x,y,z}\}\) 與 12 個未出現的密文字母 \(\{\ct{a,b,c,e,h,j,m,n,p,s,u,y}\}\) 之間有 \(12!\approx4.8\times10^8\) 種對應都與密文一致——訊息唯一，金鑰不唯一。這是替換密碼「一對 \((m,c)\) 只給出 \(\sk\) 的資訊」（講義 p. 12）的具體寫照；若要完整金鑰，需要更多密文。
這段只有 69 個字母，第二、三高頻的密文字母對應到 （14.5%）與 （13%），而非英文平均的 、。單純把「頻率排名」一一對應會失敗（只有 可靠）。有效的做法是頻率 + 單字結構 + 重複模式交替使用，每猜一個字母就回頭驗證全文——這就是講義「需要足夠但出奇地少的密文」的實際含義。
(iv) Vigenère 密文（金鑰長度 3）
180 個字母。題目已給金鑰長度 \(3\)，但我們先示範如何自己找出來，再依講義 p. 21 分流攻擊。
第 1 步：確認金鑰長度（Friedman 的 \(\IC\) 檢驗）。
整段密文的 \(\IC=0.0467\)——介於英文（0.0655）與隨機（0.0385）之間，是多字母表密碼的指紋。對每個候選週期 \(p\)，把密文分成 \(p\) 條子密文，計算平均 \(\IC\)：
\(p=3\)（及其倍數 \(6\)、\(9\)）明顯跳回英文水準，其餘停在 \(0.045\) 左右 \(\Rightarrow\) 金鑰長度 \(3\)。
Kasiski 檢驗找重複的三字母以上片段：只有 （位置 6、96，距離 90）與 （位置 9、25，距離 16）。\(\gcd(90,16)=2\)——錯誤答案！距離 90 \(=3\times30\) 確實支持 3，但 16 是巧合。180 個字母太短，巧合重複淹沒了真正的訊號；\(\IC\) 檢驗用所有字母的統計量，穩健得多。
第 2 步：分成三條子密文（講義 p. 21）。
忽略空白，第 \(1,4,7,\dots\) 個字母為子密文 1，第 \(2,5,8,\dots\) 為子密文 2，第 \(3,6,9,\dots\) 為子密文 3，各 60 個字母。各自的字母計數：
| 子密文 1 | 3 | 1 | 5 | 4 | 1 | 4 | 4 | 5 | 3 | 1 | 4 | 1 | 1 | 2 | 10 | 1 | 3 | 7 | ||||||||
| 子密文 2 | 2 | 4 | 3 | 2 | 3 | 4 | 7 | 2 | 1 | 1 | 4 | 2 | 2 | 6 | 2 | 2 | 4 | 4 | 1 | 4 | ||||||
| 子密文 3 | 1 | 11 | 1 | 1 | 2 | 6 | 2 | 4 | 2 | 4 | 6 | 2 | 3 | 7 | 1 | 1 | 4 | 2 |
第 3 步：每條子密文都是 Caesar，求位移。
子密文 1：最多的是 （10 次）。若 \(=\)，位移 \(=21-4=17=\) 。\(\chi^2\) 檢驗：\(k=17\) 的 \(\chi^2=9.0\)，第二名 \(k=23\) 高達 \(215\)——毫無懸念。
子密文 2：最多的是 （7 次）。若 \(=\)，位移 \(=7-4=3=\) ，但 \(\chi^2_{3}=365\)，非常差。\(\chi^2\) 最小的是 \(k=14=\) （\(\chi^2=11.5\)，第二名 \(237\)）。檢查：以 \(k=14\) 解密後 \(\to\)（7 次）、\(\to\)（6 次）——這條子密文裡 恰好比 多一次。「最多的字母就是 e」在 60 個字母的樣本上會失誤；\(\chi^2\) 用全部 26 個頻率，不會。
子密文 3：最多的是 （11 次）。\(=\) 給位移 \(2-4=-2=24=\) ；\(\chi^2_{24}=19.1\)，第二名 \(185\) ✓。
金鑰 \(\sk=(17,14,24)=\) 。
第 4 步：解密。
注意題目「為了方便保留了空白」：空白不佔金鑰位置——第 \(i\) 個字母（跳過空白計數）用 \(\sk_{((i-1)\bmod3)+1}\)。前幾個字母：\(\ct{z}-\ct{r}=25-17=8=\ct{i}\)、\(\ct{j}-\ct{o}=9-14=-5=21=\ct{v}\)、\(\ct{c}-\ct{y}=2-24=-22=4=\ct{e}\)、\(\ct{j}-\ct{r}=9-17=18=\ct{s}\)……
出自《Blade Runner》（銀翼殺手，1982）結尾、複製人 Roy Batty（Rutger Hauer 飾）臨終的「Tears in rain」獨白——金鑰 正是他的名字。
（若誤把空白也算進金鑰位置，會得到 ：開頭的 與 剛好在位置對齊時正確，其餘是亂碼——這種「偶爾對、大多錯」的輸出正是計數方式弄錯的徵兆。）
程式化的完整流程。
import string, collections A = string.ascii_lowercase ENG = [8.17,1.49,2.78,4.25,12.70,2.23,2.02,6.09,6.97,0.15,0.77,4.03,2.41, 6.75,7.51,1.93,0.10,5.99,6.33,9.06,2.76,0.98,2.36,0.15,1.97,0.07]
def ioc(seq): n = len(seq); cnt = collections.Counter(seq) return sum(v*(v-1) for v in cnt.values()) / (n*(n-1))
def chi2(seq): # how far is seq from English? n = len(seq); cnt = collections.Counter(seq) return sum((cnt[ch] - n*p/100)**2 / (n*p/100) for ch, p in zip(A, ENG))
def crack_vigenere(ct, max_len=10): L = [ch for ch in ct if ch in A] # drop spaces period = max(range(1, max_len+1), key=lambda p: sum(ioc(L[i::p]) for i in range(p)) / p) key = [] for i in range(period): stream = L[i::period] best = min(range(26), key=lambda k: chi2([A[(A.index(ch)-k) key.append(best) out, j = [], 0 for ch in ct: if ch in A: out.append(A[(A.index(ch) - key[j else: out.append(ch) return "".join(A[k] for k in key), "".join(out)
print(crack_vigenere("zjc jsce hfzbej mml dcfdjv ...")) # -> (’roy’, ’ive seen things ...’)
Caesar：任何一點結構（單字母單字、重複單字、trace）都足以一擊致命；暴力搜尋只是保底。
替換：\(2^{88}\) 的金鑰空間毫無幫助；69 個字母就夠用頻率 + 單字模式破解。而且攻擊者不需要整把金鑰。
Vigenère：先用統計量（\(\IC\)）找週期，再分而治之；用 \(\chi^2\) 而非「最多的就是 e」；小心空白等格式細節。
三者都只用到密文與語言先驗——講義 p. 20 的兩個前提——這是最弱的攻擊模型（COA）。