in

Colossus计算机的历史

要点:
  • 马克斯·纽曼设计了一台名为希思·鲁宾逊的机器,根据插图设计师的设计来解密机密信息。
  • 弗拉尔斯是一位工程师,他设计并建造了一个名为科洛苏斯的机器,以满足马克斯·纽曼对加快破解洛伦兹密码的要求。
  • 科洛苏斯能够将破解洛伦兹密码所需的时间从几周缩短到几小时,及时解密出提供给艾森豪威尔和蒙哥马利的关键信息。

数学家马克斯韦尔·纽曼和工程师托马斯·弗拉尔斯

科洛苏斯计算机,由马克斯·纽曼和托马斯·弗拉尔斯设计

二战阻碍了像阿塔纳索夫祖塞这样的计算机发明家的进展,但对首次创造电子计算机的英国步伐产生了相反的影响。在战争期间,英国外交部的通信部门创建了使用电子电路的机器,以协助英国解码德国的无线电消息,这些消息使用特殊的机器进行编码。英国的电子计算机是由一组人创建的,其中著名的英国数学家马克斯韦尔·纽曼和工程师托马斯·弗拉尔斯担任领导角色。还有许多其他人发挥了重要作用,包括艾伦·图灵和c.e.温威廉姆斯。

上图是bletchley park

拦截和解码德国消息是盟军胜利的重要因素,这个事实直到最近才被保密。这项工作在位于伦敦以北约80公里处的bletchley park的政府密码和密码学学校(gc&cs)中进行,这是一个维多利亚式庄园。根据历史学家哈里·辛斯利的说法,gc&cs中的密码分析员的工作对于盟军的胜利至关重要,缩短了战争时间约两年。

一台恩尼格玛密码机

德军开始使用恩尼格玛密码机对军事消息进行编码,于1925年。与德国人的信念相反,恩尼格玛机并不安全。1928年,波兰人通过截获一台运往德国大使馆的恩尼格玛机并对其进行检查,获得了关于德军恩尼格玛的知识。一系列的恩尼格玛机在华沙工厂生产。一群在波兹南大学的优秀数学学生(雷耶夫斯基,罗齐茨基和齐加尔斯基)被招募到波兰总参谋部的密码部门工作。1932年,他们解密了德国的恩尼格玛信号。为了方便解密,雷耶夫斯基设计了一台他称之为波姆巴(波兰语的炸弹)的机电一体化可编程机器,因其像炸弹一样的滴答声而得名。1939年7月,波兰人将波兰制造的恩尼格玛机的复制品以及有关恩尼格玛、波姆巴和解密信息的图纸和信息提供给了法国和英国。在gc&cs工作的两位数学家,艾伦·图灵和戈登·韦尔奇曼,改进了波姆巴机器,并由英国制表机器公司制造了200多台波姆巴

英国人对通过使用“炸弹”解码所有德军通信非常热衷,但是在1940年初,拦截者开始截获德国消息,这些消息使用不同的机器进行编码,无法解码。发生了什么?

一台复古密码机

在1930年代末,德军高级指挥部要求c. lorenz ag公司为他们生产一台高安全性的电传密码机,以使他们能够通过无线电进行完全机密的通信。lorenz ag公司设计了sz40和sz42密码机,这些密码机基于加法方法,用于对电传机的消息进行加密,该方法是由纽约布鲁克林的gilbert s. vernam于1918年发明的(请参阅vernam的专利)。自从1940年以来,恩尼格玛机通常由野战部队使用,洛伦兹机则用于高级通信(包括希特勒的命令),可以支持大型机器、电传机和固定电路。vernam系统通过逐个字符地将一组混淆字符添加到消息文本中来进行加密,从而生成加密文本,并将其传输给预期的接收者。vernam系统的简单之处在于,如果以一种特殊的方式(称为模2加法)添加了混淆字符,那么以完全相同的方式将混淆字符添加到接收到的加密消息中,就可以取消混淆字符并恢复原始消息。vernam建议混淆字符应完全随机,并预穿在纸带上,以与输入消息字符同步地逐个字符消耗。使用纯随机的混淆字符的密码系统是无法破解的。

困难在于,在热战情况下,确保通信链路的两端都有相同的随机字符纸带,并且它们都设置为相同的起始位置。洛伦兹公司决定,构造一台机器来生成混淆字符序列会在操作上更容易。由于它是一台机器,它无法生成完全随机的字符序列。它生成的是所谓的“伪随机”序列。不幸的是对于德军来说,它更多地是“伪”而不是“随机”,这就是它被破解的原因。sz机器的惊人之处(与波兰的密码破译员成功破译恩尼格玛机相比)在于,gc&cs的密码破译员直到战争快结束时才看到了一台实际的sz机器,但他们已经破解洛伦兹密码两年半了。

