跳转至
密码分析学 Part 2 of 16

第 2 章：恩尼格玛密码机的破解

频率分析、重合指数等技术的出现，说明单表代换或密钥流周期较短的密码已不能满足安全通信的需求。恩尼格玛 (Enigma) 密码机由德国发明家 Scherbius 于 1918 年设计，通过线路接线板与扰频器的随机排列可以产生高达 \(1.59\times10^{20}\) 种密钥，后来成为德军无线电秘密通信的主要手段。图灵在 Rejewski 等人工作的基础上，结合德军的语言习惯和 Enigma 的不随机特性，大大缩小了密钥搜索范围，实现了破解。

发布于 3,229 字 · 约 9 分钟

这一章我们用 Enigma 的破解来体会第一章所说的“区分”和“分割”：先用不随机特性识别明密文对应关系；再借助特殊的明密文对，把扰频器与线路接线板分割开，依次测试候选密钥；同时结合提前终止技术降低复杂度。Enigma 的结构见算法附录。

§ 01猜测明密文的对应

Enigma 的破解是唯密文攻击。按 Kerckhoffs 假设，攻击者能拿到 Enigma 机，反射器和各转子的置换表已知，但不知道线路接线板的设置 \(K_1\) 和扰频器的设置 \(K_2\)。所以第一步要先确定明密文的对应关系，才有判断密钥正确与否的依据。这一步利用的是下面的性质。

命题 1.1Enigma 的不随机特性

记 Enigma 的加密算法为 \(E\)，则对任意输入 \(\alpha\)，\(E(\alpha)\ne\alpha\)。

证明

反证。设 \(\alpha=E(\alpha)\)。记线路接线板为 \(S\)，扰频器组合为 \(R\)，反射器为 \(T\)，则

\[ \alpha=S^{-1}\circ R^{-1}\circ T\circ R\circ S(\alpha), \]

移项得 \(R\circ S(\alpha)=T\circ R\circ S(\alpha)\)。令 \(\gamma=R\circ S(\alpha)\)，即 \(\gamma=T(\gamma)\)，与反射器没有不动点矛盾。

注

同样由 \(T^2=\mathrm{id}\) 可得 \(E^2=\mathrm{id}\)，所以相同设置下加密和解密用同一台机器。这里的 \(E\) 指某一次按键时的置换；机器每按一次键都会步进，所以连续两个字母用的不是同一个 \(E\)。

德军每天早上 6 点后会发送一条加密的规范天气报告，所以 6 点零 5 分截获的密文几乎都含单词 WETTER（德语“天气”），且位置高度统一。结合上面的命题，就能猜出 WETTER 对应的密文。

例 1.2

截获包含 WETTER 的一段明文对应的密文为 AETJWPXER，求 WETTER 对应的可能密文。

解

从前往后依次猜测起点。WETTER 对齐前 6 个字母 AETJWP 时，E 被加密成了 E，与命题矛盾，不可能。右移一位对齐 ETJWPX，没有字母加密为自身，是一个候选。再右移得 TJWPXE，也是候选。

\[ \begin{array}{l|ccccccccc} \text{密文}&A&E&T&J&W&P&X&E&R\\\hline \text{起点 0}&W&\underline{E}&T&T&E&R&&&\\ \text{起点 1}&&W&E&T&T&E&R&&\\ \text{起点 2}&&&W&E&T&T&E&R& \end{array} \]

注

对应关系并不唯一，不能保证 \(100\%\) 的成功率。实际中还要结合通常的出现位置、消息结尾常用词等进一步排除；仍有多种时，就依次代入下一步的密钥恢复中尝试。

这样得到的明密文组合称为克利巴 (crib)。

习题 1.3

截获包含 HELLOWORLD 的一段明文对应的密文为 WELLDONEEFGHIJ，求 HELLOWORLD 对应的可能密文。

解

共 5 个可能的起点。起点 0（WELLDONEEF）中 L 对 L，起点 1（ELLDONEEFG）中 L 对 L，都被排除；起点 2、3、4 对应的 LLDONEEFGH、LDONEEFGHI、DONEEFGHIJ 都没有字母加密为自身，均为候选。

接下来要确定 \((K_1,K_2)\)，使它能把 WETTER 加密成 ETJWPX。最直接的办法是穷举每一种设置，但要试 \(1.59\times10^{20}\) 种，远超当时的计算能力。

§ 02恢复扰频器的设置

为降低复杂度，我们要分割密钥空间：找到只与部分密钥有关的区分器，先恢复这部分密钥，再结合穷举或其他方式恢复整个密钥。

2.1 利用环路实现分割

