Enigma 是怎样被数学家破解的：置换群与共轭

全文分三层：

1. 通俗理解：Enigma 怎么工作，它的致命弱点
2. 实际用处：波兰的破译、图灵的 Bombe，以及对现代密码设计的影响
3. 数学原理：置换、轮换分解、共轭，Rejewski 的定理，附手算例子

第一层：通俗理解

1.1 Enigma 是一台"会换表的替换密码机"

最简单的替换密码：把字母表打乱，A→Q、B→W……这很好破，因为字母频率（E 最常见）会暴露它。

Enigma 的改进是：每按一个键，替换表就变一次。

• 转子：每个转子内部是一套固定的接线（一个置换）。每按一次键，最右边的转子转一格，像里程表一样进位。
• 反射器：把电流送回去，再穿过转子一次。
• 插线板：用电线交换 10 对字母，这一步贡献了绝大部分密钥空间。

总密钥数约为 $10^{23}$ 量级。德军认为它牢不可破。

1.2 两个"方便"带来的致命弱点

1. 加密和解密是同一个操作。因为反射器的存在，若 A 加密成 G，则 G 也加密成 A。操作员不用切换模式，很方便。
2. 没有字母会加密成它自己。这也是反射器造成的。

第二点后来被图灵团队大量利用：如果你猜到某段密文对应的明文（比如天气报告里一定有 "WETTER"），可以把这个词沿着密文滑动，凡是有字母对上自己的位置都可以排除。

1.3 第三个弱点：重复发送

1930 年代，德军每条消息开头把 3 个字母的"消息密钥"连发两遍（共 6 个字母），以防发报错误。这意味着第 1 和第 4 个密文字母来自同一个明文字母，第 2 和第 5、第 3 和第 6 也是。Rejewski 正是从这里切入的。

第二层：实际用处

• 情报（代号 Ultra）对大西洋战役影响巨大。常见的说法是它让战争缩短了两年左右，但这类估计很难精确验证。
• 布莱切利园后来又破译了更复杂的 Lorenz 密码机，为此建造了 Colossus，它是最早的可编程电子计算机之一。

对今天的启示：

第三层：数学原理

3.1 置换与轮换

26 个字母的所有置换构成对称群 $S_{26}$。任何置换都可以唯一地写成不相交轮换的乘积，比如

$$\sigma = (A\ C\ F)(B\ D)(E)\cdots$$

表示 A→C→F→A，B↔D，E 不动。各轮换长度组成的多重集叫轮换类型，例如上面是"一个 3-轮换、一个 2-轮换……"。

Enigma 的单次加密是一个没有不动点的对合：它由 13 个对换组成，自己乘自己等于恒等。这正是"加解密相同"（对合）和"没有字母加密成自己"（没有长度为 1 的轮换）的代数表述。

3.2 共轭不改变轮换类型

抽象代数里的一个基本事实：对任意 $\tau \in S_n$，

$$\tau\, (a_1\ a_2\ \cdots\ a_k)\, \tau^{-1} = \big(\tau(a_1)\ \tau(a_2)\ \cdots\ \tau(a_k)\big).$$

也就是说，共轭只是把轮换里的字母改个名字，轮换的长度一个都不变。所以 $\sigma$ 和 $\tau\sigma\tau^{-1}$ 的轮换类型完全相同。$S_n$ 中两个置换共轭，当且仅当它们轮换类型相同。

3.3 Rejewski 的观察

设某天第 $i$ 个位置的加密置换是 $E_i$，那么

$$E_i = S^{-1}\, T_i\, S,$$

其中 $S$ 是插线板（自己是对合，$S^{-1} = S$），$T_i$ 是转子加反射器在该位置的置换。

因为消息密钥发了两遍，若某个明文字母 $x$ 在位置 1 被加密成 $y_1$，在位置 4 被加密成 $y_4$，那么 $E_4 E_1$（$E_1$ 是对合，所以先用 $E_1$ 从 $y_1$ 回到 $x$）把 $y_1$ 送到 $y_4$。收集当天几十条消息的开头，就能把乘积置换 $E_4 E_1$ 完整写出来，而且不需要知道任何明文。

关键一步：

$$E_4 E_1 = S^{-1} T_4 S \cdot S^{-1} T_1 S = S^{-1}\,(T_4 T_1)\,S.$$

插线板 $S$ 只是在外面做了一次共轭。所以 $E_4E_1$ 的轮换类型等于 $T_4T_1$ 的轮换类型，完全不受插线板影响。

Rejewski 团队于是把转子顺序和起始位置的约 10 万种组合，逐一记录 $E_4E_1$、$E_5E_2$、$E_6E_3$ 的轮换类型，做成卡片目录（他们用的是一台叫"cyclometer"的装置）。每天截获消息后算出这三个轮换类型，查目录就能锁定转子设置，再单独解决插线板。

总结