密码界传奇史诗:二战著名恩尼格玛密码系统破译记

  • A+
发布日期:2017年03月02日 所属分类:史话
密码界传奇史诗:二战著名恩尼格玛密码系统破译记

电影《模仿游戏》(The Imitation Game)讲述的是关于著名密码系统恩尼格玛(Enigma)的故事。

电影《模仿游戏》(The Imitation Game)讲述的是关于著名密码系统恩尼格玛(Enigma)的故事。二战时纳粹德国正是利用了这套密码系统,隐秘而高效地传递着军事情报。恩尼格玛的最终破译成功地扭转了战局。人们普遍认为,它的破译使盟军在西欧的胜利提早了两年。

阿兰·麦席森·图灵 (Alan Mathison Turing ,1912年6月23日-1954年6月7日),英国著名的数学家和逻辑学家,被称为计算机科学之父、人工智能之父,是计算机逻辑的奠基者,提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。图灵同时还是著名的男同性恋者之一,但不幸因为其性倾向而遭到当时的英国政府迫害,最终自杀。2013年12月24日,英国女王伊丽莎白二世宣布赦免图灵。

密码界传奇史诗:二战著名恩尼格玛密码系统破译记

阿兰·麦席森·图灵 (Alan Mathison Turing ,1912年6月23日-1954年6月7日),英国著名的数学家和逻辑学家,被称为计算机科学之父、人工智能之父,是计算机逻辑的奠基者,提出了“图灵机”和“图灵测试”等重要概念。

巴顿说过:战争是靠武器来打的,但获胜却得靠人。图灵证明这句话有一半是对的,他和一台机器帮助同盟国取得了二战的胜利。

在轰轰烈烈的一次大战中,德国一次最惨重的外交失败,就是美国的参战。而美国参战的直接原因,则是“齐默尔曼电报”被英国“40号房间”破译,从而导致德国谋求和墨西哥结盟牵制美国不参与欧洲战争的阴谋被曝光。

1923年,英国出版的一些历史资料,使得德国意识到一战期间他们的密码通讯被协约国破译导致战争的失败,因为谋求一种安全可靠并且方便迅捷的密码通讯手段。而当时随着加密技术的机械化,一系列密码机开始问世。德国从其中选中了1918年,由德国发明家谢比尔斯发明的密码机“恩尼格玛”(谜)。德国总共购买了约20000台“恩尼格玛”密码机,在海陆军中广泛使用。

密码界传奇史诗:二战著名恩尼格玛密码系统破译记

恩尼格玛实现了加密者的梦想,德国对于恩尼格玛系统表现出绝对的信任。

作为一种密码机,恩尼格玛的原理比较简单,其主要由键盘,扰频器,显示屏三部分组成,键盘输入字母,扰频器为字母加密,显示屏显示字母(当时的显示屏是由一系列用灯照亮的字母组成)。其关键的扰频器,也有三个主要部分,插线板-转轮-发射器。通过插线板可以讲字母对换,然后经过三个联接在一起的转轮,每输入一次,转轮往前进一步,则下一个文字转轮状态就已经变化了,最后是反射器,将输入文字变换为另一个文字返回。最初的恩尼格玛机通过在插线板中交换6对字母,再加上三个转轮,总共可以生成的密匙总量是10的16次方个。也就是说如果每一秒钟尝试一个密匙,大约需要3亿年时间才能全部尝试完。恩尼格玛实现了加密者的梦想。简单,其原理可以是透明的,依靠其设置(密匙)保证整个密码系统的安全。正是由于这点,德国对于恩尼格玛系统表现出绝对的信任。

一战中,协约国的情报机构破译德国大量密码,从而取得巨大优势,但是战后随着“凡尔赛体系”的形成,导致西方列强对和平充满信心,英国的“40号房间”显著衰败,美国流行孤立主义,甚至关闭了密码破译机构“黑屋”。德国新的恩尼格玛机的问题,使得各国破译者对此都望而却步(作为一种密码机,恩尼格玛的商用版也向企业出售。因此西方列强对其原理有初步认识)。这是一种用传统手段(词频分析,猜字双向破译等)绝对无法攻克的加密系统。西方国家对此丧失了信心。

