Vigenère Cipher
维吉尼亚密码使用一个长度为 m 的密钥来对明文进行加密。其中明文也被分为许多组,每一组长度为 m 。对于每一组中的字符 Pi, 其加密的方法为:
Ci≡Pi+Ki(mod26)
解密方法为:
Pi≡Ci+Ki(mod26)
密码分析
简单的代换密码可以通过频率分析实现,但是直接的频率分析并不适用于此。但是仍然可以通过不同的特征对密码进行破译。
Kasiski 试验
Kasiski 试验基于一个事实:如果两个相同的明文加密为相同密文段,那么他们的间距 δ 满足:
δ≡0(modm)
而如果有多个相同的密文段,那么可以猜测 m 为 δi 最大公因子的因子(即所有 δi 的因子)
Friedman 试验
Kasiski 试验可以猜测 m 的值,而 Friedman 试验则可以更准确地确定 m。Friedman 试验利用重合指数(Index of Coincidence)来描述字母频率出现的随机性。假设一个文本中字符长度为 n,每个字母出现的频数为 f0,f1,⋯,f25,则定义重合指数为:
Ic(x)=n(n−1)∑i=025fi(fi−1)
重合指数可以表示字符串中两个随机元素相同的概率。
由于英语文本中字母出现的频率是相对固定的,所以一个英语文本串的重合指数可以近似计算出来:
Ic(x)=i=0∑25pi2≈0.065
直接使用单表代换的密码并不会使得重合指数发生变化。所以可以将密文进行分组:
y1=y2=ym=y1ym+1ym+2y2ym+2ym+3⋮ymy2my3m⋯⋯⋯
若 m 为密钥长度,则每一组的重合指数应当接近于 0.065。而如果是随机的字符串,重合指数近似于:
Ic≈26(261)2=261≈0.038
通过这一方法可以更准确确定密钥的长度。
在确定密钥长度之后需要确定每一组的密钥 g,这同样可以通过计算(类似的)重合指数来实现。对于某一组,设其长度为 n′,fi 为某一个字母出现的频数,对于明文 i,其加密之后对应下标为 i+g。可以与重合指数类似地定义数值:
Mg=i=0∑25pin′fi+g
若密钥正确,则 Mg 应当接近于 0.065。