站在巨人的肩膀上：纳粹的最终灭亡
波兰数学家马里安·雷杰夫斯基利用恩尼格码设计和使用的各种缺陷破解了商用恩尼格码。但是由于德国军方对恩尼格码设计和使用的改进以及战争的临近，波兰科学家们不得不放弃了对恩尼格码的研究，并将所有研究成果随带着一个波兰制造的恩尼格码样机送到了英国。当时除了英国之外的其他盟国包括法国，苏联等都低估了德国的战力以及恩尼格码在战争中的重要性，并在拿到波兰科学家研究成果之后草草得出了恩尼格码不可破解的结论。
唯独英国在经过各方国力对比之后提出了破解恩尼格码是提早结束战争及伤亡的关键。于是波兰科学家的研究成果以及那台恩尼格码机便以国家头等机密被放在了英国的布莱切利公园。当时政府决心不惜一切代价破解恩尼格码，并聘请了当时国内最有名的语言学家，密码学家以及数学家们共同研究破解方法。
当时的英国科学家们继续沿用了波兰科学家的破解方法，聘请了大量的工作人员使用记录表（具体参见上一期内容）进行人工对比。但根据上一期的描述，德国人在改进了恩尼格码的设计和使用方法之后大大增加了恩尼格码的安全性，使得波兰科学家们总结出的破解方法很难再破译改进后的恩尼格码。不仅如此，德国每天凌晨更改恩尼格码设置的决定使得破解工作的进展完全无法累积。从德国每天早上六点的第一封电文开始到凌晨12点，如果英国科学家们不能在这18个小时之内破译出当天的密钥（恩尼格码机的初始设置），那么第二天的破译工作就必须重新开始。这也使得前期的破译工作几乎毫无进展。
△图1：阿伦·图灵
然而众多科学家中有一个在当时数学界便鼎鼎有名的人— 阿伦图灵。 当时的图灵在破译团队中却比较默默无闻。原因很简单，首先，当时的图灵的德语水平远不及团队中的其他人。于是当时的团队并没有将很重要的任务交于图灵。试想一个不怎么会德语的人如何去破解别人的密码呢？其次，当时的图灵便看出了当时破译方法的弊端，于是他也很少和同事们合作，反而致力于设计一个能用相对聪明的穷举法破解所有恩尼格码的机器（后被称为炸弹机）。虽然他也知道普通的穷举法完全不可能在短短18小时内尝试所有可能，但他相信存在更聪明的办法来优化传统的穷举法并执着于用机器打败机器的想法。
根据图灵传的描述，图灵从小便痴迷于对机器的设计及制作。作为数学家的他虽然其手工方面并没有什么可圈可点的地方，但他设计的思想在当时来看却是非常前卫的。那么图灵最开始设计这款机器是从哪里得到的启发呢？答案就是波兰科学家马里安.雷杰夫斯基的发现— 加密字母的循环。
△ 图2：图灵传
上期文章中我们讲到了波兰科学家们利用恩尼格码无法用同一字母加密的缺陷，通过德国对恩尼格码机使用时重复键入这一特点找出了加密字幕的循环并制作成记录本。虽然连接板的引入大大增加了加密的可能性，但图灵相信其中还是会有字母循环的出现。为了一劳永逸，图灵萌生出了制造解密机器的想法，希望通过机器来代替人工来加速无休止的试验。为了表述方便，我们使用上期文章中的例子假设字母 A 存在循环关系 A -> F -> W -> A。（请注意，因为接线板的引入，原本的字母循环关系会相应改变，这里使用这个循环为例只是为了表述方便），并用图3来表示整个字母的循环关系。
△ 图3：恩尼格码运行原理
（细心的读者可能会问不是说恩尼格码不会用同样的字母加密其本身吗，为什么经过三次加密之后 A 又回到了 A 呢？笔者在这里强调一下恩尼格码不用同样字母加密其本身的特点指的是同样字母无论输入多少次都不会得到该字母的输出，但如果输入不同字母得到的输出则可能是之前输入过的字母。）
我们先假设字母 A 在连接板上连接着字母 B 并把转子位子调在000。在这里，P1 和 P4 的字母应该是相同的，因为接线板的另一头连接着同样的字母 A。也就是说，如果我们能检测出 P1 和 P4 的值是相等的，那么这时的转子及连接板的设置可能就是正确的当日密钥。如果检测出不正确，那么我们便假设接线板上 A 连接着字母 C，并以此类推。如果在试验了 A 和另外 25 个字母连接之后都不能得到 P1 = P4， 那么其中一个转子的位子便会移动一位。如果我们能试验所有接线板连接以及所有转子设置，那么我们一定能在某一时刻或者某几个时刻得 P1 = P4。当然，这只是字母 A 输入所得到的当日密钥，我们还需要测试其余 25 个字母。
△ 图4：炸弹机原型（图片来源：http://www.rutherfordjournal.org/article030108.html)
这就是图灵希望制造炸弹机最初的想法。在此想法之后，图灵便开始着手设计炸弹机。从图4大家可以看到炸弹机上有很多三个一组的转子，每组转子都相当于一个恩尼格码机器，用于并行试验上述的每种可能性。炸弹机在得到当日密钥之后会自动停止转动，并显示出穷举后所得来的当日密钥。但问题是，这样的炸弹机根本不会停止。原因很简单，因为上述的方法还是传统的穷举法。而在第二期的文章里已经讲到了这种穷举法的不可行性。于是图灵对炸弹机的设计进行了改进。
细心地读者可能已经发现了上述穷举法所存在的不必要的重复。因为如果某一转子设置（比如000）的情况下 A 在连接板上连接 B 不能得到 P1 = P4， 我们不仅能得出在该转子设置的情况下 A 和 B 是错误连接，我们还能得到 P2 和F，P3 和 W 的连接也是错误的。我们在接下来相同转子设置的试验中就可以不测试这几种可能性了。这个发现不仅大大减少了试验的可能性（特别是在字母循环很长的情况下），电路的设计也使得机器可以瞬间检测到这些多余的可能性并同时取消对这些可能性的试验。
虽然有了上述的改进，炸弹机的效率仍然很低，这也一度困扰了图灵及其整个团队很长一段时间。直到1941年英国海军捕获德国 U110 潜艇并获得密码本和密码机之后情况才得到了好转。恩尼格码的密码本（详见上期文章）记录着一个月每天的当日密钥。英国人利用这段时间破译了大量的德国电文并从中发现了致命的规律，比如每天早上六点德国会定点发送天气预报，每封电文的结尾都会提到希特勒万岁。正是这个规律性的使用瓦解了恩尼格码的传奇。因为英国人可以用一个已知解密后的固定词汇，比如 wetter（天气），来对比加密后的文字。因为恩尼格码不能用同样的字母加密其本身，在对比过程中便能直接去除很多可能性。
如图5所示，我们将 wetter 这个词逐字对比密文，如果出现同样的字母（显示为红色）便向右移动一个字母在进行比对，直到没有相同字母出现为止，我们得到 wetter 可能对应的密文是 ERSMCW （来自位置2的对比）。这时我们可以得到一个字母循环 W -> E -> R -> W。我们把这个循环按照图3的方式排列并对比 P1 和 P4 的值。在知道明文和密文的对应之后，我们便知道了转子之间的距离。比如在这个情况下，如果转子1的位置为0，那么转子2的位置一定为1，（经过一次加密所得）同样转子3的距离一定为5（经过5次加密所得）。知道转子间的固定距离之后，炸弹机便可以再次减少大量的试验次数。经过这次改进之后，炸弹机的效率再次得到了提高。
△ 图5：明文及密文对比
值得一提的是，在同事汤米弗劳尔斯的帮助下，图灵和同事们再次改进了炸弹机的硬件设施，使得炸弹机的效率再次得到提高。至此，炸弹机能够在20分钟左右的时间内破译恩尼格码的当日密钥，使得二战的局面得到了改善。
其实炸弹机可以说只是图灵在机器设计概念上的一次实践。早在战争前，图灵便投入大量精力进行数学和机器的研究，为现代计算机的诞生打下了坚实的基础，特别是其在1936年提出的图灵机概念更是现代计算机，程序及算法设计的雏形和基础。从下期开始，我们将从探索图灵机开始，打开现代计算机及程序设计的大门。
文/道法自然 原理（principia1687）
喜欢这类内容？也愿意再阅读其内容…？那么敬请关注【博科园】今后我们会努力为你呈现更多科学知识。