约翰·蒂尔特曼(john tiltman)是布莱切利园最顶尖的密码破译者之一,他对这些加密的电传报文特别感兴趣。它们被命名为,后来被发现是使用洛伦兹机器加密的报文称为tunny。蒂尔特曼了解弗纳姆系统,并很快确定这些报文是以弗纳姆方式加密的。由于弗纳姆系统依赖于字符的相加,蒂尔特曼推理出,如果操作员犯了错误,使用了相同的洛伦兹机器起始字符来加密两个报文,那么通过逐个字符相加两个密文,遮蔽的字符序列将消失。英国人得到了一些好处 – 1941年8月,两名德国操作员犯了一个可怕的错误,发送了相同的消息两次(根据指令绝对禁止),一个聪明的英国拦截者抓到了这两条消息。蒂尔特曼得到了这些消息,并首次成功完全恢复了两个文本。那是一个突破。

然后,在接下来的两个月里,gc&cs的研究部门完全了解了密码机的逻辑结构。在1942年初,多利斯希尔的邮政研究实验室被要求根据密码破译者的思路来制造一台逻辑实现。弗兰克·莫雷尔(frank morrell)制造了一台模拟逻辑的选通器和继电器的机架,它被称为图尼。所以现在,当测试部门中的手动密码破译者费力地找到了特定消息使用的设置时,这些设置可以插入到图尼上,并读入密文。如果密码破译者设置正确,就能得到德文。但是找出设置要花费四到六个星期的时间。这意味着尽管他们已经证明从技术上来说他们可以破解图尼,但在解码消息时,其中的信息已经过时,无法在操作上有用。密码破译者迫切需要一台更快的机器。

著名的英国数学家马克斯·纽曼(max newman)现在登场了。他认为可以通过电子设备自动化一些寻找每个消息使用的设置的部分。他创建了一台机器的规格,由多利斯希尔的工程师建造。逻辑是通过继电器构建的,但计数器是由查尔斯·艾尔·温·威廉姆斯(charles eryl wynn-williams)设计的电子计数器(t. flowers也参与其中)。这台机器被称为希思·罗宾逊,以幻想机器的漫画设计者命名。

希思·罗宾逊于1943年6月交付给gc&cs。这台机器比较了两个数据流,通过两个磁带读取器输入。第一盘磁带包含拦截的消息,第二盘包含可能解密的消息。不断比较两个磁带并逐渐移动字母将解码消息,结果将被打印在打字机上。然而,希思·罗宾逊也存在一些问题。如果磁带上出现了一长串相邻的孔或没有孔,光学磁带读取器会出错。最大的问题是保持两个磁带在每秒1000个字符的同步状态。即使稍微偏移一点,整个过程也将毫无价值。然而,希思·罗宾逊工作得足够好,证明了马克斯·纽曼的概念是正确的。

纽曼随后前往dollis hill,与托马斯·弗拉华斯取得联系。弗拉华斯是英国邮政电子工程师,他根据纽曼的要求设计并建造了colossus,以加快破解洛伦兹密码的速度。他在建造heath robinson过程中已经提供了一些建议。弗拉华斯的主要贡献是建议使用电子环路电路在电子中生成轮子图案,从而消除了一卷纸带,并完全消除了同步问题。这需要大量的电子真空管,但他相信它可以正常工作。在战争前,他曾设计过使用真空管的邮局中继器。他知道,只要永远不断开和关闭,真空管是可靠的。没有其他人相信他!后来,弗拉华斯将说:“我在1943年2月提出的建议遭到了相当多的怀疑。最初的反应是,显然需要大量真空管的机器将不够可靠,无法发挥作用。幸运的是,这个批评被邮局在其通信网络中使用数千个真空管的经验击败了。在这些条件下,真空管故障非常罕见。”

1944年的bletchley park的colossus

colossus(后来称为colossus mark i)的设计始于1943年3月。到1943年12月,所有各种电路都已经运作正常,colossus被拆卸并运往gc&cs进行组装。colossus使用最先进的真空管(热电子管)、闸流管和光电倍增管来光学读取纸带,然后对每个字符应用可编程逻辑函数,计算此函数返回“true”的次数。这台计算机(见上图)在1944年1月投入运营,并在第一次对真实加密的消息纸带进行测试时取得了成功。colossus能够以每秒5000个字符(cps)的速度读取纸带,纸带以每小时约50公里的速度通过它,将破解洛伦兹密码所需的时间从几周缩短到几小时,正好为艾森豪威尔和蒙哥马利提供了重要信息,以便在d day之前解密。这些解密的洛伦兹消息显示,希特勒相信了欺骗行动,即英格兰南部的虚拟军队,沿着海峡东移的虚假船队,希特勒相信袭击将从加来海峡发起,他正在比利时保留装甲师。在d day之后,法国抵抗运动以及英美空军轰炸和扫射了北法的所有电话和传真地线,迫使德军使用无线电通信,拦截到的消息数量突然大幅增加。

