最近看了一部电影，叫《模仿游戏》，主要讲的就是二战期间图灵破解德军通讯密码的故事，最后的意义是导致二战提前两年结束，拯救了至少1400万人的生命。电影主要以讲故事为主，后来研究了一下伟人的破解原理，用最简单的语言科普一下，这里不需要各种数学知识，没有复杂的公式，相信我，坚持耐心看完，你一定能看懂。

所谓替换，就是将明文按照一张固定的表，替换成另外的字母，比如替换表如下：

加密 在加密的过程中，第一行的字母会被替换成第二行中的字母，比如：

解密 解密的过程中，首先要拿到这张表，根据加密后的密文去查表，从而恢复出铭文 这样一个最简单的加密暴力破解难度有多大呢？答：26个字母的字母的全排列，大约是10的26次方数量级，这意味着如果全世界60亿人每人每秒可以测试一种可能的密码表，也需要21亿年才能试完所有的排列组合。然而这样也安全的话密码学也就可以退出历史舞台了。 破解 看看键盘上的字母分布？为什么要是乱序而不是ABCD按照顺序排列呢？键盘的设计按照了字母在英文中出现的统计频率进行了位置排列。下面这张图片来自维基百科，显示的是26个字母在普通的英文文本中出现的概率： 根据这样一个统计频率，截获大量加密的密文，我们去统计其中每个字母出现的频率，基本会出现这样一个分布图，直接用统计出来的结果和这张图对应就能得到替换表，然后用替换表就能解密了。

在第第一回合中：我们使用了单表替换，很容易被使用概率统计的方法破解，后来人们在这种基础上，使用了多个表，假设使用两个表： 原文|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z| 表一|C|O|M|P|U|T|E|R|S|V|W|X|Y|Z|A|B|D|F|G|H|I|J|K|L|N|Q| 表二|A|I|R|P|L|N|E|F|G|H|J|K|M|O|Q|S|T|U|V|W|X|Y|Z|B|C|D| 加密 明文第一个字母在第一张表查，第二个字母在第二张表查，第三个字母又在第一张表中查，也就是2作为一个循环。 比如： HELLO–>RLXKA 注意看HELLO中的两个L分别别替换成了X,K,用这种方式来抵抗字母频率分析。既然两个表可以，那么可以使用更多个表，比如： 解密同1 上面这张表叫做维热纳尔方阵（Vigenère square），是为了方便加密者进行多字母替换而设计的。人们可以在表中选取任意行数的字母作为密码表进行加密，进一步提高了密码的复杂程度。 多表加密 假设加密者使用了GERMANY这7行作为密码表，对字母进行循环加密，由于明文中的每一个字母都会被随机地替换为另外七个不同的字母，所以前面介绍过的频率分析法将不再起作用。这一次，密码师是不是终于得到了一份绝对安全的密文？ 非也非也！ 破解 当破解者已经得到了相当长的密文后，由于英文中反复大量重复出现the and 等等这样的词，我们来看这样一个词组(这个)： the girl the boy 使用上边的GERMANY这7行的密码表循环加密得到结果: ZLV ---- ZLV ---- 为了方便，只给出了the位置加密的结果，在密文中，间隔为7(或者7的倍数)的地方循环出现了ZLV,然后我们就可以假设使用密码表的周期为7，这样破解就简单了，认真看了上边说的字母频率分析法的，到这里应该很容易理解了： 将1，8，15… 7a+1位置的字母提取出来，组成一个集合，因为这些位置的字母用的同一行替换表 将2,9,19… 7a+2位置的字母提取出来 等等 对这些提取出来的集合进行频率统计分析，依然和单表替换加密一样可以破解。

有人说，为何不使用非常多的替换表进行替换呢？哪个时候没有计算机，完全手工进行加密解密，密码表太长，加密解密靠手工效率非常低。

先来看看看着家伙长什么样子： 主要组成部分： 1.键盘：输入明文 2.灯盘：在键盘上输入一个字母，会有相应的字母亮起来，代表被加密后的字母 3.转子：加密的核心，后边会详细讲 4.插线板：为提高安全性增加的装置，后边会讲 操作方法： 1.调整好转子位置（为什么要调整后边会将） 2.输入明文，明文对应的密文灯会亮起来。