区分器不必只和一个明文字母与密文字母的对应有关，可以综合利用多个字母，只要能得到只与部分密钥有关的可验证条件即可。图灵发现的正是这样的现象。以 WETTER \(\to\) ETJWPX 为例：

\[ \begin{array}{c|cccccc} \text{位置}&0&1&2&3&4&5\\\hline \text{明文}&W&E&T&T&E&R\\ \text{密文}&E&T&J&W&P&X \end{array} \]

位置 0 有 W \(\to\) E，位置 1 有 E \(\to\) T，位置 3 有 T \(\to\) W，三个字母连成一个环 W \(\to\) E \(\to\) T \(\to\) W。这种特殊的明密文对应称为环路克利巴，它导致了组件的分割。（环路是否真实存在，取决于上一节猜得对不对。）

\((K_1,K_2)\) 在一天内不变，且 WETTER 出现得比较早，加密 W、E、T 时很可能只有快速转子转动。设扰频器组合是从 5 个转子中选 3 个放入，加密 W 时三个转子的起点为 \((x,y,z)\)，则

  1. 起点为 \((x,y,z)\) 时，把 W 加密成 E；
  2. 起点为 \((x-1,y,z)\) 时，把 E 加密成 T；
  3. 起点为 \((x-3,y,z)\) 时，把 T 加密成 W。

（转子位置模 26 计，例如 \(x=1\) 时 \(x-1\) 对应 26。）确定 \((x,y,z)\) 以及每个位置放哪个转子，就等价于恢复了 \(K_2\)。

可见环路实际上对应了三台 Enigma：\(K_1\) 相同，选同样的 3 个转子按同样的顺序放入，起点如上，每台只负责环路中的一次加密。设 W、E、T 经过线路接线板后的输出分别为 \(L_0,L_1,L_2\)（\(K_1\) 未知，所以它们未知）。在第一台机器中，W 经过接线板变成 \(L_0\)，\(L_0\) 经过扰频器组合、反射器、逆向扰频器组合后，必然得到 \(L_1\)，因为接线板把 \(L_1\) 与 E 连在一起。类似地，第二、三台的逆向扰频器输出分别为 \(L_2\) 和 \(L_0\)。

于是出现了一个新的环路

\[ L_0\xrightarrow{(x,y,z)}L_1\xrightarrow{(x-1,y,z)}L_2\xrightarrow{(x-3,y,z)}L_0, \]

它只与扰频器组合有关，与线路接线板无关！ 这就实现了组件的分割。

2.2 连接多台机器恢复扰频器

新环路消除了接线板的影响，但也引入了新问题：\(L_0,L_1,L_2\) 的值未知，没法直接建立关于密钥的方程，能用的只有“构成回路”这一特性。图灵的办法是：把第一台逆向扰频器输出端的 26 个字母与第二台扰频器输入端的 26 个字母用导线一一相连（A 到 A，B 到 B，…），二、三台与三、一台也同样连接，再在这 26 条回路上各装一个灯泡。

命题 2.1扰频器起点的判定依据

从 5 个转子中选 3 个，按同样的顺序放入上面连好的三台机器，起点关系如上（不妨从 \((x,y,z)=(1,1,1)\) 开始），拨动转子遍历 \((x,y,z)\)：

  • 若 \((x,y,z)\) 猜对，26 条回路中至少有一条灯亮；
  • 若 \((x,y,z)\) 猜错，26 条回路中以 \(63.2\%\) 的概率至少有一条灯亮。

习题 2.2

解释上面的 \(63.2\%\)。（提示：错排问题。）

解

三台机器串联起来是 26 个字母上的一个置换 \(\pi=\pi_3\circ\pi_2\circ\pi_1\)，某条回路灯亮当且仅当对应字母是 \(\pi\) 的不动点。猜对时 \(L_0\) 就是不动点。猜错时可以把 \(\pi\) 近似看作随机置换，没有不动点的概率是错排数与 \(26!\) 之比：

\[ \frac{D_{26}}{26!}=\sum_{j=0}^{26}\frac{(-1)^j}{j!}\approx e^{-1}\approx0.368, \]

所以至少有一条灯亮的概率约为 \(1-e^{-1}\approx63.2\%\)。

基于这一特性，只需观察是否亮灯，就能对 \(K_2\) 的

\[ \mathrm P_5^3\times26^3=60\times17576\approx2^{20} \]

种可能做出筛选，称为亮灯测试。若至少一条回路亮灯，则此时的设置为候选；若都不亮，一定是错误密钥。单个环路筛出的候选还比较多，可以用其他环路克利巴验证，或结合下一节对接线板的恢复继续筛选。另外，从 5 个转子中有序选 3 个这一步与遍历 \((x,y,z)\) 无关，图灵把它并行化了：同时开展 \(60\) 组测试，每组只需测 \(26^3=17576\) 种可能。