1944年6月,改进版的colossus mark i被开发出来,称为mark ii,并且很快建造了另外八台机器以处理消息的增加。mark i被升级为mark ii,因此战争结束时,gc&cs共有十台mark ii colossi。到战争结束时,已解密了6300万个高级德国消息的字符。mark ii含有2500个真空管和800个继电器,能够以25000 cps的速度读取(比mark i快五倍),这是由于并行处理和缓冲存储器(寄存器)的组合,以及包含一个在发现可能的代码模式时自动更改程序的电路。

colossus的框图

十台colossi中的每一台占据了bletchley park的一个大房间。机架高2.3米,宽度各不相同。有八个机架排列在两个约5.5米长的间隔内,还有纸带阅读器和纸带处理器。数据输入是加密文本,以5000 cps的速度打孔在5孔纸带上读取。输出被缓冲到继电器上,并打印在打字机上。处理器具有5位字符的5位内存,保存在移位寄存器中,可插拔逻辑门和20个十年计数器,排列为5乘4的十年。时钟速度为5 khz,由输入纸带中的齿孔导出。colossus的交叉关联算法的编程通过电话插孔、电线和开关的组合实现。

胜利日后,突然一切都结束了。十台colossi中的八台被拆除在bletchley park。两台被送往伦敦,并于1960年左右被拆除,同年colossus的所有图纸都被焚毁,当然它的存在也被保密。在1970年代,有关colossus的信息开始出现。纽卡斯尔大学的brian randell教授开始研究这台机器。1980年代,flowers博士和其他一些设计工程师撰写了关于colossus的论文,描述了一些相当一般的情况。

colossus是第一台具有程序可编程性的电子数字机器,尽管从现代的角度来看,这种可编程性是有限的。然而,它并不是一个完全通用的turing完备计算机,即使alan turing在bletchley park工作过,它也不是一个存储程序计算机。当时还没有意识到turing完备性的重要性;大多数其他开创性的现代计算机也不是turing完备的(例如atanasoff-berry计算机,哈佛mark i机电继电器机器,贝尔实验室的继电器机器(由george stibitz等人),或konrad zuse的第一批设计)。将计算机视为通用目的机器,即不仅仅是解决困难但特定问题的计算器,这个概念在几年后才变得突出。

由于它的并行性,colossus非常快,即使按照今天的标准也是如此。普通的打字机纸带上的拦截到的消息每秒读取5000个字符。纸带中间的齿孔被读取以形成整个机器的时钟。这样无论纸带的速度如何,都不会出现任何同步问题,那就是colossus的速度。汤米·弗拉尔斯曾经将纸带驱动电机卷紧,想看看会发生什么。以每秒9600个字符的速度,纸带破裂并飞向房间的各个角落,速度约为100公里/小时!因此决定将速度限制在5000个字符/秒。在每秒5000个字符的速度下,齿孔之间的间隔为200微秒。在这个时间内,colossus将在五个纸带通道上同时进行多达100个布尔运算,并通过一个五个字符的矩阵进行计算。闸门延迟时间为1.2微秒,对于非常普通的电子管来说,这是相当了不起的。它展示了汤米·弗拉尔斯的设计技能。

1994年,由托尼·萨尔(tony sale)领导的一个团队在布莱切利公园开始了一次colossus的重建工作。当机器(见上图)准备好后,于2007年11月,为庆祝项目完成和标志着筹款活动的开始,《国家计算机博物馆》组织了一场比赛,让重建的colossus与全球的业余无线电爱好者同台竞技,看谁首先接收并解码三条使用lorenz sz42加密的信息,这些信息从海因茨·尼克斯多夫博物馆的无线电台dl0hnf传输而来。这个挑战很容易被业余无线电爱好者约阿希姆·舍特(joachim sch??th)赢得,他为这个事件精心准备,并使用ada计算机语言开发了自己的信号处理和解密代码。colossus团队因希望使用二战时期的无线电设备而受到阻碍,由于接收条件不佳,他们耽搁了一天。但是胜利者使用的1.4 ghz笔记本电脑,运行着他自己的代码,不到一分钟就找到了所有12个轮子的设置。这位德国密码破译者说:“我的笔记本电脑以每秒1.2百万个字符的速度处理密文,比colossus快240倍。如果你按照这个因素来缩放cpu频率,那么colossus的等效时钟就是5.8 mhz。对于1944年建造的计算机来说,这是一个非常了不起的速度。”

Written by