五千年(敝帚自珍)

主题:【原创】密码传奇(三):20、Bombe出世 -- 1001n

共:💬34 🌺50
全看树展主题 · 分页首页 上页
/ 3
下页 末页
家园 【原创】密码传奇(三):20、Bombe出世

到了这会儿,ENIGMA的破译就简单多了——针对转轮组的穷尽暴力攻击,现在已经成为了可能——转轮组不是由三个转轮组合成的么?每个转轮不是有26个位置么?那好,只要针对性地分别模拟出26 *26 * 26 = 17576种变化,一个特定转轮组的全部可能不就被穷尽了么?

看到这里,也许有兄弟会想起以前在介绍ENIGMA的转轮组时,专门讲过的“双重步进”问题——的确,特定转轮组在实际运行的时候,可能导致的变化是26 * 25 *24 = 16900 种变化;但是现在不是为了计算加密时的变化可能总数,而是为了穷尽式地破解,自然要遍历所有17576种可能;谁又能知道德国人在某封密电中,把转轮的进位点设置在哪里呢?

——还是一个不漏地全算一遍,来得比较妥当啊。

这里顺便提一句:波兰人管自己的ENIGMA破译机叫“Bomba”,得到启发的英国人则变a为e,把自己的机器叫做“Bombe”——只是由“波霸”而“宝贝”,这音译出的名字无论怎么读,意思好像都差不多。。

在讲述ENIGMA的构造的时候,我们提到过:ENIGMA其实是个电-机械复合体,所有的机械变化,其目的都在不断地改变内部连线路径,最终产生唯一一条可以导通的电路。而针锋相对的Bombe自然也不例外,同样也是这样一个电-机械复合构造:当机器飞快运行的时候,电路一般是不通的;一旦通了,灯泡亮起来,机器也就停止运转了。

停下来的时候,Bombe此时的各部件位置,就是密文拍发时的ENIGMA的转轮组位置——到这时候,ENIGMA密电的密钥也就被“算”出来了。

概括来说,ENIGMA密文的密钥应该是两部分:转轮组的多表加密是一部分,连接板(包括输入轮)的单字替代加密又是一部分。现在,多表加密已经被破解了,那么,只要把单字替代再给废掉,明文不就出现了么?

还以wetter为例吧。

比如说,在Bombe破解了当日转轮组设置以后,又依此从ENIGMA密文中还原出了“准明文”quzzue,分析员就有活干了——如果用一串数字按顺序表示quzzue的字母分布,那么quzzue就呈现为“123324”的形式;符合这个形式的德文单词并不特别多,也是可以穷尽的。这样一来,在不多的候选单词中,把它们还原成同样是“123324”格式的“wetter”,对于天天做这个的分析员来说,简直是小菜一碟。

不过,这一步也有四个地方值得说一下,那就是:

1、最后剥离连接板和输入轮两次单字替代的影响时,其实都用不着区别对待:输入轮的字母替代关系,一经出厂基本就不再改变;因此它的对应关系实际上可以作为一个附加常量,在破解连接板单字替代时一起考虑即可;

2、针对各种常见语言(专指拼音化语言),密码分析人员早就统计总结出了诸如“11233”、“123324”、“12341”之类各种排列的单词总表,对应查找的过程实际很快;

3、考虑到在实际操作中,德军往往不会把ENIGMA连接板上的所有字母全部连上,也就是不会将26个字母全部两两替换,因此刚才所举“quzzue”一例中,全部字母均为被替代过的现象,在实际破解时出现的概率并没有那么大——而搀杂了正确明文字母的“准明文”,无疑十分有利于密码分析人员的还原工作;

3、在Bombe上,其实也有机械化破解连接板的附加装置,后面还要提到。

以上说的过程,只限于明确知道转轮组选用了哪三个转轮,而且清楚知道三个转轮的排列次序的情况;在实际应用中,无法指望事先得知德国人选用哪些转轮,也不知道它们的排列次序,因此,必须穷尽所有这些可能。

在Bombe问世之初,它要对付的ENIGMA一般都是5选3的型号,也即60种转轮组的排列变化。为了得到当天的密钥,理论上确实需要让Bombe把所有可能的ENIGMA设置都“跑”上一遍;换言之,需要把17576种可能“跑”上六十次,才能无遗漏地遍历所有可能。

