博客首页|TW首页| 同事录|业界社区
2012-05-21

说来新鲜,我苦于没有英雄可写,

尽管当今之世,英雄是迭出不穷,

年年有,月月有,报刊上连篇累牍,

而后才又发现,他算不得真英雄。

——拜伦:《唐璜》,第一章第一节

 他是世界上破解能力最强的黑客,他不仅仅是一个黑客,他还是现代计算机理论的奠基者,翻开任何一本《计算机原理》的书籍,他的名字永远在计算机之父冯·诺依曼之前。他是天才,更是一个传奇,以至于有人说上帝不应该制造这样完美的天才,因此上帝公平的给天才留下了现在看似缺陷的瑕疵,并早早的扼杀了他亲手制造的天才,好似他派他来到这个世界就是为了展示智慧的奇迹,就是为了将计算机带给人类,就是为了告诉人类,上帝是如何创造智慧并让人思考的,于是他成为了人工智能之父,并如同诺贝尔一样,他的名字成为了当今计算机科学领域的最高奖项——图灵奖。

 第六章节上帝派来的数学黑客 (阿兰·麦席森·图灵)

 从某种意义上说,一个人的智力范围越是局限,那么他在某一方面的智力就越容易接近无限。换言之,天才之所以成为天才,是因为他们一方面将自己无限地拉长,拉得细长细长,游丝一般,呈透明之状,经不起磕碰。所以,大凡天才都是娇气的,如世上所有珍宝一样,阿兰·麦席森·图灵(Alan Mathison Turing1912.6.231954.6.7)就是这样一位脆弱的天才。

 

阿兰·麦席森·图灵

德国闪电般入侵波兰后,第二次世界大战爆发,1939年英国正式对德国宣战,来开了两个欧洲帝国的生死决战。虽然在此之前波兰向英国提供了破解Enigma密码机的头绪,但是波兰人毕竟没有最终完成军用Enigma的破解,而且由于波兰方面提供的破译资料多数属于数学范畴,这对于经历过第一次世界大战的老牌密码破译专家来说是不可理解的,因为在那个时候,语言在密码破译中占更有更重要的位置,人们无法想想,一个连德语都不懂的数学专家能够在破译敌方密电中起到什么作用,而这一切直到图灵的出现才最终证明数学已经成为了密码学领域最重要的一根支柱。

图灵出生于1912623日的英国伦敦,他的整个家族在学术方面有着相当辉煌的成果,家族成员中有三位当选过英国皇家学会会员,图灵的祖父还曾获得剑桥大学数学荣誉学位,不过图灵的父亲却仅仅只是一名大英帝国驻印度的公务员。但图灵显然遗传了家族中最优秀的数学细胞,他在16岁时就开始研究爱因斯坦的相对论,并开始运营深奥的数学原理独立推到力学定律,或许这注定了这位伟大的数学奇才会成为Enigma的终极杀手,也就在图灵研究相对论的那一年,Enigma之父谢尔比乌斯离开了人世。

1931年,图灵考进了剑桥大学,在该大学的“国王学院”专攻数学。剑桥是他这一生学术生涯的起点。那儿有自由的学术环境,他如饥似渴地阅读一切感兴趣的书籍,甚至是刚刚出版上市的天才大数学家冯·诺依曼的新作《量子力学的逻辑基础》。除了数学与物理之外,他的兴趣比中学时代广泛了许多,例如对哲学也产生了兴趣,他选修了哲学大师维特根斯坦教授的“数学的哲学”课,这让图灵的哲学与数学知识在逻辑学上有交汇,也开启了图灵关于人工智能的思考。

 

 图灵的手迹

 此外对图灵一生产生最重要影响的要数“数学逻辑学”,这是剑桥大学的大数学家罗素和怀特海创立的一门非常抽象、讲究逻辑思维、令人煞费脑筋且望而生畏的学科。数理逻辑学的创建,起源于一个逻辑上的“悖论”。为了非专业人士都能明白逻辑悖论的含义,哲学家或者数学家喜欢用讲故事的办法来解释它。一个经典的故事是:村子里有位理发师,他为而且只为村子里所有那些不给自己理发的人理发。现在的问题是,谁为理发师理发?假定理发师为自己理发,那么依照理发师“只为不给自己理发的人理发”的规定,由此推理得出结论:理发师是不为自己理发的人,这与假定矛盾;或者假定理发师不为自己理发,那么依照理发师“为所有不给自己理发的人理发”的规定,由此又推理得出结论:理发师应该为自己理发,这又与假定矛盾。所以,不论怎么假定,也就是说不论谁为理发师理发,都要出现不能自圆其说的结论。

在那以前,数学家们总以为,一个数学问题,虽然要找到回答也许很困难,但是理论上总有一个确定的答案。一个数学命题,要么是真的,要么是假的。但是哥德尔的不完全性定理指出,在一个稍微复杂一点的数学公理系统中,总存在那样的命题,我们既不能证明它是真的,也不能证明它是假的。数学家们大吃一惊,发现以往大家认为绝对严明的数学中原来有如此令人不安的不确定性。

每个逻辑学家都在苦苦思索,试图替陷入了危机的数学找到一条出路,他们包括当时在剑桥的贝特朗·罗素(Bertrand Russell)、阿尔弗雷德·怀特海(Alfred Whitehead)、路德维格·维特根斯坦(Ludwig Wittgenstein)这样著名的逻辑学家。在这种环境下,图灵作出了他一生中最重要的科学贡献,在他著名的论文《论可计算数》(On Computable Numbers)中,他提出了日后以他名字命名的虚拟计算机器——图灵机。

图灵机这台完全虚拟的“计算机”忽略了硬件因素,图灵思考的焦点是逻辑结构。图灵在他那篇著名的文章里,还进一步设计出被人们称为“万能图灵机”的模型,它可以模拟其他任何一台解决某个特定数学问题的“图灵机”的工作状态。“图灵机”想象使用一条无限长度的纸带子,带子上划分成许多格子。如果格里画条线,就代表 1”;空白的格子,则代表“0”。

