1

昵称865028 2013-03-07

展开全文

被征服的谜——ENIGMA的故事（一）

ENIGMA在密码学界里，绝对是划时代的丰碑。而且，还不是一座丰碑，而是两座：研究并制造ENIGMA是一座，研究并破解ENIGMA又是一座。

稍微看看ENIGMA的历史，任何人都会因其中透出的人类智慧之美而折服。如果要向这样辉煌的智慧敬献花环的话，那么主要的应该献给三个人：

首先是德国人亚瑟·谢尔比乌斯（Arthur Scherbius）；其次是波兰人马里安·雷杰夫斯基（Marian Rejewski）；第三个就是英国人阿兰·图灵（Alan Turing）。

这三个人中，德国人发明了ENIGMA；波兰人初步解破了简单的ENIGMA；而英国人彻底终结了最高难的ENIGMA。

顺着时间的主轴，先从德国人亚瑟·谢尔比乌斯说起。

（一）密码的前世

一战终于结束了，时间转眼就跨入了1918年。而在这一年，密码学界的一件大事“终于”发生了：在德国人亚瑟·谢尔比乌斯天才的努力下，第一台非手工编码的密码机——ENIGMA横空出世了！

说是终于发生，也是因为确实有点奇怪。在工业革命浪潮席卷欧洲那么多年以后，天上有了飞机，地上有了坦克，海里有了潜艇，甚至连毒气都上了战场的情况下，密码学的发展竟然不可思议地始终是停滞的——千百年来人们用来加密文件的办法，竟然还是手工操作！

此外，加密的方式也受到了重大的挑战，简单的明文字母替换法已经被频率分析法毫无难度地破解了，曾经认为是完美的维吉耐尔（Vigenere）密码和它的变种也被英国人Charles Babbage破解了。顺便说一句，这个Charles Babbage可不是凡人，他设计了差分机Difference Engine和分析机Analytical Engine，而这东西就是现在计算机的先驱。而他老人家（1792～1871）可是19世纪的人！

扯远一点，先说说这个加密的方式。一般来说，把明文里的文字用其它字母替换，可以达到无法直接识别的目的。具体操作起来，当时流行的操作有这么几种：

1、每个字母都用其它固定的字母代替，比如A换成T，也就是一对一对应的单字替换法；

2、用多个字母替代一个字母，比如A换成TVW，也就是多对一的多名码替换法；

3、几个字母成为固定组合，被另外的固定组合代替，比如AQUA换成EDDTYM，也就是多对多的字母替换法；

4、每次用不同的字母替换同一字母，比如A换成T，下次则A换成U，比如AQUA换成TWCU，也就是不断变换的多表替换法。

首先说说这个单字替换法。

我们可以自己拟定一个规则，比如说，CODE一词的字母C、O、D、E，分别被替换成A、K、L、Y。而根据同一法则，DECODE就应该成为LYAKLY。猛一看到LYAKLY，一般人是得发晕，不知道这说的是什么。但是，数学家不是一般人，他们统计了相当数量的文本以后，发明了频率分析法，专门对付这个单字替换法。

列个简单的单子，看看频率分析法是怎么破解单字替换法的：

A 0.082 | B 0.015 | C 0.028 | D 0.043 | E 0.127 | F 0.022 | G 0.020……| T 0.091 | ……| Z 0.001

其中，字母后面跟着的数字代表它在文本中出现的统计频率。可以看出，什么字母出现概率最大？毫无疑问就是e。管你怎么替换，这个字母不会是别的。分析相当数量的根据同一法则替换之后的密文，完全可以轻松将每个字母的去向一一标明，进而，也就无密可保了。

看上去更象个小聪明的单字替换法就这么可耻地失败了。而类似地，多名码替换法、字母替换法这些加密方式一样无法逃避频率分析的威力，也跟着纷纷被拿下了。但是多名码替换法却还有人在用，直到一战中，英国人还在用这个明显不可靠的加密方式，原因为何，真是只有鬼知道了。

而最后一种，也就是多表替换法，却一跃成为了一时的主宰。

多表替换法好就好在，它的明文和密文之间的字母对应是会变的。这个“变”字，就成为密码学上一个非常成功的概念。甚至后来的ENIGMA，成功也就成功在这个变字上。

1568年Leon Battista首先发明了多表替换法，之后美国内战期间，北军用的就是这个加密方法。1858年，法国的外交官Blaise De Vigenère发明了另一套以他名字命名的Vigenère密码，从Vigenère密码里又衍生出了Beaufort密码，等等。

从原理上看，无论Battista、Vigenère和Beaufort等多表替换密码，其实都只是一个范畴的不同表现而已。而数学家所使用的频率分析法失灵的原因就是，每次变的那一下子，使密文完全不符合字母出现频率的规则了。

它的原理简单描述一下，大概是这个样子（不是很严密的）：第一次对A加密的时候，出来T；下次再碰上A，按照某种顺序，比如最简单的递加顺序，则顺延T+1，变成U；第三次再碰上A，继续顺延成T+2，变成V。

于是，初始位置不知道，还可以用频率分析予以破解；但是顺延之后，频率分析就无能为力了。何况，谁知道是递加还是递减呢？谁知道是加几或者减几呢？以及，对手万一不用递加或递减，而是采用乘法除法，或者利用某个数列，比如素数数列来加密呢？而Vigenère法恰恰用的不是顺延，而是任意一组指定的数列！

这样一来，似乎无法破解的多表替代加密法就成为了密码之王。

但是，既然有人能发明，总有人能找到它的弱点。数学家又出现了！

还以多表法中最著名的Vigenère法来说。按当时的习惯，Vigenère法是这样加密明文的：

明文：ABCDEFGHIJK

密钥：3，2，6，8，1，4（表示字母向后顺延的位数）

则密文应该变为：A+3，B+2，C+6，D+8，E+1，F+4，（密钥用尽，从头开始重复加密）G+3，H+2，I+6，J+8，K+1，也就是：DDJLFJJJOQL一次标准的加密就完成了。如果要解密，就需要知道密钥，然后倒着推算回去就是了。

从刚才的例子可以看出，密文DDJLFJJJOQL里面出现了4个J（我倒，真是随手一写，没想到搞成这样），2个D，2个L，而这些所对应的明文竟然是没有重复的ABCDEFGHIJK……Vigenère法的厉害可见一斑！

但是牛人出现了。上文说过，1858年，法国人Blaise De Vigenère发明了Vigenère多表替换法。而之后仅仅五年，普鲁士的一个少校军官，F.Kasiski找到了破解的办法！顺便说一句，又过了七年，普法战争就开始了……

说起具体的破解方法，的确就是个纯粹的数学问题了，我这人，天生不擅长数学，就不具体写了——因为也写不出来，写出来也是别人的，自己看不懂：（但是，可以描述一下它的原理，那就是：密钥因为种种原因，是循环使用的。上文例子中，用了六位密钥，也就是说，每六个字母，就要循环使用一次相同的密钥加密——破绽就在这里！

实际上，除非你用的多表替换的密钥无限长，那么自然无法破解——稍微想想就明白了，那相当于你发明了另外一门使用相同字母的语言啊——但是，密钥是不可能无限长的，特别是在手工操作加密和解密的时代。例如，怎么能够想像，战火纷飞的战场上，解码员手里拿着厚厚一千多页的密钥去一个个查对字母——太长了，也容易出错啊！

当时在实际应用中，密钥一般是二十位左右长。这样，就取得了一个便用性和保密性的平衡。但是，二十位的密钥，还是太短了——在数学家眼里，这相当于把彩票要选的数字从36个降到只选5个，于是，中奖的概率大大增加了。

他们用的办法还是分析。这次，主要是分析密钥的长度，换言之，是经过多少次加密以后会出现循环现象。具体算法就不罗列了，很精彩，这里只给出一个理想情况下的结果：

如果密钥字长度为M，那么密文中随机两个字母的重合指数约为0.065（也就是说，比如我挑密文中的字母A，它对应的明文恰好也是字母A的重合指数是0.065）;