一个数字与一串数字：凯撒密码和维吉尼亚密码的破译思路

刚入门密码学的时候，几乎都听过两个名字：凯撒密码和维吉尼亚密码。前者简单到用纸笔就能算，而后者在几百年里都被认为是「不可破译」的密码。它们之间其实存在一定的关系——维吉尼亚密码无非是把凯撒密码进行反复套用。本文接下来分别介绍这两种密码的原理以及其中的漏洞和破解思路。

1. 凯撒密码

先说凯撒。传说里，凯撒给部下写信时，会把每个字母在字母表上统一往后挪几位。用英文举例子，就是选一个整数 $k$（从 $0$ 到 $25$）：

比如 $k=3$ 时，A 变成 D，B 变成 E，到了末尾再绕回开头。罗马作家苏埃托尼乌斯写过凯撒用字母替换来通信；至于历史上是不是真这么干的，其实不太影响我们理解算法——后来大家就把这种「固定移位」叫做凯撒密码了。

凯撒密码属于单表替换：整段文字共用同一张明密对照表。所以明文里某个字母出现得多，密文里对应那个字母也会出现得多，频率分布几乎搬了个家。

如何破解凯撒密码？

可能的密钥其实就 25 种（$k=0$ 等于没加密）。最直接的办法是写个循环，从 $k=1$ 试到 $25$，看哪一次解出来的文字读得通。做 CTF 的时候，很多人第一反应也是穷举。

如果觉得一个个试有点慢，可以看字母频率。英语里 E、T、A、O 出现得最多，那就先看密文里哪个字母出现次数最高，假设它对应明文的 E，反推出 $k$，不对再换别的高频字母试。不过密文特别短、或者用词很怪的时候，频率不一定准，这种情况下还是穷举更靠谱。

2. 维吉尼亚密码

凯撒这种单表替换太容易被频率分析打掉了，所以后来出现了多表替换：明文的不同位置，用不同的替换表。

维吉尼亚密码的做法是：先选一个关键词，把关键词一遍遍重复，铺成和明文一样长的密钥流，再按位置做移位。比如关键词是 LEMON，明文是 ATTACKATDAWN，可以对齐写成：

明文：ATTACKATDAWN
密钥：LEMONLEMONLE

对应公式就是：

这样同一个明文 A，碰上密钥里不同的字母，会变成不同的密文字母。你就不能再简单地说「密文里出现最多的那个一定是 E」了。

这个加密算法常挂在 Blaise de Vigenère 名下（他 1586 年出过密码书）。不过教材里常见的「关键词循环」这一版，其实更接近意大利人乔万尼·贝拉索更早提出的设计；维吉尼亚本人还写过一种自动密钥的变体，规则更麻烦一点。历史上它有个外号叫 le chiffre indéchiffrable，意思是「不可破译的密码」，在欧洲风光了很久。有意思的是，一战时期还有部队在用它，而破解方法在十九世纪中叶就已经公开了。

3. 如何破解维吉尼亚密码？

破解时一般不要一上来就猜整个关键词，而是先估计关键词长度，记作 $m$。

一个常用办法是卡西斯基检验：在密文里找重复出现的字母片段，看看两段之间隔了多少个字母。这些间距，经常是关键词长度的倍数。多找几组间距，求它们的公约数，就能得到 $m$ 的候选值。查尔斯·巴贝奇更早用过类似思路，但没怎么公开；1863 年弗里德里希·卡西斯基写成书以后，这个方法才广为人知。

假如已经认定 $m=3$，就把密文按位置拆成 3 组：

• 第 1、4、7、10… 个字母一组

• 第 2、5、8、11… 个字母一组

• 第 3、6、9、12… 个字母一组

每一组内部，其实都是在用同一个移位，也就是一次凯撒密码。对每一组再做频率分析或穷举，得到 3 个移位，拼起来就是关键词。

另外还可以用弗里德曼提出的重合指数来估计 $m$：猜对长度的时候，各组的统计特征会更接近自然语言。密文比较长、关键词又不太长时，这些方法通常都够用；如果密文很短，就只能多试几个可能的 $m$。

4. 两者差在哪里？

所以维吉尼亚并不是完全另一类东西，它主要是把「一个移位」变成了「按周期变化的一串移位」。现代密码后面走的是扩散、混淆、以及计算上难解的问题，那是另一条发展线。看古典密码时，我的提醒是：先别急着相信「不可破译」这种说法，看看明文的统计规律在密文里还剩多少。

如果想自己动手感受一下，可以先用 $k=3$ 做一遍凯撒；再用关键词 LEMON 加密一句英文；最后在密文里找重复片段，数一数间距。走完这三步，前面的公式会好记很多。