密码风云 “谜”与“如谜的解谜者”(九)

雷耶夫斯基设计的循环测定机示意图（1934～1935年）

花卷

科普作者，资深技术图书译者，译有《图解密码技术》《代码的未来》等。

小雷的格子法

小雷使出神之一手，推算出来德国军用版Enigma全部3个转轮的接线方式，这真的是立了一个大功。Enigma的三个秘密——转轮、每日密钥、指标组，其中转轮的秘密已经被完全破解，而指标组是用每日密钥加密的，因此只要破解了每日密钥，指标组也就不是秘密了。

看到这里你可能要问了，法国情报局不是有个神通广大的“德奸”施密特潜伏在德国密码局吗？如果能继续偷到每日密钥的表格，那不就大功告成了吗？怎么说呢，天下没有不透风的墙，间谍这种事情，做多了早晚会被人察觉和提防，而且施密特也并没有那么神通广大，之前他也只能拿到已经过期失效的密钥表格，那些过时的信息可以帮助小雷解开他的置换方程组，却没办法帮助波兰人破译此时此刻正在满天飞的德军密电。

回到正题，每日密钥现在成了唯一的秘密，小雷他们必须集中精力打败这个最终BOSS。我们先来回忆一下，每日密钥到底包合哪些内容。首先，Enigma一共有3个转轮，这3个转轮是可以拆卸并交换位置的，因此每日密钥需要规定3个转轮从左至右的安装顺序（Walzenlage）;其次，就是这3个转轮各自的初始位置（Grulndstellung）;第三，每个转轮的接线方式是可以偏移的，转轮外侧有一个带刻度的圆环，转动圆环可以让接线方式偏移0到25个位置，因此每日密钥还规定了圆环的位置（Ringstellung）;最后，别忘了军用版Enigma还有一个恶心的连接板，它可以将输入的字母两两交换，因此每日密钥中还需要规定连接板的接法（Steckerverbindungen）。

在此之前，小雷已经利用群论等数学方法，将电文的前6个字母，也就是加密后的指标组，写成了6个置换方程，只要有足够的电文资料，就可以计算出当天指标组的“特征结构”，也就是Enigma在这6个字母位置上的置换关系。我们前面也提到过，大部分情况下，加密指标组为6个字母时，只有最右侧的转轮会步进，左侧和中间的两个转轮都是固定不动的，再加上反射器本来就是固定不动的，那么我们就可以认为，“中间转轮→左侧转轮→反射器→左侧转轮→中间转轮”这整个一条路径，对于加密指标组的过程来说，都是固定不变的。

固定不变的东西，也就是可以忽略的东西了，于是小雷又推出一组方程，具体的内容我们不写，大致的意思是，6个字母指标组的置换，分别与右侧转轮的置换、当前右侧转轮所在位置，以及连接板的置换进行运算，所得到的6组置换，应该是完全相同的。这些条件里面，右侧转轮的置换，其实就是右侧转轮的接线方式。虽然我们不知道3个转轮里面哪个放在右侧，但既然3个转轮的接线方式都已经知道了，无非只有3种可能性而已。而右侧转轮所在位置，也只有26种可能性而已。至于连接板，由于当时德军只交换6对字母，所以对结果的干扰不算太大，稍微努力一下还是可以克服的。

于是，小雷要做的，就是尝试所有的可能性，找到一种特定的情况，使得计算出的6组置换是非常相似的（由于连接板的存在，因此6组置换不是完全相等的），这也就意味着破解了右侧转轮的编号以及它的初始位置，而最后一个未知数，也就是连接板的接法，自然就随之迎刃而解了。当然了，这个原理说起来简单，实际计算起来却是非常费时费力的。于是小雷就发明了一套工具，把每个转轮的26个位置所计算出的置换结果印在底纸上，然后将通过电文计算出来的6组指标组置换写在另一张纸上，并在纸上裁出6条格子，然后盖在印有转轮置换的底纸上。这样一来，只要逐行移动上面一张纸的位置，就可以更快地比对出具备一定相似性的置换。

神秘的ANX

