三体社区泛科幻大本营

注册

只看楼主

为一种爱情,他解开了一亿亿种可能的德军密码

美睿 发表于 2015-7-22 19:16:13 [ 上一主题] [下一主题]

《模仿游戏》迟了将近一年与内地观众见面,但至少庆幸它还是上了。
在进入电影院之前,社区娘看到一个观众看这部电影的兴趣值调查,大致排序就是:
卷福>回报张电影票>奥斯卡>听说是好电影>图灵>搅基>破译英格玛
好了,我们今天就说说排在末尾似乎最Get不到影院G点的“破译英格玛”。
……还外带点搅基。
记得当年看《志明与春娇》,有个这个密码:
1.jpg
倒过来就是I MISS U~挺感动挺惊讶,眼泪哗啦哗啦
但是我们的天才数学家图灵正太时就已经这么玩了:
2.jpg
顺便一提,传说笛卡尔告白公主时,写出公式:r=a(1-sinθ),画出来是这样:
3.jpg
图灵的解密人生也来源于爱情,现在还觉得破译密码很无聊吗?
好了,来看看英格玛的故事吧。

英格玛的华丽史

英格玛密码(Enigma),人类历史上最富有传奇色彩的密码编制方法。它名字很好听,意思也很有厚度:有“谜”、“不可思议”等多种含义。
在它之前,有很多种密码。最为有名的就是一直被认为坚不可破的维吉乃尔(Vigenere)密码及变种,后来还是被解破。但直到1918年,德国发明家亚瑟·谢尔比乌斯和他的朋友理查德·里特创办了著名的谢尔比乌斯和里特公司,扬言要用二十世纪的电气技术来取代过时的铅笔加纸的加密方法。
后来他们做到了,发明了加密精装电子机械——Enigma。
4.jpg
Enigma基本部分示意图是这样,从左到右分别为键盘、转子、显示器
5.jpg
这只是Enigma内部简化图,上图我们看见一共有26个键,键盘排列接近现在使用的计算机键盘。在下面的示意图中暂时只画6个键。图片右方方就是显示器,它由标示了同样字母的26个小灯组成,当键盘上的某个键被按下时,和此字母被加密后的密文相对应的小灯就在显示器上亮起来。

中间是“转子”,什么叫转子呢?就是它会转动!谢尔比乌斯关于Enigma的最重要的设计——当键盘上一个键被按下时,相应的密文在显示器上显示,然后转子的方向就自动地转动一个字母的位置(在示意图中就是转动1/6圈,而在实际中转动1/26圈)。下面的示意图表示了连续键入3b的情况:
6.jpg
当第一次键入b时,信号通过转子中的连线,灯A亮起来,放开键后,转子转动一格,各字母所对应的密码就改变了;第二次键入b时,它所对应的字母就变成了C;同样地,第三次键入b时,灯E闪亮。
7.jpg
实物图,左方是一个完整的转子,右方是转子的分解,我们可以看到安装在转子中的电线



觉得不够复杂?没事,后来谢尔比乌斯在机器上又加了一个转子。当第一个转子转动整整一圈以后,它上面有一个齿拨动第二个转子,使得它的方向转动一个字母的位置。看下面的示意图(为了简单起见,现在我们将它表示为平面形式):
8.jpg
咳咳,想象一下要用Enigma发送一条消息。发信人首先要调节三个转子的方向,使它们处于17576个方向中的一个(事实上转子的初始方向就是密匙,这是收发双方必须预先约定好的),然后依次键入明文,并把闪亮的字母依次记下来,然后就可以把加密后的消息用比如电报的方式发送出去。当收信方收到电文后,使用一台相同的Enigma,按照原来的约定,把转子的方向调整到和发信方相同的初始方向上,然后依次键入收到的密文,并把闪亮的字母依次记下来,就得到了明文。于是加密和解密的过程就是完全一样的——这都是反射器起的作用。
9.jpg
还有下一步,在键盘和第一转子之间增加了一个连接板。这块连接板允许使用者用一根连线把某个字母和另一个字母连接起来,这样这个字母的信号在进入转子之前就会转变为另一个字母的信号。这种连线最多可以有六根(后期的ENIGMA具有更多的连线),这样就可以使6对字母的信号互换,其他没有插上连线的字母保持不变。
10.jpg
于是转子自身的初始方向,转子之间的相互位置,以及连接板连线的状况就组成了所有可能的密匙,让我们来算一算一共到底有多少种。
三个转子不同的方向组成了26*26*26=17576种不同可能性;
三个转子间不同的相对位置为6种可能性;
连接板上两两交换6对字母的可能性数目非常巨大,有 100391791500种;
于是一共有17576*6*100391791500,大约为10000 0000 0000 0000(一亿亿)种可能性。

电影中图灵云淡风轻地说,哦,那就是解出这个本身应该用两千多万年,而我们要在几年内算出来嘛……
这才是一个天才该说的话。


英格玛的破处史

实际上,在特立独行的图灵先生很拉风地来到布拉德利庄园前,破译Enigma的工作就已经开始了而且取得很大进展。主要几位贡献者是被称为“波兰三杰”的马里安·雷耶夫斯基,杰尔兹·罗佐基和亨里克·佐加尔斯基。
11.jpg
12.jpg
13.jpg
还记得电影里说明了德国人使用Enigma进行编码的具体规定。每个月每台Enigma机的操作员都会收到一本当月的新密钥,上面有此月每天使用的密钥。也就是说,过了当天,几位手握战争终止器的专家,又得重新来过,这种煎熬可想而知。
就是在这样的情况下,“波兰三杰”还是在六年内就破了德军近十万密码。
逐渐雷耶夫斯基判断出转子的初始位置,找出字幕的对应表。