转子有两面，分别有26个点对应26个字母，转子两边的26个点用了26条导线连接起来，但是左边的A不和右边的A相连，上图中右边的杂乱的导线实现了这种对应关系，我们可以将其看作是我们最开始提到的单表替换。 转子一面 转子另一面 也就是一个转子代表了一个单表替换关系。左边输入明文，右边输出对应的单表替换的密文。 这还少最简单的单表替换，然而恩格玛机使用了三个转子串联起来了，如图： 三个转子串联，第一个转子的输出作为第二个转子的输入，第二个转子的输出作为第三个转子的输入。由于这三个转子都可以转动，也就不确定第一个转子的输出连接到了第二个转子上哪个字母作为输入,如图： 如示意图所示：A经过三个转子加密就变成了T。由于三个转子都是可以转动的，上图的中的箭头实际上是触点，并不是导线连死了，比如转子二向上转动一格，第一个转子的输出R就对应到了第二个转子的输入F上了，最后经过加密为：A->G->F->k->L->w. 由于每个转子都有26中可能的位置，所以三个转子一共可以提供26X26X26=17576个不同的密码表。这个数字已经相当可观了，但德国人还是不满足，又把三个转子设计成可以互相交换位置的形式。三个转子有六种不同的排列方式，所以密码表的数量又增加到了17576X6=105456，也就是大约十万个。德国人还是不满足，又增加了上面图片中的插线板，将密码数量进一步增大了1000亿倍（插线板的原理稍后介绍）。 恩格玛机除了转子，还有个重要装置：反射器，我们先来看看示意图： 大家可以看到一个字母A从键盘被输入之后，依次被三个转子进行三次替换然后到达反射器（红色路径），在反射器这里又被替换成另外一个字母（绿色路径），接着又沿着一条和来时不同的路径（蓝色路径），然后输出最终的加密结果，即字母G。反射器的原理还是字母的替换，这个替换可以随便用一个简单的表替换，只要保证输入输出不同就行。 这个反射器赋予了恩格玛机有两个重要的性质：

它长这个样子： 在插线板上刻有26个字母，如果操作员用一条线将其中两个字母连接起来，那么这两个字母在加密过程中会被互换。例如图片中的字母A和J被连接起来后，当操作员在键盘上敲下字母A后，这个字母A会被替换成J后进入转子。经过转子加密输出后的字母会再一次通过插线板，然后结果被输出到灯盘上。

我们在前面讲过，三个转子本身可以提供大约十万个密钥，扩大1000亿倍之后就是10^16个密钥。如果使用暴力破解的话，就算一秒钟验算一万个密钥，也需要三万多年才能穷尽所有的组合，而德军一条密钥的使用时间只有24个小时。对于破解者来说，恩格玛机所产生的庞大的密钥数量几乎让人断绝了一切进行暴力破解的念头，更不用提德军在1938年又把转子数量从三个提高到五个，海军后来又干脆提高到了八个。

以上就是恩格玛机的原理。已经看到了这里，继续加油，后边也不困难的。

恩格玛机的操作员每个月都会收到一本新的密码本，指定本月中每一天所使用的密钥。具体包含三个信息：

恩格玛机所提供的密码系统在那个年代已经是登峰造极了，但有着轻度被迫害妄想症的德国人还是不太放心。虽然每条密钥的使用时间只有区区24小时，但一天之内还是会有成百上千条信息被发出。在本文的第一部分“替换加密的原理和破解方法”中我们也可以看到，敌人截获的密文越长，就越容易发现其中的规律和模式。

于是，德国人又采取了一样非常聪明的防范措施： 操作员在按照密码本上的指示设置好恩格玛机后，再发送每条信息前，都要随机选取三个字母作为对本条信息加密的三个转子的初始刻度。是的，“随机”的意思指的就是操作员本人在发送信息的这一秒里脑海里浮现出的任意三个字母。

这样做有什么好处呢？ 每天通讯的内容只有每条信息的前六个字母是用密码本上的规定的初始位置加密的，而每一条信息的正文都是用不同的密钥进行加密的。如此一来，大大降低了敌人针对每一个密钥所能截获的密文长度。

加密

解密

坚持读到了这里，恭喜你已经站在几十年前伟大的破解者同一起跑线上了，加油!