图灵想象这台“计算机”还具有读写存储功能:既可以从带子上读出信息,也可以往带子上写信息。计算机仅有的运算功能是:每把纸带子向前移动一格,就把“1”变成“0”,或者把“0”变成“1”。“0”和“1”代表着在解决某个特定数学问题中的运算步骤。“图灵机”能够识别运算过程中每一步,并且能够按部就班地执行一系列的运算,直到获得最终答案。

 

图灵想象的电脑

图灵的文章从理论上证明了制造出通用计算机的可能性。几年之后,美国的阿坦纳索夫在1939年果然研究制造了世界上的第一台电子计算机ABC,其中采用了二进位制,电路的开与合分别代表数字01,运用电子管和电路执行逻辑运算等。ABC是“图灵机”的第一个硬件实现,看得见,摸得着。而冯·诺依曼不仅在上个世纪40年代研制成功了功能更好、用途更为广泛的电子计算机,并且为计算机设计了编码程序,还实现了运用纸带存储与输入。到此,天才图灵在1936年发表的科学预见和构思得以完全实现。

与图灵一样有天赋的冯·诺依曼看过图灵的论文后极为赞赏,惺惺相惜,极力邀请图灵毕业后到普林斯顿高等研究院工作,做他的研究助手。然而图灵深爱着剑桥大学,执意要回到母校任教,令冯 ·诺依曼教授惋惜不止。惋惜的远不止冯·诺依曼,不知有多少学者发出叹息,当年两位科学奇才没能走在一起。尽可以想象,由于两大世纪天才的合作,数学、计算机科学等会获得怎样的发展?“11定会大于2”,两颗灿烂的巨星一处发光,显然会将科学的天空照耀得更加明亮。

但是,当图灵在剑桥刚刚打算做一名优秀的教师和学者之时,193994日,英国对德国宣战,开始了第二次世界大战漫长的拉锯战。而图灵则在第二天就被军方应招入伍,来到了远离城市乡村,一个名为布莱切利的庄园。在这里,英国军方安排给图灵的工作就是破译密码,虽然此前英国军方已经能够运用一些德军的操作漏洞破译部分Enigma的密码,但是这个漏洞随时可能会被德国人修补,因此英国军方希望能够在德国人修补漏洞前,找到真正彻底攻破Enigma的方法。

 

布莱切利的庄园

在分析了大量德国电文后,图灵发现许多电报有相当固定的格式,他可以根据电文发出的时间、发信人、收信人这些无关于电文内容的信息来推断出一部分电文的内容。例如,德国人每天的天气预报总在早上六点左右发出,要是在六点零五分截获了一份德国电报,它里面八成有Wetter这个词,也就是德文中的“天气”。根据在此之前德国人天气预报电文的死板格式,图灵甚至能相当准确地知道这个词具体在密文的哪个位置。这就使得图灵想到了用“候选单词”这一方法来破译Enigma电文,在英语中,图灵把这些“候选单词”叫做Cribs

可图灵并不清楚在密文中出现这个候选单词时的转子状态,但是图灵想的办法很巧妙,他想如果用3Enigma同时加密这个候选单词,会发生些什么事?图灵的绝妙主意就是用3Enigma把连接板上连线的效应抵消掉,这样他就只要考虑1054560种转子方向就可以了。把候选单词,字母循环圈和用线路连接起来的多台Enigma机构成了密码分析的强大武器。图灵对Enigma的破译方法完全是纯数学和理论性的,也只有图灵,这个数学虚拟机器的发明人,才能有这样的想象力。

 

炸弹的众多转子

后来图灵得到了来自英国军方的十万英镑拨款,制作了一款专门破解Enigma的逆向破解机“炸弹”(Bombes)。每个“炸弹”里都有十二组转子,理论上能够快速的完成对Enigma密电的破解。图灵的发明赢得了他在布莱切利庄园的同事的尊敬,大家把他看做是超群的密码分析专家。他的一位同事彼得·希尔顿(Peter Hilton)回忆道:“图灵毫无疑问是个天才,而且是个极近人情的天才。他总是愿意花费时间和精力来解释他的想法。这不是一个钻在狭窄领域里的专家,他的思想遍布科学的许多领域。”

当然图灵的工作在布莱切利庄园之外是绝对机密,就连他的父母都不知道他在干破译密码的工作,因为他是全英国最厉害的密码分析专家。有一次去看他母亲时图灵提到过他正在为军事部门工作,但是没有透露其他风声。他母亲在意的是他儿子剃的头很难看。虽然领导布莱切利庄园的是些军人,不过他们也知道在生活细节上不能对这些知识分子严格要求,在这方面都是睁眼闭眼。图灵就经常不刮脸,穿着皱皱巴巴的衣服,指甲又长又黑。但是军队没有过问图灵的同性恋,是因为他们不知情。布莱切利庄园的退伍军人杰克·古德(Jack Good)后来说:“幸亏布莱切利庄园的负责人不知道图灵是个同性恋,否则的话,我们就会打败这场战争。”

 

 

炸弹

 

依然可以使用

 

 

细节

 

 

 

并不是每一台炸弹都相同,它们对应了德军不同的Enigma

 

 

 

图灵的设计

 

莱切利庄园的密电截获设备

1940314日第一台“炸弹”运抵布莱切利庄园。可是它运行得太慢,有时要一个星期才找得到一个密钥。工程师们花了很大的努力来改善“炸弹”的设计,然后开始制造新的“炸弹”,这又花了四个月时间。但是在510日,最令英国密码分析专家担心的事情发生了,德国人修补了Enigma的漏洞,这使得布莱切利庄园破译的电文量急剧下降。幸运的是,改进以后的“炸弹”在88日到达,而且这次它运行得很好。在接下来的八个月里,十五台新“炸弹”在布莱切利庄园全力开动,而每一台“炸弹”可以在一小时里找到一个Enigma的密钥。

