sponsored links

Vigenere Decode

维吉尼亚无密钥解密

  为方便破解,把破解密码分成4个文件进行执行,分别为Vigenère.pykasiski.pykeycrack.pydecipher.py

Vigenère.py

from kasiski import kasiski
from keycrack import keycrack
from decipher import decipher

def main():
    kasiski()
    keycrack()
    decipher()

if __name__ == '__main__':
    main()

  这个文件主要是进行调用其他三个部分的破解环节,便于修改。

kasiski.py

  原本按照卡西斯基的算法思想写了一个脚本,通过查找重复字段

  如下脚本:

# -*- coding: utf-8 -*-
from string import find
'如果重复字段差有公因子,则输出公因子列表。若无,输出一个二维列表,每维第一个元素表示重复字段差的因子,第二个元素表示拥有此因子的字段差总数。'
def GCD(step):
    gcd_list=[]
    buf=[]
    if not len(step):
        return "None has ben found"
    else:#find GCD
        step_min=max(step)/2
        for con in xrange(2,step_min+1):
            flag=True
            for each_step in step:
                if each_step%con:
                    flag=False
                    break
            if flag:
                gcd_list.append(con)
    if len(gcd_list):
        return gcd_list
    else:#find GCD list
        for con in xrange(2,step_min+1):
            gcd_list.append([con,len(step)])
            for each_step in step:
                if each_step%con:
                    gcd_list[con-2][1]-=1
        for each in gcd_list:
            if each[1]:
                buf.append(each)
        for i in xrange(1,len(buf)):
            j=i
            while j>0:
                if buf[j][1]<buf[j-1][1]:
                    tem=buf[j-1]
                    buf[j-1]=buf[j]
                    buf[j]=tem
                j-=1
        return buf


def kasiski():
    f=open("C:/Users/XX/Desktop/212/sec.txt")
    sec_msg="".join(f.readlines())
    step=[]
    flag=False
    lenth=len(sec_msg)
    for i in xrange(lenth-5):
        flag_tem=0
        i_tem=i
        while True:
            flag_tem=sec_msg[i_tem+3:].find(sec_msg[i_tem:i_tem+3])
            if flag_tem==-1:
                break
            flag_tem+=3
            step.append(flag_tem)
            i_tem+=flag_tem

    print GCD(step)


if __name__ == '__main__':
    kasiski()

运行截图:

Vigenere Decode

  后决定尝试另一种方式,逐一计算不同密钥长度下的重合指数,当重合指数接近期望的0.65时,我们就可以推测这个即为我们所期望的密钥长度。

  如下脚本:

#!/usr/bin/python
import string
def kasiski():
    f=open("C:/Users/XX/Desktop/Vigenere/sec.txt")
    sec_msg="".join(f.readlines())
    for klen in range(0,int(raw_input("please input the key max length:"))):#遍历从0到期望的密钥长度
        r=[]
        for i in range(0,klen):
            s=sec_msg[i::klen]
            len_str=len(s)
            sum_a=0;
            for y in range(0,26):
                r.append(s.count(chr(97+y),0,len_str))
            for p in range(0,26):
                sum_a=sum_a +r[p]*(r[p]-1)
            klv=float(sum_a)/(len_str*(len_str-1))#重合指数
            if abs(klv-0.065)<0.01 :#挑出接近0.65的长度,当调试时可以取消循环,输出所有,挑出最适合的
                print klen
                print klv
                return 

if __name__ == '__main__':
    kasiski()

运行截图:

Vigenere Decode

keycrack.py

  当知道密钥长度时,就开始破解密钥,当知道密钥长度n时,就可将密文分解成n组,每一组都是一个凯撒密码,然后对每一组用字母品读分析进行解密,最终和在一起即为最终密钥。

  如下脚本:

# -*- coding: utf-8 -*-
import string

Alphabet_boom=[0.082,0.015,0.028,0.043,0.127,0.022,0.020,0.061,0.070,0.002,0.008,0.040,0.024,0.067,0.075,0.019,0.001,0.060,0.063,0.091,0.028,0.010,0.023,0.001,0.020,0.001]

