主题：【原创】密码传奇（三）：19、图灵机发威 -- 1001n

感谢大家的夸奖，动力澎湃中这就加快上帖速度，早日填完这个英国无底洞……

这一节又有点偏“硬”，大家多担待

---------------------------------------------------------

ENIGMA，已经实现了密码编码的机械化；从这个意义上讲，针对ENIGMA的密码分析，自然最好也该是机械化的。前面我们提到，波兰人已经发明了Bombe，但是由于资金和技术的问题，没有能够跟上ENIGMA系列的不断升级，最终抱憾而停。

而无论是图灵的研究对象（那些可灵活组合，发挥不同功效的“图灵机”），还是他的研究思路（机械化的计算方法），不都是破译ENIGMA最需要的么？

老实说，图灵如果继续留在大学里，或许会研究出很多理论性很强的成果；但在政府密码学校，他的特长却可以让他在实践上大放异彩——总的来说，在庄园里各行各业的专家群里，怕是没有比图灵更加“专业对口”的了！

机会只留给有准备的人，此话真是一点不错啊。

图灵仔细分析了波兰人的Bombe，从中得到了相当的启迪：

ENIGMA破译，难就难在它是复合加密，也就是转轮组和连接板的双重加密。因此，破译的大前提就是必须想办法把两次加密拆开，分别对待。

波兰人雷杰文斯基的办法是：只收集德军电文报头的六个字母，来构造相应的字母循环圈（其中内容，请参见【ENIGMA故事波兰篇】，及【本篇篇外之活拆了ENIGMA】）；尔后构造群论方程组，消除掉连接板的影响，在此基础上对转轮组进行穷尽暴力破解，最终实现对ENIGMA的整体破译。

而取头六个字母，根据是什么？我们前文曾经提到过：电文头六个字母，就是操作员任意选择的三个字母连续加密两次而成；这样一来，由于第一和第四，第二和第五，第三和第六个字母都是针对同样的字母加密而来，相互之间就有了“关联”，因此才能分析。

重要，就重要在这个“关联”上——只不过，波兰人的办法，确实还存在着两个问题：

第一：摒弃全文而只用前六个字母，从密码分析的角度看，是不是比较浪费“素材”？在一定程度上，是不是也因此加大了己方破译的难度？

第二：要是敌人放弃了重复两遍的三码组，这样的“关联”不存在了，又该怎么办？

特别是第二点，可以说是雷杰文斯基方法的最大漏洞；一旦德国人规定，不再由操作员任意选择三个字母并连续拍发两遍作为临时密钥，波兰人的Bomba将立刻陷入无码可破的境地。

二战爆发后不到一年，德军真的专门规定：临时密钥不再拍发两遍。

怕什么来什么，波兰人的办法，果然就失灵了——可是战火已起，英国人又怎么等的起？没有了那六个标志性的字母，难道就不破译ENIGMA了么？

为了解决这个问题，图灵试着倒着去追溯波兰人的思路，即：

8、根据每日密钥破译电文

↑

7、破译每日密钥

↑

6、穷尽每日转轮的选用和排列

↑

5、计算所有转轮的内部设置

↑

4、构造群论方程，计算最右边的转轮设置

↑

3、利用字母循环圈构造字母深层对应关系

↑

2、截取头六个字母构造字母循环圈

↑

1、寻找字母的“关联性”

这其中，究竟有几步现在已经无法做到了？

——显而易见，随着重复三码组的取消，第2步就已经是无源之水了；但是与此同时，其它的步骤是不是也全部失效了呢？

当然不是。

不难看出：只要密文还是由ENIGMA（包含反射板）生成的，或者说，这份密文依然是“对合”的，那么，其中的字母循环圈法，就依然可以使用，而波兰人思路的绝大部分，也依然是正确的！

的确，字母循环圈法作为一个分析方法，它本身并不在乎你取的是什么字母，只要有“关联”就成；而波兰人为了达到这个目的，这才取了前六个字母——那么，电文中还有没有别的字母，可能有某种“关联”？

恰如一道闪电，劈开了图灵的思维：就是啊，为什么非要只取头六个字母呢？