布莱切利庄园出色的密码破译工作引起了英国领导人的注意,温斯顿·丘吉尔亲自访问了布莱切利庄园,他把这帮具有稀奇古怪才能的密码分析专家称为“从不呱呱叫的下金蛋的鹅”。到1942年底,密码局拥有49台“炸弹”,密码分析人员的队伍也在不断扩大。事实证明玩填字游戏的高手往往会成为密码分析的高手,英国情报部门甚至在报纸上登出填字游戏来招聘新的密码分析人员。

在大西洋海战中,德国海军元帅邓尼茨使用“狼群战术”来对付英国的海上运输线,这使英国付出了惨痛的代价。首先,德军众多的潜艇分散在大西洋广阔的海域中,试图寻找合适的目标;如果其中有一艘潜艇发现目标,它就会通知其它潜艇赶来增援;一旦在此海区中潜艇数量足够,它们就向目标发动进攻。很显然,在这种需要高度协作的战术中,保密和快速的通讯起着决定性的作用,而如果英国方面不能及时破译这些通讯内容,所遭受的打击是毁灭性的。

 

现在终于不是秘密,被公开的“炸弹”

但经过图灵和布莱切利庄园密码分析人员的努力,盟军终于能够了解德国“狼群”的位置,从而为运输船队选择一条安全的航线,不仅如此,英国海军的驱逐舰甚至还能主动出击,寻找德军潜艇并将其击沉。但是这里还是存在着如何恰到好处地使用所得到的情报,以免德军总部怀疑他们的最高机密已被破译的问题。正所谓兵不厌诈。通过对Enigma的破译,盟军能够知道德国潜艇的位置,但是击沉所有这些潜艇是愚蠢的,因为突然升高的损失不可避免地会使德国人猜测到他们的通讯并不安全。所以盟军经常放掉一些已经到手的肥肉,只攻击那些被侦查机发现的潜艇,当然盟军也会发出一些假的侦查到潜艇的消息来掩盖随之而来的攻击。有一次布莱切利庄园破译了一条电文,其中有九条德国油轮的方位,为了避免德国人起疑心,英国海军总部决定只进攻其中的七条油轮。这七条油轮沉没后,对破译Enigma和需要保持秘密一事一无所知的皇家海军舰队“不幸”恰好又碰上了另两条倒霉鬼,于是也将它们送入了海底。在柏林德国人为此事进行了调查,但是他们的疑心集中在这是一次偶然的事件,还是由于英国谍报人员的渗透,没有人怀疑这是英国人破译Enigma所取得的胜利。

 

 操作炸弹的女士

布莱切利庄园所破译的不仅仅是德国的Enigma密码,在战争期间他们同样破译了意大利和日本的密码系统,这三方面的情报来源被冠以“Ultra”的代号,意为“绝密”。通过Ultra提供的情报,盟军在战场上取得了明显优势。德国在二战后期,又研究开发了一个代号为“Geheimschreiber”的加密机,它由大名鼎鼎的德国西门子公司生产制造,是比Enigma更为复杂的加密装置,它拥有10~12个字母转子转盘,这使得被它加密的密文很难被破解。Geheimschreiber是德军最高统帅部和希特勒本人专用的密码,但是图灵最终又成功了攻破了Geheimschreiber

 

 

希特勒使用的Geheimschreiber

历史学家大卫·凯恩(David Kahn)评价布莱切利庄园的作用时说:“这拯救了生命。不仅仅是俄国人和盟军的生命,它也拯救了德国人,意大利人和日本人的生命。对许多在二次大战后幸存下来的人来说,没有这个方案,他们将已不在人世。这就是这个世界欠这些密码破译者的债务,他们的胜利折换成人类生命的价值。”

 

布莱切利庄园内的德军U型潜艇模型

 

图灵和他的同事在搜寻与打击德军的U型潜艇、协助盟军诺曼底登陆等重大军事行动中发挥了关键作用。人们估计布莱切利庄园的工作使欧洲的战事至少提前两年结束。图灵也因此在1946年获得“不列颠帝国勋章”,这是英国皇室给予为国家和人民做出巨大贡献、立下大功的人士的最高荣誉。

战争结束后,布莱切利庄园的秘密却仍不能被公之于众,原因就在于Enigma的加密措施太出色了,英国人想继续利用Enigma出色的加密方法,他们将在战胜后所缴获的数以千计的Enigma机分配给自己在世界各地的殖民地,让它们继续发挥余热,因为在那里Enigma仍然是是坚不可摧的“谜”。

战后布莱切利庄园被关闭,“炸弹”被拆毁,和战时密码分析和破译工作有关的档案资料全部都被封存,严密地看护起来。在几千名原来的工作人员中,有一些成员得以继续为军方新的密码分析机构工作,但是大多数人都被遣散,转回了原来的平民身份。他们宣誓对在布莱切利庄园的经历保守秘密。从战场上回来的老战士们可以自豪地谈论他们在二战中的战斗经历,但是在布莱切利庄园工作过的人们却不得不隐瞒自己在战争中为国家作出的贡献。一位曾在6号小木屋中工作过的年轻密码分析专家甚至收到了一封他早年所在的中学的老师寄来的信,责骂他在战争中逃避战斗的懦夫行为。

更具有讽刺意味的是,当2000年好莱坞影片《U-571》上映时,遭到了大量英国舆论的批评。影片描述了美国海军机智勇敢地夺取德国潜艇上Enigma机的故事。英国舆论认为,首先从德国潜艇上夺取Enigma机的是英国皇家海军,美国人这样做是把他人之功据为己有。而图灵没有能活到看见自己在破译Enigma中作出的巨大贡献为人所知的这一天,没有看到人们为此向他的深深敬意。

1945年第二次世界大战全面结束,图灵随后被英国国家物理实验室聘为高级研究员,于是他又回到了伦敦专心研究计算机理论。计算机的研究在当时属于绝密,他撰写的论文都没有公开发表。而当年图灵写了若干份“内部报告”,明确提出了“自动程序”的概念,在1970年得以解密,后来收入爱丁堡大学的《机器智能》论文集中。

