维吉尼亚可视化破解

发表于:2018-10-19 09:22:32 来源:  合天网安实验室 阅读数(0人)

0x00 已知密匙加解密


python一句话加密


					print("".join([chr((ord(plain[i])+ord(key[i%len(key)])-ord("a")*2)%26+ord("a")) for i in range(0,len(plain))]))

python一句话解密


					print("".join([chr(((ord(cipher[i])-ord(key[i%len(key)]))%26)+ord("a")) for i in range(0,len(cipher))]))
					

0x01 不知道密匙的情况下破解


原理解释


首先破解维吉尼亚我们要知道密匙的长度,然后逐个猜解字符或者说是符号


猜测密匙的长度的话,如果密文够长的话,可以用重合指数法,弗里德曼老人家提出的,首先假设密匙长度,分组以后每一组都是凯撒,计算对应的每一组的重合指数,求出平均值再和普通英语的重合指数作对比,即可估算密匙长度,这个在密文足够长的情况下还是比较好的


也可以用Kasiski测试法,搜索长度至少为3的重复序列,密文很长的时候,甚至可以找到多组相同的长度为3的重复序列,这样的话他们的距离的公约数其中之一很有可能就是密匙长度


如果密文还保留有明文的空格的话,那也可以通过语法,人工分析,三个单独的字母可能是the或者其他的出现频率高的,从而一点点的泄露出密匙的部分


然后根据密匙长度分组,计算每组中每个字母出现的概率,因为每一组都是凯撒,所以按字母顺序排序后的频率分布图看起来只是正常英文频率分布图左右移动的效果,跟正常英文的频率分布作对比,从而算出移位数,从而算出密匙的每一个字母。


代码是看到了之前一个可视化破解的网站,想自己也用python写一个,结果就写出来了


具体代码实现


以网鼎杯第四场的维吉尼亚密码做例子


首先以下这是密文,太长了就放在百度网盘里了


链接: https://pan.baidu.com/s/1bEPSiix6uNizwJW79kDd0Q 提取码: fqam


首先猜测密匙长度


					import re
from tabulate import tabulate
import itertools
import collections
cipher=""#上边那一坨
cipher="".join(re.findall(r"[a-z]",cipher))
#计算距离的2到20内的因数
def get_fact(n):
	result=[]
	for i in range(2,21):
		if(int(n/i)==n/i):
			result.append(i)
	return result

#计算重复序列的各种组合的距离
def calc_space(str,sub_str):
	n=[]
	for i in range(0,len(cipher)-(len(cipher)+2)%3):
		if sub_str==str[i:i+3]:
			n.append(i)
	n=(itertools.combinations(n,2))
	n=[abs(i[0]-i[1]) for i in n]
	n=set(n)
	return (n if n!=set([]) else 0)

l=[]
seqs=[cipher[i:i+3] for i in range(0,len(cipher)-(len(cipher)+2)%3)]
for seq in seqs:
	n=calc_space(cipher,seq)
	if n!=0:
		for i in n:
			m=get_fact(i)
			l+=m
			#print(seq,i,m)

a=collections.Counter(l).most_common()
print(tabulate(a))
					

运行结果如下


					C:\Users\sayhi\Desktop>python vigenere.py
--  -----
11  11709
 2   7646
 3   5039
 4   3628
 5   2893
 6   2666
 7   1902
 9   1895
 8   1698
10   1404
12   1292
13   1083
18   1024
15   1014
14    989
16    815
17    749
20    739
19    699
--  -----
					

我们可以看到移位的公约数中11最多,也就最有可能是密匙长度,其次是2等等等等, 然后我们根据密匙长度分组进行频率统计


from tabulate import tabulate
import itertools
import collections
import re
import string
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl


def draw_bar(X,Y):
	a=ord('a')
	n=-1
	fig,ax=plt.subplots()
	while True:
		ax.cla()
		ax.bar(np.append(X[n:],X[:n]),np.append(Y[n:],Y[:n]))
		ax.legend()
		plt.pause(0.3)
		l=input("左移?")
		if(l=="d"): return
		n+=1
		if(n==26):n=0
		print(chr(a+n))


cs=string.ascii_lowercase
regular_freq=[8.2,1.5,2.8,4.3,12.7,2.2,2.0,6.1,7.0,0.2,0.8,4.0,2.4,6.7,7.5,1.9,0.1,6.0,6.3,9.1,2.8,1.0,2.4,0.2,2.0,0.1]
print(sum(regular_freq))
cipher=""

cipher="".join(re.findall(r"[a-z]",cipher))

key_len=11
grouped=[]
groups=[cipher[i:i+key_len] for i in range(0,len(cipher),key_len)]
for i in range(0,key_len):
	str1=""
	for group in groups:
		str1+=group[i]
	grouped.append(str1)

#draw_bar([c for c in cs],np.array(regular_freq)/np.amax(regular_freq))

for group in grouped:
	f=collections.Counter(group)
	draw_bar([c for c in cs],[f[c] for c in cs])

	#print(f)
	#print(sorted(f, key=lambda f:f[0]))
	#print()

首先绘制出正常文本的频率分布如下图




然后打开画好的正常频率分布图作参照,运行脚本,按回车向左移动,命令行里会显示移位对应的密匙字符,plt里实时更新对应的频率分布,直到两个图的频率分布对应好,命令行里最后显示的就是密匙的一个字母


如图所示前两个字母已经出来了


第一个字母




第二个字母




前两个字母分别为i和c,已经显示在了命令行里


可视化的好处我就不用多说了吧,如果你用拟重合指数法的话,看见的只是数据,可视化可以看到不同字母对应频率按顺序排列的变化趋势,一眼就可以看出两个频率分布可以相似对应


					print("".join([chr(((ord(cipher[i])-ord(key[i%11]))%26)+ord("a")) for i in range(0,len(cipher))]))
					

用以上代码解密后得明文


最后切片一下就找到flag啦


					>>> a[a.index("flag"):a.index("flag")+50]
'flagandvigenereisveryeasyhuhandforsuccessiveletter'
>>>
					

相关新闻

大家都在学

课程详情

信息安全意识教育

课程详情

小白入门之旅

课程详情

信息安全基础