看了这么多原理，终于要进入破解之路啦！ 我们来总结一下解密需要的信息：

通过间谍活动，波兰人(你没看错，确实是波兰人，图灵是在波兰人的基础上做的)得到了1和2,接下来，波兰人需要做的就是破解德军所使用的每日初始设置（下文简称为日密钥)

通过以上的总结，我们了解到：每条信息的正文都是用不同的秘钥(三个随机字母)加密的，但是前6个字母是使用当天的日秘钥加密的，这看起来很完美，但是波兰人雷耶夫斯基用难以置信的洞察力发现了其中的一个漏洞。

我们想象雷耶夫斯基截取到了一段德军的电文，前六个字母是：HGABLE，他知道这是三个字母连续输入两次恩格玛机的结果，虽然我们不知道这三个字母是什么，但是知道HGABLE中的第一个字母H和第四个字母B是同一个字母加密后的结果，由于转子在期间转动了三次，所有同一个字母在两次加密时被替换成了不同的字母，我们可以吧它们组成一对： H - B 如果雷耶夫斯基在一天之内接货到了更多的电报，对每封电报的前六个字母进行类似操作，就可以得到更多字母对，直到26个字母全都对上： H - B A - O … Z - U 我们来想想恩格玛机的本质是什么？ 那个时候没有用到混淆扩散，就是简单的字母替换。 在设置不变的情况下，输入的26个字母得到的替换字母都是确定不变的。 为了后边方便，我们设定一个规则： 这个公式非常简单，不要害怕，我只是为了好描述 A经过转动n次转子后替换后变成成为B描述为：A(n)=B 上边截获的HGABLE，我们假设明文为X,Y,Z可以描述为：

我们来回想恩格玛机的其中一个个重要性质： 自反，例如A加密后为G,则G加密为A 这可以描述为A(0)(0)=A,好像有点意思了，我们把第四行X(3)=B可以写为：

我们在去看看X(0)=H,H是我们已经截获的密文，那么上边就可以变成：

神奇的事情发生了，原始的X被抵消掉了，H和B之间的关系和加密每条信息的开始设置的随机数是没有关系的，只与一天的初始配置有关系，即开始时候三个转子的初始位置。 我们再来想想(0)(3)的物理意义：即将恩格玛机按照密码本设置好后，在转动三格得到的一种替换，本质还是单表替换，与文章开头的单表安全一样。 当截获大量的通信的前6个字母后：可以得到很多这样的消息：

等等，用上边的推理，可以得到一张(0)(3)对应的表： 如图： 也就是：我们知道每个字母在初始化转子位置后，在转动三格得到的结果，例如：初始化在转动三格，A对应C,B对应O，这样如果不考虑插线(几对字母交换)的影响，就只需要知道初始位置和三个转子的排列顺序就破解了恩格玛机器，这样的可能有：

如果制造100台恩格玛机，100个人同时进行暴力破解，每人10秒一次检查，可以再3小时内完成，具体方法是：

我们先来做一个联系，假设有个八个字母的密码替换表如下：

我们可以来一个首尾接龙的游戏： 上边这个密码替换表中，A被替换成C，C被替换成E,E被替换成A，首尾接住了，分为一组：

B被替换成了H,H被替换成G,G被替换成D,D被替换成F,F被替换成B,首尾接住了，分为一组：

原始的替换表就变成了(A,C,E)(B,H,G,D,F),和密码替换表完全一样，这样对于每种可能的密码替换表都可以写成这种形式，可以表示为[3,5]，这样，随便用线将两个字母连起来，交换两个字母，都不会改变每个分组的长度，这样就绕开了插线的干扰，我真想说，这些人的脑子是怎么长的，佩服的五体投地。 接下来是体力活：刚分析了光26个字母和三个转子可以组成大概10万众可能，然后人工对这10万种可能进行我们上边玩的首尾接龙游戏，然后按照分的组数，每组的长度进行分类，接着在利用上边截获的报文的前6个字母得到的(0)(3)表叶玩一次首尾接龙游戏，得到这这个表的分组情况，利用分的组数和每组长度去分相应的分类中进行暴力查找，这个查找次数比10万小很多很多 到这里，波兰人已经拿到了德军日密钥中除了插线板意外所有的内容。 得到转子的设置之后，雷耶夫斯基将会把一台恩格玛机按照这种设置装好，但是插线板不接线，把一段密文输入机器，他将得到一段没有意义的信息，因为信息中的六对字母被随机对调了，但是这种字母互换只是一种非常初级的加密方式，连我们最开始讲的单替换表都不如，可以人工根据单词的意思猜测到哪六对字母互换了，这样就拿到了插线板的设置。

