好久没学东西了咕咕咕,趁着ATSAST开始前学点东西。

维吉尼亚密码

$P$,$C$和$K$分别为明文空间、密文空间和密匙空间,且有 $P=K=C=(Z_{26})^m,\quad m\in Z$,$m$为密匙长度,密匙$k=(k_1,k_2,\cdots ,k_m)$。
定义加解密函数为:
$$
\begin{cases} e_k(x_1,x_2,\cdots,x_m)=(x_1+k_1,x_2+k_2,\cdots,x_m+k_m)\ d_k(y_1,y_2,\cdots,y_m)=(y_1-k_1,y_2-k_2,\cdots,y_m-k_m) \end{cases}
$$
当明文长度长于密匙时,将明文按长度为$m$分组,然后对每一组使用密匙$k$加密。

分析

分析主要分为三步:确定密匙长度、确定密匙、恢复出明文

确定密匙长度

实际应用中常先用Kasiski测试法初步确定密匙长度,然后用重合指数法校验。

Kasiski测试法

该方法的基本原理是:对于长度为$k$的密匙,当明文中有两个字母在明文序列中间隔的字母数为$k$的倍数时,这两个字母的密文相同。
反过来,当密文中两个字母相同,不一定明文相同且间隔为$k$的倍数,但可能性很大。
因此,可以将密文中相同的字母组找出来,并对其之间的间隔进行因式分解,密匙长度$k$很有可能就在这些公因子之中。

重合指数法

设重合指数$I_C=\underset{i=1}{\overset{n}{\sum}}p_i^2$,即两个随机字母相同的概率。

若明文与密文的重合指数都接近于英文文本的重合指数$0.065$,则说明该密文为单表代换加密。

由于现实中密文长度有限,因此可以用$I_C$的无偏估计值$I_C'=\underset{i=1}{\overset{n}{\sum}} \frac{x_i(x_i-1)}{L(L-1)}$来近似$I_C$,公式中的$x_i$表示密文符号$i$出现的次数,$L$表示密文长度,$n$表示包含的字母数,英语为$26$。

由于维吉尼亚密码中间隔为密匙长度$k$的字符构成的子串可以看做一个单表加密密码,因此,这些子串的重合指数$I_C\approx 0.065$。由此,可以通过重合指数判定一个维吉尼亚密码的密匙长度。

Exp1

密文为:

CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWQIMMQMNKGRFVGXWTRZXWIAXLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRICHRCLQOHPWQAIIWXNRMGWOIIFKEE

分析密文,可以看出CHR出现了5次,第一次出现到各次的距离分别为$165,235,275,285$,使用Kasiski测试法分析,$\mathrm{gcd}(165,235,275,285)=5$,因此,猜测密匙长度为$5$。

接着使用重合指数法来验证结论的正确性。

将密匙间隔为$k$的字符组合成为子串,对每一个子串求$I_C$后求均值。

密匙长度 所有子串平均$I_C$
1 0.045
2 0.044
3 0.047
4 0.042
5 0.067

可以看出,当$k=5$时,每一个子串的重合指数更接近于$0.065$。

可以得出,该密匙的长度为$5$

确定密匙

拟重合指数法

确定密匙可通过拟重合指数法,拟重合指数定义为$x=\underset{i=1}{\overset{n}{\sum}}r_i q_i$,$r_i$为字母$i$在第一个分布中发生的概率,$q_i$为字母$i$在第二个分布中发生的概率。

继续沿用重合指数法中拆解出来的子串,由于该子串符合单表代换加密,对每个子串分别求取该子串对应的$k_i$。
令$f_0,f_1,\cdots,f_{25}$分别表示密文子串中的字母A, B, ..., Z出现的概率,再令$n$为该子串的长度,则密文中26个字母出现的概率为$\frac{f_0}{n'},\frac{f_1}{n'},\cdots,\frac{f_{25}}{n'}$。
因此,存在$k_i$使得:$\frac{f_{k_i+0}}{n'},\frac{f_{k_i+1}}{n'},\cdots,\frac{f_{k_i+25}}{n'}$近似于英文文本中A, B, C的概率分布$p_0,p_1,\cdots,p_{25}$。
假设$0\le j \le 25$,定义数值$M_j=\underset{i=1}{\overset{25}{\sum}}\frac{p_if_{i+j \pmod{26}}}{n'}$,当$j=k_i$时,有$M_j\approx0.065$。因此,可以求解出$k_i$

恢复明文

加回去就行


一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。