理论上的准备已经充分,而且在战争时期已经具有运用计算机的经验,此时的图灵对计算机的发展前景胸有成竹,他兴致勃勃地拟订了一份“自动计算机(ACE)”的设计方案,完整地描绘出通用数字电子计算机的结构。此时的图灵更注意到存储量与运算速度是计算机的核心,他设计的ACE在性能上,大体相当于上个世纪80年代美国苹果公司研制的个人电子计算机“麦金塔”。图灵实在太超前了,国家物理实验室认为制造原原本本的ACE在工程与技术方面过于困难,知难而退,仅仅制造了一台简化了的ACE,其运算速度和存储量均大为逊色。

尽管不如图灵所愿,但这台ACE毕竟是图灵研制成功的第一台公开对外的电子计算机。况且 ACE一鸣惊人,被公认为是当时世界上最快的电子计算机之一。图灵特别满意它的存储功能,骄傲地向参观者介绍:“它能十分轻松地记忆任何一本小说中的10 页内容,一字不差!”

1946年,英国皇家学会成立计算机实验室,设在曼彻斯特大学,一时群英荟萃,成为英国计算机事业的中心,总负责人是图灵在布莱切利庄园的老同事和好朋友纽曼教授。图灵是皇家学会计算机实验室的常务副主任,实际上的负责人。图灵成为实验室的灵魂,他的计算机理论指导着实验室的发展,世界上第一台商业计算机“马克一号”即在这里问世。

他在思考与探讨人脑与计算机之间的关联与互动。图灵在他的另一篇划时代的论文《机器能思考吗?》中,这样描述他的设想:“人的大脑好似一台巨型的电子计算机,初生婴儿的大脑皮层像尚未组织好的机器,可以经过训练,使之成为组织好了的类似于万能机式的机器。” 早年在剑桥大学获得的数学与哲学方面的深厚功底又一次发挥了力量,图灵是当之无愧的现代“人工智能”之父。也正因为图灵和他的“人工智能”,电子计算机方有了另外一个名字:“电脑”。

 

图灵测试

为了演示人机对话,图灵编写了一套象棋程序,当时却没有一台足够好的计算机去执行这个程序。于是图灵就亲自模拟计算机,严格执行他预先编写的程序走棋,模拟的“计算机”每走一步要用半小时。他就这样与同事下了一盘,结果“计算机”输了。图灵明确提出:“机器能思考”。或者说,具有人脑智力的机器才是图灵心目中真正的万能机。图灵没有说空话,他进一步给出机器是否具有人脑智力的判别法,后来被称之为“图灵测试”。在图灵的时代,全世界仅有的计算机中,当然没有一台能够通过“图灵测试”,那时计算机的水平与今天的不可同日而语。可那限制不了图灵的想象和预见,他相信在20世纪末,定会有计算机能够通过“图灵测试”。他的预言得到证实:IBM研制出的一台会下国际象棋的电子计算机“深蓝”,战胜了当年的国际象棋世界冠军卡斯帕罗夫。

但在图灵生命的后来的时光,他并没有被看做一个英雄,而是因他的性倾向而饱受骚扰纠缠。1952年因被小偷入室行窃,他向警察报了案,但是不通世事使他忘了向警察掩盖他和另一位男士同居的事实。1952331日图灵被警方逮捕,被以“有伤风化”罪的罪名起诉,并被判为有罪。在整个过程中他不得不忍受报纸对他的案件的公开报道。

195468日,图灵去世的噩耗像晴天霹雳,不仅英国,乃至全世界都为之震惊。最先发现图灵死亡的是清扫房间的女佣。早就过了图灵通常起床的时间,他却仍然沉睡在床上,神态自若安详,枕边有个只吃了一小口的苹果。书桌上灯亮着,有一封准备寄出的信。法医在图灵没有吃完的那只苹果里检验出了氰化钾,剧毒化学药品的残留物。警方在多方搜集证据后,对外正式宣布调查结果:图灵是服毒自杀。

图灵自杀的原因一时成为全世界的难解之谜,猜测纷纭。他的母亲不相信、不接受警方“图灵服毒自杀”的判断,因为桌子上那封未寄出的信里提到“同意在几天后接受采访”云云。她认为图灵是不小心接触到了他实验室里的剧毒化学药品,是死于意外事故。警方则认为,那封信是图灵故布疑阵,令母亲相信儿子意外中毒而亡,心里会好受些。困扰人们的问题是图灵为什么要自杀?在195467日的那个晚上,当代最伟大的头脑之一,就这样在四十二岁时离开了这个世界。

英国当年的法律主张严厉惩戒同性恋,图灵不得不接受注射激素,否则会有牢狱之灾。激素疗法非但不能改变同性恋倾向,反而呈现出多种副作用,图灵变得意志消沉,越发寡言少语。图灵曾经去看心理医生,医生建议这位科学奇才放松情绪,换换脑筋,不妨读读好的小说。结果图灵真的喜欢上了列夫·托尔斯泰的小说,不过,情绪并未因此而好转。人们普遍认为,图灵情绪的低沉抑郁,最终导致了他的自杀,是那不人道的激素疗法害了他。

图灵的死无疑是计算机科学界的巨大损失,无以弥补。牛津大学著名数学家安德鲁·哈吉斯说道:“图灵似乎是上天派来的一个使者,匆匆而来,匆匆而去,为人间留下了智慧,留下了深邃的思想,后人必须为之思索几十年、上百年甚至永远。” 图灵将引领世界计算机的“风骚数百年”,他25岁首创的“图灵机”概念如石破天惊,而立之年探讨的仿真系统和自动程序设计概念如仙人指路,不惑之“晚年” 开创的人工智能和“图灵测试”如开山辟路,无一不是超前的科学预见,无一不展现着这位天才的过人智慧。

