凯撒密码

作为一名杰出的军事领袖，尤里乌斯•凯撒深知指挥官对前方将领的命令对于一场战争的重要性，这些信息绝对不能让敌方知道，于是他设计了一种对重要的军事信息进行加密的方法，即使这些信息被截获，敌方也不一定能看懂——这就是著名的凯撒密码，也算是最早的密码实例。

在这种密码中，从A到W的每个字母在加密时用字母表中位于后三位的那个字母代替，字母XYZ分别被替换成ABC。凯撒在这里是将字母向右移动了三位（如下图）。比如，在三个移位的情况下，信息DOG（这种需要加密的信息统称“明文”）就变换成GRJ（这种经加密后产生的的信息统称“密文”）；密文FDW对应的明文则是CAT。可以看到，加密、解密过程都是以字母移位的位数为参照的。这种在加密和解密的算法中依赖的参数则被称为——密钥。

当然，移位的选择并不仅仅限制在三位，从1到25任何数的移位都能产生类似效果。只要通信双方事先约定好，这个选择就很任意。很明显的是，移位方法最多也只有25种，这成为凯撒密码的致命弱点。一般情况下，穷举25种移位方法，得到25组新编码，必有一种编码是真实的情报内容，由于其它24组多是是毫无意义的字母组合，所以凯撒密码很容易就能被破译。

但是凯撒在当时很成功的使用了这种密码，还在《高卢战记》中颇为得意的记录下了这个加密设计。究其原因，只能是他的敌人并没有意识到他在使用密码。

改进后的加密法

在凯撒密码的缺点暴露后，有人便对它做出了改进：用一个按随机顺序排列的字母表来替代正常顺序的字母表。这种简单代换方法达26！种，这个看起来不大的数字，数量级达到了10 ²⁶ ，也就是说穷举法破译已经失效了。但是，这种方法并非无懈可击，当它对一段比较长的英文信息加密时，依然容易被破译。这是英语本身的统计特性决定的。

众所周知，英语具有统计特性。每个字母的使用频率不同且差别很大。一篇文章中字母出现的相对预期频率是可以通过统计大量英语文章确定出来的。比如，英语文章中 E 的出现频率最高，大约是 12.7% 这样子；而 J 的出现频率最低，只有 0.1% 左右。当使用上述的简单代换密码时，字母表中特定字母总是被同一个字母代替，导致密文中字母出现的频率也会出现同样的不平衡性，再加上破译者对发密方背景的了解，要确定密文中包含的信息依然不是一件困难的事。

一个好的解决办法是用多个密文符号来表示同一个字母。每个字母有不同数量的的密文符号替代，替代者的数量与每个字母在英语统计中的频率成正比。例如，字母 a 在书面英语大约占 8% 的比例，所以我们可以分配8个符号来表示它。明文中出现的字母 a 在密文中可以被这8个符号中任一个替换。这样一来，每个符号在密文中的频率都在 1% 左右。类似处理所有英文字母。这样设计出的一套字母替换表，打乱了密文中的英语统计特性。但由于每个密文符号只代表唯一的明文符号，也会带来风险：对于一个给定的密钥，破译者能汇编出一部已知的明文与密文相对应的词典。

好几个世纪以来，上述的几种加密法保证了信息的安全。不过自从频度分析这种方法被引进到欧洲后，密码破译者终于占据了上风。苏格兰玛丽女王的悲剧充分诠释了这种密码的弱点。

“不可破译”的密码

1586年，英国政府破译了苏格兰玛丽女王和同党谋反的密信，玛丽女王惨遭吊死。而她使用的就是字母替换这种单码加密法。这个事件也正式宣告上述密码已经全部失效。

同年，一位名叫维热纳尔的法国外交家出版了一本《密码理论》，介绍一种以他自己名字命名的新密码，而这本书一直无人问津。直到两百年后莫尔斯电码流行开来，为了防止电报员泄露信息和间谍窥探秘密，维热纳尔密码才被广泛应用。

维热纳尔密码一度被认为是无法破译的，以致让一些掌握这种密码的人洋洋自喜，不过很快，以建立了现代计算机的理论框架而闻名于世的怪才查尔斯•巴贝奇解决了这个难题。

事情起源于一个布里斯托尔的一个牙医赛瓦特。这个牙医其实对密码学知之甚少，1854年，他声称发明了一种新密码，并写信给《艺术协会杂志》企图获取专利。而他只不过是将维热纳尔密码重新包装了而已。巴贝奇写信揭露这个事实，赛维特却不愿承认，甚至为难巴贝奇让他破解这个密码。其实能否破解密码和密码是不是新创造的毫无关系，但这已足以激起巴贝奇的好奇心了。很快，他就成功破解了维热纳尔密码。

对于这样重要的成果，巴贝奇却没有发表它。这也符合他的性格：他一直是这种懒洋洋的态度。而更重要的原因恐怕是英国政府要求巴贝奇保密，从而让他们可以在这方面领先全世界9年——直到1863年卡西斯基也发现了破译方法并将它发表。

有趣的是，在美国的南北战争期间，南方联军仍然在使用黄铜密码盘生成维热纳尔密码，自始至终都只主要使用三个密钥，而那个时候这密码早就被破译了，所以北方政府在情报战上一直是笑而不语的。

维热纳尔密码的原理

维热纳尔密码又叫做维吉尼亚密码。它的加密过程是这样的：首先选择一个无重复字母的密钥词（比如 MATH ），重复密钥词直至它成为一个和明文信息一样长的字母序列，再利用下面这种方阵加密这条信息。为加密第一个字母 I，此时它下方对应的密钥词是 M，于是，加密 I 时由 M 对应的那行中读出 i 列下的字母即 U，类似的，得出所有密文：

信息	I	L	O	V	E	Y	O	U
密钥	M	A	T	H	M	A	T	H
密文	U	L	H	C	Q	Y	H	B

这无疑是一种高明的加密手段，维热纳尔密码用严格的轮换方式重复使用一串简单的代换密码，很好的伪装了基础语言中的字母频率。它还有很多变化，比如有一种可以允许密钥词中出现重复字母。每种变化都会产生一些新的特征，从而引发破译方式的变化。

查尔斯•巴贝奇是破译维热纳尔密码的第一人，他的思路是：在已知密码周期（即所使用的密码组件数目，显然，上述版本的维热纳尔密码周期就是密钥词长度）为 p 的情况下，将密文改写成 p 行，使得每一列按原来的密文顺序排列，例如，p=3，密文 c1c2c3c4c5c6c7c8c9… 就排列成：

c1 c4 c7…

c2 c5 c8…

c3 c6 c9…

这样排列后，每行都是使用同一简单代换密码所得出的，如此就可以对每一行都使用上一节提到过的统计分析了。事实上，对每一行而言，这种简单的代换密码正是凯撒密码。

所以对于维热纳尔密码的破译者来说，关键就在于确定周期 p，巴贝奇则用了一种精巧的方法：在密文中搜索重复的字符串，它意味着两个重复模式之间的距离可能等于周期的整数倍！

难题又被破解！再一次，密码编译者开始寻找新的方法，继续这场智的较量。