古典密码之维吉尼亚密码(无密钥破解)

介绍

维吉尼亚密码又译维热纳尔密码:

是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。

维吉尼亚密文是通过明文加上密钥，根据维吉尼亚密码表来生成密文。

就是把每个字母用不同的凯撒加密了一下

明文与密文之间的关系:

假设明文是:ABCDEFG

密钥是AAAA  密文就是:ABCDEFG

密钥是BBB     密文就是:BCDEFGH

密文是QWER 密文就是:QXGUUBK

如果密文比明文短就循环直到和明文一样长进行一一对应的凯撒加密

维吉尼亚的密码强度是跟密钥的长度有关，或者你可以用几个密钥进行加密，如果几个密钥进行加密，那么我们尽量让不同密钥的长度互质，如果明文不长，当密钥长度和明文一样长，理论上是不可破译。然而，实际上很那做到密钥长度和明文长度一样长，因此这就给维吉尼亚密码破译提供了可能。

破解

步骤：1、确定密钥的长度 2、确定密钥的内容 3、根据密钥恢复明文。

1、首先，我们从维吉尼亚密码加密方式可以发现，假如密钥的长度为 k ，那么明文中第 X_i ，X_i+k ，X_i+2*k，……是不是用同一个密码加密，那么不就是凯撒密码吗？ 那么问题来了，我们怎么获取到密钥长度是多少呢？

2、Kasiski 实验

　　　为了获取到密钥长度，我们需要进行Kasiski 实验，什么是Kasiski 实验呢？

假如有一段密文: ACEBTSSTRCESQSSTQRCK

那么我们从中挑选出至少三个字符以上相同的字串，并且比较他们相邻两个字串相邻位置之差：比如密文中 “SST”，它们相差了8。

因为在加密过程中，出现至少三个字符以上相同的字串，明文不同的概率是很小的，那么我们是不是可以知道，密钥的长度一定是8的因子。

如果还能找到其他至少三个字符以上相同的字串，那么密钥长度是它们的最大公约数的概率非常大。

到目前为止我们可能已经有好几种密钥长度的可能了，那么怎么来确定密钥长度呢？或者说怎么求出密钥，获取明文呢？

3、重合指数攻击

      设一门语言由n个字母组成，每个字母出现的概率为 P_i ，则重合指数是指两个元素随机相同的概率之和，记作 CI =∑ P_i²  (1<= i <= n)；

经分析，英文中，一段文字是随机的话，CI =0.0385 ；如果这段文字是有意义的，那么 CI=0.065  （约等）。实际上计算的CI应该用这个公式

 L：密文长度； fi ：在密文中的出现次数。  （公式来源）

　　这个有什么好处呢？

　　好处就是用我们猜测的密钥长度来进行分组，分别计算每组的CI，再求个平均，计算当前密钥长度下，CI 的值与0.065相差多少。然后按照最接近0.065的密钥长度进行排序，为了提高解密的成功率，一般会取前5~10个较为接近的密钥长度作为猜测。

4、字母频率分析

　　密钥长度知道了，然而怎么获取密钥到底是多少呢？

       还是根据统计学：我们可以知道每个字母在英文中的频率

　　字母表频率

　　正常的文本中，每个字母出现的频率是遵循上述规则。

　　那么破解密钥就变得很简单了，我们统计在某个密钥长度下的密各个组的字母频率，这样对单个组来说，就是凯撒密码，我们循环26次，判断哪种情况下字母频率与统计字母频率的内积最大，即 R=∑Pi*Qi  (‘a'<= i <=’z’)  。

　　这样我们对密钥的某个单个字符破解出来了，同理我们可以破解出密钥。

最后从你程序输出的几组结果进行人工判别一下，哪个是有意义的明文。

在线解密

文章转载:古典密码之维吉尼亚密码无密钥破解 – ISGuXing – 博客园 (cnblogs.com)