1998623日,伦敦市政府在图灵的出生地,那所故居的迎面墙上镶嵌上一块象征人类智慧与科学的蔚蓝色的铜匾,铸刻着计算机科学创始人的名字和出生年月,纪念这位计算机大师诞辰86周年,数万人参加了纪念仪式。那一天,也恰好是图灵在曼彻斯特大学亲手设计成功的电子计算机问世50周年。图灵的这个纪念活动牵动全世界计算机科学家的心,也惊动了英国国会。众议院极其不寻常地赶在前一天晚上1030分,以压倒多数的投票,通过了一项法案,承认了同性恋者的平等权益。英国政府以他的特殊方式表达了对这位科学巨人的伟大成就的敬意,对令他遭受不公正惩罚的忏悔。

 

 

 

英国大学校园里拿着苹果的图灵铜像

200467日,为纪念这位计算机科学与密码学的绝顶天才逝世50周年,来自世界各地的学者、学生数千人不约而同来到曼彻斯特市,聚集在图灵离世前5年曾经居住的公寓前。曼彻斯特市政府在这所表面极其普通却因图灵而成为永久的历史性建筑的墙上,隆重镶嵌上一面纪念铜牌,还是蔚蓝色的,上写:19121954,计算机科学奠基人与密码学家,战争年代破译Enigma的功臣艾兰·图灵居于斯,逝于斯。

 

曾经担任过冯·诺依曼研究助手的美国物理学家弗兰克尔教授这样写道:“许多人都推举冯·诺依曼为‘计算机之父’,然而我确信他本人从来不会促成这个错误。或许,他可以被恰当地称为‘计算机的助产士’。依我之见,正是冯·诺依曼使世界认识了由图灵引入的计算机的基本概念。”弗兰克尔教授此言不虚,在 1949年,冯·诺依曼发表了一篇题为《自动计算机的一般逻辑理论》的论文,客观而公正地阐述了图灵在计算机理论上的重大贡献。他写道:“大约12年前,英国逻辑学家图灵就开始研究可计算问题,他准确地给出了自动计算机的一般性定义。”冯·诺依曼宁愿把“计算机之父”的桂冠转戴在图灵头上。当然,这已经是在图灵离开普林斯顿十来年以后的事了,他当年在普林斯顿并没有像后来那样受人景仰。图灵曲高和寡,当年就能看明白他那篇文章划时代意义的,仅仅是少数杰出的数学家,如冯·诺依曼者。

 

 图灵铜像,他正在破解密码

我们之所以将图灵视为世界上最伟大的黑客之一,是因为,在现如今,当互联网上那些只会使用注入扫描器狂扫漏洞的时候,在他们认为,用工具就能够神奇的拿下网站的时候,却往往并不知道,注入扫描器所使用的逻辑计算原理来源于一个1912出生的数学家,一个破解过纳粹德国Enigma加密机的计算天才。我们由衷的希望,那些自视为什么都懂的“黑客“能够多一些清醒……

 

 

在我渺小的日子里,我也曾阅历帝国的兴亡,

但是我并没有衰老;

当我把自己的忧患和那一切相比,

它虽曾奔腾象海湾中狂暴的浪涛,

却成了小小水化的泼溅,

随时平息;

的确,

有一些什么-连我也不明了-在支持这不知忍耐的灵魂;

我们并不白白地(即使仅仅为它自己)贩来痛苦。

——拜伦《书寄奥古斯达》选段

黑客是征服者的战争,然而征服往往是从被征服开始的。

二战前夕,随着世界上最先进的密码机Enigma(意为“谜”)在纳粹德国的铺开使用,让波兰、法国、英国等国家的顶尖智慧群体,陆续被卷入了这场旷日持久的密码战。加密、破解,疯狂升级,天才、叛徒,粉墨登场,也由此掀开了人类历史上最波澜壮阔的加密与解密大战……

00000011/三章节 加密之王Enigma

第二次世界大战爆发于1939年,历时6年之久,先后有60多个国家和地区参战,波及20多亿人口,战争交战各方共动员军队1亿多人。在这场人类有史以来最惨烈的战争中,决定最后战争命运走向的竟然是几台机器和制造它们的天才数学家们。而在第二次世界大战中最大的军事秘密,除了原子弹外,就是纳粹德国的核心密码——Enigma

Enigma从外表看起来并没有什么能够让人感到惊奇的地方,它似乎跟普通的打字机别无二致。Enigma是一种转轮式密码机,原理并不复杂,但在第二次世界大战之前要破解它却基本上是不可能的。

一台普通的Enigma通常有三个部分组成:键盘、转轮和显示器。

 

Enigma的键盘排列接近我们现在使用的计算机键盘。不过为了能够让密电尽量简短和难以破译,它没有空格和标点符号。而它使用的加密方法在现在计算机的很多软件注册中依然常见,这种加密方法叫做“代替密码算法(Substitution cipher)”。

代替密码算法是历史上最古老也是最有效的加密算法之一,它很早就登上了历史的舞台,最著名的“恺撒密码”(又名Caesar密码)所采用的就是这种加密方式。传说,它的发明人是人类历史上最著名的皇帝之一,有着“古罗马唯一的天才”之称的朱利斯·凯撒(Julius Caesar)。

据说凯撒是这样使用这种加密方法的:他先把自己的军事命令中的字母写成字母顺序的数字,然后他在将每个数字加3。如果这个数字大于字母表中的数字,那么凯撒就将这个数字与字母顺序中最后也是最大的那个数字相减之差来表示。通过这种数字机密的信息,凯撒派出的传令兵即便被抓到了,敌人也无法迫使他们供出绝密的信息,而接收到该加密密文的罗马将领们只需反过来运算,就可以得到原始军事命令了。例如:

明码字母表:abcdefghijklmnopqrstuvwxyz

密码字母表:DEFGHIJKLMNOPQRSTUVWXYZABC

根据上面的加密对照表,凯撒如果想发出“VeniVidiVici”,即凯撒征服本土国王之后向罗马元老院发出的呐喊“我来,我见,我征服!”,那么加密后的密文应该是这样的:

明文:veni, vidi, vici

密文:YHAL, YLGL, YLFL

