1912-6-23:Alan Mathison Turing

1939年7月,英国情报部门在伦敦北面约80公里的一个名叫布莱利奇的地方征用了一所庄园。一个月后,英国的“政府代码和密码学校”迁移至此,校长是阿利斯泰尔·丹尼斯顿海军中校。

在丹尼斯顿的领导下,破译“恩尼格玛”、研制英国式“炸弹”的工作在这个庄园开始运作。丹尼斯顿物色了高手奈杰尔·德格雷和英国最好的数学家来完成这一任务,其中包括后来成为当代计算机科学巨匠的艾伦·图灵,当时他才27岁。

在布莱奇利庄园中,图灵第一次认识了“恩尼格玛”。

恩尼格玛(Enigma)是由德国发明家亚瑟·谢尔乌比斯首先发明的。由于其早期版本已经被波兰密码学家亨里克·佐加尔斯基、杰尔兹·罗佐基和马里安·雷杰夫斯基初步破解,因此德军使用的Enigma是改进版本。

Enigma的密钥空间为150,738,274,937,250种。 Enigma最大的特点是消除了单表代换密码中的频率分析攻击,这使得对Enigma的破解在开始的时候只能采用密钥穷举法,要用20,000,000年才能枚举所有的密钥。

Turing的破解基于两个非常重要的思想:其一是使用机器,而非人力进行破解,这使得密钥的搜索速度大幅提高,同时也避免了人工计算所可能带来的错误。其二是暗中使用了Known Plaintext Attack进行攻击。

为了使德军的电报明文中出现布莱奇利庄园所希望的词,英国人想了各种方法。

例如先派飞机把重要航道上的某个灯光浮标炸毁,然后注意截收途经此处的德国舰艇发出的无线电报,其中必有Leuchtboje(灯光浮标)一词。

此外德军的常用词,如军衔、职务等,以及德语中的常用词,如eins(一个),对破译也相当有用。

德国人的自作聪明也帮了布莱奇利庄园的忙。他们规定在一个月内,密钥轮的排列顺序不得重复。这就使得英国人不必对已发现在月内使用过的排列顺序再作测试。

有时德国人把一份电报既用“恩尼格玛”加密,又用其他易破译的密码加密,分别发给不同的单位,这就给布莱奇利庄园送上了一份“同文密报”。

德军对英国空战屡次失败,希特勒曾经怀疑过Enigma是否安全,于是命令德军对考文垂进行一次空袭实验。英军破译了这一情报,丘吉尔为使德军相信Enigma未被破译,决定放弃考文垂。这一空袭成功使得德军对Enigma的安全性深信不疑,从战略上说,考文垂的牺牲具有重大的价值。

战史专家在对二战的评估中,认为盟国成功破解Enigma密码机,使战争的结束至少提早了两年。

终战后图灵致力于设计真正的电脑,命名为Automatic Computing Engine,比同时在美国由冯纽曼(John von Neumann)设计的「冯纽曼机」与稍后的ENIAC(EDVAC的前身)还要先进许多,世界从此进入电脑的新纪元。

 

今天是图灵诞辰105周年,百度做了个H5的专题,只是粗浅介绍他对Enigma破解而已。

诚然,假如没有破解Enigama,二战中胜利的可能就是德国,而世界走向也可能会是《高堡奇人》里描述的那样。

但是图灵机的概念仍然比密码贡献大得多。

Kindle里的《阿兰·图灵传》看了一个多月,还只看到45%,他生命短短41年,后人却要用很长的文字来记叙。

假如图灵没有意外死亡,人工智能的前进脚步现在不知道会走到何等程度。