title: “维吉尼亚密码的破解” key: 2019-03-10-Vigenere-Cipher tags: crypto pageview: true modify_date: shraring: true show_author_profile: true show_subscribe: true
最近在把自己csdn的一些东西搬到这里来
维吉尼亚密码的破解
密码学作业，做的时候发现网上和书上讲的都不是很详细，导致花了很多时间，所以这里记下来一点希望能有帮助。
##维吉尼亚密码破解步骤：
- 确定密钥长度
- 确定密钥内容
- 根据密钥恢复明文
确定密钥长度
- 在密文中找到重复出现三次以上（这样做是为了保证精确度和减少计算量）的字母组合。这里，字母组合的意思是两个及以上的重复字母组比如tn、pm。
- 然后列表写出每一个重复字母组的位置。（字母组的位置以字母组的第一个字母为准，就是列出每个字母组的第一个字母是整个密文里面的第几位）比如书上的例子BZGTNP，这里面tn的位置是4。
- 接着计算相对距离。就是在第二步里面算出的重复字母组的位置两两相邻的差。比如字母组的位置是4，19，410，那么这一步得出的结果就是15，406。
- 给出相对的距离的因子数。还是这个tn的例子，105 = 3 x 5 x 7，406 = 2 x 7 x 29，那么这一步得出来的结果就应该是2,3,5,7,29
- 将上面的步骤运用于所有重复三次以上的字母组合，生成一张表格。（以上步骤是根据kasiski测试法猜测出的可能）
- 根据重合因子测试法确定密钥长度。（这一步里面，书上的做法是每一个自然数都做了重合指数计算，我觉得这样似乎就让上面求的因子数没有什么意义了，不过还是都求出来保准一点儿吧）。
关于重合因子测试法
这里面要用的两个混的量，一个是重合指数，一个是重合指数的无偏估计值。
重合指数：设某种语言由n个字母组成，每个字母$i$发生的概率为$p_{i} (1<=i <=n)$，则重合指数就是两个随机字母相同的概率。
对于随机文本，这一值大约是0.038。而对于英文文本，这一值大约是0.065。（因为在英语语言中，各个字母出现的频率是有分布的）。
\[IC = \sum^{n}_{i=1}{p_{i}^{2}}\]重合指数的无偏估计值:
\[IC' = \sum^{n}_{i=1}{\frac{x_{i}(x_{i}-1)}{L(L-1)}}\]其中L表示密文长度，$x_{i}$表示密文符号i出现的次数，n表示某门语言包含的字母数（在英语里，取26）。
这两个有什么区别呢，简单来说就是如果判断文本是否被单表加密的时候，要用重合指数来计算。如果密文的重合指数较低，就可能是一个多表代换密码。（这里的理解是，如果是单表加密相当于凯撒密码，每个字母出现的次数看作一个数组的话，加密前后只是数组的下标发生了变化，下标和次数的对应关系顺序变化，而整个数组的内容没有变化。计算重合指数的时候，又和下标无关，只和整个数组里面数字的出现次数有关。）
而在破解维吉尼亚密码的时候，因为密文长度有限容易出现偏差，所以这时候用无偏估计值来计算。
我们从1开始计算密钥长度对应的分组对应的重合指数的无偏估计值。
密钥长度为1的时候，整个密文是一个组内，所以无偏估计值是整个文章的无偏估计值。
密钥长度为2的时候，将第1,3,5,7….分为一组，将2,4,6,8….分为一组，然后对两组分别求无偏估计值并求平均值。
密钥长度为3的时候，将第1,4,7,10…分为一组，第2,5,8,11…分为一组，第3,6,9,12….分为一组。然后对三组分别求无偏估计值病区平均值。
当求到一个重合指数的无偏估计值最接近0.065的密钥长度的时候，可以认为这个长度就是密钥的长度。
确定密钥内容
在这一步中，我们要用到另外一个指数，拟重合指数。
设某种语言由n个字母组成，每个字母i在第一个分布中发生的概率为$r_{i}$，在第二个分布中发生的概率为$q_{i}$，则拟重合指数定义为：
\[x = \sum_{i=1}^{n}{r_{i}q_{i}}\]而在破解维吉尼亚密码的过程中，第一个分布即为正常英语文本，第二个分布为我们分组下的维吉尼亚密码密文的文本。
根据我们在上一步求的密钥，把维吉尼亚密码分成m个组（m为密钥长度）。这样在每个组内的密文都是由同一个字母（密钥）加密而来的，就相当于凯撒密码。所以我们从a-z测试这个作为密钥的字母到底是什么。当拟重合指数取最大的时候，可以认定这个就是使用的密钥。
根据密钥就可以轻而易举得到明文啦(^▽^)