密码那些事儿｜ 十七 年轻数学家首次破解恩尼格玛机(图灵破解恩尼格密码)
密码那些事儿｜ 十七 年轻数学家首次破解恩尼格玛机(图灵破解恩尼格密码)
受影视文学作品影响，提到年轻数学家破解恩尼格玛机，人们的脑海中都会浮现出图灵的名字。不可否认，图灵为最终破解恩尼格玛机确实做出了巨大的贡献，但那是他站在了“巨人的肩膀上”。事实上，在图灵之前，首次破解恩尼格玛机要归功于三位年轻的数学家，他们全部来自波兰。
一战后世界处于暂时的停火状态，波兰位于德国和苏联之间，属于在两个大国的夹缝中求生存。东边经常被苏联渗透，西边的德国又谋划着收复失地，所以波兰的警惕性极高，总感觉随时会被两边的强敌攻陷，从没放松过密码学研究。这种威胁下的恐惧感给了他们破解恩尼格玛机的最大动力。
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 Turing: The Enigma》改编，由卷福饰演图灵，豆瓣评分8.5，好过89%的传记片。
好的传记电影就是这样，庄重而不浮夸，迭起而不失真实。故事以倒叙插叙开始，讲述图灵的一生。
二战期间，英国苦于德国纳粹密码系统“恩尼格玛”无法破译，便召集了一批数学专家进行秘密破解工作，艾伦·图灵便是其中之一。图灵作为破译团队主力，率领团队制造出当代计算机原型——“图灵机”，成功破译“恩尼格玛”。
一场战争，生灵涂炭，上帝未能拯救人类，而图灵却用用科学的力量为二战扭转了战局，使其提前两年结束，拯救了至少2000万人的生命。
英国首相丘吉尔认为艾伦·图灵对二战胜利做出的贡献比任何人都多。然而，本该是举世瞩目的英雄人物，却在2013年之前蒙受罪名。
如今我们称为无腐不欢的英国，在20世纪曾是对同性恋惩罚最严厉的国家。而艾伦·图灵也正因是同性恋而被整个社会所不容。
被人发现是同性恋之后，艾伦·图灵被定罪，在面临坐牢和化学阉割疗法之中，图灵选择了后者。美其名曰“激素治疗”的阉割疗法让图灵几度精神崩溃。1954年，绝望的图灵吃下涂有氰化钾剧毒的苹果自杀。
去世时的图灵，年仅四十一岁，伟大的生命就此谢幕，对世界文明的损失，不可估量。
相传，乔布斯的苹果公司被咬了一口的苹果logo，便是致敬图灵自杀时咬下的半个苹果。
电影界有奥斯卡小金人，科学界有诺贝尔奖，1966年，美国计算机协会（ACM）设立了“图灵奖”，每年奖励一名在计算机技术领域做出突出贡献的人。图灵为计算机领域奠定了不可埋没的基础，没有他就没有计算机的今天。
艾伦·图灵的成就直至自杀那一天都在保密，他对二战胜利所做的贡献是个秘密，而他的与众不同却成了千夫所指的罪过。2012年，著名科学家斯蒂芬·霍金等人要求英国政府为其平反。2013年，图灵，这个“被国家所亏欠的英雄”，终被英国女王赦免。
天才总是天真、坦荡、毫不设防地迎向这个庸人占领的世界，而代价却是，他们为世界带来了创造，世界给他们带去了毁灭。
正像《生活大爆炸》中的谢尔顿，图灵也是个标准的宅男，他的大脑可以运算出世界最难解的方程式，提出最科学最高明的新理论，但对人情世故，他却一窍不通。性格孤僻，不善交际，与周围人格格不入的图灵甚至不止一次炮轰过当时的领导人。
讯问图灵的警官询问图灵机器是否会思考时，图灵回答道，“机器不同于人类，所以他们和人类思考的方式不同。有趣的是，仅仅因为某样东西思考的方式与你不同，难道就意味着不思考么？”图灵这番话，点出了他这一生最重大的两个主题：事业与性向。
其实图灵的性取向与他发明的图灵机一样，都是超越了当时的社会而在主流群体中不被接受的。在科研领域图灵不懈努力，并坚持他所认为对的理念；明知世俗不容他的性取向，他也不愿意为之妥协。人们总是喜欢拒绝不一样的人或事物，总希望改变与同化一切与众不同。即便时间会证明谁对谁错，但图灵的悲剧，让我们看到美好的时刻总是来的太迟。
在图灵的墓碑上，刻有以下碑文：艾伦·麦瑟森·图灵（1912-1954），计算机科学之父、数学家，逻辑学家、战时密码破译者、偏见的受害者。
图灵的存在充满光芒，结局却是这般黯淡。改写了人类的历史，触动了文明前行，拯救无数人死于战争车轮下的他，最终死于世俗偏见的践踏。
“有时，恰恰是那些意想不到的人会完成最意想不到的事。”
我们看到那些少数天才带来的社会进步，却一直未能看到人性的进步，我们总是固执地用一己想法改变着世界，而图灵等天才却用一己想法改变着我们。
在布莱切利园中，德国海军的恩尼格玛密码一直被认为是最难以破解的。
德国海军历来极其重视无线通信的可靠性和保密性，就是他们率先使用了恩尼格玛机来加密。而且，德国海军还频繁地在结构和操作方式上对恩尼格玛机进行改进，以确保它无懈可击、牢不可破。
第二次世界大战前夕，德国陆军和空军将恩尼格玛机的转子从3个增加到了5个，而德国海军则是继续增加到了7个，最后更是丧心病狂的增加到了8个。
而且，德国海军还使用了与陆军及空军不一样的新操作规程，主要包括两个方面：
一、增加“密钥手册”，规定每天0点更新初始参数。
（a）选择8个转子中的3个并规定其基左中右位置；
（b）设定各转子的内外轮之间的相对位置；
（c）设定接线板上的10对接线；
（d）设定3个转子的初始位置。
二、采用“双字替换表”
（a）发报前，先从密钥手册中选3个字母，比如ABC，作为密钥，然后把恩尼格玛机的3个转子调到当天规定的初始位置，输入ABC，假设得到FTN，再把转子调到FTN的位置，开始加密正式电文；
（b）再从密钥手册中选另一组字母，比如XYZ，在XYZ的左边和密钥ABC的右边任意增加一个字母，比如P、Q，列成两行，上下对齐。
P X Y Z
A B C Q
（c）根据当天有效的“双字替换表”把各列的字母对PA、XB、YC、ZQ分别替换，比如替换成IS、OW、MD、UV；
（d）发送电报时，把这4对字母加在正式密文的首尾；
（e）对方接收到电报后，先对4对字母反向操作，得到3个字母ABC，再得到FTN，然后开始解密正文。
这样一来，原来重复加密3个字母密钥的操作就不存在了，以致雷杰夫斯基发明的破解方法完全失效。
在图灵来到布莱切利园之前，几乎所有人都认为德国海军的密码是无法破译的，因此没有人愿意为它浪费时间。图灵到来之后，发明了基于crib方法的“炸弹”机，理论上是可以对德国海军的密码进行破译的，但由于早期的“炸弹”机性能过低，所以破解的效率极为低下。
当时德国的U-潜艇正在严重威胁盟军的大西洋生命线，寻找有效的破解德国海军密码的方法变得刻不容缓。经过一段时间的摸索和研究，图灵终于发明了基于贝叶斯统计原理的“班布里方法”，能够有效破解德国海军的恩尼格玛机。
班布里方法基于语言学中的一个统计事实：把任意两段文字拿来排成行上下对齐进行比较，查看其中有多少对字母是相同的；当这两段文字属于同一编码系统时出现相同字母对的概率，明显高于当它们不属于同一编码系统时的相应概率。
基于这个原理，图灵找到了破解德国海军恩尼格玛机的途径。不过图灵所用的方法包含了大量数学理论，过程也相当繁琐，这里就不详细表述了，我们只说一下图灵的大致思路。
首先，通过对比分析大量的电文头尾的明文字母，部分甚至完全破解“双字替换表”，从而获得电文密钥；
其次，用班布里方法，确定右边转子是8个转子中的哪一个；
再次，重复使用班布里方法，进一步确定中间转子是哪一个；
最后，用“炸弹”机破解全部密文。
这个步骤被验证是行之有效的，图灵就这样搞定了最高级别的德国海军恩尼格玛机。
1940年5月8日，用班布里方法破解德国海军密码首次获得成功。以后的三年里，此方法结合“炸弹”机成为英国破解德国海军密码的主要手段，为盟军重创德国U-潜艇舰队、守住大西洋生命线做出了巨大贡献。
据不完全统计，破解之后，盟军全年被击沉船只的吨位下降了60%；而德军潜艇的损失率，从破译前的不到7%，猛增到50%。
更多文章：
密码那些事儿｜（二十）破解恩尼格玛机的图灵方法
密码那些事儿｜（十九）在人性与规则中找寻漏洞
密码那些事儿｜（十八）跨越英吉利海峡的恩尼格玛机
密码那些事儿｜（十七）年轻数学家首次破解恩尼格玛机
密码那些事儿｜（十六）二战中大放异彩的“超级情报”
密码那些事儿｜（十五）坚持就是胜利——初代恩尼格玛机
密码那些事儿｜（十四）古典密码的巅峰——恩尼格玛机
密码那些事儿｜（十三）尴尬的维吉尼亚3.0
密码那些事儿｜（十二）短命的维吉尼亚2.0
密码那些事儿｜（十一）南北战争时的维吉尼亚密码较量
密码那些事儿｜（十）“钥匙”打开维吉尼亚的锁
本人是官方授权会员推广专员，点击 会员专属通道 成为会员，您将会获得钻奖励及诸多权益！
《钻奖励调整公告》
您知道计算机科学之父是谁吗？你知道阿兰•图灵背后的故事吗？计算机科学之父阿兰图灵的故事是图灵生平的缩影，摘自《图灵的秘密：他的生平、思想及论文解读》。励志故事:图灵的秘密，365语录台词把这篇文章分享给大家，下面就是365语录台词网为你搜集整理的精彩内容，就让我们一起来欣赏一下吧！
2014年6月7日是阿兰·图灵逝世60周年。这个名人故事是图灵生平的缩影，摘自《图灵的秘密：他的生平、思想及论文解读》。
阿兰•图灵（1912—1954）是英国数学家、逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。为纪念他在计算机领域的卓越贡献，美国计算机协会于1966年设立图灵奖，此奖项被誉为计算机科学界的诺贝尔奖。 1912年6月23日，阿兰·图灵生于伦敦，是家中的第二个男孩。
1926年图灵进入公立学校舍伯恩学习。他害羞、孤独，似乎总是衣衫不整，学习上也没有表现得特别优异。只有在数学上，他的智力天赋初露端倪。1929年，图灵开始着迷于《物理世界的自然》（1928）一书。期间认识克里斯托弗·莫科姆，并交往密切，他们在科学和数学上有着共同的兴趣。回想起来，图灵很可能在那时发现了他的同性恋倾向。
1929年12月，图灵和克里斯托弗共同参加了剑桥大学奖学金考试，随后克里斯托弗被三一学院录取，图灵落榜。但两个月后，克里斯托弗突然生病，在一周内去世。一位舍伯恩的旧日同窗在信中写道：“可怜的图灵因为这个打击几乎崩溃，他们一定是极其要好的朋友。”
1930年12月，图灵再次参加了三一学院的考试，仍然未被录取。他调整目标，瞄准第二选择剑桥大学国王学院，全心钻研G. H. 哈代的经典著作《纯数学教程》备考。1931年秋，图灵开始了他在剑桥大学国王学院的学习。
1935年春，图灵修读了麦克斯·纽曼的“数学基础”课程，课程涵盖了尚未解决的判定性问题。同年夏天，图灵开始研究判定性问题。
图灵的毕业论文发表在伦敦数学学会1936年11月和12月的论文集里，这就是图灵流芳百年的“OnComputable Numbers, with an Application to the Entscheidungsproblem”（论可计算数及其在判定性问题上的应用）。他的论文采用了一种不同寻常的数学证明方法，甚至创造了一个通用机器，它能模拟其他任何一台计算机器的操作。
毕业后图灵来到美国普林斯顿大学攻读数学博士学位，期间他对密码学产生了兴趣。
1939年9月1日，德国入侵波兰，第二次世界大战爆发。两天后，英国向德国宣战。9月4日，图灵受邀到英国政府情报破译中心布莱切利庄园报到，致力于破译德国海军的密码。1940年，第一台“图灵Bombe”开始运行。它重达一吨，可模拟30台并行运行的恩尼格玛密码机。1941年，德军恩尼格玛加密的通信被攻破，图灵在其中起到了重要作用。
1943年初，图灵到贝尔实验室待了两个月，在这里遇到了开辟数位采样理论的哈利·奈奎斯特和克劳德·香农。
1951年3月15日，因在可计算数方面所做的工作，图灵被评为英国皇家学会会士，举荐人是麦克斯·纽曼和伯特兰·罗素。
1952年2月，因同性恋行为，警方传讯了图灵。最终，法庭判处图灵“严重猥亵罪”，且强制实施荷尔蒙治疗。图灵的择业因此受到限制，计算机之路也严重受阻。
1954年6月7日晚，睡前，图灵照例吃下苹果，但是，这只苹果蘸上了剧毒氰化物，41岁的天才就此了结了自己的一生。
2009年9月10日，英国前首相戈登·布朗代表英国政府为图灵当年受到的不公正待遇公开致歉。2013年12月24日，英国女王伊丽莎白二世为图灵追授死后赦免状。
由Windows编程大师Charles Petzold耗时多年编写的《图灵的秘密：他的生平、思想及论文解读》剖析了现代计算机原理开山之作、阿兰•图灵流芳百世的论文 “On Computable Numbers, with an Application to the Entscheidungsproblem”。图灵在其中描述了一种假想的计算机器，探索了其功能和内在的局限性，由此建立了现代程序设计和可计算性的基础。这本书也像是一本小说，行文间穿插讲述了图灵的成长经历和教育背景，以及他跌宕起伏的一生，包括破解德国恩尼格密码的传奇经历，他对人工智能的探索，他的性取向，以及最终因同性恋的罪名而在41岁时自杀的悲惨结局。全书完整揭示了阿兰•图灵非凡、传奇而悲剧的一生，是了解图灵的思想和生平的极好著作。（365语录台词网为您编辑发布，喜欢我请持续关注）
