密码学引论 维吉尼亚密码分析

确定密钥长度

采用自然语言的一些统计特征，比如重合指数，自然语言（英语）的重合指数约位 0.065，且单表代换不会改变该值。

重合指数的定义：

设x=x1x2…xn是含有n个字母的串，则再 x 中随机选择两个元素，且这两个元素相同的概率为：

(x[i] * (x[i] - 1)) / (length * (length - 1))

其中 x[i] 是第 i 个字母出现的次数，length 就是 x 的长度。

自然重合指数就是 26 个字母重复次数的和，即：

for i in range(26):
    Ic += (n[i] * (n[i] - 1)) / (length * (length - 1))

在这个前提下，假设密钥长度为 d，提取相同密钥字加密的密文。测试其重合指数，因为单表代换不会改变重合指数，而对应相同密钥字加密的密文就相当于做的单表置换，因此如果枚举的长度正好是密钥长度 d 或 d 的倍数，那么其重合知乎值接近 0.065，否则，字符串表现得更为随机，一般在0.038（1/26）～0.065之间。

按位确定密钥字

在确定密钥长度后，将密文分成 key_len 个组，按位确定密钥。

考虑一个问题，自然语言的重合指数的计算方法，可以是：

for i in range(26):
    Ic += (x[i] / length_x) * F[i]

其中 x 是一段自然语言的字符串，F[i] 是统计学中的字母频率，自然语言的这个重合指数应该是接近 0.065。

但是相同密钥字加密的密文的重合指数却不是接近 0.065，为什么？因为对一个经过单表替换后的字符串，统计学中的字母频率 F[i] 是会发生改变的，而这种改变恰好就是每一组的单个密钥加密的结果（加密导致偏移）。那么，如果这一步枚举这个偏移（<26），找到那个偏移后再计算的重合指数最接近 0.065，那就能确定这一位的密钥了。

补充思考

老师课上讲的是在确定密钥长度后，通过计算不同组之前的重合互指数，来确定密钥字的相对位移，从而得到一组不同密钥相对位移的多项式，然后通过枚举其中一个密钥字，就可以利用这组多项式求解出其他的密钥字，最后用统计学的方法确定解密后的明文是否符合条件。

本文中的按位枚举实际上是在枚举密钥的过程中，直接计算了当前相同密钥字加密的密文和自然语言的重合互指数。和老师讲的方法相比，忽略了不同密钥字直接相对位移的关系，失去了密钥字之间关系的约束性，所以解出的密钥可能存在误差。但在密文足够长的前提下，这种误差也会不断减小进而可以忽略。

代码实现

没得发，会被抄实验报告。