5.5.5 经典密码分析方法

密码分析研究的目的是不知道密钥而由密文产生关于对应的明文的最优信息. 这些分析仅对于非法 “窃听者” 有意义, 但从使用者的观点看也有助于获取密码体制的安全性.

5.5.5.1 统计分析

每个自然语言显示特定字母、两个字母组合、字等的典型频率分布. 例如, 在英语中字母 e 以最高的频率使用:

字母:	相对频率
E	12.7%
$\mathrm{T},\mathrm{A},\mathrm{O},\mathrm{I},\mathrm{N},\mathrm{S},\mathrm{H},\mathrm{R}$	56.9%
D, L	8.3%
$\mathrm{C},\mathrm{U},\mathrm{M},\mathrm{W},\mathrm{F},\mathrm{G},\mathrm{Y},\mathrm{P},\mathrm{B}$	19.9%
V, K, J, X, Q, Z	2.2%

如果给出足够长的的密文, 那么就有可能根据字母的频率分布破译单字母的单一密码代换.

5.5.5.2 Kasiski-Friedmann 测试

将 Kasiski 和 Friedmann 的方法相结合有可能破译 Vigenère 密码. 攻击得益于加密算法周期性地应用密钥的事实. 如果相同的明文字母串被密钥的同一部分加密,那么将产生相同的密文字母串. 密文中这种相同的串相隔距离的长度 $>2$ 必然是密码长度的倍数. 在几个重复出现的密文串的情形密码长度是所有距离的最大公因子的某个因子. 这种论述称为 Kasiski 测试. 但是我们应该意识到由于可以偶然地出现匹配而产生错误结论的可能性.

Kasiski 测试可使我们确定密钥长度至多是真实密钥长度的倍数. Friedmann 测试则产生密钥长度的数量. 设 $n$ 是某个英文明文用 Vigenère 方法加密得到的密码的长度. 那么密钥长度 $l$ 由

$$\begin{array}{}\text{(5.275a)}& l=\frac{0.027n}{\left(n-1\right)\mathrm{IC}-0.038n+0.065}\end{array}$$

确定,其中 IC 表示密文的重合指标. 这个指标可以从字母 $a_i\left(i\in \{0,1,\cdots ,25\}\right)$ 在密文中出现的次数 $n_i$ 推出

$$\begin{array}{}\text{(5.275b)}& \mathrm{IC}=\frac{\sum _{i=1}^{26}{n}_i\left(n_i-1\right)}{n\left(n-1\right)}.\end{array}$$

为确定密钥,长度为 $n$ 的密文被分裂为 $l$ 个列. 因为 Vigenère 密码借助移位密码产生每个列的分量,所以只需确定 $\mathrm{E}$ 在列基上的等价性. 如果 $\mathrm{V}$ 是在列中最频繁出现的字母, 那么 Vigenère 表将指出密钥的字母 R:(5.275c)

如果 Vigenère 密码使用非常长的密钥 (例如, 与明文一样长), 那么所说的方法迄今都未获成功. 但是, 它有可能推断应用的密码是否为单一字母的、短周期多字母的或长周期多字母的.