一旦破解了右侧转轮和连接板，剩下的两个转轮就简单多了，因为它们的位置几乎是固定不变的，而且也不受连接板的干扰。剩下两个转轮当然也可以用小雷的格子法来搞定，但是既然它们的置换是固定的，那我事先把所有的置换都算出来做一张表不就好了吗？所有的置换有多少种呢？3个转轮放在2个位置上有3×2=6种可能性，每个转轮有26种位置，那么两个转轮就是26×26=676种可能性，那么总共就是6×676=4056种置换——这个数字并不大！于是，小雷和同事们就日以继夜地做了那么一张大表，剩下两个转轮的顺序和位置，只要一查就可以分分钟破解！

好了，每日密钥的4大要素，我们已經破解了其中的3个，就只剩下那个偏移圆环的位置不知道了。对于这块硬骨头，小雷也只能硬啃，每个转轮的偏移圆环有26个位置，那么总共就是26×26×26=17576种可能性。这个数字说大吧，也还算可以，因为毕竟不是每次都赶上最坏的情况。但问题是，即便是要用穷举法一个一个试过来，我怎么才能验证试到哪一种可能性就是正确的呢？要想验证结果对不对，我们需要一些线索，比如加密之前的一部分明文的内容，也就是我们之前提过的“已知明文攻击（known plain-text attack）”，这是一种非常重要的密码攻击方法（快拿个本子记下来）。

可是，怎么才能知道一部分明文的内容呢？这时候德国人的循规蹈矩又帮个了大忙，根据可靠的分析，德军的大部分电文正文开头三个字母都是ANX。这个神秘的ANX到底是什么意思呢？AN是德语里“TO”的意思，也就是“发给×××”，用来指定电报的收件人;而后面一个×则是代表空格，因为Enigma键盘上只有26个字母，没有数字、标点和空格，因此这些东西都需要用特定的字母来替代，其中×就用来代表空格。

有了这个线索，剩下的就是用最简单暴力的穷举法一个一个尝试了。波兰人手上有复刻版的Enigma机器，还有用小雷的格子法计算出来的转轮排列、初始位置以及连接板的接法，把这些条件都用上之后，他们就不断改变偏移圆环的位置来尝试解密正文，如果碰巧解出了ANX三个字母，那就说明他们成功啦！一旦找到了偏移圆环的位置，就意味着每日密钥的所有要素都已经被破解了，也就是说，这一天所有的德军电文，波兰人统统能够轻松破译！

尽管如此，毕竟密钥是每天变化的，每一天对波兰人来说都是争分夺秒，因为越早破解每日密钥的所有要素，就能够越早解读当天的电文。在这个问题上，德国人又放松了警惕——我们之前也提到过，Enigma的转轮排列顺序不是每天换的，而是每三个月才换的。这样一来，波兰人就用不着每天拿着三张底纸去搜索正确的置换，而是只要拿一张就够了，因为他们知道最右侧的转轮是哪一个，这工作效率可就大大提高了。

循环测定机

在破译密电这件事上，时间就是生命，小雷对这个格子法的效率并不满意，他认为这个方法还是非常的“费劲”。还记得小雷之前发现的那个“特征结构”吗？简单来说，就是电文前6个字母（加密的指标组）可以形成一些有规律的循环序列。小雷又发现，尽管连接板的变化可以影响循环序列中所出现的字母，但是却不影响循环序列的长度特征！于是小雷灵机一动，我们为什么不能用循环序列的长度特征作为索引，从而像查字典一样快速查出所对应的置换呢？

小雷通过计算发现，对于1对指标组置换来说，循环序列的长度总共只有101种模式，而指标组置换共有3对，因此101的三次方总共有100多万种组合;而3个转轮所产生的置换变化总共有6×26×26×26=105 456种，它们之间是多对多的对应关系。我们可以先计算出指标组的循环序列长度模式，再查出这个模式对应那些置换——通常来说，一种循环序列长度只对应一种或者几种置换——也就可以破解每日密钥了，更重要的是，这个过程完全不受连接板的影响！