也让我们做个小规模的估算:假如Bombe“计算”一种可能,也就是机器“跑”上一“步”,需要半秒钟的话,那么为了计算一个特定排列,就需要

17576 ÷ 2 ÷ 60 ≈ 146 分钟,也即2个小时26分钟。

因此,遍历所有可能的时间为

146分钟 * 60 = 146 小时 = 6天零2小时

这就是说,破译某份ENIGMA密电的密钥,在最糟糕的情况下(Bombe处理的最后一种情况才是正确答案),大约需要一周的时间。

考虑到运气一般不会那么背,破译密钥的平均可能时间,大致应该在6天的一半,也就是3天上下——这个结果,应该说比较理想了;虽然不能做到当天密电当天破译,但是时间延迟也不是太厉害,应该属于“总比没有强的多”的可接受范围。

但是,图灵对此不满意——这样做,显然没有发挥Bombe应有的潜力。既然对ENIGMA的密码分析都已经被拆成了串联的图灵机组,那么,这样的机组为什么就不能多做几个,大家同时来呢?

由是,“串联”之后又出现了“并联”,也就是把每个破解单元进行横向并联——它们工作时,不会彼此互相干扰;但是,一旦有某个单元解算出了结果,其它单元也就可以停下来了。

在图灵的设计中,这样的破解单元一共并联了36个;这样一来,初步设计的Bombe,工作速度又可以提高到单组的36倍;过去需要6天零2小时,现在只需要1/36的时间,也即大约4个小时多一点就够了——只不过,这是我们估测的理论速度,具体速度嘛,后文我们再介绍吧。

雷杰文斯基的Bomba,可以同时模拟6台ENIGMA;而图灵的Bombe,则可以同时模拟36台ENIGMA。

更重要的地方在于,图灵Bombe的模拟层次不一样——以现代计算机的CPU工作原理打个不一定很恰当的比方,那就是图灵Bombe的“流水线”要更深一些;也因此,它能处理的字母循环圈长度,比Bomba要长。

能处理的字母循环圈越长,就越有利于选择更多更长的“可疑明文”。上文说到的wetter,长度是6;而诸如德军电文中常见的成套词组,如

oberkommandoderwehrmacht (国防军高级司令部)

wettervorhersage biskaya (天气预报 法国比斯开湾)

wettervorhersage deutsche bucht (天气预报 德国海港)

obersturmbannfuehrer (高级冲锋队指挥,上校)

obergruppenfuehrer (武装党卫军地区总队长,中/上将)

keine besondern ereignisse (无特殊情况)

[注:以上几处,特别是纳粹泛军事组织的军衔翻译,系从英文译回,如有不准确处,欢迎多多指正]

等,现在也都可以依样画葫芦地来构造字母循环圈了。

不仅如此;即便“猜测式明文攻击”无效,图灵的Bombe机还可以用其它手段进行密码分析——比如搜索重复码,及搜索重复计数等等,这里就不多讲了。总的来说,Bombe不仅仅是ENIGMA的杀手,同时还蕴涵了图灵脑海中“万能机器”的一部分设想。

如果说,波兰人雷杰文斯基制造Bomba,其目的就是单纯地为了对付ENIGMA的话,那么英国人图灵设计的Bombe,多少了有点“大小通吃”的味道了——从这个原理出发,Bombe不仅能对付ENIGMA,还能对付当年德国的另一种高级别场合使用的转轮密码机LORENZ(一种通过有线线路进行文电加密及传输的机器)。从这个意义上说,Bombe的起点,的确要比波兰人的Bomba要高上一大截。

以不变应万变”,一旦抓住敌人最致命的缺陷,就予以最凶猛的攻击而绝不罢手——对于不断升级的ENIGMA,图灵的招数才真正是砸中了要害!

对此,《图灵传》的作者安德鲁·霍奇斯(Andrew Hodges)做出了公允的评价:

图灵,是正式提出用基于可能字(也即文中所说的可疑明文,1001n注,下同)搜索逻辑一致性(比如字母循环圈等)的机械化原理的第一人