这样，波兰人就拿到了德军日密钥的全部内容，也就是雷耶夫斯基与德军中的接收员处在了完全对等的位置，德军所有的通讯对于波兰人来说都是完全透明的。

说到这里，图灵还没有出现 那么图灵做了什么呢？ 德军在二战爆发前后，又采取了很多措施来加强恩格玛机的安全性（变态啊），其中的一些使得波兰人上面的这种破解方法失效：

补充内容，可看可不看

有人好奇上边第一条中密钥中转子的位置让操作员选择，那么解密方怎么解密呢？如果你对这个好奇，就继续看，如果不好奇，就简单理解为波兰人那一套行不通了，这部分可以不看。 在后期的恩格玛机中，德军又对转子进行了改造，使得转子芯外面的字母圈可以绕着转子旋转。这样一来，德军的日密钥内容就变成了以下三个部分：

这里请大家注意，在德军实行新规定之后，日密钥中已经不存在每日通用的转子初始位置。在发送每一条信息前，操作员都要自己选择转子初始位置，然后再自己选择本条信息的信息密钥。 举例来说，操作员按照密码本上的日期对恩格玛机完成三项设置后，准备发送一条信息。在发送前，他选择了ABC和XYZ分别作为转子初始位置和信息密钥。他首先把恩格玛机的三个转子拨动到A-B-C的位置上，键入两次XYZ后得到HBLZQO，这样就完成了对信息密钥的加密。接着他把恩格玛机的转子拨动到X-Y-Z的位置上继续输入信息的正文。 那么这个操作员怎样把ABC这个转子初始位置发送给接收方呢？答案是用明文发送。是的，你没看错，就是明文发送！所以操作员将会依次以明文发送ABC，接着是加密过的HBLZQO，最后是以信息密钥加密后的信息正文。 接收方收到以上信息后，会首先将恩格玛机拨动到ABC的位置，键入HBLZQO后得到XYZXYZ，于是他知道接下来的信息正文是用密钥XYZ加密的。接着他只要把恩格玛机转动到XYZ的位置键入密文，就可以得到信息的明文。 就算破解者截获到这段电报并且知道ABC是明文，也无法知道本条信息的信息密钥。因为破解者不知道德国人手中恩格玛机上的字母圈相对于转子被旋转了多少位，所以并不知道ABC所对应的转子真实位置到底是什么。 雷耶夫斯基巧妙的利用了德军“每条信息的前六个字母都是用同一个通用密钥加密”这一点来进行破解。但是德军采取上述做法之后，每条信息前面的这六位字母都变成是用不同的密钥加密的。所以雷耶夫斯基的破解方法也随之失效。 不过，这个时候的波兰人又想出了另外一种有效的方法进行破解（人类智力的潜能真是无穷无尽啊），直到1940年德国人规定信息密钥只需输入一次后，才彻底失效。

接下来，英国人图灵出场了。 1939年德军进攻波兰前夕。波兰人将恩格玛机的复制品和他们掌握的破解方式提供给了英法两国。图灵虽然赞叹波兰人的只会，但是他意识到这种破解方式过度依赖德国人的漏洞，后来德军升级恩格玛机，这种破解方式随之失效，于是图灵追求的是一种更加直接暴力的破解方式：机器对抗机器。如果说波兰人是利用敌人防线上的漏洞进行伞兵奇袭，那么图灵想要的更像是步兵师的正面对抗。机器创造出来的密码怪兽，只有用机器才能战胜。而人类的任务不过是设计机器的工作原理以及优化机器所要进行的运算量。

做了这么长的铺垫，终于要进入大结局了。我们来一起看一下英国人的破解恩格玛机的。