密码界传奇史诗:二战著名恩尼格玛密码系统破译记

恩尼格玛系统总共可以生成的密匙总量是10的16次方个。也就是说如果每一秒钟尝试一个密匙,大约需要3亿年时间才能全部尝试完。

恩尼格玛破译的难度,以及德国对其信任,使得整个二战期间,同盟国对恩尼格玛的破译过程,成为密码学界一篇难忘的史诗。

史诗的第一章,是个卑微的叛徒。汉斯·施密特是个在德国密码机构供职的官员,他的哥哥鲁道夫是这个机构的长官,因此他有着良好的条件能接触机密,却暗中对德国不满。1931年,汉斯·施密特在比利时被法国情报机构招募,提供了“恩尼格玛”系统中的设置规则和原理图。虽然如此,法国情报人员意识到,由于恩尼格玛机加密的关键在于密匙(转轮和插线板的设置方式),即便了解其结构和规则,破译用恩尼格玛加密的密电,依然毫无可能。因此他们将汉斯·施密特的情报转卖给了波兰情报机构(这在情报界是很常见的事情)。

波兰当时局势非常危险,一边由于一战的结果,波兰吞并了大批原先属于德国的领土,德国民族主义者一直信誓旦旦的要报复;另一边,由于俄国革命后波兰的干预和随之而来的俄波战争,苏俄兵败华沙。苏联对于波兰也虎视眈眈。波兰处于重重危机中,绝对不能放弃一个在情报领域取得优势的机会。

波兰人从施密特提供的情报中得知,德国人使用的密匙每天都在更换。在传输当天设置内容时,为了保证信息内容才传输过程中不会出现错误,按规定德国密码员必须把带有设置信息的密文重复一次,也就是说每天开始工作的第一个密文中的第一部分,其原始的明文是重复的(密文当然不可能重复,因为有转轮存在)。波兰密码研究人员雷臼斯基针对这点,经过研究,逐步发现了一些特点。假如密匙是三个字母组成,而明文是一致的,如果设第一个字母加密时设施是S,第二次加密同一个字母,设置是S+3(转轮转了3次)。也就是说,S和S+3是同一个字母加密的结果。

由于每天所有密码员都要按照自己约定的密匙进行加密,所以波兰情报机构能截获足够的密电,找到大量(S,S+3)这样关联。这里请注意,为了互相能通信,同一个系统机初始设置是一样的,这是个非常重要的前提。雷臼斯基通过大量(S,S+3)对研究,意识到不管其字母如何,每天的这样对构成的字母链(譬如,a-u,u-c,c-t,t-a),和当天的设置相关,而且由于插线板的存在,字母是可以对换的,所以当天的设置只和字母链的长短有关。这个字母链长短之和转轮设置有关,和插线板无关!这样就不需要测试全部10的16次方密匙,转轮的设置一共只有10万种!

雷臼斯基和他的团队,根据施密特的资料复制了一台“恩尼格玛”。然后对于十万种转轮设置和字母链的关系一一作了对比。从此只要搜集足够的(s,s+3)字母对,雷臼斯基就能搞清楚当天密码机的转轮设置。而插线板虽然可能产生的密匙更多,但是本质上是一种很传统的加密技术“代换”,用经典的词频分析等手段就能对付。

以此,雷臼斯基利用德国在恩尼格玛机系统上一个疏忽,攻破了这个貌似坚不可摧的密码堡垒。

