本文主要是介绍古典密码之维吉尼亚密码破解思路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
首先要说一句,这是我第一次用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里边的,也没有具体的答案,只能讲个大概的过程,书上对维吉尼亚的破解讲的也十分模糊,我只能尽力理解到这里了。
原文地址:点击打开链接
这篇关于古典密码之维吉尼亚密码破解思路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!