def boom(sec_msg,lenth,word):
    Mg=[[0.0 for i in xrange(26)] for j in xrange(lenth)]
    for group in xrange(lenth):#遍历key分组lenth
        f=[0.0 for i in xrange(26)]#统计频数
        for i in xrange(len(word[group])):
            f[ord(word[group][i])-ord("a")]+=1
        for key in xrange(26):#遍历分组内key26
            for each in xrange(26):  #遍历word内第lenth个分组字符串,计算 Mg[lenth][key26]=累加fp/n'
                Mg[group][key]+=f[(each+key)%26]*Alphabet_boom[each]/len(word[group])
    key=""
    for i in xrange(lenth):
        max_=max(Mg[i])#得到最大频数字母
        if max_<0.05:#若小于0.05,则表示错误
            print "none!"
            key+=" "
            continue

        temp=[]
        for j in xrange(26):
            if Mg[i][j]==max_:
                temp.append(chr(j+ord("a")))#将数字转换成相应字母
                print chr(j+ord("a")),
                print '---------->',
                print Mg[i][j]
        if len(temp)!=1:
            key+='('+''.join(temp)+')'
        else:
            key+=temp[0]
    print "key>>",key
    f=open("C:/Users/XX/Desktop/Vigenere/key.txt", 'w') #将密钥写入文本
    f.write(key) 
    f.close() 

def keycrack():
    f=open("C:/Users/XX/Desktop/Vigenere/sec.txt")#获取密文
    sec_msg_temp="".join(f.readlines())
    f.close()
    sec_msg=""
    lenth=int(raw_input("lenth\n"))#输入上回得到的最可能的密钥长度
    for each in sec_msg_temp:
        if each in string.letters:#排除非字母符号
            sec_msg+=each

    word=["" for i in range(lenth)]#设置数组存放分组密文
    for i in xrange(len(sec_msg)):
        word[i%lenth]+=sec_msg[i]#按key长分组
    boom(sec_msg,lenth,word)

if __name__ == '__main__':
    keycrack()

运行截图:

Vigenere Decode

decipher.py

  得到密钥后,直接进行破解

  如下脚本:

# -*- coding: utf-8 -*-

def decipher():
    f=open("C:/Users/XX/Desktop/Vigenere/key.txt")#打开密钥
    key="".join(f.readlines())
    f=open("C:/Users/XX/Desktop/Vigenere/sec.txt")#打开密文
    text="".join(f.readlines())
    str='abcdefghijklmnopqrstuvwxyz'
    keylen=len(key)
    tlen=len(text)
    plaintext = ''
    i = 0
    while i < tlen:#进行移位解密
        j = i % keylen
        k = str.index(key[j])
        m = str.index(text[i])
        if m < k:
            m += 26
        plaintext += str[m-k]
        i += 1
    print plaintext
    f=open("C:/Users/XX/Desktop/Vigenere/plaintext.txt", 'w') #将明文写入文件
    f.write(plaintext) 
    f.close() 

运行截图:

Vigenere Decode

心得体会

  通过这次密码破解,我学习到了维吉尼亚密码的具体原理, 懂得维吉尼亚密码是在单一恺撒密码的基础上扩展出多表代换密码,根据密钥(当密钥长度小于明文长度时可以循环使用)来决定用哪一行的密表来进行替换,以此来对抗字频统计。当不知道密钥时,破解维吉尼亚密码第一步是确定密钥长度,学习到如何使用重合指数算法来确定密钥长度,在确定密钥长度后就可以尝试确定密钥,通常可以使用卡方检验来找到每个字母的偏移量,最终破解密文。
  这次编写,不仅让我懂得如何去破解,也让我提升关于python脚本的编写能力,大大提高我的综合水平。通过讨论,不断的修改自己的代码,吸取他人优秀的地方,开阔了思维方式。


最后:非常感谢1phan大神,基本上是参考1phan给的代码学习编写的,非常感谢

Tags: