游戏百科

密码破译如何催生了计算机科学的黎明?

沉默的加冕礼1939年9月1日,德军装甲师越过波兰边境。同一天,伦敦海军部无线电监听室截获了一组来自大西洋的信号。对于监

沉默的加冕礼

1939年9月1日,德军装甲师越过波兰边境。同一天,伦敦海军部无线电监听室截获了一组来自大西洋的信号。

对于监听员来说,这些信号并不陌生。它们由摩尔斯电码组成。但是,这组字母组合没有任何意义。此前,德国海军的电报虽然加密,但总有一些固定的报头或格式可循。这一次,记录纸上只有杂乱无章的字母流。

并没有人意识到,这是一种新的数学语言。

在此前一周,德国海军上将卡尔·邓尼茨下令更改了所有U型潜艇的恩尼格玛(Enigma)密码机设置。转子的起始位置变了,插线板的连接变了。对于英国情报机构来说,大海突然变成了一个黑洞。

数据随即在劳埃德保险公司的账簿上体现出来。9月3日,“雅典号”客轮被击沉;9月17日,“勇敢号”航空母舰被击沉。1939年的最后四个月,英国商船损失了超过75万吨。

每一艘船沉没前都发出了求救信号,但英国海军无法提前预警。对手不是某一位狡猾的指挥官,而是一台装在木盒里的机械装置。这台机器每按下一个键,电流就会流经三个转动齿轮和一块插线板,将原本的字母变成另一个毫不相关的字母。

人类的大脑无法对抗这种排列组合。英国军情六处(MI6)不仅需要更多的听音员,他们需要一种能与齿轮对话的逻辑。

华沙的快递

早在战争爆发前的五周,1939年7月25日,两个英国人和两个法国人穿过华沙南部的皮里森林,走进一间代号为“BS-4”的地下室。

波兰密码局的马里安·雷耶夫斯基(Marian Rejewski)没有寒暄,他指着桌上的一个黑盒子。那是波兰人逆向工程制造的恩尼格玛复制品。

在那个年代,英法情报界的共识是:密码破译属于语言学家。他们寻找单词的频率,猜测句子的结构。雷耶夫斯基是数学家,他通过群论(Group Theory)分析出,德军通信员为了省事,经常将三个字母重复输入两次得到六个字母的密钥。利用这个操作漏洞,波兰人制造了一种名为“Bomba”的机电装置——这是历史上第一台以此目的制造的机器。

Bomba运行时发出巨大的滴答声,仿佛炸弹倒计时。

这个英国人震惊地看着这台机器和厚厚一叠德军恩尼格玛机的内部线路图。

此时,英国密码学校甚至还不知道恩尼格玛机内部转子的具体接线逻辑。波兰人将这一切装进外交邮袋,交给了英国人。

然而,这份馈赠不仅附带了答案,也附带了绝望。雷耶夫斯基坦承,德国人在1938年12月增加了两个新的转子,并将插线板的连线数量从6根增加到10根。排列组合的数量呈现指数级爆炸。波兰人的资金和算力已经耗尽。

就在英国人带着机器回到伦敦后不久,德军再次升级了系统。他们不再重复输入密钥。波兰人的方法瞬间失效。英国人手里捧着的是一份过期的操作手册,而战争已经开始了。

布莱切利园的怪人

英国政府在布莱切利园(Bletchley Park)设立了政府密码学校。这是一座位于伦敦和剑桥之间的维多利亚式庄园,建筑风格混杂,被形容为“像一堆丑陋的砖块堆砌在一起”。

这里没有正规军的肃杀气氛。草坪上散步的是象棋冠军、古埃及纸草研究者、填字游戏高手和几位数学家。

阿兰·图灵(Alan Turing)骑着一辆链条松动的自行车报到。为了防止链条脱落,他在骑行时会数踏板的转数,每到特定圈数就倒踩一下。因为患有花粉症,他在庄园内行走时戴着防毒面具,用绳子系住裤脚。

图灵被分配到8号营房(Hut 8),负责德国海军密码的破译。

这里的负责人迪尔温·诺克斯(Dillwyn Knox)是一位古典学者,他信奉直觉和语言学分析。图灵对这种“猜谜”游戏毫无兴趣。他甚至不怎么与其他同事在食堂吃饭。在图灵看来,依靠语言学家的直觉去对抗一台数学机器是徒劳的。

只有机器才能击败机器。

图灵在8号营房的办公桌上铺开图纸。他不再试图通过语言规律去寻找破绽,他要从逻辑上证明,某些组合是绝对不可能的。

一亿亿种可能

恩尼格玛机的核心在于复杂性。

一台标准的陆军型恩尼格玛机有三个转子,每个转子有26个刻度。这产生了26 X 26 X 26 = 17,576种位置。但这只是开始。

这三个转子可以从五个备选转子中选取,排列顺序有60种(计算方法:排列数P(5,3)=5×4×3=60种)。最致命的是机器前端的插线板。操作员用10根电缆连接20个字母,交换它们的电流路径。仅仅这一个步骤,就产生了150万亿种可能性。(计算方法:10根电缆连接20个字母的组合数为C(26,20)×(19!!)=150,738,274,937,250(约150万亿)——用10根电缆需先从26个字母中选出20个(这一步对应组合数 C(26,20)),再将这20个字母两两配对,另外19!! 为双阶乘,代表 20 个元素两两配对的无顺序组合数))

综合计算,恩尼格玛机的总设置状态约为1590亿亿种,相当于让全球 70 亿人每秒尝试 1 种组合,需要约 7000 万年才能遍历所有可能。

这是一个天文数字。

德国国防军对此充满信心。他们知道这台机器在理论上并非不可破解,但他们赌的是时间。战术命令的时效性通常只有几小时甚至几十分钟。如果英国人需要一个月才能解开今天的命令,那么这条破译信息就是废纸。

图灵盯着电路图。他发现了一个并非数学、而是物理设计上的特征:恩尼格玛机的反射器设计导致了一个致命的逻辑闭环——一个字母加密后,永远不会是它自己。A绝不会变成A。

这个微小的物理限制,成为了撬动1590亿亿的支点。

铜与铁的逻辑陷阱

图灵并没有试图寻找“正确”的答案,他开始寻找“矛盾”。

他设计了一台巨大的机电装置,叫“炸弹机”(The Bombe)。但这台机器的逻辑完全不同。

图灵需要一个突破口,行话叫“Cribs”(猜词)。德军气象观测站每天早上6点会在固定的格式中发送天气预报,必然包含德语单词“Wetter”(天气)。

图灵将这种必然性转化为电路逻辑:如果假设某个位置的字母是W,而机器解密出来是W,根据“A不等于A”的铁律,这个设置就是错的。

英国制表机公司(BTM)负责制造这台机器。它高约2米,宽约2.5米,重达一吨,正面布满了模仿恩尼格玛转子的彩色转鼓。

另一位数学家戈登·韦尔什曼(Gordon Welchman)加入进来。他发现图灵的设计虽然能运作,但效率依然不够高。韦尔什曼设计了一个名为“对角板”(Diagonal Board)的电路附件。这个简单的连接装置利用了恩尼格玛机插线板的可逆性(如果A连B,则B连A),让机器能够在检测到一个矛盾的瞬间,同时排除掉成千上万个相关联的错误组合。

1940 年 3 月,首台炸弹机原型机完成测试;同年 8 月,第一台量产型炸弹机‘阿格尼斯’投入使用。

机器启动时,几十个转鼓飞速旋转,发出令人牙酸的金属摩擦声和继电器的咔哒声。它不是在计算数字,它是在进行每秒数千次的逻辑判断。

当所有转鼓突然停止,噪音消失,那意味着电流找到了一条没有逻辑矛盾的通路。那一刻,显示在面板上的设置,就是德军当天的密钥。

U型潜艇的M4

1941年,大西洋海战正在进行。

虽然德国陆军和空军的密码陆续被破译,但德国海军在1942年2月给U型潜艇配备了新的恩尼格玛机(M4)。这种机器增加了第四个转子。

布莱切利园陷入了黑暗。

在随后的10个月里,没有任何一艘潜艇的信号被解读。大西洋上的运输船队只能盲目航行。吨位损失图表上的曲线几乎垂直上升,直逼英国承受力的极限。

图灵的炸弹机是针对三转子系统设计的,面对四转子,计算量增加了26倍。现有的机器跑断了齿轮也跟不上。

既然数学遇到了瓶颈,英国海军部决定动手抢。