小知识:消息(Message)被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程被称为加密(Encryption),被加密的消息称为密文(Ciphertexe),而负责把密文转变成明文的过程成为解密(Decryption

Enigma采用的加密方法正是这种看似简单的加密方式。它通过由电线相连的键盘、转轮和显示器,将键盘上的信号对应到加密机显示器上。但是很明显,这种简单的方法只有26种可能性,不足以实际应用,用这种方法所得到的密文还是相当容易被破解的。

因此在公元九世纪,阿拉伯的密码破译专家就已经娴熟地掌握了用统计字母出现频率的方法来击破简单代替密码。破解的原理很简单:在每种拼音文字语言中,每个字母出现的频率并不相同,比如说在英语中,e出现的次数就要大大高于其他字母——这种方法后来在计算机应用密码学中被称之为重合码计数法(Counting coincidence)。

所以如果取得了足够多的密文,通过统计每个字母出现的频率,通过揣摩上下文等基本密码破译手段,很快就可以猜出密码中的一个字母对应于明码中哪个字母。柯南•道尔在他著名的福尔摩斯探案集中《跳舞的人》里就详细叙述了福尔摩斯使用频率统计法破译跳舞人形密码的过程。

因此谢尔比乌斯发明了对于Enigma来说最关键的加密部件——转轮机(Rotor machine)。它是一个会自动转动替换对应字母的设备,是从凯撒加密法中延伸出来的更为复杂的维吉尼亚(Vigenere)和博福特(Beaufort)密码的电子机械实现。维吉尼亚密码与凯撒加密法的最大区别就在于它引入了“密钥(Key)”这一概念,即根据密钥来决定用哪一行的密表来进行替换,以此来对抗字频统计。

当在Enigma键盘上一个键被按下时,相应的密文在显示器上显示,然后转轮的方向就自动地转动一个字母的位置。也就是说,当第一次键入b时,信号通过转轮中的连线,灯A亮起来,放开键后,转轮转动一格,各字母所对应的密码就改变了;第二次键入b时,它所对应的字母就变成了C;同样地,第三次键入b时,灯E闪亮。

这是Enigma的秘密所在,它绝非是以往的那种“简单代替密码算法(Simple Substitution cipher)”。同一个字母b在明文的不同位置时,可以被不同的字母替换,而密文中不同位置的同一个字母,可以代表明文中的不同字母,频率分析法在这里就没有用武之地了。这种加密方式被称为“多表代替密码算法(polyalphabetic substitution cipher)”。

多表代替密码有多个单字母密钥,每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母,第二个密钥加密明文的第二个字母等等。在所有的密钥用完后,密钥又再循环使用,若有20个单个字母密钥,那么每隔20个字母的明文都被同一密钥加密,这叫做密码的周期。

在经典密码学中,密码周期越长越难破译,使用计算机就能够轻易破译具有很长周期的代替密码。跟今天不断升级的加密算法位数一样,加密过程中编码重复出现的现象是很危险的,重合指数(index of coincidence)过高可以使试图破译密码的人看见规律性的东西。为了避免在加密过程中产生大量的重复编码,Enigma可以在机器中任意添加转轮,每添加一个转轮,就会增加新的破解难度,如同64位加密算法升级到128位一样,当第一个转轮转动整整一圈以后,它上面有一个齿拨动第二个转轮,使得它的方向转动一个字母的位置。

用这样的方法,要26*26=676个字母后才会重复原来的编码。而事实上通常使用的Enigma里有三个转轮,它使得不重复的方向个数达到26*26*26=17576个。机密度更高的部门可以添加更多的转轮,如二战后期德国海军所用的Enigma甚至有四个转轮,因为所有的转轮以不同的速度移动,n个转轮的机器的加密周期就是26n次方,这样的加密强度可想而知。

而在此基础上,谢尔比乌斯更是十分巧妙地在三个转轮的一端加上了一个反射器,这样能够让Enigma把键盘和显示器中的相同字母用电线连在一起。反射器和转轮一样,把某一个字母连在另一个字母上,但是它并不转动。

事实上它只是一个巧妙的开关,使用者并不需要知道它的是如何工作的情况。他们只需要知道,当一个键被按下时,信号不是直接从键盘传到显示器(要是这样就没有加密了),而是首先通过三个转轮连成的一条线路,然后经过反射器再回到三个转轮,通过另一条线路再到达显示器上,在这种设计下,反射器虽然没有像转轮那样增加可能的不重复的方向,但是它可以使译码的过程和编码的过程完全一样,大大的提高了使用的简洁性。

在今天,我们仍然可以想象这样场景,一台Enigma摆放在我们的面前,我们将它轻轻的开启,发送一条消息。我们首先通过调节Enigma三个转轮方向,使它们处于17576个方向中的一个,而转轮的初始方向就密匙,这是我们收发双方事前就预先约定好的秘密。

我们轻轻敲打它富有历史感觉的键盘,加入明文的消息。在Enigma的显示器中,每个被键入的字母都依次闪亮并被记录下来,接着它把加密后的消息转换为密文通过电报传送出去。我们的收信方在接收到密电后,打开手中同样的Enigma

按照我们的事先约定,把转轮的方向调整到和发信方相同的初始方向上,然依次键入收到的密文,并把闪亮的字母依次记下来,就得到了明文于是加密和解密的过程就是完全一样的——这都是反射器起的作用。不过反射器也并非十全十美的,它所带来的一个副作用就是你输入的每一个字母都永远也不会被加密成它自己本身,因为反射器中每一个字母总是被连到另一个不同的字母伤了。

Enigma的设计思想理念中,转轮的初始方向决定了整个密文的加密方式。这就造成了一个问题,如果通讯过程中有敌人监听,而且他能够截获到完整的密文,这样他就可以实施破解。但是由于不知道三个转轮的初始方向,他唯一的办法就是不得不一个个方向地试验来找到这个密匙。

此时关键的问题出现了。

17576个初始方向似乎并不是非常大的一个数字,如果试图破译密文的人非常有耐心你,他就可以把转轮调整到某一方向,然后键入密文开头的一段话,再判断一下出现的结果是否是有意义的内容。如果没有意义,那么再转动一下转轮,让它调换到下一个出示方向——如果测试一个方向只需要一分钟,而他一天二十四小时日以继夜地工作,那么在大约两星期后,敌人就能够找遍转轮所有可能的初始方向。此时,如果对手用许多台机器同时破译,那么所需要的时间更会大大缩短。

显然,这种加密的强度显然不够健壮和强大。

当然,你可以让谢尔比乌斯继续增加转轮,但是每加一个转轮只是让初始方向的可能性多了二十六倍而已,而仅仅依靠转轮的增加来增强加密强度,也会让Enigma的体积无限增大,缺乏易用性。此时,谢尔比乌斯相当了一个更加巧妙的办法。

首先谢尔比乌斯把Enigma的三个加密转轮制作成为可方便自由拆卸的形式,这样能够让使用者自己DIY调整Enigma转轮的组合方式,这样一来初始方向的可能性变成了原来的六倍。

假设三个转轮的编号为123,那么它们可以被放成123-132-213-231-312-321六种不同位置,当然现在收发消息的双方除了要预先约定转轮自身的初始方向,还要约定好这六种排列中的使用一种。

接下来,谢尔比乌斯又在Enigma的键盘和第一个转轮之间增加了一个连接板。这块连接板能够让使用者用一根信号线将某一个字母和另外一个字母任意连接,这样这个字母的信号在进入转轮之前就会转变为另一个字母的信号。这种连线最多可以有六根甚至更多,当然连接板上的连线状况也是收发信息的双方需要预先约定的。

于是转轮自身的初始方向,转轮之间的相互位置,以及连接板连线的状况就组成了所有可能的密匙,好的,现在让我们来算一算做了这样改动的Enigma一共到底有多少种组合加密可能性哪?

三个转轮不同的方向组成了26*26*26=17576种不同可能性;

三个转轮间不同的相对位置为6种可能性;

连接板上两两交换6对字母的可能性数目非常巨大,有 100391791500种;

于是一共有17576*6*100391791500,大约为10000000000000000,即一亿亿种可能性。

如果双方都有密匙,那么收发密文与加密解密很容易。但是对于不知道密匙的破解者来说,在这巨大的可能性面前,想通过逐一尝试来找到密匙的方法是没有任何可行性的。

既然连接板如此重要,那么为什么谢尔比乌斯还要兴师动众的为Enigma设计转轮之类的东西呢?原因在于连接板本身其实就是一个简单替换密码系统,在整个加密过程中,连接是固定的,所以单使用它是十分容易用频率分析法来破译的。

转轮系统虽然提供的可能性不多,但是在加密过程中它们不停地转动,使整个系统变成了复式替换系统,频率分析法对它再也无能为力,与此同时,连接板却使得可能性数目大大增加,使得暴力破解的方法成为永远的不可能。

强大的Enigma让德国军方很快的爱上了它,他们几乎对于Enigma的加密信心显得无比十足。而Enigma的强悍加密方式在当时而言,也的确是困扰盟军的巨大障碍,面对一个个通过Enigma相互联系的德国海狼U型潜艇们,面对如此高强度但造价却低廉的Enigma,盟军第一次开始品尝到加密的噩梦。

Enigma也成为了战争史上最成功的信息加密之王。

但它是真的是不可能被破解的吗?

……待续……

 

资料:Enigma发展史

1926年,民族仇恨绝不比丘吉尔先生弱的德国海军、首当其冲吃了英国海军部“第40号房间”大亏的德国海军,率先决定采购Enigma的海军型——Enigma Funkschlüssel C型。

1927年,Enigma-D开发成功;

1927年,Enigma-E开发成功;

1927年,Enigma-F开发成功;

1927年,Enigma-D在英国获得专利;

1928年,Enigma-D被美国军队获取;

1928年,Enigma-G军用型开发成功,德国陆军、空军开始批量采购;

1929年,Enigma-H开发成功;

1930年,Enigma-Ⅰ(这里是罗马数字Ⅰ)军用型开发成功,被德国陆军、空军批量采购;

1930年,Enigma-H在英国申请专利,次年获得专利权;

1931年,Enigma-K开发成功;

1932年,波兰、瑞典先后获得EnigmaK

1932年,在Enigma-Ⅰ军用型的基础上,Enigma-Ⅱ军用型开发成功,再次被德国陆军、空军采购;

1934年,日本购得Enigma-K

1934年,Enigma Funkschltissel M(海军型)开发成功;

1935年,西班牙、意大利先后获得Enigma-K

1936年,在Enigma-Ⅰ军用型的基础上,改制出德国国防军型EnigmaWehrmacht Enigma);