如此评价,图灵确实是当之无愧。

对比波兰人因为经费困窘而无力继续发展Bomba的境况,布莱奇利庄园可真是幸运多了;深知密码利与害的丘吉尔对庄园非常关心,因此庄园的财政经费一直还算比较充裕。

为了制造Bombe,庄园设法筹集了10万英镑,在1939年年底委托赫特福德郡(Hertfordshire)的不列颠制表机公司(British Tabulating Machine Company,BTW),制造了英国第一台专门用来破译密码的机器——Bombe。

点看全图

这是ENIGMA的官方标志

点看全图

这个就是Bombe,具体点说就是BTM制造的Bombe的商标

图灵到庄园五个多月以后的1940年3月18日,工厂终于做出了Bombe,体积也令人瞠目:宽2.1米,厚0.6米,高2米——稍微计算一下就知道,这第一台Bombe的体积达到了2.52立方米。

而这么大体积,又是个什么概念呢?

我们在【纯技术篇之终结篇】里提到过,ENIGMA家族中,最元老、最笨重的A型,其体积大概是0.1立方米;一般的家用冰箱,体积大概是1.8 * 0.5 * 0.5 = 0.45立方米——这么一比较就清楚了,第一台Bobme,体积居然是第一台ENIGMA的25倍,或一台家用冰箱的5倍半!

大家也不妨想像一下五台冰箱放一块,会有个什么视觉效果……

为了模拟ENIGMA的转轮,Bombe引入了模拟转轮,于是每3个模拟转轮,正好可以模拟ENIGMA转轮组的一种排列情况;这样的模拟转轮组,每12组又编组为1群(group),全机器上一共有3群,算起来共有3* 12 * 3 = 108 个模拟转轮——而这108个模拟转轮,全部并列装在Bombe的正面,看起来煞是壮观!

可惜,这些机器现在存世不多了;下面几张,是近年来重建的Bombe复原型:

点看全图

模拟转轮明显分成3群,这样的108个模拟转轮,可以同时模拟ENIGMA转轮组的36种排列

点看全图

再来一张,注意左侧面的那个附加装置,那是用来模拟连接板情况的

而之所以中间一“群”会多出一组3个模拟转轮,1001n个人认为可能是用来显示正确密钥的

点看全图

这张是没有安装模拟转轮的槽位裸照

点看全图

模拟转轮特写——注意上面也有字母位置的设置,其实就是ENIGMA转轮的变形

点看全图

威风凛凛的正面背后,Bombe才表现出了它令人瞠目的复杂性

点看全图

换一个角度来欣赏Bombe的后背吧

点看全图

看看这接线关系,头都难免有点大

点看全图

这就是当年实现数学计算的代价,但真的很美,不是么?

ENIGMA - A也好,这刚造出来的Bombe也好,基本都是原型机,可是体积和复杂程度就能差这么远——虽然这个比较并不严格,但是多少也从中看出:比起密码编码,密码分析要付出的代价又会有多大。

对这台重达1吨的机器,英国人当然充满了期盼,并给它起了个极好的名字:胜利(Victory)——是啊,面对猖狂无比的纳粹,英国人实在太需要密码分析的胜利了。

可是这台原型机的速度并不快,原因是因为算法上还是有不足。如果我们做个不严格的对比就会发现:波兰人的Bomba,只需要110分钟,即不足2小时的时间内,便可以把5选3的ENIGMA的全部可能设置“跑”上一遍;而英国人的Bombe,速度上的差距确实还比较远——其实,为了找到第一个密钥,在边维修边计算的状态下,英国人花了将近一周的时间才搞定——尽管,它的功能比Bomba还是强大了很多的。

这时候,有人提出了改进意见;他就是后来六号棚屋的负责人,数学家戈登·威尔士曼(Gordon Welchman)

就在1939年9月4日图灵正式进入庄园的那一天,33岁的威尔士曼对ENIGMA的研究也取得了进展;具体说来,也是类似的机械化破译的路子。而相当难得的是,他当时并没有被允许加入对破译ENIGMAA机器的研究,对于图灵的思路,他完全不知情。

