详解维吉尼亚密码（附四种攻击策略）

2023-12-31 10:45:17

目录

一. 介绍

二. 破解维吉尼亚密码

2.1 频率统计

2.2 提高型频率统计法

2.3 Kasiski攻击法

2.4 重合指数攻击法（index of coincidence method）

三. 小结

一. 介绍

我们知道英语字母的出现频率是有规律的，比如像下表：

掌握了这些规律后，像凯撒密码等单表置换密码就不安全了。因为固定的密文字母一定对应着同样的明文字母。这个时候就出现了，略微高级的维吉尼亚密码。

维吉尼亚密码（Vigenere cipher）又叫做多表置换密码（poly-alphabetic shift cipher）。举个例子，明文字母为ab，可能对应密文DZ；明文字母是ac，可能对应密文TY。我们发现同一个明文字母a，在密文中有的时候是D，有的时候是T

首先说明下，这些密码都是把字母a~z对应0~25，密钥字母相加对应数字相加，必要时需要模26。举个例子，比如密钥是cafe，加密过程如下表：

明文tellhimaboutme
密钥cafecafecafeca
密文VEQPJIREDOZXOE

需要注意的是密钥cafe是会被重复利用的，以4为循环。也就是说加密第一个字母，加密第五个字母，加密第9个字母使用的同一个密钥c；以此类推。

观察下密文，我们发现密文E有的时候对应明文e，有的时候对应明文a，看起来似乎毫无规律。另外，当密钥足够长时，破解起来就更加难了。

维吉尼亚密码是在16世纪提出了，直到过了200多年，人们才陆续发现了破解的方法。

二. 破解维吉尼亚密码

2.1 频率统计

假定密钥长度为t，也就是密钥k包含t个字母，可以写做：

k=k_1\cdots k_t

借此，我们把密文可以分成t组。比如把第一个密文，第t+1个密文，第2t+1个密文放一起，等等。这些密文所使用的密钥是一样的，如下：

c_j,c_{j+t},c_{j+2t},\cdots

这些密文都使用同一个私钥k_j。密码学中很喜欢把一组叫做一流（stream），第j组，也就是第j流。

首先，最傻的穷搜攻击(brute-force search），一共有t组，每一组的密钥都有26种可能性（26个英文字母），如果直接穷搜的话，也就是26^t，这显然是不可行的。

那应该怎么做?

我们可以统计每一组密文字母的频率，比如我们发现在某一组密文中P出现的频率最高，那么它对应的明文大概率是e（看上面英文字母频率统计表）。由此就可以推导出这一组的密钥，这样其它的字母也就可以解决了。这种攻击方法的时间复杂度为26t。

2.2 提高型频率统计法

以上统计字母概率的方法误差太大了，比如如果你发现两个字母频率一样，咋办？

所以，实际利用的时候大都采用频率平方和的数字分析方法。还是一样，把英文字母a~z跟整数0~25对应起来。令p_i代表第i个字母的概率，注意是概率。根据字母表，我们发现：

\sum_{i=0}^{25}p_i^2\approx 0.065

在同一组密文中，使用的密钥是相同的。也就是对于密文来讲，令q_i代表第i个字母的频率，假定该组的密钥为k，那么明文p_i应该与q_{i+k}相对应，由此计算：

I_j=\sum_{i=0}^25 p_iq_{i+j}

密钥有26种可能性，只需要最多计算26次，当发现这个计算结果也接近0.065时，这个密钥就是正确的。

这个在现代密码学中可以被看成密钥恢复攻击（key recovery attack）。

2.3 Kasiski攻击法

Kasiski算法最早于19世纪中期被提出，该方法可以用来猜测密钥具体长度。我们知道英语中会经常出现“the”这个单词，加密形成密文后，很有可能对应相同的密文字母。

假如某维吉尼亚密码的密钥是beads，我们来看一个例子：

密文中重复出现了LII，它们都对应着明文the，说明这两个明文使用的是同一个密钥字母。我们把密钥的长度看成周期，两个LII之间的距离为30，说明30是密钥周期的倍数。

2.4 重合指数攻击法（index of coincidence method）

这种方法主要也是用来猜测密钥长度的，比上一个方法更加准确，利用代码也更容易实现。

假定密钥长度为t，在给定密文的情况下，我们希望通过重合指数攻击法，导出t的具体值。

按照之前分组的思想，第一组(stream)密文使用同一个密钥，如下：

c_1,c_{1+t},c_{1+2t},\cdots

同一个密钥代表同一种移位的加密方式。

令q_i代表第i个明文字母的频率，假设此组密文的移位为j，也就可以得到：

q_{i+j}\approx p_i

其中p_i代表明文第i个字母的概率。也就是q_0,\cdots,q_{25}就是把p_0,\cdots,p_{25}移位j得到的，这种移位其实很类似于抽象代数中循环群。比如假设明文a的概率为0.01，那么移3位的话，密文中C的频率应该接近0.01。考虑一个字母的话，误差太大。

所以：

\sum_{i=0}^{25}q_i^2\approx\sum_{i=0}^{25}p_i^2\approx 0.065

由此便可以大致确定移位的多少。假定候选的密钥长度\tau=1,2,\cdots,T，攻击的步骤如下：

  1. 抽取第一组密文c_1,c_{1+\tau},c_{1+2\tau},\cdots
  2. 形成直方图，统计每个字母的频率q_0,\cdots,q_{25}
  3. 接着计算：

S_{\tau}=\sum_{i=0}^{25}q_i^2

如果此时的\tau恰好为密钥长度t时，最终S_{\tau}的计算结果必定接近0.065.

如果密钥长度分析不对的话，每个字母出现的频率会均匀相等。因为是乱码，相当于均匀随机取，所以q_i\approx 1/26，也就可以得到：

S_{\tau}\approx \sum_{i=0}^{25}(\frac{1}{26})^2\approx 0.038

总结下就是，当密钥正确时，计算出的结果接近0.065；当密钥不对时，计算出的结果接近0.038.

也可以拿第二组密文来验证此时的密钥长度分析是否正确。

三. 小结

维吉尼亚密码的攻击算法需要密文的长度足够长，因为只有这样才能利用频率来代替概率。

可以想到如果密钥长度足够长，这个密码方案可以实现香农意义上的完美安全。

文章来源:https://blog.csdn.net/forest_LL/article/details/135300302
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。