本文主要是介绍古典密码之维吉尼亚密码破解思路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先要说一句，这是我第一次用python coding，所以很多地方都不太懂，吐槽自己竟然用sum当变量名，之后有用sum()函数，然后报了错还不知道为什么。不知道用ascii码要做chr()转化，等等，还比如在重合指数函数和拟重合函数中可以提炼出一个共同的函数，但是我写完重合指数才发现，越改越乱所以就算了吧。但是我终于还是写完了，应该比C语言的代码少个几百行吧，我是不会说这篇文章，我从开始看原理到敲代码写了一天多。
多表代换密码体制的分析方法主要分为三步：第一步确定秘钥长度，常用的方法有卡西斯基（Kasiski）测试法和重合指数法（Index of Coincidence）;第二步就是确定秘钥，常用的方法是拟重合指数测试法；第三步是根据第二步确定的密钥恢复出明文。
Kasiski测试法：若用给定的m个密钥表周期地对明文字母加密，则当明文中有两个相同字母组在明文序列中间隔的字母数为m的倍数时，这两个明文字母组对应的密文字母组必相同。但反过来，若密文中出现两个相同的字母组，它们所对应的明文字母组未必相同，但相同的可能性很大。如果我们将密文中相同的字母组找出来，并对其相同字母数综合研究，找出它们的相同字母数的最大公因子，就有可能提取出有关密钥字的长度m的信息。
具体方法：搜索长度至少为3的相同密文段，记录这些相同密文端到起始点之间的距离（d1,d2,d3……），找出（d1,d2,d3……）的所有公因子，同样为了确保秘钥长度的准确性，我们在搜索另一至少长为3的相同密文段，重复上操作，最后找出他们共同的公因子，若公因子不唯一，则在采用下边的重合因子测试法确定密钥长度。
重合因子测试法：利用随机文本和英文文本的统计概率差别来分析秘钥长度。设一门语言由n个字母构成，每个字母发生的概率为pi，1≤i≤n，则重合指数是指其中两个随机元素相同的概率，记为：
。
实际使用CI的估计值CI’: L:密文长度；xi：密文符号i发生的数目
下面就让我们拿个例子说一下吧。
koommacomoqeglxxmqcckueyfcurylyligzsxczvbckmyopnpogdgiaztxddiaknvomxhiemrdezvxbmzrnlzayqiqxgkkkpnevhovvbkk
tcssepkgdhxyvjmrdkbcjuefmakntdrxbiemrdprrjbxfqnemxdrlbcjhpztvvixyetniiawdrgnomrzrreikioxrusxcretvzaozygyukndwpio
uoriyrhhbzxrceayvxuvrxkcmaxstxsepbrxcs1rukvbxtgzuggdwhxmxcsxbiktnslrjzhbxmspungzrgkudxnaufcmrzxjrywymi
这是一个使用维吉尼亚进行加密的密文段，从中选取一些一眼看到的重复字段，并计算相隔的距离。
import string def findstr(str1,str2): a = 0 r = [] while a < len(str1): a = word.find(str2, a) if a == -1: break r.append(a) a = a + 1 x = 0 while x + 1 <len(r): print(r[x + 1] - r[x]) x = x + 1 word = "密文段落" findstr(word,'sxc')
通过计算，结果如下：
观察发现，大部分都有公因子7，基本可以推断密钥的长度为7.（如果公因子还有其他的，可通过重合因子测试法进一步确定密钥长度）
当然还可以通过重合指数法推断密钥长度：
#重合指数算法，str为文本，n为假设的秘钥长度，可以分别1-n密钥长度下的ic值，找到峰值ic对应的n的大小 def count_IOC(str,n): x = 0 r = [] ic_all = [] while x < n: sum_all = 0 c = str[x::n] len_str = len(c) for y in range(0,26): r.append(c.count(chr(97+y) ,0,len_str)) for p in range(0,26): sum_all = sum_all + r[p] * (r[p] - 1) ic = float(sum_all)/(len_str * (len_str - 1)) print(ic) ic_all.append(ic) x = x + 1 return sum(ic_all)/ n #假设猜测秘钥长度在10以下 for x in range(0,10): count_IOC(word, x)
结果如下，峰值为n = 7时，佐证了用kasiski测试法算出的秘钥等于7.
知道了密钥，下一步就是利用拟重合指数测试法了。
首先按照已知秘钥的长度，将密文7个一行7各一行进行分组，把每列作为一组进行分组，
#对密文进行分组（密文文本，第i组，秘钥长度） def divstr(str, i, n): c = str[i::n] return c
拟重合指数测试法：首先子密文段重各个字母的频率进行统计（记为fi, i∈a – z），查看字母频率分布统计概率(记pi)，计算子密文段长度为n，
使用公式
计算出M0，然后对子密文段移位25次，同样按照上述方法求出M1 — M25的值，
根据重合指数的定义知：一个有意义的英文文本，M ≈0.065，所以利用这个规律，就可以确定秘钥中的每一个字母。
#所有成员自增 def member_plus(r):m = []for i in r:if i == 'z':i = chr(96)m.append(chr(ord(i)+1))return ('').join(m) 这里有必要说一下return('').join(p)，p是一个list，而我们需要的是个字符串，如果返回list，下边就会报错，因为python中有list.count(ord)和str.count(sub,,)函数。#拟重合指数 def count_NIOC(i, c):p = [0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025,0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150,0.01974, 0.00074]len_str = len(c)r = []sum_m = 0for y in range(0, 26):r.append(c.count(chr(97 + y), 0, len_str))#统计字串中a-z的数量for x in range(0, 26):f = (r[x] * p[x]) / len_str sum_m = sum_m + fprint(i,sum_m)#改变第二个参数：第几组子密文段，第三个参数：秘钥长度，分别计算秘钥中的各个字母 str0 = divstr(word,2,7) for x in range(0,26):count_NIOC(x, str0)str0 = member_plus(str0)#每计算一次Mx，子密文段自加
以代码中的第3组为例对上文例题计算结果如下图：
可以看到x = 16时，M最接近0.065，所以x = 16 对应的字母q就是第三组密文的秘钥。
终于写完了，激动地快要哭了。很多地方纠结了很久，这个例题是网上下载的ppt里边的，也没有具体的答案，只能讲个大概的过程，书上对维吉尼亚的破解讲的也十分模糊，我只能尽力理解到这里了。
原文地址：点击打开链接
这篇关于古典密码之维吉尼亚密码破解思路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
