Skip to content

Vigenère Cipher

维吉尼亚密码使用一个长度为 mm 的密钥来对明文进行加密。其中明文也被分为许多组,每一组长度为 mm 。对于每一组中的字符 PiP_i, 其加密的方法为:

CiPi+Ki(mod26) C_i\equiv P_i + K_i \pmod {26}

解密方法为:

PiCi+Ki(mod26) P_i\equiv C_i + K_i \pmod {26}

密码分析

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

Kasiski 试验

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

δ0(modm) \delta\equiv 0 \pmod{m}

而如果有多个相同的密文段,那么可以猜测 mmδi\delta_i 最大公因子的因子(即所有 δi\delta_i 的因子)

Friedman 试验

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

Ic(x)=i=025fi(fi1)n(n1) I_c(\boldsymbol{x}) = \frac{\sum_{i=0}^{25}f_i(f_i-1)}{n(n-1)}

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

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

Ic(x)=i=025pi20.065 I_c(\boldsymbol{x}) = \sum_{i=0}^{25}p_i^2\approx0.065

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

y1=y1ym+1ym+2y2=y2ym+2ym+3ym=ymy2my3m \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}

mm 为密钥长度,则每一组的重合指数应当接近于 0.065。而如果是随机的字符串,重合指数近似于:

Ic26(126)2=1260.038 I_c\approx 26\left(\frac{1}{26}\right)^2=\frac{1}{26}\approx0.038

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

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

Mg=i=025pifi+gn M_g = \sum_{i=0}^{25}p_i\frac{f_{i+g}}{n'}

若密钥正确,则 MgM_g 应当接近于 0.065。

Comments