维吉尼亚可视化破解
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))]))
原理解释
首先破解维吉尼亚我们要知道密匙的长度,然后逐个猜解字符或者说是符号
猜测密匙的长度的话,如果密文够长的话,可以用重合指数法,弗里德曼老人家提出的,首先假设密匙长度,分组以后每一组都是凯撒,计算对应的每一组的重合指数,求出平均值再和普通英语的重合指数作对比,即可估算密匙长度,这个在密文足够长的情况下还是比较好的
也可以用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' >>>