注

猜错时有 \(63.2\%\) 的概率误通过，一个环路只能淘汰约 \(37\%\) 的错误设置。若有 \(s\) 个相互独立的环路，错误设置全部通过的概率约为 \(0.632^s\)，所以需要多个环路才能把 \(2^{20}\) 个候选压到很少。

§ 03恢复线路接线板的设置

对接线板，我们主要依据下面的特性进行筛选。

命题 3.1线路接线板的判定依据

接线板的连线条数已知，且一根线只能连接两个字母，即不会出现 \(\alpha\leftrightarrow\beta\)、\(\beta\leftrightarrow\gamma\) 且 \(\alpha\ne\gamma\) 的情况。

设接线板有 10 条连线。在上一节猜测 \(K_2\) 时，若某条回路灯亮，就得到 \(K_2\) 的一个候选 \(k_2\)，在此 \(k_2\) 下还可以恢复接线板的部分设置：

  1. 灯亮的回路给出 \(L_0,L_1,L_2\) 的具体值 \(l_0,l_1,l_2\)，于是确定接线板有 W \(\leftrightarrow l_0\)、E \(\leftrightarrow l_1\)、T \(\leftrightarrow l_2\)（可能是自身到自身，即这个字母没接线）。若其中出现与命题矛盾的情况，说明 \(k_2\) 猜错，换下一条亮灯回路重复。
  2. 继续利用环路以外的明密文对 (T, J)、(E, P)、(R, X)：
    • 由 T \(\leftrightarrow l_2\) 与 \(k_2\)，可求得 \(l_2\) 经过扰频器、反射器、逆向扰频器的输出 \(l_3\)，于是接线板上有 J \(\leftrightarrow l_3\)；类似地确定 P \(\leftrightarrow l_4\)。
    • 对 R 和 X，若前面没有确定与它们有关的连线，就猜测：遍历与已有设置不冲突的 \(l_5\)（\(l_5\notin\{\mathrm{W,E,T,J,P},l_0,\cdots,l_4\}\)），设 R 与 \(l_5\) 相连，再确定 X \(\leftrightarrow l_6\)。

每一步若出现与命题矛盾的情况，就返回扰频器的恢复阶段。可见基于 WETTER 这个克利巴，至多恢复 7 条连线，不足以确定全部 10 条，还要结合其他克利巴；若仍不能全部确定，就穷举剩余连线解密，看明文是否有意义。

§ 04密钥恢复攻击

综上，整个密钥恢复过程如下。

定理 4.1算法（Enigma 的密钥恢复攻击）

  1. 根据已有的克利巴，找出全部环路克利巴，设有 \(s\) 个；
  2. 从 5 个转子中有序选 3 个（60 种选法可并行）；
  3. 对 \((x,y,z)=(1,1,1),\cdots,(26,26,26)\)：
    1. 对 \(s\) 个环路依次作亮灯测试；若通过，记录亮灯字母，得到接线板的部分连线；若与已有连线冲突，或某个环路不亮灯，就换下一个 \((x,y,z)\)；
    2. 若 \(s\) 个全部通过，在已确定连线下，用环路以外的明密文对继续恢复接线板；若出现冲突，换下一个 \((x,y,z)\)；
    3. 若连线已达 10 条，用此设置解密密文，若明文有意义则输出 \((K_1,K_2)\)；若不足 10 条，则依次猜测未确定的连线并解密，直到明文有意义，若全部是乱码就换下一个 \((x,y,z)\)；
  4. 若所有 \((x,y,z)\) 都不通过，换一种转子选法，回到第 3 步。

在当时的条件下，纯人工完成上述算法仍很难在一天内做完。图灵因此设计了能加快检测速度的机械装置，为了向波兰的破译机致敬，取名为“炸弹 (Bombe)”。每个“炸弹”由 12 组相连的 Enigma 组成，可以处理更长的环路克利巴，投入使用后大约 20 分钟就能恢复 Enigma 的密钥。

回顾整个过程，已经蕴含了现代密码分析的两个关键要素：

  • 区分：Enigma 绝不会把字母加密为自身，这被用来识别明密文对应关系，是后续攻击的前提；
  • 分割：利用环路克利巴把接线板和扰频器剥离开，先单独搜索扰频器（还可以并行），再求解接线板，把计算上不可行的问题变成了实际可破解的问题。

参考：王美琴主编，《密码分析学》，科学出版社，2024，第 2 章。

完

评论

查看图表
本文目录