1937年,日本依靠购来的Enigma-K,参考借鉴后成功研发出大名鼎鼎的紫密;

1937年,德国党卫队开始装备Enigma

1938年,Enigma MOB-38型开发成功,装备德国陆军、空军;

1938年,Enigma的海军型升级为Enigma Funkschlossel M-2型(即M2Enigma);

1938年,Enigma商业型(具体型号不详)被德国帝国邮政局采购并装备;

1938年,Enigma商业型(具体型号不详)被德国帝国铁路局采购并装备;

1939年,日本在Enigma-K及紫密的基础上,发展出日本海军型密码机;

1939年,Enigma MOB-39型开发成功,装备德国陆军、空军;

1939年,Enigma的海军型再次升级为Enigma Funkschltissel M-3型(即M3Enigma);

1939年,开发出德国军事情报署型EnigmaAbwehr Enigma)。

二战爆发

1942年,Enigma的海军型升级为Enigma Funkschltissel M-4型(即M4Enigma);

1942年,开发出德国一日本海军通用型号Enigma-T(或EnigmaModel T型);

1943年,海军型又升级出M-B型、M-8型;

1945战争结束,甚至到了纳粹德国苟延残喘的1945年,全新开发的M-5型和由M-B型发展而来的M-10型还分别装备了陆海空三军……

参考资料:

D.KahnThe Codebreakers: The Story of Secret WritingNew York: Macmillan Publishing Co.1967

B.C.W.Hagelin,” The Story of the Hagelin Cryptos ”