1941年5月,英国驱逐舰逼停了受损的德国潜艇U-110。登船队直奔无线电室,成功俘获完整的恩尼格玛机、密码本及操作手册。1942年10月,类似的剧情在U-559号潜艇上重演。但是两名英国水手在抢救文档时随潜艇沉没溺亡。

这些用生命换来的纸质文档——包括气象短码本——填补了数学计算的空白。图灵利用这些文档缩小了搜索范围,让原本过载的炸弹机重新开始破译密码。

此时,图灵并没有留在布莱切利园庆祝。他搭乘没有任何护航的邮轮穿越充满潜艇的大西洋,前往美国。

在俄亥俄州的代顿,图灵视察了美国国家现金出纳机公司(NCR)。美国人正在利用强大的工业能力量产炸弹机。图灵的任务是确保美国人制造的机器能用,同时严守核心机密。这是一场微妙的博弈:英国人有逻辑,美国人有产能。

随着数百台美制炸弹机投入运转,大西洋不再是黑洞。

巨人机的诞生

就在图灵对抗海军密码的同时,另一个更庞大的阴影出现了。

德国最高统帅部开始使用一种代号为“Tunny”的洛伦兹密码机(Lorenz SZ40/42)。这种机器有12个转子,用于希特勒与其元帅之间的直接通讯。比起恩尼格玛,它的复杂程度高出一个量级。

布莱切利园的数学家马克斯·纽曼(Max Newman)试图用机械装置破解它,但洛伦兹机的加密流太长,机械式读带机的速度受限于物理摩擦,一旦加速,纸带就会被扯断。

邮政局的工程师汤米·弗劳沃斯(Tommy Flowers)站了出来。他提出一个激进的方案:抛弃继电器,使用真空电子管。

当时的工程界公识是电子管不可靠,寿命短,极易烧毁。弗劳沃斯反驳道:电子管烧毁是因为开关时的热冲击,如果让机器永远开着,它们就能一直工作。

虽然图灵没有直接参与这个项目,但他经常出现在纽曼的办公室里。早在1936年,图灵发表了一篇题为《论可计算数》的论文,提出了“通用图灵机”的概念——一种能够模拟任何算法逻辑的机器。

弗劳沃斯制造的机器正是这种理论的物理实体。

1943年12月,第一台“巨人机”(Colossus)运抵布莱切利园。它使用了1500个电子管,每秒能处理5000个字符。它没有机械转动部件,只有光电阅读器和电子流。

当巨人机的光电管亮起,它不再只是在破译密码。它在证明,逻辑符号可以通过电流进行高速运算。这是人类历史上第一台可编程的电子数字计算机。

毁灭证据

1945年5月,欧洲战事结束。

布莱切利园收到了来自温斯顿·丘吉尔的直接命令:毁灭一切。

没有庆祝仪式,没有勋章授予。工程师和数学家们拿起锤子和螺丝刀。几千台耗资巨大的炸弹机和巨人机被拆解成废铁。图纸被扔进火炉,电路图被撕碎。每一个组件都被砸得面目全非,以确保没有任何人能复原它们。

丘吉尔称这些人是“下金蛋的鹅,但绝不叫唤”。

为了保护这一秘密,英国政府决定让它从历史上消失。参与者被告知,如果有谁泄露半个字,将以叛国罪论处。数千名曾在那个庄园里用数学左右战争进程的人,回到了原本的生活。他们变成了沉默的数学老师、银行职员和家庭主妇。

大西洋彼岸,美国人公开了埃尼阿克(ENIAC),并宣称那是世界上第一台电子计算机。

阿兰·图灵在战后被国家物理实验室聘用,试图设计通用计算机(ACE),但因官僚主义受阻。1952年,他因同性恋行为被定罪,被强制进行化学阉割(注射雌激素)。

1954 年 6 月 7 日,图灵被发现死于家中,床头留有一个咬过的苹果,验尸报告判定为氰化物中毒,官方结论为自杀,后世对此存在部分争议。

历史的遗留

直到1970年代,关于布莱切利园的档案才开始解密。此时,计算机科学已经建立了自己的神殿,而它的基石——那些在寒冷的8号营房里被推导出来的逻辑——才刚刚被世人知晓。

今天,在每一块硅片的微观电路里,在每一个逻辑门的开合之间(比如手机、电脑),依然运行着图灵在1936年设想的规则。

为了对抗战争,人类被迫发明了思考机器。战争结束了,但机器留了下来,并接管了世界。