密码那些事儿｜ 十七 年轻数学家首次破解恩尼格玛机(图灵恩尼格玛密码机)
密码那些事儿｜ 十七 年轻数学家首次破解恩尼格玛机(图灵恩尼格玛密码机)
受影视文学作品影响，提到年轻数学家破解恩尼格玛机，人们的脑海中都会浮现出图灵的名字。不可否认，图灵为最终破解恩尼格玛机确实做出了巨大的贡献，但那是他站在了“巨人的肩膀上”。事实上，在图灵之前，首次破解恩尼格玛机要归功于三位年轻的数学家，他们全部来自波兰。
一战后世界处于暂时的停火状态，波兰位于德国和苏联之间，属于在两个大国的夹缝中求生存。东边经常被苏联渗透，西边的德国又谋划着收复失地，所以波兰的警惕性极高，总感觉随时会被两边的强敌攻陷，从没放松过密码学研究。这种威胁下的恐惧感给了他们破解恩尼格玛机的最大动力。
1929年1月，波兰波兹南大学数学系的一群20多岁的大学生和部分研究生被要求宣誓保密，然后开始学习一门密码学课程。他们每周上两个晚上的课，在几星期后就开始破解各种密码，无法完成破解功课的学生则会被淘汰。最终只剩下了三名优秀者，他们分别是雷杰夫斯基、齐加尔斯基和鲁日茨基。
正是这三位年轻的波兰数学家，破译了曾经被认为不可能被破译的初代恩尼格玛机，其中尤以雷杰夫斯基居功至伟——他建立了破解恩尼格玛机的数学方程。
在破解之前，波兰密码局通过情报渠道掌握了德国人使用恩尼格玛机的一些规定：
1.相互间进行通信的恩尼格玛机都有相同的初始设定，其中包括转子的排列和起始位置，初始设定每天变更一次，操作员每个月都会收到一本新的密码簿，上面记录着每天的初始设定；
2.发报员在每发一份电文前，先按密码簿上的当天设定，初始状态为QCW（假设），然后脑子里随意想3个字母，比如说ABC，用设置成QCW状态的机器给ABC加密，比如说加密后ABC变成了BMW。但一次还不够，还要再加密一次，比如第二次ABC又变成了FTN。然后把两次加密的结果并列写一起，形成BMWFTN；
3.收报员收到加密的电文后，先把自己密码机的转子调到当天规定的起始位置，然后输入密文的前6个字母BMWFTN，解密得到ABC，再把3个转子调到ABC的位置，开始解密正式的电文。
通过这些情报，雷杰夫斯基发现： 从数学的角度来看，密码机的作用就是对26个字母进行置换。
随后，他又根据19世纪法国天才数学家伽罗瓦（这位哥们也是密码学史上的重要人物）的“置换群”代数理论——n个元素的所有置换通过合成关系形成为一种代数结构，建立了恩尼格玛机的“置换群”方程。
比如：字母a被加密成x，字母b被加密成y，字母c被加密成z，就形成了三个置换方程：
T(a)=x，T(b)=y，T(c)=z。解出这个方程的解，也就找到了破解恩尼格玛机的关键。
但是这种置换群的结构仍然十分复杂，想求解也是十分困难。雷杰夫斯基又根据恩尼格玛机的特点，发现了两个限定条件：
第一个条件是由于反射器的作用，恩尼格玛机加密与解密的过程完全一致，也即是T(a)=x与T(x)=a是一致的；
第二个条件是操作规程中的前6个字母。比如，某一天密文的前6个加密字符是BMWFTN，那就可以假设加密前的明文为ABCABC，ABC这三个字母就是该电文的密钥，也就是加密电文时3个转子的初始位置参数。
那么把它用置换方程描述出来就是，T1(A)=B，T2(B)=M，T3(C)=W，T4(A)=F，T5(B)=T，T6(N)=N。
根据第一个条件，就可以转化为，T4(T1(A))=F，T5(T2(B))=T，T6(T3(C))=N。
雷杰夫斯基把这三个置换称为这一天密码的“特征集”，想知道T1、T2、T3、T4、T5、T6，只需要把特征集置换的所有对换总结出来就可以了。
具体的工作就是，把当天截获的信息中，所有可以对应的字母都找出来。
假设波兰人截获四封电文，其中每封电文的开头六个字母分别为：
根据上述的操作方式，每封电文的第一个和第四个字母是同一字母加密而来，于是通过上面四封电文，我们可以得到第一个及第四个字母的联系如下：
如果每天可以得到足够多的电文，那么上面的关系表便可以补充完整如下：
仔细观察这个表格，我们不难发现字母关系中会有如下循环：
同样对第二和第五，第三和第六个字母我们也可以写出类似的循环。
而且三位数学家还进一步发现，这种循环，也即由每天的密钥决定的特征集，当中所包含的环的长度和个数只与转子的排列和初始位置有关。
于是他们决定把所有的特征集按其所包含的环的长度和个数分类。为此雷杰夫斯基在恩尼格码的基础上设计了一台能同时验证所有转子位置的机器，取名为炸弹（La Bomba）。经过一年多的连续运行记录，终于收集到了全部数据。这样，波兰人便从每日截获的大量电文中写出字母循环圈，然后根据循环圈的数目和长度从记录表中检索出相对应的转子位子，即是当日的密钥。
至此，第一代恩尼格玛机被全部破解。以后几年，波兰密码局每天都能破译大量的德军情报。
上面对雷杰夫斯基的工作的介绍是极其简单化的，只以举例的形式介绍了其中最重要的思路。雷杰夫斯基对于ENIGMA的分析是在密码分析史上最重要的成就之一，整个工作都是严格地数学化了的（求解关于置换矩阵的方程），决非上面所举例子可以包含。比如说，找到当日密钥中转子状态后，还需要找到连接板状态，才能真正译出密文。
为了表彰雷杰夫斯基、齐加尔斯基和鲁日茨基的功勋，2000年时他们被追授了“波兰复兴大十字勋章”。在2005年雷杰夫斯基诞辰100周年时，他的家乡比得哥市还为他建立了一座铜像，以纪念他在破解恩尼格玛机中的丰功伟绩。
往期文章：
密码那些事儿｜（十六）二战中大放异彩的“超级情报”
密码那些事儿｜（十五）坚持就是胜利——初代恩尼格玛机
密码那些事儿｜（十四）古典密码的巅峰——恩尼格玛机
密码那些事儿｜（十三）尴尬的维吉尼亚3.0
密码那些事儿｜（十二）短命的维吉尼亚2.0
密码那些事儿｜（十一）南北战争时的维吉尼亚密码较量
密码那些事儿｜（十）“钥匙”打开维吉尼亚的锁
密码那些事儿｜（九）维吉尼亚登场
密码那些事儿｜（八）玛丽女王被密码改变的人生
密码那些事儿｜（七）以频率之矛，攻移位之盾
密码那些事儿｜（六）中外古时候的移位加密
本人是官方授权会员推广专员，点击 会员专属通道 成为会员，您将会获得钻奖励及诸多权益！
《钻奖励调整公告》
图灵发明了破译德国格恩密码机，是计算机的雏形。但并不是人工智能，但对人工智能有很多贡献。艾伦·麦席森·图灵（Alan Mathison Turing，1912年6月23日－1954年6月7日），英国数学家、逻辑学家，称为计算机科学之父，人工智能之父。图灵对于人工智能的发展有诸多贡献，提出了一种用于判定机器是否具有智能的试验方法，即图灵试验，至今，每年都有试验的比赛。图灵发明了破译德国格恩密码机，是计算机的雏形。但并不是人工智能，但对人工智能有很多贡献。艾伦·麦席森·图灵（Alan Mathison Turing，1912年6月23日－1954年6月7日），英国数学家、逻辑学家，称为计算机科学之父，人工智能之父。图灵对于人工智能的发展有诸多贡献，提出了一种用于判定机器是否具有智能的试验方法，即图灵试验，至今，每年都有试验的比赛。
情报，左右战争胜负之关键。 无论是冷兵器时代，还是现代战争，一条关键情报所起到的作用能够胜过千军万马。 第二次世界大战堪称是情报战争，可以说，改变战争走向的不是军备，甚至不是策略，而是情报。毕竟很多策略都是在情报的基础上制定的。 于是，反法西斯联军的胜利，除了要感谢做出英明决策的领导人，奋勇拼杀的士兵，还得感谢前线以及幕后的情报人员。其中一个人，是有着计算机之父，人工智能之父的Alan Mathison Turing，艾伦·麦席森·图灵。 电脑科技的鼻祖怎么和战争扯上关系呢？ 电影《模仿游戏》给出了答案。 在深入这部2015年奥斯卡热门影片之前，不妨先透过故事背景，了解真实世界中的艾伦·图灵，以及那段鲜为人知的二战历史。 《模仿游戏》采用的是非线性叙事，一开始就去到了1951年。不过主故事线是从1939年开始。 1939年9月1日，人类回想起了被战争所支配的恐惧。德国军队在那一天对波兰发起闪击战，第二次世界大战，爆发。 这时候的艾伦·图灵已经是个小有名气的数学家，被誉为英国数学领域的奇才，他 *** 到「 ”布莱奇利庄园”参加一个秘密项目，专门研究破译德国的密码通讯系统「 ”Enigma”。 「 ”布莱奇利庄园”里的秘密组织，就是英国 *** 通讯总部前身，相当于美国的国家安全局，与英国军情五处、六处合称为英国情报机构的「 ”三叉戟”。 有资料显示，1939年二战爆发时，布莱奇利庄园里的工作人员已经达到200人；到1943年，其规模超过了6000人。 ”Enigma「 ”，恩尼格玛密码机，则是电影中的终极BOSS，是一种用于加密与解密文件的密码机。 纳粹德国的军事通讯文件，大都用这种恩尼格玛进行加密和解密，尤其是高级机密，就算反法西斯联军截取了情报，面对一串天文数字也无可奈何。超过一亿亿种排列组合的可能性，没打错字，是「 ”10,000,000,000,000,000”，不是一亿，想靠「 ”暴力破解法”来逐一试验可能性，破解的可能性犹如花十辈子来买中一次彩票。 更让情报人员绝望的是，德国人每一天都会用不同的密码设置模式，也就是说，情报人员只有18小时的时间破译，因为第二天又得换一种新的方式重新来过。 总之，”Enigma「 ”犹如德国的一条加强版马奇诺防线，摆在了反法西斯联军的面前，所有人都认为它牢不可破。 电影中，图灵很快就意识到，光靠「 ”人力”，根本不可能完成任务。 于是他开始设想一种「 ”模仿游戏”，用机器去模仿人工运算。其他人在努力做数学题，他却自己一个人搞起了机械工程。 这好比数学课上做物理作业，领导很生气，图灵也受到了很大的阻碍。 「 ”阻碍设置”是《模仿游戏》成功的重点因素，不过本文先学习下历史知识，下一篇在谈电影剧本的优秀之处。 真实的历史中，图灵遇到的麻烦肯定也不比电影的少，只是现实和改编故事似乎有点不一样。 首先是机器，影片中由图灵一手策划打造的「 ”克里斯托弗”机器，俗称「 ”图灵机”，澎湃新闻的一篇报道，百度百科的资料都指出，实际上早在1938年底就有了，而且发明者也不是图灵，而是波兰的数学专家。机器的名字也不叫「 ”克里斯托弗”或「 ”图灵机”，而是La Bomba，「 ”炸弹”。 图灵是很天才，但「 ”用机器对付机器”的想法绝不只有他一个人才能想出来。正如中校所说，图灵并不是唯一擅长做「 ”游戏”的人。 图灵故事的开始之前，还有着一段非常重要的前史。现实中，如果没有这段前史，单凭图灵一个人，根本是不可能在短短几年内打败恩尼格玛。 电影中，这段前史通过中校的一句台词带过。 「 ”是波兰情报局从柏林弄回来的。” 恩尼格玛是德国发明家亚瑟·谢尔比乌斯于1918年成功发明，1926年德国方面就开始投入使用。对于德国这些不知所云的电文，英国等大国的情报部份纷纷宣告放弃破译，他们尝试过很多方法都毫无用处。 但德国的邻国波兰就不敢松懈了，他们没有放弃破译的工作。正当专家们一筹莫展之时，德国的一位知情人士把恩尼格玛机器的情报给了法国间谍，法国专家终于可以复制出一 *** 用的恩尼格玛来研究。 所谓知己知彼百战不殆，可是就算恩尼格玛弄到手，知道它的运行原理，法国人还是没能破解密码，于是他们只好把情报给了波兰人。 波兰人似乎要更聪明一些，他们通过复制出来的原型机找到了恩尼格玛的弱点，并制造了「 ”炸弹”机器用来破译。终于，波兰人真的成功破了一些恩尼格玛密码。 所谓道高一尺魔高一丈，有所察觉的德国人升级了恩尼格玛，波兰人又懵逼了。1939年4月27日，德国撕毁同波兰签订的和平条约，波兰方面赶紧把研究成果交给同盟国，结果，一位作家把一台波兰制造的恩尼格玛回了英国。 大概就是电影中出现的那一台机器。 所以感谢图灵的同时，也必须记得三位波兰数学家的代表人物，马里安·雷耶夫斯基、杰尔兹·罗佐基和亨里克·佐加尔斯基，以及那些不知名的工作人员，他们为破译恩尼格玛做出了重大贡献。 只可惜，波兰人的研究还没来得及完全成功，德国人就在1939年9月发起侵略战争，不到一个月时间，就把波兰给灭了。 既然得到了波兰人的研究成果，英国布莱奇利庄园这边的方向应该很明确才是。所以《模仿游戏》中只有图灵一个在研究机器的情节不一定真实，特别是他说要花10万英镑造机器的点子，知道内情的领导肯定不会反对，因为波兰人就是通过机器破解的密码，别说10万，100万他都不会拒绝。 事实上，图灵只是整个恩尼格玛漫长破译历程的最后一步，如果直接搜索关于恩尼格玛的资料，图灵的名字并不是排在最前面，也不是出现次数最多的。 在休·怀特摩尔创作的戏剧「 ”破译密码”把图灵视为二战中帮助英国破解恩尼格玛机的密码的最大功臣之后，图灵在这方面的贡献才得到了一定的加强。 如果不是一部《模仿游戏》，可能更多的人还不知道这位天才曾经在英国的情报机构上过班，用另一种方式参与过第二次世界大战。 图灵确实在整个破译过程中起到了关键作用，他根据波兰人的研究成功，用自己的理论，升级了「 ”炸弹”破译机器。电影里也不否认他是从老的「 ”波兰编码机”中受到启发。 依照图灵理论制造的新炸弹机投入使用后，英国破解恩尼格玛如鱼得水。两年内，英国就造了大约50台「 ”图灵炸弹机”。 恩尼格玛，至此被彻底打败。 与电影的描述相同，布莱奇利庄园里所有相关破译人员没有立刻得到表彰，反法西斯联军也为了不让德国人发现已经成功破译，不得不「 ”装不知道”，做出了很多牺牲。 几十年后，普罗大众才知道，布莱奇利庄园对恩尼格玛的成功破译，至少使得战争提前两年结束，并至少挽救了1400万人的生命。 《模仿游戏》与历史的情况基本相符，只是为了要突出主角，个别情节做出了修改，并且大大渲染了图灵的功劳。看完电影后，真的好像是图灵凭借一己之力扭转了整个二战的局势。只是理性地思考一下，事实肯定不是这样的。 而对于图灵性格孤傲，与同事相处很不愉快，这是确实存在的。对他性取向问题的描写，不仅迎合事实，还提升了影片的情感深度。 1952年，图灵家中遭遇盗窃，警察因此发现他是同性恋者。那时候，同性恋在英国是违法行为，图灵被控以「 ”明显的猥亵和性颠倒行为”的罪名。也就是《模仿游戏》开头的情节，只不过电影里的时间写的是1951年。 二战的功劳还不能公开，图灵只好默默接受了「 ”化学 *** ”的处罚。他的人生也从此一蹶不振。 17世纪，一个苹果启发了「 ”经典力学之父”牛顿发现万有引力； 20世纪，一个苹果却杀死了「 ”计算机之父”艾伦·图灵。 1954年6月7日，图灵服食了一个带有氰化物的苹果，在家中床上去世，享年41岁。 人们发现暴力带来深深的满足感，但除去这些满足感，暴力行为会变得非常空洞。——《模仿游戏》
英格玛密码机由波兰人马里安·雷耶夫斯基、杰尔兹·罗佐基和亨里克·佐加尔斯基最先破解。
1931年11月8日，法国情报人员与德军通讯部门长官（就是他下令德军使用恩尼格玛密码机的）的弟弟，汉斯-提罗·施密特，在比利时接头。在德国密码处工作的施密特很厌恶德国，于是他就向法国情报人员提供了两份有关恩尼格玛密码机的操作和转子内部线路的资料。但是法国还是无法破译它的密码，因为恩尼格玛密码机的设计要求之一就是要在机器被缴获后仍具有高度的保密性。当时的法军认为，由于凡尔赛条约限制了德军的发展，所以即使无法破译德军的密码，将来如果在战场上相见也不会吃多大亏，于是在得出德军密码“无法破译”的结论之后就再也没有用心地研究它了。
与法国不同，第一次世界大战中新独立的波兰的处境却很危险，西边的德国根据凡尔赛条约割让给了波兰大片领土，德国人对此怀恨在心，而东边的苏联也在垂涎着波兰的领土。所以波兰需要时刻了解这两个国家的内部信息。这种险峻的形势造就了波兰一大批优秀的密码学家。他们很容易就监控住了德军内部的通讯系统，但是1926年被德军启用的恩尼格玛密码机却给他们造成了很大困难。
1921年，波兰与法国签订了一个军事合作协议。在波兰的坚持之下，法国把从施密特那里得来的情报交给了波兰人。波兰人正是以这个缺点为突破口破译了商业用恩尼格玛密码机。
但1941年英国海军在Joe Baker-Cresswell舰长的斗牛犬号军舰捕获德国潜艇U-110才真正拿到德国海军用的密码机和密码本，并将此事保密只告诉美国罗斯福总统，英国国王乔治六世称赞此事件是整个二次大战海战中最重要的事件。这让原本连数学天才图灵也破译不出的德军密码机得到破译，盟军设计的专门用来破译恩尼格玛密码的“炸弹”机也大大提高了布莱切利园的工作效率。
在战争结束以后，英国人并没有对破译恩尼格玛一事大加宣扬，因为他们想让英国的殖民地用上这种机器。1967年，波兰出版了第一本有关恩尼格玛破译的书，1974年，曾在布莱切利园工作过的英国人F.W.温特伯坦姆写的《超级机密》（The Ultra Secret）一书出版，这使外界广泛地了解到了第二次世界大战中盟军密码学家的辛勤工作。