第一个字母:ABCDEFGHIJKLMNOPQRSTUVWXYZ
第四个字母:___P_____M_RX____________

第一个字母:ABCDEFGHIJKLMNOPQRSTUVWXYZ
第四个字母:FQHPLWOGBMVRXUYCZITNJEASDK
当然,光凭这个没办法知道当天的通用密钥。逐渐雷耶夫斯基在字母的循环圈中发现某些循环圈中的字母变了,但是循环圈的数目仍旧是四个,每个循环圈的长度也没有改变。应用置换变换的理论,雷杰夫斯基可以从数学上严格证明这一点对于任何的连线变化都是成立的。 
后来根据循环圈的个数和长度可以看作是这个密钥的“指纹”——通过建立密钥“指纹”档案大大简化了破译工作。但光建立这样一个档案花了整整一年时间,工作相当艰苦,有时工作人员的手指都被磨出血来。


其他科学家中,佐加尔斯基还设计了用在纸上钻孔的方法来迅速查询对应于某类字母循环圈的转子状态的方法。
14.jpg
15.jpg
电影里也致敬了,不过有点密恐

后来雷杰夫斯基和罗佐基有了一个更好的主意。他们在Enigma的基础上设计了一台能自动验证所有26*26*26=17576个转子方向的机器,取名为“炸弹”
“炸弹”,这就是图灵制造解密机器的灵感来源。
不过紧接着德国加强了ENIGMA的加密能力,“炸弹”难以再顺畅工作下去。
192991日,希特勒发动“闪电战”入侵波兰。917日,苏联入侵波兰。928日,德军占领华沙,波兰不复存在。
16.jpg

“闪电战”的提出者,德国装甲部队之父,纳粹德国的海因茨·古德里安
(Heinz Guderian)将军在指挥车上。在照片的左下方我们可以看见一台ENIGMA

下面有请图灵先生正式出场。
17.jpg
不对
18.jpg
应该是他。

图灵先生非常拉风地走进布莱切利公园。这是个什么地方呢?
这里是英国的政府代码及加密学校,说白了就是密码破译中心。一座歌特都铎式的城堡。
19.jpg
1939年,这座城堡成为密码分析人员的工作场所,6号木屋是负责破译德军ENIGMA电报的,从那里出来的明文由3号木屋翻译并进行综合情报分析,8号木屋专门负责对付德国海军的ENIGMA,一开始在布莱切利公园工作的只有大约二百人,可是到了五年后战争结束时,城堡和小木屋中已经多达七千人!
图灵就是直奔破译ENIGMA来的,当时大家还是延续“炸弹”及雷耶夫斯基的方法。而图灵发现许多电报有相当固定的格式,他可以根据电文发出的时间、发信人、收信人这些无关于电文内容的信息来推断出一部分电文的内容。
比方说,德国人每天的天气预报总在早上六点左右发出,要是在六点零五分截获了一份德国电报,它里面八成有Wetter这个词,也就是德文中的“天气”。根据在此之前德国人天气预报电文的死板格式,图灵甚至能相当准确地知道这个词具体在密文的哪个位置。图灵把这些词称为“候选单词”。
20.jpg
图灵并不清楚在密文中出现这个候选单词时的转子状态,但是假设他猜对了这个候选单词,把这个候选单词起始时转子的方向记为S,那么在此时ENIGMAw加密成了E;然后转子转到下一个方向,就是S+1ENIGMAe加密成T;在方向S+2上一个不属于这个循环的字母被加密了,这个我们暂且不去管它;接下来在方向S+3ENIGMAt加密为W
经过大量当时人们(也包含现在)完全转不过来的解密方式,图灵把候选单词,字母循环圈和用线路连接起来的多台ENIGMA机构成了密码分析的强大武器。
只有图灵,艾伦·图灵,这个数学虚拟机器的发明人,才能有这样的想像力。图灵对ENIGMA的破译方法完全是纯数学和理论性的,他为此写了一篇著名的论文,目的就是让工程师来来造电影里那台叫“克里斯托弗”的机器。
21.jpg
很不幸,真实中,它还叫“炸弹”……不是“克里斯托弗”
22.jpg
如上所说,英格玛这套系统最有价值也是最蛋疼的地方在于,它的算法可以抵消频率攻击,也就是说在有机器的情况下,也要手工破解这万亿亿种组合。在布莱切利公园有一大群为破译Enigma作出了卓越贡献的人们。但是如果只能选择性地讲述一个人的功绩,那么这个人无论如何还是阿兰·图灵。

你好,图灵,再见,图灵





“有时候,正是那些人们认为的无用之人,成就了无人所成之事”
“好友”克里斯托弗的话见证图灵走完一生,有时思维缜密的伟大科学家世界里,往往单纯和透彻地令人心疼。
这事情是真的,电影改编也晃不过这整个令人扼腕的真实。在如今对他隆重的追忆,与2013年英国对他简短的“pardon”里,暂且就相信,图灵先生为世界所贡献的,仅仅是为了心中最美好的爱情吧。
clipboard.png
(资料来源于林正山老师)



22222.jpg

回复 点赞(4)

美睿 发表于 2015-7-22 19:17:01

1

沙发

点评 引用回复 点赞(1)

提示:close

 

已赞!

 

提示:close

 

已关注!

 

您需要登录后才可以回帖 登录 | 立即注册

关注我们新浪微博微信 3

  

沪ICP备14049458号    网站地图

Powered by Discuz! X3.2@2001-2013, Comsenz Inc 版权信息

更多友情链接

钛度社区 3G小说网 磨铁中文网 创世中文网 网易原创 起点中文网 潇湘书院 红袖添香 小说阅读网
科幻世界 书海小说网 纵横中文网 科幻星云网

快速回复 返回顶部 返回列表
close