首先，英国人需要在密文中确定一条“Crib”。所谓Crib，指的是一段猜测出来的明文与密文中字母的一一对应关系。在密文中猜测出几个单词的明文并不困难，因为循规蹈矩的德国人在信息正文中喜欢用固定的词组，比如Keine besonderen Ereignisse（无特殊情况），Heil Hitler（希特勒万岁）等。另外一个例子是英国人发现德国人喜欢在早上6点钟发送一条天气预报，所以在早上6点钟截获的电文开头中肯定包含wetter（天气）这个词。在《模仿游戏》中，讲的是希特勒万岁。

猜出密文中包含的明文单词后，如何精确地确定它们的位置呢？希望你还没有忘记我们前面讲过的恩格玛机的第二个非常非常重要的性质，那就是一个字母永远不会被替换为自身。根据恩格玛机的这个特性，我们可以把一段明文字母在猜测对应的密文上方来回移动进行判断。下面我们用德文单词wetter做一个简单的示例：

在上面这张图片中，明文位置1可以被排除掉，因为在这个位置上明文中的E又被加密成了E，而这是违反恩格玛机特性的。同理，明文位置3也可以被排除掉，因为明文中的R又被加密成了R。排除掉不可能的情况，明文位置2就极有可能是wetter这个单词所处的真实位置。这样我们就得到了一个Crib，其中明文与密文的对应关系如下：

在上边这个对应关系中，图灵利用其中首尾相接的字母链设计出了可以暴力破解恩格玛机的机器。这段的加密过程为：

我们来详细看一下w->E的加密过程：

当操作员按下W后，如果W上接线和另外一个字母连接了，就替换成另外的那个字母，没有接线就替换，我们记操作员按下W后，没有进入转子之前生成的字母为V1,V1经过三个转子加密生成V2,V2经过插线板(有线替换，没有线就不替换)，输出E

我们将W-E-R-W这个字母链连接成一张图，用三台恩格玛机串联，如图： 解释一下，v2和v3: w经过插线板，转子位置0加密后得到v2,v2经过插线板输出E,这个E作为下一台恩格玛机的输入，经过插线板，当然还是v2,相当于一个反向替换(如果没有线就不替换)，很容易理解,V3同理。 同理得到W经过插线板没有进转子之前得到V1,则当输出结果为W时，在输出插线板之前转子之后，结果还是V1,所以V1==V4，所以图中，E和R之两边的插线板是多余的，图可以化简为：

那么图灵工作的精髓来了： 用三个恩格玛机的转子串联起来，从刚才我们计算的所有可能中选一种，作为第一个恩格玛机的位置0，第二个恩格玛机相对于第一个偏差1，第三个相当于第一个偏差5，暴力破解者写所有的可能为： — 所有转子可能位置：26X26X26种

每次在V1位置输入A-Z这26个字母，V4位置正好对应这26个字母，那么当前的转子位置0就是德军加密时候设置的位置0。如果有足够多的Crib,甚至可以直接锁定唯一的转子设置，没有的话就是暴力破解者100多万中，机器应该很快，那个时候还没有计算机，以现在的i5也就是秒级别的破解吧。

至于电影提到的在酒吧遇到的一个女的猜测她喜欢的男的有女朋友的片段对图灵的启发应该在于：帮助图灵找到灵感，找到上文中提到的wetter这个单词，电影中用到的是：希特勒万岁。

我们来看一下这个机器长啥样：

这个也是看知乎上大神的回答，自己看了在难以理解的地方又添加了点东西让更容易理解，但是我还有一些疑问希望和大家共同探讨： 1939年德军将密码机升级了以后，有个重大的改进：每个转子外侧的字母圈相对于转子芯有一个偏移，德军通信的时候，自己随机选择一个初始位置(例如ABC)，将其作为初始位置，用明文发送给对方，接收方收到是ABC，然后将自己的机器初始位置设置为ABC，然后再去解密对方接着发送来的以后发送消息时候要用的初始位置。这里有个疑问：对于波兰来说，同样可以接受到明文的ABC,文中提到的之所以波兰截获到ABC也不会解开接下来发送消息要用的解密密钥的初始位置，因为波兰不知道他们机器的转圈上的字母相对于转子的偏移。那么问题来了，如果缴获或者用间谍搞到他们一台密码机，是不是整个密码体系就崩溃了？欢迎讨论。

-----------------------------------end------------------------------------