Vigenère Cipher

维吉尼亚密码使用一个长度为 \(m\) 的密钥来对明文进行加密。其中明文也被分为许多组，每一组长度为 \(m\) 。对于每一组中的字符 \(P_i\), 其加密的方法为：

\[ C_i\equiv P_i + K_i \pmod {26} \]

解密方法为：

\[ P_i\equiv C_i + K_i \pmod {26} \]

密码分析

简单的代换密码可以通过频率分析实现，但是直接的频率分析并不适用于此。但是仍然可以通过不同的特征对密码进行破译。

Kasiski 试验

Kasiski 试验基于一个事实：如果两个相同的明文加密为相同密文段，那么他们的间距 \(\delta\) 满足：

\[ \delta\equiv 0 \pmod{m} \]

而如果有多个相同的密文段，那么可以猜测 \(m\) 为 \(\delta_i\) 最大公因子的因子（即所有 \(\delta_i\) 的因子）

Friedman 试验

Kasiski 试验可以猜测 \(m\) 的值，而 Friedman 试验则可以更准确地确定 \(m\)。Friedman 试验利用重合指数（Index of Coincidence）来描述字母频率出现的随机性。假设一个文本中字符长度为 \(n\)，每个字母出现的频数为 \(f_0, f_1,\cdots,f_25\)，则定义重合指数为：

\[ I_c(\boldsymbol{x}) = \frac{\sum_{i=0}^{25}f_i(f_i-1)}{n(n-1)} \]

重合指数可以表示字符串中两个随机元素相同的概率。

由于英语文本中字母出现的频率是相对固定的，所以一个英语文本串的重合指数可以近似计算出来：

\[ I_c(\boldsymbol{x}) = \sum_{i=0}^{25}p_i^2\approx0.065 \]

直接使用单表代换的密码并不会使得重合指数发生变化。所以可以将密文进行分组：

\[ \begin{aligned} \boldsymbol{y}_1 =& y_1y_{m+1}y_{m+2} &\cdots \\ \boldsymbol{y}_2 =& y_2y_{m+2}y_{m+3} &\cdots \\ & \vdots \\ \boldsymbol{y}_m =& y_my_{2m}y_{3m} &\cdots \end{aligned} \]

若 \(m\) 为密钥长度，则每一组的重合指数应当接近于 0.065。而如果是随机的字符串，重合指数近似于：

\[ I_c\approx 26\left(\frac{1}{26}\right)^2=\frac{1}{26}\approx0.038 \]

通过这一方法可以更准确确定密钥的长度。

在确定密钥长度之后需要确定每一组的密钥 \(g\)，这同样可以通过计算（类似的）重合指数来实现。对于某一组，设其长度为 \(n'\)，\(f_i\) 为某一个字母出现的频数，对于明文 \(i\)，其加密之后对应下标为 \(i+g\)。可以与重合指数类似地定义数值：

\[ M_g = \sum_{i=0}^{25}p_i\frac{f_{i+g}}{n'} \]

若密钥正确，则 \(M_g\) 应当接近于 0.065。

Comments