正式定義（講義 pp. 9–10）
集合 \(X\) 上的是雙射 \(\pi\colon X\to X\)；所有排列的集合記為 \(\Perm(X)\)（Week 2 寫成 \(\mathrm{Sym}(X)\)）。 ：字母表 \(\alpha\)， \[\calK=\Perm(\alpha),\qquad \calM=\calC=\alpha^* .\]
\(\KGen\)：從 \(\calK\) 均勻抽出 \(\sk\)（一個排列）。
\(\Enc(\sk,m)\)：拆 \(m=m_1\cdots m_\ell\)；對 \(i\in[\ell]\) 令 \(c_i=\sk(m_i)\)；回傳 \(c=c_1\cdots c_\ell\)。
\(\Dec(\sk,c)\)：拆 \(c=c_1\cdots c_\ell\)；對 \(i\in[\ell]\) 令 \(m_i=\sk^{-1}(c_i)\)；回傳 \(m=m_1\cdots m_\ell\)。
正確性：\(\sk^{-1}(\sk(x))=x\)，因為 \(\sk\) 是雙射所以反函數存在且唯一。
金鑰最方便的寫法是兩列表（講義 p. 9）：上列是 \(\alpha\) 的自然順序，下列是它們的像；加密「由上往下」查，解密「由下往上」查——這就是 \(\pi^{-1}\)。
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
密文 & f&b&z&&a&v
用 §1.3 的 Fisher–Yates 程式（種子 2025）抽出一把金鑰：
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
密文 & x&i&w&v&e&s&j&k&n&d&z&t&b&o&g&y&h&m&l&a&q&f&p&u&c&r
則 \(\Enc(\sk,\ct{the quick brown fox jumps over the lazy dog})=\ct{ake hqnwz imgpo sgu dqbyl gfem ake txrc vgj}\)。 解密時查下列找上列：\(\ct{a}\mapsto\ct{t}\)、\(\ct{k}\mapsto\ct{h}\)、\(\ct{e}\mapsto\ct{e}\)（\(\ct{e}\) 恰好是這把金鑰的不動點）…… 注意兩個 都變成 ：同一個明文片段永遠給同一個密文片段。
討論：金鑰空間的大小（講義 p. 11）
Caesar 的 26 把金鑰每一把都是一個排列（位移），所以 Caesar 的金鑰空間是 \(\Perm(\alpha)\) 的子集；替換密碼只是「允許任意排列」。 \[\abs{\calK}=\abs{\Perm(\alpha)}=\abs\alpha!\,,\qquad 26!=403{,}291{,}461{,}126{,}605{,}635{,}584{,}000{,}000\approx4.03\times10^{26}\approx2^{88.4}.\] （第一個字母有 26 種像，第二個剩 25 種……，乘法原理；Week 2 命題 4.1 (c)。）
若每秒能試 \(10^{12}\) 把金鑰（一台很強的 GPU 叢集），試完 \(26!\) 把需要 \(4\times10^{14}\) 秒 \(\approx1.3\times10^7\) 年。 暴力搜尋確實不可行——但 §[sec:cryptanalysis] 會看到，69 個字母的密文用頻率分析幾分鐘就能手動破解。 「金鑰空間大」只封住了講義 p. 8 的第一個弱點。
討論：如何均勻抽出一個排列？（講義 p. 11）
這次不能只擲五枚硬幣了。標準做法是 Fisher–Yates 洗牌（Fisher & Yates 1938 的統計表；Durstenfeld 1964 給出就地版本，Knuth《The Art of Computer Programming》稱為 Algorithm P）：
Input : alphabet as an array A[0..25] = (a, b, ..., z) for i = 25 down to 1: j <- uniform integer in 0, 1, ..., i # rejection sampling! swap A[i] and A[j] Output: sk = the permutation x_k -> A[k] # A is now a uniform permutation
若每一步的 \(j\) 都在 \(\{0,\dots,i\}\) 上均勻且各步獨立，則輸出的排列在 \(\Perm(\alpha)\) 上均勻。
Proof. 演算法共做 \(25\) 次選擇，可能的選擇序列有 \(26\cdot25\cdots2=26!\) 條，每條機率 \(\prod_{i=1}^{25}\frac1{i+1}=\frac1{26!}\)。 不同的選擇序列給出不同的排列（第 \(i\) 步決定「哪個元素落在位置 \(i\)」，之後不再動它），而排列總數也是 \(26!\)，所以選擇序列與排列一一對應，每個排列機率恰為 \(1/26!\)。 ◻
錯誤的洗牌：「對每個位置 \(i\)，和整個陣列中隨機一個位置交換」。這給出 \(26^{26}\) 條選擇序列，而 \(26!\nmid26^{26}\)，所以不可能每個排列等機率（Week 2 的鴿籠原理）。
模偏差：用 取 \(j\)。與 §[sec:caesar] 相同的問題。
關鍵字字母表：許多教科書用一個關鍵字（如 ）生成排列。好記，但金鑰空間從 \(26!\) 縮成「英文單字的數量」，而且敵手猜出前幾個對應就能推出其餘——這違反 。
import random def fisher_yates(seed=None): rng = random.Random(seed) # demo only; use ‘secrets‘ for real keys A = list("abcdefghijklmnopqrstuvwxyz") for i in range(25, 0, -1): j = rng.randint(0, i) # Python’s randint is unbiased A[i], A[j] = A[j], A[i] return "".join(A) # image of a, b, ..., z in order
print(fisher_yates(2025)) # -> xiwvesjkndztbogyhmlaqfpucr
討論：潛在弱點（講義 p. 12）
L4.6cmL9.8cm 弱點 & 說明
message, ciphertext pairs give information about \(\sk\) & 講義刻意把 Caesar 的「give \(\sk\)」改成「give information about \(\sk\)」：一對 \((m_i,c_i)\) 只透露排列表的一格。要拿到整把金鑰，需要 26 個明文字母都出現過；但實務上拿到十幾格就足以讀懂其餘密文。
frequency analysis & 每個明文字母仍被送到固定的密文字母，所以字母的頻率分布只是被重新貼標籤：最常出現的密文字母大概就是 （§[sec:cryptanalysis]）。
(more fundamentally) deterministic encryption & 與 Caesar 完全相同：\(m_0=\ct{aa}\)、\(m_1=\ct{ab}\) 即可區分。確定性是結構性的缺陷，換再大的金鑰空間也救不了。
講義最後一句話是下一節的動機：「如果能在維持大金鑰空間的同時，讓頻率分析變得更困難呢？」——答案（Vigenère）會告訴我們，「更困難」和「安全」之間還差得很遠。
若把訊息空間限制成單一字母 \(\calM=\alpha\)，則對均勻的 \(\sk\in\Perm(\alpha)\)，無論 \(m\) 是什麼，\(c=\sk(m)\) 在 \(\alpha\) 上都是均勻分布（每個 \(c\) 恰有 \(25!\) 把金鑰把 \(m\) 送到它）。 依 §[sec:perfect] 的定義，這是完美保密的（KL-IMC 習題 2.9）！Caesar 限制成單一字母也一樣（Shannon 定理：\(\abs\calK=\abs\calM=\abs\calC=26\)，每對 \((m,c)\) 恰有一把金鑰）。 所以三個歷史密碼的問題都不在「一個字母怎麼加密」，而在同一把金鑰被用在許多字母上——金鑰重用，正是本週反覆出現的主題。
約 9 世紀，巴格達的博學者 al-Kindī（約 801–873）在《解讀密文手稿》（Risāla fī Istikhrāj al-Muʿammā）中描述了頻率分析——已知最早的破譯方法，比 Caesar 晚了九百年、比下一個突破（Kasiski）早了一千年。
1586 年，蘇格蘭女王 Mary 與 Babington 密謀的信件使用替換密碼加上代碼字（nomenclator），被 Walsingham 的密碼專家 Phelippes 破譯，成為她被處決的證據。
文學裡的替換密碼：Poe〈金甲蟲〉（1843）、Conan Doyle〈跳舞的人〉（1903）都以頻率分析為情節核心——主角第一步都是「最多的符號是 」。