从理论上说，能想到这一点，确实是很聪明；但是如果仅此而已，图灵也说不上有什么过人之处。或许也有人早就想到这个问题，但是，“关联”啊“关联”，你到底在哪里？

而图灵，还就找到了这个关联！

为了说清楚，我们不妨把雷杰文斯基的思路和图灵的思路做个对照：

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

雷杰文斯基 图 灵

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

目的 寻找关联 寻找关联

范围 头六个字母 全文

依据 相同字母经过两次加密 明文字母和密文字母必然一一对应

实质 密文字母之间的关联 明文-密文字母的关联

方法 循环字母圈 + 暴力破解 循环字母圈 + 暴力破解

适用 老规则ENIGMA电文 所有ENIGMA电文

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

从上表可以看出，图灵大大扩展了雷杰文斯基的思路，关键就在于选取关联字母的范围从“密文-密文”，扩大到了“明文-密文”；也因此，图灵的方法，适用范围明显要广泛的多。

这就产生了一个问题：雷杰文斯基的办法再狭隘，“素材”的获得却也不难，只要截收到电文就能做到；而按图灵的办法，又要去哪里找“明文”呢？

是啊，本来破译的目的，就是从密文中恢复明文；现在却反而要以明文为基础去破译密文，以获得明文——这个逻辑思维，是不是混乱了点儿？

一点都不混乱。

关键是，这里说的“以明文为基础”，实际上不是立足于真正已经破译出来的明文，而是猜出来的“明文”！

举例而言，在某段时间内，布莱奇利公园几乎每天都能截收到一份很短的电文；除非个别，这样的电文中，大部分长度都是相等的。从道理上讲，能够天天截收到长度大致相当的短电文，这本身很可能是一种巧合——但是更巧合的是，这样的短电报还有个共同特征，那就是：都是早晨06时05分拍发的！

负责对截收电文进行初步整理的工作人员玛格丽特·罗克（Margaret Rock），非常细心地注意到了这个问题，并产生了极大兴趣：什么电报会在每天清晨准时播发一次呢？

很快她就猜出了正确的答案：这不是别的，只能是天气预报！

在这里，我们也多说一句吧——玛格丽特·罗克不仅正确判断出了例行短电报的属性，还以她的细心，为庄园又立一功：经过她的仔细观察，这些天气预报的报文还有个特点：在全文的倒数第5至倒数第15个字母之间，几乎就从来就没有出现过字母X。

这说明了什么问题？

一份两份电文，特定位置不出现X，可能是巧合；但是所有电文都这样，岂非有诈？

密码分析，真的应该是聪明人的专利——她很快就判定：正是由于ENIGMA不可能把明文字母加密成相同的密文字母，因此，这些位置不出现X，肯定是因为其中有过X！

稍微详细解释一下就是：ENIGMA由于有反射板的存在，不能把明文字母A加密成密文字母A；其中搀杂了相当数量的明文字母X后，再经过ENIGMA加密，这些X当然就被转换成了其它字母——这样一来，按照总体分布规律统计，出现X的几率当然明显低于正常密文了。

那么，德国人为什么要在文电末尾加上一大堆X呢？玛格丽特·罗克断定，这绝对是对手的花招——他们在文电末尾特定区间加上数量不等的字母X，目的就是为了迷惑试图解密这些电文的人！

她的判断完全正确。这个例子再次生动地说明了：在智力的较量中，性别并不是最重要的问题——在将来的【密码传奇美国篇】中，我们没准儿会看到更多的巾帼高手，谁知道呢：）

那么，一份已知是天气预报的电文，会对破译ENIGMA起什么帮助作用呢？

我们可以设想一下：天气预报，无非几个指标：

阴晴天候

云量情况

风向风力

气温变化

外加可能的海水水温及风浪情况，等等。总体而言，这些指标的变化幅度相当之小；比如气温，顶多也就是从零下几十度到零上五十度——这已经涵盖了从U艇活动的北冰洋，到北非军团鏖战的热带的全部可能气温——全加起来，最多也就是一百多种变化而已。

