三、灭亡（上）
整整十三年里，英国人和法国人都以为ENIGMA是不可破译的，波兰人的成功重新鼓起了他们的勇气。虽然德国人已经加强了密码机的安全性能，但是波兰人的实践表明，ENIGMA决非坚不可破。波兰密码局的经验也表明，数学家在密码分析中能够起到多么重要的作用。在英国密码局（40局），以往都是由精于文字的语言学家或作家来担负起密码分析的重任，此后40局开始通过局内人际关系向牛津大学和剑桥大学招聘数学家和数学系学生。
英国的政府代码及加密学校(GC&CS, Government Code and Cipher School)是40局新设的机构，它的的总部坐落在白金汉郡的布莱切利公园(Bletchley Park)里，40局新招聘的密码分析专家就在那里学习和工作。布莱切利公园的中心是一座歌特都铎式的城堡，19世纪时由金融家赫伯特·莱昂(Herbert Leon)爵士建造，GC&CS的领导机构就设立在它的图书馆、宽大的餐厅以及装饰得富丽堂皇的舞厅里。从城堡的
布莱切利公园
底层望出去，外面是宽阔的花园。不过在1939年的秋天，那里的风景可不怎么样，花园里戳满了新建的小木屋，那是密码分析人员的工作场所，各种信息在担负不同任务的小木屋进进出出。比方说，6号木屋是负责破译德军ENIGMA电报的，从那里出来的明文由3号木屋翻译并进行综合情报分析；8号木屋专门负责对付德国海军的ENIGMA，这是一种特别复杂的ENIGMA机，和普通型不同，它有四个转子，在这里破译的情报由4号木屋中的情报人员翻译和分析。一开始在布莱切利公园工作的只有大约二百人，可是到了五年后战争结束时，城堡和小木屋中已经多达七千人！
英国数学家和其他密码分析人员很快就掌握了波兰人进攻ENIGMA 的技巧和方法。布莱切利公园拥有比波兰密码处多得多的人员和资金，所以足以对付由于德国人对ENIGMA的改动而增加到原来十倍的破译工作量。和在波兰密码处的情景一样，布莱切利公园的男女们日夜紧张工作，为的就是找到德国人当天的密钥。一到午夜，转子和连线板的设置就会变动，一切又要重新开始。
由此而破译的情报极其珍贵。如果布莱切利公园能够及时得到德军的情报，德国人的计划和行动就会暴露无遗。如果德军计划一次进攻，英军就可以采取相应的增援或撤退措施；更妙的是，如果德国将军在他们的电报中争论己方的弱点，英国军队就可以采取德国人最担心的计划。1940年4月德国入侵丹麦和挪威，布莱切利公园取得了一份详细的军事计划。同样在英伦战役之初，密码分析人员准确预告了德军轰炸的准确时间和地点，并且取得了德国空军(Luftwaff)极为宝贵的情报，比如飞机的损失情况，新飞机的补充数量和速度等。这些情报被送往M16的总部，再由那里转送战争部、空军部和海军部。
布莱切利公园的密码分析专家们有时也有点空余时间，最受欢迎的消遣活动是圆场棒球，球赛就在那座城堡前的草坪上举行。和自自在在的大学生一样，这些肩负着重任的男女也经常为一个有争议的球严肃地争论得面红耳赤。
在掌握了波兰人对付ENIGMA的手段后，英国密码分析专家也开始摸索出自己独特的方法。在正式用“炸弹”开始系统搜索当日密钥以前，他们总要试一遍“投机取巧”的门道。根据德军通讯的规定，每一条电文都要随机选择三个不同的字母组合，但是在激战之时，德军指挥官经常顾不上“随机”，往往在键盘上敲上三个相邻的字母了事，比方说DFG或者VBN，有时甚至重复使用某三个字母的组合来当密钥。英国密码分析专家把这样的密钥叫“西尔丝”(cillies)，即三字母组合CIL的读音，大概来源于哪位倒霉德国军官的女友的名字。
“西尔丝”并非ENIGMA本身的弱点，而是ENIGMA使用者的弱点。另一种更为严重的人为使用错误是密钥本编制者对密钥使用过分严格的规定。为了强调密钥的不可预见性，他们规定每天在三个放置转子的位置上，不得有和昨天放在此位置上相同的转子。比如说每台 ENIGMA机一共配备编号为1、2、3、4、5的五个转子，而前一天所使用的转子顺序为134，那么第二天可以使用例如215这样的转子顺序，但是214这样的顺序是不允许的，因为和前一天相比较，在第三个位置上都是4号转子。看起来这样交叉使用转子是个好主意，避免了象上面所说的重复使用某个密钥的过失，但是如果过分强调这一点，却会使英国密码分析专家的工作量减小一半，因为在开始分析当日密钥前，他们就可以把所有至少有一个转子处在前一日位置上的那些转子的排列排除在外了。德军密钥编制的另一条规定是，在连接板上不允许把两个相邻的字母连接起来。直觉似乎告诉人们不该使用这样简单的字母交换，但是这样的规则搞得太严格过了头，也就反而会帮对手的忙，对手根本就不用考虑这样的可能性了。
在整个战争过程中，ENIGMA机被不断改善，所以这样的“投机取巧”也变得十分重要，密码分析专家可以通过对密钥的猜测来推断出密码机新的变动，从而相应地改善“炸弹”的设计，使用新的策略。英国人能够在战争其间成功地持续破解ENIGMA密码，和小木屋里各种各样不同寻常的怪才的努力分不开。他们之中有数学家，各类科学家，语言学家，象棋冠军，填字游戏高手……一个难题经常从一只手传到另一只手，直到它最终得到解决；也有可能一个人解决一点，再由另一个人解决另一部分……按照6号木屋的负责人戈尔登·魏齐曼 (Gordon Welchman)的话来说，这是“一群想方设法嗅出一条线索的猎犬”。
在布莱切利公园有一大群为破译ENIGMA作出了卓越贡献的人们。但是如果只能选择性地讲述一个人的功绩，那么这个人无论如何应该是阿兰·图灵(Alan Turing)。
阿兰·图灵
图灵1912年6月23日在伦敦出生，他的父亲是当时英国殖民地印度南部的行政官员。他的父母为了使儿子在英国出生，暂时从印度回到了英国。图灵出生后不久他父亲重新回到印度，十五个月后他的母亲也离开英国返回印度，把图灵一个人留在伦敦，由保姆和朋友抚养长大，一直到了图灵上寄宿学校的年纪。
1926年，14岁的图灵进入了雪伯恩(Sherborne)学校就读。上学的第一天恰好碰上罢工，为了不错过就学典礼，图灵从南安普敦到雪伯恩一气骑了一百公里的自行车，为此他上了当地的报纸。在学校里一年下来，他给人的印象是个爱害羞，做事笨手笨脚的男孩，但是在自然科学方面充满才华。雪伯恩学校是培养为大英帝国效力的男子汉的地方，图灵的性格却似乎于此不合拍，所以那几年他的学校生涯不免有些难捱。
在学校里他唯一的朋友是一个名叫克里斯多夫·莫尔贡(Christopher Morcon)的男孩。他俩都热爱科学，经常在一起谈论最新的科学发现，做各种科学小实验。这段友谊激发了图灵对科学的兴趣，他对莫尔贡的感情似乎也超出了朋友的范围，成为一种依恋。但是莫尔贡永远不会知道这点了，在他们认识的第四年，1930年的2月13日，他死于突发性结核病。这对图灵是一个巨大的打击，他失去了唯一的朋友。似乎是为了让自己代替朋友活着，他学习更加努力。在去世前莫尔贡已经取得了一份剑桥大学的奖学金，图灵决定自己也将进入剑桥大学学习，去完成亡友的未竟事业。
1931年图灵如愿以偿地进入剑桥大学国王学院。当时的数理逻辑学界正热烈地讨论着二十世纪最伟大的数学发现之一——昆特·哥德尔的不完全性定理。在那以前，数学家们总以为，一个数学问题，虽然要找到回答也许很困难，但是理论上总有一个确定的答案。一个数学命题，要么是真的，要么是假的。但是哥德尔的不完全性定理指出，在一个稍微复杂一点的数学公理系统中，总存在那样的命题，我们既不能证明它是真的，也不能证明它是假的。数学家们大吃一惊，发现以往大家认为绝对严明的数学中原来有如此令人不安的不确定性。
每个逻辑学家都在苦苦思索，试图替陷入了危机的数学找到一条出路，他们包括当时在剑桥的贝特朗·罗素(Bertrand Russell)、阿尔弗雷德·怀特海(Alfred Whitehead)、路德维格·维特根斯坦(Ludwig Wittgenstein)这样著名的逻辑学家。在这种环境下，图灵作出了他一生中最重要的科学贡献，在他著名的论文《论可计算数》(On Computable Numbers)中，他提出了日后以他名字命名的虚拟计算机器——图灵机。
图灵设想的虚拟机器拥有一条无限长的纸带、一个读写头，和一个控制装置。控制装置具有有限个内部状态，它能够根据这些内部状态来控制读写头作出相应的动作，比如说沿着纸带前后移动，在纸带上记录改变或抹去信息，或者读取纸带上的信息并据此改变自己的内部状态。你可以把纸带上的信息看做是指令或者数据，读写头根据这些指令和数据来完成一系列的动作。图灵提出了各种各样这样的机器，有些能做加法（只要在纸带上先写好两个数，然后让图灵机运行，最后机器停止时写在纸条上的那个数就是起先两数的和），有些能做乘法，等等等等。当然有些似乎什么也不做，或者在纸带上乱涂乱画，而另外有一些，好像永远也不停下来。这就是在信息科学史上和“冯·诺依曼机器”齐名的“图灵机”。
图灵机的个数是可数无限个，所以我们可以用自然数把所有的图灵机都标上号。图灵发现了这样一种图灵机，它能够做到任何一台图灵机能办到的事情，只要在纸带上首先标出想要模拟的图灵机的号码，然后给出相应的输入，最后它的输出将是号码被指定的那台图灵机的输出。可以说这是一台“万能”图灵机，当然它只是一种理想的计算模型，或者说是一种理想中的计算机。事实上我们平时使用的计算机就可以被看做是这样一台“万能”图灵机（只是它没有一条无限长的纸带，也就是内存。不过如今内存便宜得这个模样，对于一般的问题来说，差不多可以说有无穷的内存了），纸带上的那些指令就相当于程序和数据，如果程序不同，计算机可以完成的任务也不同。
图灵发现，有些问题是这台“万能”图灵机也不能回答的。比如说著名的“停机问题”：给定一台图灵机的编号，和纸带上的输入，是否总能回答它最终是否会停下来？不能。这是和哥德尔不完全性定理密切相关的，图灵的结果从另一个侧面支持了数学中的“不确定性”。但是和不完全性定理不同的是，图灵的成果给数学家指出了一条具体构造这样一台“万能机器”的途径。虽然那还是在二十世纪的三十年代，当时的技术能力还不能将图灵的设想变为现实，但是他毫不怀疑自己的设想能够实现。这无疑是二十世纪科学理论最重要的发展之一，在计算机被广泛应用，甚至影响到我们每个人的日常生活的今天来看，尤其如此。当年，图灵年仅二十六岁。
这是图灵事业最为辉煌的时期，他在国王学院取得了教职，在剑桥过着平静的学术生活。1938年迪斯尼公司著名的动画片《白雪公主和七个小矮人》上映，图灵兴冲冲地跑去看。在后来的一些日子里，他的同事听见他不停地哼哼电影中巫婆王后泡制毒苹果时的歌：“毒液浸透苹果，如睡之死渗入。”
图灵喜欢他在剑桥的岁月，成功的事业，活跃和宽容的环境。大学并不对同性恋大惊小怪，他可以和几个人同时结交而不用担心谁在背后叽叽喳喳。但是在1933年他的学院生涯突然中断了，他受代码及加密学校的邀请成为一个密码分析专家。1939年9月4日，就在首相张伯伦向德国宣战的第二天，图灵离开了剑桥，来到离布莱切利公园五公里的雪纳利布鲁克恩德(Shenley Brook End)居住。他每天骑自行车到布莱切利公园上班。因为患有对花粉过敏的鼻炎，图灵就常常戴个防毒面具骑车上班，招摇过市。
在布莱切利公园里，每天他花一部分时间和其他人一样在小木屋里进行破译密码的工作，而另一些时间他就呆在被称为“智慧水箱” (Think Tank)，原来用来放水果的储藏室里。在那里密码分析专家思考在未来日子里有可能碰到的难题以及它们的解决方法。
直到当时，对ENIGMA的破译都采用雷杰夫斯基的方法，即利用每条密文最开始重复的密钥。如果此电文的密钥为YGB，那么电文开头就是六个由YGBYGB加密而成的字母，德国人以此来预防可能的传送错误。但是这是ENIGMA使用中的一个重大弱点，德国人很可能会发觉这一点并取消这种重复，这样就会使英国密码分析专家的破译手段变得毫无用处。图灵的任务就是要找到另一种不必利用重复密钥的破译方法。
在分析了以前大量德国电文后，图灵发现许多电报有相当固定的格式，他可以根据电文发出的时间、发信人、收信人这些无关于电文内容的信息来推断出一部分电文的内容。比方说，德国人每天的天气预报总在早上六点左右发出，要是在六点零五分截获了一份德国电报，它里面八成有Wetter这个词，也就是德文中的“天气”。根据在此之前德国人天气预报电文的死板格式，图灵甚至能相当准确地知道这个词具体在密文的哪个位置。这就使得图灵想到了用“候选单词”这一方法来破译ENIGMA电文，在英语中，图灵把这些“候选单词”叫做 Cribs。
如果在一篇密文中，图灵知道Wetter这个词被加密成了ETJWPX，那么剩下的任务就是要找到将Wetter加密成ETJWPX的初始设置。如果采用一个一个试过去的暴力破解法，那就会碰到1590亿种组合这个大问题。但是雷杰夫斯基的天才思想告诉图灵，必须把转子方向变化造成的问题和连接板交换字母造成的问题分开来考虑。如果他能够象雷杰夫斯基那样发现在Cribs中某些不随连接板上连线方式变化的特性，他就可以最多只用尝试1054560次（60种转子放置方法乘以17576种转子初始方向）便可找到正确的转子设置。
图灵找到了这样的特性。这是一种和雷杰夫斯基发现的循环字母圈类似的东西，只不过这回和重复的密钥没有关系，却是基于候选单词。假设图灵已经正确地猜到wetter被加密成了ETJWPX，这里就存在着一个字母循环圈：
图灵并不清楚在密文中出现这个候选单词时的转子状态，但是假设他猜对了这个候选单词，把这个候选单词起始时转子的方向记为S，那么在此时ENIGMA把w加密成了E；然后转子转到下一个方向，就是 S+1，ENIGMA把e加密成T；在方向S+2上一个不属于这个循环的字母被加密了，这个我们暂且不去管它；接下来在方向S+3，ENIGMA把t 加密为W。
这看起来好像还是让人摸不着头脑，但是图灵想的办法很巧妙，因为在这个字母循环圈里有3个字母，所以他想像如果用3台ENIGMA 同时加密这个候选单词，会发生些什么事。三台ENIGMA的初始设置除了转子方向外完全一样，第一台ENIGMA机的转子初始方向被定为原来的S，而第二台ENIGMA机的转子初始方向却是S+1，第三台的转子初始方向是S+3。当然一开始图灵根本就不知道这个S具体是什么（要是知道的话密码也就破译出来了），所以只能一个一个方向地试。大家可能会问，那为什么需要3台ENIGMA呢？只要在第一台上我们发现了一个把wetter加密成ETJWPX的转子方向，不就找到了密码吗？
这就要考虑连接板的问题。上面我们说过，如果只用一台ENIGMA 来试所有的密码，我们要试的就不仅仅是所有的转子方向，而且还要考虑所有的连接板上的连线方向，那个数目是1590亿种。图灵的绝妙主意就是用3台ENIGMA把连接板上连线的效应抵消掉！这样他就只要考虑1054560种转子方向就可以了。
图灵把三台ENIGMA的显示器按下图的方式连接起来，也就是说
把第一台ENIGMA显示器上的E和第二台ENIGMA显示器上的e连起来，又把第二台上的T和第三台上的t连起来，最后把第三台上的W和第一台上的w连起来（注意ENIGMA上字母没有大小写之分，这里我们只是用大小写来区别密文和明文）。下面的解释听起来稍微有一点复杂，最好对照着上面的图来读。假设连接板上有关的交换字母的连线是下面这样的（三台ENIGMA机上的都一样）
E←→L1
T←→L2
W←→L3
当然这里的L1、L2和L3都还是未知的。
现在假设字母w被输入第一台ENIGMA，它先通过连接板变成了L3，然后通过三个转子经过反射器，再通过三个转子返回连接板；因为我们根据候选单词知道w此时会被加密成E，所以没有经过接线板前它一定是和E对应的L1；L1经过接线板变成E后，直接成了第二台ENIGMA 的输入。提醒一下，第二台ENIGMA的转子方向是S+1，所以根据候选单词知道e此时会被加密成T，我们来看看具体是怎么回事。从第一台 ENIGMA来的e通过连接板变成了L1，再通过转子和反射器回来变成了连接板上和字母T对应的L2；通过连接板后变成了T，然后这个T又变成第三台ENIGMA机上的输入t。第三台ENIGMA机的转子方向是S+3，这个传送过来的t会被加密成E，具体的情况和上面第一第二台上的类似。我们发现现在三台ENIGMA机的线路组成了一个闭合回路，如果在里面加上一个灯泡，它就会亮起来。这个闭合回路事实上就是那个字母循环圈的形象化。
稍微思考一下就可以看到，无论连接板上的连线实际如何（也就是说无论L1、L2和L3实际上是什么），只要转子方向凑对了，这个闭合回路就会形成（当然如果有闭合回路形成不等于这个方向就一定是正确的，但是这样的情况很少，用手工就可以把正确的方向从中选出）。就这样，连接板上的连线效应被消除了。找到了转子的初始方向S，当然还要找到连接板上的连线，才能最终找到完整的密钥，但是这就相当简单了，这只是一个简单替换密码。如果在一台普通的ENIGMA上不接连线板，调整好找到的转子方向，键入密文ETJWPX，出来的明文成了tewwer，我们马上就知道w和t被交换了。键入密文的其他部分可以猜出其他字母的交换状况。
把候选单词，字母循环圈和用线路连接起来的多台ENIGMA机构成了密码分析的强大武器。而只有图灵，这个数学虚拟机器的发明人，才能有这样的想像力。图灵对ENIGMA的破译方法完全是纯数学和理论性的，他为此写了一篇著名的论文，在http://frode.home.cern.ch/frode/crypto/Turing/ 你可以读到这篇论文的一部分。但是他的理论研究已经完全可以让工程师来实际造出这样一台机器了。
布莱切利公园得到十万镑的经费来研制这种机器，绰号仍叫“炸弹”(bombes)。每个“炸弹”里都有十二组转子（因为根据上面的分析，显示器，连接板实际上都没必要存在了。而上面的例子里只要三台ENIGMA的原因是字母循环圈的长度是3，十二组转子的目的就是要攻击更长的字母循环圈）。一台这样的“炸弹”高两米长两米宽一米。图灵的研究于1940年初完成，机器由英国塔布拉丁机械厂(British Tabulating Machinery)制造。
图灵的发明赢得了他在布莱切利公园的同事的尊敬，大家把他看做是超群的密码分析专家。他的一位同事彼得·希尔顿(Peter Hilton) 回忆道：“图灵毫无疑问是个天才，而且是个极近人情的天才。他总是愿意花费时间和精力来解释他的想法。这不是一个钻在狭窄领域里的专家，他的思想遍布科学的许多领域。”
当然图灵的工作在布莱切利公园之外是绝对机密，就连他的父母都不知道他在干破译密码的工作，因为他是全英国最厉害的密码分析专家。有一次去看他母亲时图灵提到过他正在为军事部门工作，但是没有透露其他风声。他母亲在意的是他儿子剃的头很难看。虽然领导布莱切利公园的是些军人，不过他们也知道在生活细节上不能对这些知识分子严格要求，在这方面都是睁眼闭眼。图灵就经常不刮脸，穿着皱皱巴巴的衣服，指甲又长又黑。但是军队没有过问图灵的同性恋，是因为他们不知情。布莱切利公园的退伍军人杰克·古德(Jack Good) 后来说：“幸亏布莱切利公园的负责人不知道图灵是个同性恋，否则的话，我们就会打败这场战争。”
1940年3月14日第一台“炸弹”运抵布莱切利公园。可是它运行得太慢，有时要一个星期才找得到一个密钥。工程师们花了很大的努力来改善“炸弹”的设计，然后开始制造新的“炸弹”，这又花了四个月时间。但是在5月10日，最令英国密码分析专家担心的事情发生了，德国人改变了密码传递规则，他们的密钥不再重复，这使得布莱切利公园破译的电文量急剧下降。幸运的是，改进以后的“炸弹”在8月8 日到达，而且这次它运行得很好。在接下来的八个月里，十五台新 “炸弹”在布莱切利公园里轰然作响。一般上一台“炸弹”可以在一小时里找到一个密钥。
但是并非有了“炸弹”就万事大吉了。在让它运行之前还有许多困难要克服。比如说使用“炸弹”前先要找到一个候选单词。但是密码分析人员不能保证他猜的词一定在电报的明文中；就算猜对了，要把候选单词所在的位置正确地找出来也不是一件容易的事情，很有可能他猜到了电文中的一整句话，但是把这句话的位置搞错了，那“炸弹”也就白白运行了。密码分析人员找到了一些技巧，比如说，他知道下面“wetterbullsechs”一定在电文明文中，但是具体位置却只知道个大概。于是他猜想密文和明文的对应是：
候选单词： wetterbullsechs
密文：IPRENLWKMJJSXCPLEJWQ
在介绍ENIGMA的构造时我们知道，由于反射器的作用，一个字母从来也不会被加密成它本身。所以上面的候选单词所对应的位置一定是不对的，因为第二个字母e被对应到E上了。解决方法可以是慢慢地移动候选单词，看看是否每个字母都对应一个和自己不同的字母。比如把上面例子中的候选单词向左移动一位，变成
候选单词： wetterbullsechs
密文：IPRENLWKMJJSXCPLEJWQ
现在就符合要求了，所以此时才可以让“炸弹”去试试它的威力。
英国领导高层当然非常注重密码分析工作，温斯顿·丘吉尔亲自访问了布莱切利公园，他把这帮具有稀奇古怪才能的密码分析专家称为“从不呱呱叫的下金蛋的鹅”。在图灵和他的同事的努力和丘吉尔的亲自过问下，布莱切利公园解决了经费和人员缺乏的困难。到1942 年底，密码局拥有49台“炸弹”，密码分析人员的队伍也在不断扩大。事实证明玩填字游戏的高手往往会成为密码分析的高手，英国情报部门甚至在报纸上登出填字游戏来招聘新的密码分析人员。
没有评论:
发表评论