密码学（二）：古典密码之维吉尼亚密码的破解

维吉尼亚密码的破解

一、引言

上一章我们介绍了维吉尼亚密码的原理，是通过移位替换的加密方法进行加密，但是因为概率论的出现这种简单的移位或替换就容易破解了，其原理很简单，英文中字母出现的频率是不一样的。比如字母 e 是出现频率最高的，占12.7%；其次是t，9.1%；然后是a，o，i，n等，最少的是z，只占0.1%。 具体概率表

除了英语，其他语言也有相关统计（图片来源）

二、一般破解的方法

1. 穷举密钥搜索

只适用于与小的密钥空间，而像维吉尼亚密码的 Z 26 n Z^n_{26} Z26n​ 是 26 的 n 次方的空间，当 n 很大时，计算量是相当大的。

2. 频率统计

单表代换

移位密码： 相同的明文字母总是对应相同的密文字母，因此，尽管字母的外形改变了，他出现的概率还是不变的，只要根据足够多的样例来进行统计，最终密文字母的出现概率总是近似于明文字母的出现概率，并且与之一一对应。

多表代换

维吉尼亚密码： 相同的明文字母可能对应不同的密文字母，这里讲的维吉尼亚密码的破解也是根据字母出现的频率的蛛丝马迹进行破解。

三、维吉尼亚密码的破解

1. 确定密钥长度

方法一：Kasiski测试法

原理：密文中出现两个相同字母组，它们所对应的明文字母相同的可能性很大，这样的两个密文字母组之间的距离可能为密钥长度的整数倍。 尽管在维吉尼亚密码中相同的明文可能对应不同的密文，但是若连续出现相同的密文，那么用同样的密钥加密的概率会大大增加。这里密文 Z B ZB ZB 都是用 H I HI HI 加密，计算两者之间的距离为 5 5 5，因此可推断出来密钥长度为 5. 5. 5.

方法二：重合指数法

原理：自然语言（以英语为例）的重合指数约为 0.065，而且单标代换不会改变该值。 重合指数定义：

设 x = x 1 x 2 . . . x n x=x_1x_2...x_n x=x1​x2​...xn​ 是含有 n n n 个字母的串，则在 x x x 中随机选择两个元素且这两个元素相同的概率为：

定义： f i f_i fi​ 为 26 个字母中第 i i i 个字母在 x x x 中出现的次数

[例如： x = A A Z Z Z , n = 5 , f 0 = 2 , f 25 = 3 x=AAZZZ,n=5,f_0=2,f_{25}=3 x=AAZZZ,n=5,f0​=2,f25​=3，第一次取出 A 的概率为 f 0 n \frac {f_0}{n} nf0​​，第二次再取出 A 的概率为 f 0 n ∗ f 0 − 1 n − 1 \frac {f_0}{n} * \frac {f_0-1}{n-1} nf0​​∗n−1f0​−1​]

当我们把 26 个字母的概率全部相加，得到的总的概率就是重合指数： I c ( x ) = ∑ i = 0 25 f i ( f i − 1 ) n ( n − 1 ) I_c(x)={\frac {\displaystyle\sum_{i=0}^{25}f_i(f_i-1)}{n(n-1)}} Ic​(x)=n(n−1)i=0∑25​fi​(fi​−1)​ 当计算的数量很大时，我们将 n ( n − 1 ) n(n-1) n(n−1) 近似为 n 2 n^2 n2，将 f i ( f i − 1 ) f_i(f_i-1) fi​(fi​−1) 近似为 f i 2 f_i^2 fi2​

因此 I c ( x ) ≈ ∑ i = 0 25 p i 2 ≈ 0.065 I_c(x) \approx \displaystyle\sum_{i=0}^{25}{p_i^2} \approx0.065 Ic​(x)≈i=0∑25​pi2​≈0.065 这里的 p i p_i pi​