且不说天气预报是分地区的，一个地区在某一天的气温变化一般也不会超过20℃——即便超过了，其变化幅度也必然不大——而诸如阴天还是晴天、多云，下不下雨、雪，几乎都只有个位数的变化可能；再考虑上风力和海浪情况，各自一般也不会超过二十种变化情况。

同时，气象情况是有连贯性的，比如昨天的天气，一般就不会和今天的天气差太远。

总而言之，天气预报由于其本身性质，必然成为一种内部数据指标大量重复的明文。也就是说，天气预报是最容易导致明文泄露的一种文本——只不过，当年的德军还远远没有认识到这一点……

从密码分析的角度，至少可以从三个层次着手对付天气预报密电：

1、统计学破解：由于明文里面涉及的数据就是那么多，又反复出现，这肯定是一个漏洞；

2、比照式破解：如果能够知道这样的天气预报是针对哪个地区的，破译方只要拿自己一方对该地区的相应天气预报，就能进行“大致相同明文”基础上的密文对照分析——以上两个层次的破解，是1001n自己猜测的，如有不对，也希望大家指正：） ；

3、猜测式已知明文攻击：不仅使用于天气预报密电，还适用于能够大致估计出明文部分内容的各种密电。

而图灵的办法，正是立足于第三种办法，也就是“猜测式已知明文攻击”。

这个思路，图灵早在1939年夏天，还没正式到布莱奇利庄园上班时就产生过；这里，我们就以天气预报密电为例，来做个说明吧。

天气预报密电中，很有可能会出现“天气”这个词——特别是对手还没注意到天气预报本身是泄密途径之一的时候。而在德语中，“天气”对应的单词是“wetter”——OK，一切就从这个wetter开始好了。

以下为一个虚拟的例子——假设我们在06时05分截获了一份电报

电文：QPLUD OETQW KYOFI XZMDF ……

我们已经知道它是天气预报密电。通过详细观察这份电文，以及不同日期相同时刻截收的其它电文，我们很有可能发现一个特点：那就是从第六个字母起，到第十一个字母止，从来不会出现以下字母（请特别注意，这里是虚拟例子）：

第六个字母： 从来不出现W

第七个字母： 从来不出现E

第八个字母： 从来不出现T

第九个字母： 从来不出现T

第十个字母：从来不出现E

第十一个字母：从来不出现R

这样一来，根据ENIGMA的加密特点，我们有理由怀疑，明文中的这六个字母，分别就是W、E、T、T、E、R。

整理刚才的电文，也即

假定明文： WETT ER

|||| || →可疑对应关系

密文：QPLUD OETQW KYOFI XZMDF ……

开始构造字母循环圈，规则是：

1、从一个假定明文字母出发，连接它所对应的密文字母；

2、之后从密文字母出发，寻找已对应字母之后位置的假定明文字母，如果有相同的，则予以对应；前提是：这个对应关系，应该尽量保证能以最短的对应次数，回到初始假定明文字母。

3、重复第1步、第2步，直到出现循环圈现象。

说起来比较容易糊涂，我们就实际操练一下吧。

现在，假定明文字母是W、E、T、T、E、R，对应的密文字母是E、T、Q、W、K、Y。根据前面的规则，我们可以得到：

明文字母 W E T T E R

第一步： |

密文字母 E T Q W K Y

尔后，密文字母的E，就可以和明文字母中的E对应上了，如下

明文字母 W ┌ E T T E R

第二步： | │

密文字母 E ┘ T Q W K Y

按规则，再把明文字母E和它直接对应的T相连接，即

明文字母 W ┌ E T T E R

第三步： | │ |

密文字母 E ┘ T Q W K Y

从密文字母T出发，按规则应该对应下一个可疑明文字母T，也就是第三个明文字母；但是第四个明文字母也是T，而且对应的是密文字母W，有希望构成循环圈——因此，对应关系跳跃，直接对应第四个明文字母，也就是第二个T。

┌───┐

明文字母 W ┌ E │ T T E R

第四步： | │ | │

密文字母 E ┘ T ┘ Q W K Y

┌───┐

明文字母 W ┌ E │ T T E R

第五步： | │ | │ |

密文字母 E ┘ T ┘ Q W K Y

┌───┐

明文字母 ┌ W ┌ E │ T T E R