英国长期重视密码破译工作。随着战争的来临,“40号房间”活动逐渐活跃起来,他们在布莱切里庄园建立了密码破译中心,极盛时哪里有超过7000人。波兰人虽然由于德国提高加密能力而失败,但是他们先前的成果使得英国人放弃了“恩尼格玛无法破译”的观念。1939年,英国人掌握了波兰人的技术,开始继续破译恩尼格玛。虽然转轮密匙增加了十倍,但是还在英国人所能动用资源的处理范围内。但是英国人非常担心,总有一天,德国人会意识到,将部分电文重复加密,是个极其严重的漏洞。1940年5月1日,德国停止了重复发送的信息,补上这个漏洞,雷臼斯基法这下完全失灵了。

英国人还有办法,他们有图灵。图灵是个伟大的数学家(虽然“伟大”一词经常被滥用,但用来形容图灵,是当之无愧的)。他所构思的“万能图灵机”是计算机界和人工智能界的基石之一。而他本人也是个悲剧人物,因为他是同性恋,战后遭到当时不宽容的英国社会的迫害而自杀身亡。他的朋友这么评价此事:幸好战争期间我们不知道此事(指他是同性恋),不然我们可能输了这场战争。

图灵的工作继承了先前密码破译学的成就,并且发挥自己超人般的才智。布莱切里庄园的工作者发现恩尼格玛系统的部分弱点,譬如某密码员喜欢使用相邻的字母作为密匙,另一个操作员不喜欢让转轮两天里处于同一个位置等等。而图灵的破译,基于德国人刻板的个性,譬如每天固定时间发送格式化的电文,甚至其中每个词的位置都不变。这样密码破议员很容易猜出其中部分电文的明文内容(譬如每天定时发送的天气信息)。图灵就从这里着手破译。

图灵利用猜出部分明文的电文,参照了雷臼斯基的想法建立自己特殊的字母链,譬如S1,明文w被加密为e,S+1,明文e被加密成T,s+3,明文t被加密成w,这样就构成了一个特殊环链,图灵称其为crib(克里巴)。以此,他设想有三台恩格尼码机,分别完成这三个加密过程,而第二台的设置正好比第一台进一步,第三台进三步。

因为三台机器的初始设置是一样的,也就是说插线板是一样的,只有转轮有“步”的区别,如果把第一台的输出输入到第二台,第二台的输出再输入第三台,第三台的输出再输入第一台,这样只有一种可能——正确的设置,才能让这个线路能导通。这下图灵又一次把插线板的因素排除在外,而单独对付转轮设置,并且比雷臼斯基进一步的是,他不需要德国密码员重复输入的信息。

1940年3月,按照图灵的设想制造的第一台“炸弹”进入布莱切里,但是效率非常低,5月德国改变了密码规则,不再重复输入密匙。在破译停顿了几个月后,8月份,一台被命名为“上帝的羔羊”的炸弹机进入布莱切里,英国人很及时的又开始能够破译“恩尼格玛”密码!从而将情报优势一直保持到战争结束。

战后,由于第三世界国家依然在使用“恩尼格玛”加密自己的电文。为了保持在密码破译上的优势,英国选择对二战破译恩格尼码采用保密措施。布莱切里庄园被关闭,当时参与项目的人员进行保密宣誓后复员。甚至1954年图灵因同性恋被披露而自杀时,没有人知道他的功勋。直到上世纪70年代,由于恩尼格玛已经很少有政府使用,也由于当时负责情报机构的英国官员的呼吁,英国“有关部门”终于许可官员撰写关于布莱切里庄园的回忆录,算是解除了当年参与的宣誓。从此,恩尼格玛的破译,这个密码学界的史诗,才逐渐为世人所知。

一个叛徒,一个不谨慎的失误,一些算不上是“过失”的习惯,一些墨守的教条,导致一个事关国家命运的密码系统被攻陷,德国继一战密码战失败后,又在二战尝试了完败的滋味。这个教训告诉我们: 绝对不要相信任何一个系统的“完善”,系统,总是会“耗散”的。

weinxin
致知微信公众号
扫描(或长按识别)左侧二维码,订阅致知公众号。点击下方多彩标签,继续浏览你感兴趣的专题。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: