8.1　经典密码学简史

秘密消息的历史和人们传递消息的历史一样久远。朱利叶斯·凯撒使用过一个简单的替换加密算法，即将每个字母替换为它在字母表位置往后数第三个位置的字母。

The early bird gets the worm（早起的鸟儿有虫吃）就变成了Wkh hduob elug jhwv wkh zrup。这种字母替换的加密方法被称为凯撒密码。

图8-1　凯撒密码

这种技术在古罗马非常好用，加过密的消息看起来像是胡言乱语，而那时人们有限的技术还无法破译这种密码。到了公元9世纪，数学家发现了通过统计字母和短字的频率来破解密码的方法。我们来看Wkh hduob elug jhwv wkh zrup，注意其中字母h出现了4次，比其他字母都多。英语中出现频率最高的字母是e，所以可以（正确地）推测h代表e。然后注意到Wkh出现了2次，而如果h代表e，那么可以推测Wkh代表the。按此方法，很快就能破译这条消息。

在15世纪的意大利文艺复兴时期，莱昂·巴蒂斯塔·阿尔伯蒂创造了一种更为复杂的加密方法，称为多字母加密法（polyalphabetic cipher），对消息的不同部分使用不同的替换规则。这些密码在很长一段时间内都无法被破解，直到19世纪人们发展出了更系统化的密码破译方法。

作家兼诗人埃德加·爱伦·坡也对密码分析颇有研究。1839年他公开征集难以破译的密码，以供他研究密码破译的方法。一年后，爱伦·坡发表了一篇名为“谈谈秘密写作”（A Few Words on Secret Writing）的文章，他在其中声称“人类的创造力无法创造自身不能破译的密码”。他在1843年的小说《金甲虫》（The Gold-Bug）中就有破译密码的情节，它属于第一批描述密码的小说。

1903年亚瑟·柯南·道尔发表了《跳舞的小人》（The Adventure of the Dancing Man），这本小说讲述了歇洛克·福尔摩斯如何破译一个由火柴棍小人构成的替换密码。

图8-2　跳舞的小人

随着机械时代的到来，出现了一批加密和解密消息的机器设备。其中最知名的可能要数恩尼格玛密码机（Enigma machine），是德国人亚瑟·谢尔比乌斯在1918年发明的。

恩尼格玛密码机有数个转子，在打字过程中，这些转子将字母替换成其他的字母。由于每个转子的转速不同，每一个字母具有不同的替换规则。这个机器可以看做是阿尔伯蒂的多字母加密法的一个更复杂的版本，用它加密的消息非常难以破译。

图8-3　恩尼格玛密码机

恩尼格玛密码机是第二次世界大战中德军使用的主要密码来源。在开战之前，波兰军事情报机构向英国提供了该机器的描述和一些破译技术。英国政府随即启动了一项代号为“超级”（Ultra）的计划来破解密码。征募的研究人员有纵横填字和国际象棋高手，也有大数学家，其中包括计算学之父阿兰·图灵。第一台可编程电子计算机“巨人”（Colossus）就是在计划的实施过程中诞生的。温斯顿·丘吉尔曾说：“是‘超级’计划让我们赢得了战争。”

密码学从诞生以来都是（而且将来也是）一场猫鼠游戏，即密码制造者和密码破译者双方的斗智斗勇。但是在20世纪70年代，随着计算机科学家开始构造基于难以求解的NP问题的加密方法，这个游戏的格局发生了重大变化。