在图灵Bombe遇到瓶颈的时候,经过仔细的研究,威尔士曼勇敢地提出了他的见解:他认为,图灵的思路非常好,但由于算法的问题,大大浪费了机器的本身潜力。具体来说,图灵Bombe在运行中,可能会因为内部冲突而导致意外停机;而这样的错误,是由于算法不够优化而导致的。

威尔士曼提出了一个“对角线板”的简单的电工学方法,使那些可能被错误连接的机会得到了消除,同时又不会遗漏可能的正确结果。不仅如此,这个办法更适合比较短的“可疑明文”攻击——显然,过长的“可疑明文”毕竟不太好找。

点看全图

经威尔士曼改良过的图灵Bombe示意图,右上方即是“对角线板”

图灵毕竟是人,不是神;面对这个极为巧妙的办法,一时难以理解之余,他也曾表示过怀疑——但是事实说明了一切,威尔士曼的办法的确大大提高了Bombe的工作效能。在“胜利”诞生五个月后的1940年8月8日,根据威尔士曼意见改进而成的新型Bombe终于问世了;它的名字是“阿格尼斯(Agnes)”,至于为什么这么叫,现在已经不清楚了。有人怀疑,这似乎是在暗指美国的一位密码分析学家Agnes Meyer Driscoll,至于是不是,也只有问上天了。

浴火重生的阿格尼斯,终于带着一身杀气来到了庄园——实践证明,针对当时5选3的ENIGMA,阿格尼斯只要15分钟就能解决问题!

这个速度,比“胜利”要快不知多少倍——更重要的是,由此破译的ENIGMA电文,可以达到“准实时”的效果,其重要意义不言而喻。

在【纯技术篇】我们曾经提到过,ENIGMA系列不断升级,起初的5个转轮选3个的全排列为60种;后来的7个转轮选3个的全排列为210种;尔后8个转轮选3个的全排列为336种。

值得提一句的是:这最后一种情况,实际上指的就是1942年才问世的M4型ENIGMA:虽然它有4个转轮,但是第四转轮和转轮组中的其它三个转轮并不能互相替换,因此,参加转轮组全排列的,仍然是3个转轮;但是在破译时,Bombe仍然需要构建全部4个转轮的破解单元,由此衍生出了系列中的后续型号。

即便在后来ENIGMA不断升级的情况下,Bombe破译当日密钥最长也只要六个小时,实际运行中往往只用一半时间——也就是三个小时——便能解决问题。考虑到德军每日变更密钥的时间都在午夜,如此一来,英国人拿到破译的密文,其时间一般不会超过中午。

敌人当天发报,我们当天破译”,即便是对一份两份电报来说,已经就很了不起了;而庄园,是在成捆成捆地破译——在密码分析的历史上,这绝对是一个里程碑式的事件,它所揭示的,正是科学技术的无比威力!

点看全图

这是当年工作人员在操作Bombe某后续型号时的场景

阿格尼斯的出世,并不意味着Bombe改进的终点;随它之后,更多的Bombe后续型号,如“Jumbo”、“Funf/Twinn”、“Giant”、“Ogre”、“Click/Clique”、“Ming”、“Cobra”……等等,陆续投入了实战:

1941年3月底,“大家伙(Jumbo)”问世,此时英国人已经有了8台Bombe;

1941年年底,数字增长为16台;

1942年年底,数字增长为49台;

1943年3月底,数字增长为60台;

1943年年底,数字增长为99台;

到1945年3月,也就是纳粹德国只剩两个月阳寿的时候,英国人已经有了211台Bombe;而为了操作这些大家伙,庄园陆陆续续差不多投入了两千工作人员!

这破译密码,可也真是个昂贵的任务啊。

关键词(Tags): #密码#破译#ENIGMA#布莱奇利#图灵元宝推荐:不爱吱声,海天,

本帖一共被 1 帖 引用 (帖内工具实现)
家园 再坐沙发,先花后看
家园 英国人真是下了血本, 一台得多少钱?
家园 吼吼,闯进前三。
家园 夜兄有没有看过《暗算》?

里边破译密码的部分讲的云山雾罩,俺这个外行也看不出说的对不对。另外,用算盘组成的计算中心破译密码会有效么?

家园 【建议】answer.com劲过“德语高手”