于是，小雷的任务就是要制作出一本包含105456种置换表的字典，然后把它们按100多万种循环长度模式进行索引。然而，在没有计算机的年代，纯手工制作这本字典可以说是相当艰难，而且还容易出错。我们的小雷同学之所以能被后人称为破译Enigma的第一功臣，那自然是搞出过超级神器的，这个神器就叫作“循环测定机（Cyclometer）”。

这玩意儿是干啥用的呢？当然是用来编那本字典的。这个机器里面装了两套Enigma转轮，通过特定的方式把它们连接在一起，然后通过让转轮按规则步进，在机器上显示出相应的置换和循环序列，然后再由工作人员抄在纸上。虽然这个过程还不是特别自动化，但总比一个一个手工计算要快多了，也准确多了。根据小雷的回忆，他们花了将近一年的时间才编好这本字典，但是一旦有了这本字典，波兰人只要花大约15分钟的时间，就可以完全破译当天的每日密钥！这个速度简直是逆天了！

穿孔纸片

不知道是波兰人的保密工作做得不好，还是德国人的嗅觉太灵敏，从1936年起，德国人开始密集地提高Enigma加密流程复杂度。比如说，Enigma的转轮顺序原本是三个月一换的，从1936年2月开始变成每月一换，到了1936年11月又变成每天一换——这给波兰人设置了一个很大的障碍，但努努力还是可以克服的。可更糟糕的是，1937年11月，德国人更换了所有Enigma密码机上面的反射器，也就是说，波兰人之前计算出的所有置换表一夜之间都变成了废纸，他们不得不再花一年的时间做一本新的字典出来。

如果上面这两件事还不算太糟，那下面这件事可就是毁灭性的打击了。1938年9月，德国空军和陆军全面改变了指标组的加密方式，其中最重要的改变是，一天中每封电文的指标组不再使用同一个转轮初始位置来加密了，这让小雷之前发现的“特征结构”也报废了，相应地，循环测定机也就跟着报废了。我要是小雷，那真是要气得一口老血喷出来。

小雷这几年被弄得心力交瘁，这时候他的队友齐加尔斯基给他搭了一把手。我们之前也讲过，齐加尔斯基——我们还是叫“小齐”吧——跟小雷是大学同学，也是一起被密码局挑进去的三位数学家中的一位。一开始，破译Enigma的工作只有小雷一个人做，后来另外两个人才被允许参加这项任务。小齐发现，尽管德国人修改了加密流程，现在每条电文的指标组都不是用统一的密钥来加密了，但是有一件事没变，那就是指标组依然重复加密两次，这6个字母的置换也依然是按规律步进的。

小齐还发现，有大约1/8的电文会出现一种特殊情况，那就是指标组的第1/4或者2/5或者3/6个字母被加密成了同一个字母。我们知道，指标组的明文本来就是重复两遍的，比如ATXATX，但是加密之后，理论上说，相同的字母应该会被加密成不同的字母，比如说GYKPWR，但是偶尔也会碰上特殊情况，比如说被加密成了GYKGWR，或者GYKPYR，或者GYKPWK，也就是第1/4、2/5、3/6個字母的密文也重复了。

小齐把这种情况称为“samiczki”，翻译过来是“女性（female）”的意思，我也不知道这里面是个什么梗，大概寄托了宅男数学家们的一些荷尔蒙冲动。反正他认为这种情况是可以被利用的，并且发明了一套穿孔纸片。这套纸片分为6组，因为3个转轮共有6种排列顺序;每一组有26张纸片，代表最左侧转轮的26种可能的初始位置;每张纸片上印有51×51的方阵，代表中间和右侧转轮的所有可能的位置组合。这套纸片的关键在于上面打的密密麻麻的小孔，打孔的地方表示在这个位置组合上，可能出现一对“samiczki”。只要有足够数量的包含“samiczki”的电文样本，通过这些纸片上的孔来进行筛选，就可以找出有限的几个可能的组合，这也就意味着成功破译了当天的每日密钥。

（正所谓道高一尺魔高一丈，尽管波兰人如此努力，但德国人也不会善罢甘休。“二战”的战火即将点燃，留给波兰人的时间不多了，面对不断升级的Enigma，波兰人将何去何从？我们接下来会继续讲。）

齐加尔斯基设计的穿孔纸片