究竟图灵是怎样破解德军的密码系统 Enigma ? http://goo.gl/6o7ylZ 20 十二月 作者 果汁机大叔 http://www.ilord.com/images/enigma/enigma-installed-rotors-100.jpg 相信今天不少人也会留意到关於英国着名数学家、密码学家、电脑科学之父 阿兰图灵 的故事， 原因当然是平安夜当日英国女王伊莉莎白二世赦免了 阿兰图灵 於上世纪因同性恋行为而被定的罪。 今天不少媒体也有报导这件事，亦有介绍 图灵 生前的主要事迹。 当中 图灵 在二战时破解了德军的 Enigma Code，但其实 Enigma 是甚麽，怎样运作， 又是怎样被破解的？ 有兴趣的网友们其实可以看看 Numberphile 关於 Enigma 的特辑， 两部短片分别介绍了 Enigma 的运作方式 (包括商用及纳粹德军所用的版本)， 以及 图灵 是如何利用 Enigma 的漏洞破解了这套令德军引以为傲的密码系统。 158,962,555,217,826,360,000 (Enigma Machine) - Numberphile http://youtu.be/G2_Q9FoD-oQ 早於二战发生之前，Enigma 已在 1920 年代被用於商业之中， 目的是加密商业公司内部的机密文件。 Enigma 的最大特色在於加密时不会像传统密码同一明文翻译成同一密文， 例如 MM 翻译时必定为 AA/BB 或 CC， 而 Enigma 则可以把源讯息中同一个字母转换成不同的字母， 例如把讯息 MM 转成密文 SX。 同时亦可以把不同的字母转换成同一字母，例如讯息 KL 转成密文 AA。 换言之，Enigma 并非如传统密码中基於密码表简单地把讯息加密， 令到普通的解密手法失效。 而 Enigma 的原理在於它有三个旋转盘，旋转盘由错综复杂的电路组成， 每一旋转盘共有 26 个电路选项。 透过这些电路，在按下明文某一字母(如 A)时令代表密文某一字母(如 E)的电灯亮着， 因此，商用 Enigma 密码机 可以拥有 26 × 25 × 26 = 16,900 (注意不是 26×26×26) 个组合， 而且军用的 Enigma 更是要在共五个旋转盘 (标记为I,II,III,IV,V)中选择(其後增为 8 个) 其中三个(即总旋转盘组合为 5×4×3= 60)。 但是纳粹德军(海军)所使用的 Enigma 还不是如此简单。 因为德军所使用的 Enigma 密码机还设有 Plugboard (接线板) 的装置， 可以把共十对的字母互换，例如把 Q 转换为 E ，E 同时转换为 Q， 令加密组合数量大幅增加，总共为 158,962,555,217,826,360,000 个组合。 德军每月都会有一张以可融化的墨制成的 code sheet， 用来选择当天 Enigma 的旋转盘，设定旋转盘及接线板。 密码表每天都会改变组合，因而德军认为他们的 Enigma 密码系统无可能被破解。 Flaw in the Enigma Code - Numberphile http://youtu.be/V4V2bpZlqx8 可是，Enigma 密码系统并非完美，因为它存在两个漏洞， 第一个就是任何字母经过 Enigma 密码机的转换後， 永远无可能是「自己」(即是当输入明文 A 时，密文必不为 A)。 这个漏洞成为了其中一个破解的关键，因此盟军解密团队和图灵就利用这个漏洞， 先估计德军所发出的讯息的可能词汇，例如每天 6 时德军也会发出的「天气报告」， 德文为「wetterbericht」，再对应盟军接收到的密文， 以上述漏洞估计讯息中哪一段密文最有可能为「wetterbericht」， 如果发现组合有重覆，例如出现估计密文 T 是明文 T 的话则错误，要再次推测。 再而逐一测试德军 Plugboard 及旋转盘的组合。 例如一开始估计旋转盘是 1-1-1，以及 plugboard 上「TA」是连接着一起， 再以此推测其他 Plugboard 的连接方法，但如果後来又遇到「TX」， 当中 T 不可能出现两次，那麽代表之前所有推测都是错误的，包括中间所作的假设， 这就是第二漏洞。 这要再次假设可能「TB」是连接着一起。 直至尝试到「TZ」或成功解到「wetterbericht」为止。 如果没有一个是正确，那麽代表旋转盘的设定错误，要尝试下一个，即 1-1-2。 但是，这样的人手破解方式实在太慢，图灵就基於这样的原理， 制造出专门破解德军 Enigma 密码的密码破解机「炸弹」，不断尝试这些组合， 而「炸弹」解密机可以在 20 分钟内破解出德军每天的组合，从而得知德军的加密讯息。 资料来源：维基百科、Numberphile http://zh.wikipedia.org/wiki/Enigma -- Q 台湾人的需求金字塔 ◢◣ █ 安全、无毒的食物 S ◢██◣ █ 有钱结婚生养小孩 W ◢████◣ █ 买得起的房子 E ◢██████◣ █ 被老板当人看 E ◢████████◣ █ 下班还来得及和亲友吃晚餐 T ▄▄▄▄▄▄▄▄▄▄▄▄ █ 租得起房子█ 找得到工作 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.134.89.190 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/ScienceNote/M.1425328756.A.B47.html