obersturmbannfuehrer: http://www.answers.com/topic/obersturmbannf-hrer?method=8

obergruppenfuehrer: http://www.answers.com/obergruppenfuhrer%20

u上加两点的国际拼法为ue.ae,oe也适用于ä,ö。

另外,okerkommandoderwehrmacht应为oberkommando der wehrmacht.ober意为高级。der为冠词不能组成符合词。

家园 【击节送花】这个大家伙肚子里面

大概都是继电器

也就是开关,集成电路一小片就能把这个大家伙给装进去了。

家园 正在看暗算

小说很久以前就看过.

看来麦家同学还是典型的文科生逻辑,对密码问题基本上还停留在字母图表替换的时代.估计他要是看了1001n老兄的雄文,就会编的更象样一点.

家园 文中提过,为第一台的研制,大约需要十万英镑

后文还要提到,不过就没第一台那么贵了

家园 说来惭愧,还真是没看

已经下载了一个多月,硬是抽不出时间来看一下。原著我倒看过,其实我也想知道再把它改编成电视剧,会有多好看,呵呵。。

没时间啊,也是郁闷

“以算盘中心对抗密码”这个说法倒是头一次听说,不过老兄一提,我倒想起了电影《横空出世》——里面有个场景,就是我国核科技人员计算原子弹参数时,搞的那个的算盘会战。不知道是不是受过启发?呵呵。。

家园 谢谢表扬,呵呵

只不过他写的不是技术性的东西,而是为了表现人性。。小说和真事,还是不要互相比较了吧。此外,电视剧里如果真要搞的字母成串,又循环又步进,时不时的还来个什么伟大的方程组——老实说,即便本系列,都把方程组给略掉了——估计投资方跳井的心都有。。。

前提是:如果还真能有什么投资方的话

家园 非常感谢老兄的帮助和指正

本人实在是一点都不懂德语,为了翻译那些可爱的词组,真是快要了我的命——不怕老兄笑话,本人为此先后查了《德汉军语辞典》,又下载了英德电子词典,最后还是抱着一本《现代德汉词典》,几个字母几个字母一组,硬猜出来的。。

看来老兄娴熟于德语,以后再有类似问题,定当请教,也请老兄不要客气,多多指点:)

关于变元音的问题,我也是发愁。以前这个问题出现过两次,大家也提出,应该以通行规则ue、ae和oe来替代。后来接触的一些词汇中,这些字母又出现了大写,对德语一窍不通的我就彻底晕了,不知道是不是还如此类推。这次原稿中本是大写,发上来之前才临时改了小写,又忘掉了修正,实在是汗颜

ober/oker,这个是我自己输入时的手误,由于毫无语感,检查来检查去,还真没看出一点毛病,晕~~老兄细心看出来了,非常感谢指正!我这就修正它去~~只不过它们的确切中文翻译,我还得仔细查一查,先空一会儿吧:)

关于oberkommandoderwehrmacht,电文之间是没有空格的,因此连写,资料里也是这样连下来的:)

关于answer.com的问题,老兄算是帮了我大忙;给我条鱼,不如给我个鱼竿儿——这个思路很重要,对我以后的写作很有帮助:以前我查找德语单词,总是想从中文站点中找到答案,而忽视了英文站点——谢谢老兄提醒!

老兄既指正了错误,又提供了思路,只好两朵花致谢!现在一朵,六个小时之后再来一朵

家园 一下就想到前辈的游戏硬件工程了,拐弯在此致敬!
家园 夜兄实在是太客气了

看你的文章让小弟获益良多。以后有用得着小弟的地方知会一声便可。

关于大写的问题,如果是整个词都是大写字母组成就在后面跟大写E,如果只是第一个字母大写则跟e。

关于answer.com上有德语名词的解说是因为二战前很多英语的科技,军事名词都是直接从德国抄来的。但随着战后那批牛人不是投奔自由世界就是被苏联虏走,我们就在也看不到新的德语外来词了。取而代之的是英文在德语中是无忌惮的渗透。

家园 老兄的速度快了很多啊

看都看不及了。

It never rains but it pours.

全看树展主题 · 分页首页 上页
/ 3
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河