Bruce Schneier,《应用密码学——协议、算法与C源程序》

2012-05-18

落在广岛和长崎这两座日本城市的原子弹,通过这种死神才能够呼吸出的恐怖力量,让第二次世界(1939~1945)大战戛然而止。

随之而来的是被称为冷战的时期。在上一个千禧年临近尾声前的50年间,美国和苏联两个帝国,分别代表着资本主义和共产主义两个敌对的政治体制,成了不言而喻的敌手。他们并不曾直接兵戎相见,但相互都亮出了不少恫吓的招数。由于这两者都掌握着足以将对方完全摧毁的手段,因此谁也不敢先下手,致使世界系于提心吊胆的和平状态下。它们都各自不断开发出新的致命武器,而且势头简直无法遏止。这就是所谓的“军备竞赛”。在这场有如“打冤家”的长期争斗中,这种载有核弹头,轻而易举就能够打倒其它国家的导弹,无疑是最强大的武器。因此,争相取得有关技术的进步,本身也成了这两大世界强权极力角逐的内容。无论是实现军事抱负,还是争取技术进步,空间探索都能提供诸多的机会。美国和苏联谁能最先将人送上月球,就将无疑证明自己胜过了对方。

当苏联宇航员尤里.阿列克塞耶维奇.加加林(Yuri Alekseyevich Gagarin)在1961年环绕地球飞行了一周,让苏联人大为欣喜、美国人沮丧不堪之后,人们才知道,一场伟大的探险已告开始。这是一场人类脱离自身栖身的小小行星、大胆进入宇宙的宏伟大业的肇始之笔。对于这场伟业,固然有人满怀希望,却也有人心存恐惧。心怀疑惧的理由是,****人已开始了对空间的征服,并使冷战技术实现了令人震惊的飞跃。美国人林登.约翰逊在他当副总统时说过:“我可不高兴在共产主义的月亮下入睡。”这句话是很有代表性的。

而也就是在1957年前苏联发射第一颗人造卫星之后,美国国防部“高级研究计划署”(Advanced Research Project Agency)出于对前苏联太空实力的恐惧与防止远程核打击冷战思维考虑,开始建立ARPA网,ARPANETThe Advanced Research Projects Agency Network)后来成为世界上第一个运营的封包交换网络,它是全球互联网的始祖,而在此后的四十多年时间里,它所延伸出来的Internet成为了病毒与黑客肆意成长的温床。

Enigma与现代密码学

ARPANET的诞生,不但是一个新时代的开始,也是20世纪内一场激荡起伏的网络黑客时代的开始。而在ARPANET出现前的几十年前,现代黑客的另一项重要“加密与破解”技术已经开始变得日益重要,以至于它推动了现代密码学的发展和电子计算机的诞生。

对于各国的密码加密和解密精英们,这一奋战始于1918年,在那一年德国工程师阿瑟·谢尔比乌斯(Arthur Scherbius)申请了他设计的一种使用转子的密码机的专利,而这台机器成为了现代密码学历史上最出名的密文加密机器恩尼格玛密码机(德语:Enigma,又译哑谜机,或谜),不幸的是,这台居于历史意义的机器在最初销售的时候,并没有人对它产生任何兴趣。

不过随后英国政府发表了两份关于一次大战的文件使得德国军队开始对恩尼格玛密码机兴趣大增。其中一份是1923年出版的温斯顿·丘吉尔的著作《世界危机》,其中有一段提到了英国和俄国在军事方面的合作,指出俄国人曾经成功地破译了某些德军密码,而使用这些成果,英国的40局(英国政府负责破译密码的间谍机构)能够系统性地取得德军的加密情报。德国方面几乎是在十年之后才知道这一真相。第二份文件同样是在1923年由皇家海军发表的关于第一次世界大战的官方报告,其中讲述了在战时盟军方面截获(并且破译)德军通讯所带来的决定性的优势。这些文件构成了对德国情报部门的隐性指控,他们最终承认“由于无线电通讯被英方截获和破译,德国海军指挥部门就好象是把自己的牌明摊在桌子上和英国海军较量。”

为了避免再一次因为文件被敌方的密码破译人员“破解”,德军对谢尔比乌斯的发明进行了可行性研究,最终得出结论:必须装备这种加密机器。从1925年开始,谢尔比乌斯的工厂开始系列化生产Enigma,次年德军开始使用这些机器。接着政府机关,比如说国营企业,铁路部门等也开始使用Enigma。这些新型号的机器和原来已经卖出的一些商用型号不同,所以商用型机器的使用者就不知道政府和军用型的机器具体是如何运作的。

在接下来的十年中,德国军队大约装备了三万台Enigma。谢尔比乌斯的发明使德国具有了最可靠的加密系统。在第二次世界大战开始时,德军通讯的保密性在当时世界上无与伦比。似乎可以这样说,Enigma在纳粹德国二战初期的胜利中起到的作用是决定性的,但是我们也会看到,它在后来希特勒的灭亡中扮演了重要的角色。但是谢尔比乌斯没有能够看见所有这一切。有一次在套马时,他被摔到了一面墙上,于1929513日死于内脏损伤。

不过在谢尔比乌斯意外死亡的那一年,一位名叫阿兰·麦席森·图灵(Alan Mathison Turing)的17岁少年开始研究爱因斯坦的相对论,随后他以优异的成绩考入剑桥大学国王学院,开始他的数学生涯,他在大学中主攻研究量子力学、概率论和逻辑学。而也就是这位天资无比的年轻人,在随后的战争期间凭借着他的天才设想设计出了Enigma的破译机。这台机器主要由继电器构成,还用了80个电子管,由光电阅读器直接读入密码,每秒可读字符2000个,运行起来咔嚓咔嚓直响。它被图灵戏称为“罗宾逊”,至今没人能搞懂图灵究竟如何指挥它工作。但“罗宾逊”的确神通广大,在它的神奇般的破译中,Enigma的看似在当时不可能被破译的秘密屡次被攻破,让二战中的德国飞机一再落入圈套,死无葬身之地。

附录:

现代黑客的划分