第六步： │ | │ | │ |

密文字母 │ E ┘ T ┘ Q W K Y

└────────┘

成功。经过六步操作，可疑明文字母和密文字母之间，终于呈现了“关联”！

这就意味着，新的字母循环圈已经建立，即

明 密 明 密 明 密

文 文 文 文 文 文

┌→ W → E → E → T → T → W ─┐

│ │

└────←──────←────┘

从理论上讲，由于假定明文太短（才六个字母），可疑密文字母与这些假定明文字母之间，能够出现如此的对应关系的概率，其实并不大。但是，这样的对应关系有助于图灵的思考，能让他把问题逻辑化；尔后，他的强项就开始闪光了。

ENIGMA属于流式密码机，也即流水般以字母为单位加密明文，一个明文字母，必然对应一个密文字母；这就意味着，在连续加密明文字母时，机器内部的转轮组必然是在加密前一个字母的位置基础上，又做了进一步运动的。

那么，如果我们把转轮组加密某个明文字母X时的位置记做P（X），则加密X后续的第一个字母（X+1）时，位置就是P（X+1）。因此，上文对六个假定明文字母的加密时，我们就以加密第一个字母时转轮组的位置为P1，下一个为P2，如此类推，一直到最后一个字母为P6。

对照上面的循环关系，

┌───┐

明文字母 ┌ W ┌ E │ T T E R

│ | │ | │ |

密文字母 │ E ┘ T ┘ Q W K Y

└────────┘

则有

P1 P2 P3 P4 P5 P6

┌───┐

明文字母 ┌ W ┌ E │ T T E R

│ | │ | │ |

密文字母 │ E ┘ T ┘ Q W K Y

└────────┘

图灵毕竟是图灵，他马上把自己的拿手思路套了进来：这每一步，不正是一台“虚拟机器”——“图灵机”——能做的事么？

将ENIGMA的流式连续加密过程，分解为一步步的工作，进而引申成一台台机器的“独立工作”，正是图灵的天才所在；而事实也将会证明，这一步的飞跃是多么漂亮！

将P（X）直接想像成独立的图灵机，则P1～P6就变成了六台图灵机，记做T（X）；因此，我们刚才的P1～P6，也就相应成为了T1～T6。根据这个定义不难理解，不管怎么加密，T2永远比T1更前进一个位置，而T6永远比T3更前进3个位置。也即：

T1 T2 T3 T4 T5 T6

┌───┐

明文字母 ┌ W ┌ E │ T T E R

│ | │ | │ |

密文字母 │ E ┘ T ┘ Q W K Y

└────────┘

到此为止，ENIGMA的流水作业确实被拆开了；但是，这对破译到底有什么帮助呢？

——我们要说，图灵高就高在这里：看起来，似乎只是把ENIGMA的工序给分解了，但其实质，是打破了“ENIGMA加密是由一台机器完成的”这样的思维定势，进而极大地解放了后续的工作思路。

顺着这条新思路，图灵的智慧也爆发了：既然是几台机器一起在工作，那么，把它们“连接”起来，又会如何？

——实在是令人佩服得五体投地！

连接的办法并不难，说白了就是个串联；可这一串联，却出现了一个极为奇妙的结果——为了说清楚，我们不妨先简单回顾一下ENIGMA的加密流程：

输入明文字母 → 进入连接板 → 进入输入轮 → 进入转轮组 → 被反射板反射回来 → 进入转轮组 → 进入输入轮 → 进入连接板 → 显示为密文字母

我们将其中的蓝字步骤做一概括，则整个流程可以简化为：

输入明文字母 → 进入连接板 → ……加密…… → 进入连接板 → 显示为密文字母

对照我们刚才取得的字母循环圈，可整理为

T1 T2 T4

┌──┐ ┌──┐ ┌──┐

明 密 明 密 明 密

文 文 文 文 文 文

┌→ W → E → E → T → T → W ─┐

│ │

└────←──────←────┘

化简一下，只考虑图灵机的串联关系时，就可以表示为

┌ T1 → T2 → T4 →┐

│ │

└──←───←──┘

对第一台图灵机T1而言，输入W，输出E，可以记录如下：

T1：W → 进入连接板 → 加密 → 进入连接板 → E

对第二台图灵机T2，以及第三台图灵机T4，则有

T2：E → 进入连接板 → 加密 → 进入连接板 → T

T4：T → 进入连接板 → 加密 → 进入连接板 → W

对T1而言，输入字母进入连接板后，立即被连接板交换加密过一次，我们不知道是什么字母，记为C1；尔后又两次经过转轮组和输入轮加密，在即将回到连接板时，究竟变换成了哪一个字母，我们也还是不知道，于是把它记为C2。

则完整过程是：

T1：W → 进入连接板 → C1 → 加密 → C2 → 进入连接板 → E

以这个思路，把三台图灵机T1、T2、T4串联，相应地把T2内的未知加密字母记做C3、C4，而T4内的未知加密字母记做C5、C6，则可以整理为

┌─ T1：W → 进入连接板 → C1 → 加密 → C2 → 进入连接板 → E ─┐

│ │

│┌──────────←───────────←─────────┘

││

│└ T2：E → 进入连接板 → C3 → 加密 → C4 → 进入连接板 → T ─┐

│ │

│┌──────────←───────────←─────────┘

││

│└ T4：T → 进入连接板 → C5 → 加密 → C6 → 进入连接板 → W ─┐

│ │

└───────────←───────────←─────────┘

仔细看上面这张表，有什么问题么？

好像没有……？

也建议大家不要着急看后面的分析，不妨自己思索一下，看看里面到底有什么问题？提示：连接板设置，肯定是不变的。。

好，我们继续分析吧。

无论T1、T2还是T4，它们都是针对发布同一电文的ENIGMA的不同步骤进行模拟的，所以，这三台图灵机的连接板设置必然是相同的；进而，所谓的C1、C2、C3、C4、C5、C6，也就是那些我们还不知道的字母，是可以拿来做文章的！

现在，就让我们从第一行的C2看起吧。在T1中，C2经过连接板两两交换，被交换成了E；那么在T2中，输入E，经过同样设置的连接板交换，当然会被还原成C2——这就是说，C2 = C3。

同样地，在T2中，C4进入连接板被交换成T，在T4中，T又被交换成C5——因此，C4 = C5。

再来——在T4中，C6被交换成了W，而W在T1中被交换成了C1——因此，C6 = C1。

以上几个结论，又有什么意义呢？

让我们仔细看这张表，为了清楚起见，我们把每次涉及到的连接板编上流水号，虽然它们其实都是同一块板子：

K1 K2

┌─ T1：W → 进入连接板 → C1 → 加密 → C2 → 进入连接板 → E ─┐

│ │

│┌──────────←───────────←─────────┘

││ K3 K4

│└ T2：E → 进入连接板 → C3 → 加密 → C4 → 进入连接板 → T ─┐

│ │

│┌──────────←───────────←─────────┘

││ K5 K6

│└ T4：T → 进入连接板 → C5 → 加密 → C6 → 进入连接板 → W ─┐

│ │

└───────────←───────────←─────────┘

根据上文的结论，C2 = C3，这就意味着C2可以直接替代C3的位置，而C2和C3之间要经过两次连接板，即K2和K3，现在可以被忽略掉了；

由于C4 = C5，同样道理，K4和K5也可以被忽略掉了；

由于C6 = C1，K6和K1也被忽略了。

其效果，大致如下图：

同样颜色的标志，两两一组，互相抵消

顺便发句牢骚：这是文本的原样。西西的行距太宽，所有竖线都成虚线了

至此，三台图灵机里的连接板被全部屏蔽掉了——而这，又意味着什么？

它只意味着一件事：

构造好了字母循环圈以后，ENIGMA那令人挠头的连接板，现在已经是废物一块了！

回想波兰人雷杰文斯基，为了清除掉连接板的影响，辛苦构造了群论方程；而现在，图灵只用几台串联起来的机器就达到了同样的目的，并且消解的漂漂亮亮——虽然字母循环圈方法是波兰人发明的，但是在去除连接板方面，图灵实在是要高明得多！

• 1001n的《密码传奇》系列网址