Enigma 密码破解
背景
Enigma 机是二战时德军使用的加密装置。它拥有三个可以转动的转子，一个固定的反射器，插线板，键盘，灯板等组件。插线板能够交换两个字母，转子可以将一个字母映射为另一个字母。这都是通过电路实现的。使用者点击键盘上的按键输入明文字母后，机器中电池产生的电流将通过插线板、三个转子、反射器，然后折返，再次通过三个转子和插线板，将灯板上的密文字母对应的灯泡点亮。每次按下按键时，转子会产生旋转，并且在到达特定位置时会产生进位。因此，每次加密时导通的电路会发生变化，使得 Enigma 机的加密过程难以被破解。Enigma 的实现和软件模拟器可以参考前面的文章自己打造一台恩尼格玛密码机。
在二战后期，德军使用的 Enigma 机允许操作者从多个转子中选择 3 个，每个转子有 26 种初始位置，并且插线板上可以交换 10 组字母。这产生了一个巨大的密钥空间，看上去使 Enigma 机坚不可摧。然而，波兰数学家 Rejewski 在 30 年代就发现了 Enigma 机操作流程上存在的弱点，并针对其设计了破解方法。在二战爆发后，相关的技术被共享给了盟军的情报机构，但德军也加强了 Enigma 密码的安全性。英国数学家和计算机科学家 Turing 进一步地设计了已知明文攻击的方法，成功破解了 Enigma 机，为世界反法西斯战争的胜利做出了重要的贡献。笔者复现了 Rejewski 和 Turing 破解 Enigma 机使用的方法，并将在本文中详细介绍。
算法原理
Rejewski 的破解方法
在上世纪三十年代，Enigma 机的操作流程是：每天所有人都会使用相同的日密钥，但日密钥不用于加密信息；在发送一条信息时，操作者需要先随机生成三个字母的信息密钥。操作者会首先使用日密钥，将信息密钥输入两次，产生的 6 个字母的密文作为开头。随后，操作者将机器的转子调整为信息密钥所对应的转子位置，并开始加密信息。信息密钥输入两次的原因是为了避免信息传输中因为干扰出现错误，收信方如果发现通过日密钥解码出的前 6 个字母明文不是重复两次的格式，则可以发现问题。但是，重复是加密的敌人，Rejewski 敏锐地观察到了这一点。第一个字母和第四个字母是同一个明文加密出来的，并且输入第一个字母时，转子的设置都是日密钥，是完全相同的。于是，在某一天中收到的所有由 Enigma 机加密的密文，都会满足类似这样的规则：
- 如果第 1 个字母为 A，那么第 4 个字母为 E；
- 如果第 1 个字母为 B，那么第 4 个字母为 L；
- 如果第 1 个字母为 C，那么第 4 个字母为 C；
- …
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| E | L | C | O | N | W | D | I | A | P | K | S | Z | H | … |
表：密文的第一个字母和第四个字母的对应表格（部分）
将结果列出，如上表所示。Rejewski 发现，表中的字母存在一些 “链”，例如，上一行的字母 A 对应下一行的字母 E，上一行的字母 E 对应下一行的字母 N，以此类推，最后又回到字母 A。这样就产生了字母链 AENHI。同时，也可以找到其它的字母链：BLSJP，C，DOFWVG，K，MZURTY，Q，X。如果机器的初始状态相同，那么得到的字母链自然也是相同的。更重要的是，Rejewski 发现，插线板的存在只会改变字母链中的字母，但不会影响各个字母链的长度。
例如，在上面的场景中，额外将 A 和 C 之间加入一条接线，那么，原先的 AENHI 链会变为 CENHI，C 链会变为 A 链；但两条链的长度是不变的。因此，字母链的长度特征是插线板作用下的不变量，它只和转子的初始位置有关，由此可以将插线板的作用和转子的初始位置解耦合。波兰的破译团队用了一年的时间进行预计算，得到了所有转子初始位置与字母链的长度的对应关系。此后，在收到新的密文后，破译者可以查表，将字母链的长度与预计算的结果进行比较，得到可能的转子的初始位置。在成功恢复出转子初始位置后，破译者可以对密文进行解密，之后进一步地分析插线板的状态。具体的算法原理如下。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35输入：前6个密文字母的对应表格 T
输出：解集 Solutions
预计算阶段：
----------------------------------------
# 由波兰 Bomba 机模拟的 Enigma 机
E ← Enigma()
# 存储的数据库，用于之后查表
Database ← Map()
for each S in PossibleSettings:
E.setPosition(S)
C ← FindChainsByEnigma(E)
Database.store(S, C)
破解过程：
----------------------------------------
Solutions ← Set()
for each S in PossibleSettings:
Matched ← true
for i ← 1 to 3:
Chain ← FindChainsInTableRow(T[i], T[i+3])
Expected ← Database.get(S + i)
if Chain ≠ Expected:
# 字母链没有通过检验
Matched ← false
if Matched = true:
# 当前初始状态对应的字母链通过了检验
# 将可能的解加入解集
Solutions.add(S)
