维吉尼亚密码的破解算法及python代码实现

⽬录

1. 密⽂描述

1.1 密⽂1

密⽂：krkpekmcwxtvknugcmkxfwmgmjvpttuflihcumgxafsdajfupgzzmjlkyykxdvccyqiwdncebwhyjmgkazybtdfsitncwdnolqiacmchnhw cgxfzlwtxzlvgqecllhimbnudynagrttgiiycmvyyimjzqaxvkcgkgrawxupmjwqemiptzrtmqdciakjudnnuadfrimbbuvyaeqwshtpuyqhxv yaeffldmtvrjkpllsxtrlnvkiajfukycvgjgibubldppkfpmkkuplafslaqycaigushmqxcityrwukqdftkgrlstncudnnuzteqjrxyafshaqljsljfunh wiqtehncpkgxspkfvbstarlsgkxfibffldmerptrqlygxpfrwxtvbdgqkztmtfsqegumcfararhwerchvygczyzjaacgntgvfktmjvlpmkflpecjq tfdcclbncqwhycccbgeanyciclxncrwxofqieqmcshhdccughsxxvzdnhwtycmcbcrttvmurqlphxnwddkopqtehzapgpfrlkkkcpgadmgx dlrchvygczkerwxyfpawefsawukmefgkmpwqicnhwlnihvycsxckf

密钥： crypt (长度为5)

明⽂:

I am alive here, my beloved, for the reason to adore you. Oh!How anxious I have been for you and how sorry I am about all you must have suffered in having no news from us. May heaven grant that this letter reaches you. Do not write to me, this would compromise all of us and above all,do not return under any circumstances. It is known that it was you who helped us to get away from here and all would be lost if you should show yourself.We are guarded day and night. I do not care you are not here. Do not be troubled on my account. Nothing will happen to me. The national assemble will show leniency. Farewell the most loved of men. Be quiet if you can take care of yourself.For myself I cannot write any more, but nothing in the world could stop me to adore you up to the death.

1.2 密⽂2

密⽂：cbkznkiyjsrofgnqadnzuqigscvxizgsjwucusrdkxuahgzrhywtvdjeiuwsrrtnpszbvpzncngztbvsrnzuqigscvfjwqgjwcytwdazuqigscvfj wqgjwjhkfdylmcbmhonbmbvdnvbmwbnacjaphhonbmbvdnvbmwbnaublsbdnjjneoroyfmxfhixpzpcozzuqigscvxcvhdmfgxmgov zsqmvzyvwyzmsczoajsejifoakdcrehwhgdehvmtnmvvmesvzifutzfjzoalwqztunwvdvmfhesvzifutzfjzoalwqztunpsnoyfleoxdetbwf soyfjmfhjuxuagnarsfqydoyfjzsrzeujmfhjuubihrjdfinwsnepcawdnkbobvnmzucmghijjmbscjejnapddehlmqddmfxncqbfpxwfejifp qzhikiyaiozimubwuzufazsdjwdiudzmztivcmgp

密钥：uiozvrb(长度为7)

明⽂：

It was the best of times.It was the worst of times. It was the age of wisdom. It was the age offoolishness. It was the epoch of belief. It was the epoch of incredulity. It was the season of light. It was the season of darkness. It was the spring of hope. It was the winter of despair.We had everything before us. We had nothing before us. We were all going direct to heaven. We were all going direct the other way. In short, the period was so, far like the present period, that some of its noisiest authorities insisted on its being received, for good or for evil, in the superlative degree of comparison only.

2. 破解原理

2.1 重合指数法确定密钥长度

重合指数是指字符串中两个随机元素相同的概率，记为。设某种语⾔由个字母组成，每个字母发⽣的概率为，则：

现实世界中密⽂有限，故从密⽂计算的重合指数总是不同于理论值，所以⼀般⽤的⽆偏估计值：

其中，是密⽂中i出现的次数，L表⽰密⽂长度，n表⽰字母数，此处n=26。

对于英⽂字符串，通过词频统计可以得到26个英⽂字母出现的期望概率。通过⼤量的英⽂样本，利⽤公式（1）可得⼀般英⽂⽂本重合指数值：

对于⼀个完全随机的字符串，其重合指数值：

因为0.065与0.038间隔的充分远，所以能够通过这种⽅式确定密钥长度。具体计算步骤如下：

Step1：初始化d = 1。

Step2：将密⽂分成d个⼦串，分别对每⼀个⼦串利⽤公式（2）计算其重合指数，及它们的平均值。若d为密钥长度，那么该平均值的IC值将接近于0.065。

Step3：d = d+1，若d < 10重复步骤⼆。

Step4：⽐较每⼀个d下的重合指数平均值，取最接近0.065的d值即为所求。

以密⽂1为例，利⽤上述算法，得到部分结果见表1。表1 密⽂1密钥长度与重合指数对应表

从计算结果可以确定密⽂1的密钥字长度为5，此时每⼀个⼦串的平均重合指数为0.06254。

对于密⽂2采⽤同样的计算⽅法得到密钥字长度为7，此时平均重合指数为0.07392。对于其余的情况，

平均重合指数均在0.035-0.046之间波动。

2.2 互重合指数确定⼦串间相对偏移

从以上结论可知密钥字长度。下⾯本⽂将采⽤互重合指数法来确定相对位移，其精确定义如下。

已经确定密钥字长度为m，密⽂⼦串中的各个密⽂字母都是由同⼀个单表代换得到。设密钥为，可估算的值。显然，中的⼀个随机元素与中的⼀个随机元素同时为第h个英⽂字母的概率，这⾥下标运算为模26运算。因此有

IC n i P 1≤i ≤n i ()IC =P ，1i =1∑n i 2

()IC IC = .2i =1∑n

L L −1()x x −1i (i )考古墓地

()x i IC =P =i =0∑25i 2

0.065 ，3()IC =26=(261)2

0.038 .4()

Y i K =K K …K 12m MI Y ,Y c (i j )Y i Y j P P ,0≤h −K i h −K j h ≤25

该估计值仅仅依赖于，称其为和的相对位移。易得，当相对位移s为0时，互重合指数估计接近0.065；当s不为0时，这些估计值在0.031-0.045之间波动。因此可以确定⼦串之间的相对位移，以密⽂1为例得到结果见表2。表2 密⽂1互重合指数表

第1组和第2组之间偏移为11时，互重合指数为0.06141；

第1组和第3组之间偏移为4时，互重合指数为0.06148；

第1组和第4组之间偏移为13时，互重合指数为0.05907；

第1组和第5组之间偏移为9时，互重合指数为0.06198。

于是密钥字为 2.3 密钥字的确定

对遍历26个英⽂字母后，可以得到26种可能的密钥。对每⼀个密钥均对密⽂进⾏解密。通过分析“明⽂”的前20个字母，可以确定：

密⽂1密钥为crypt, k=(2,-9,-2,-11,-7) ；

密⽂2密钥为uiozvrb, k=(20,8,14,-1,-5,17,1) 。

2.4 密⽂破解

利⽤上述密钥对密⽂进⾏破解，引⼊wordninja库对英⽂明⽂进⾏分词操作。最后，为明⽂进⾏标点调整。

3. 破解代码

Python代码(代码说明见代码注释)

运⾏环境：python 3.7 + numpy、wordninja第三⽅库

'''维吉尼亚破解'''

import numpy as np

import wordninja

def alpha (cipher ): #预处理，去掉空格以及回车

c = ''

for i in range (len (cipher )):

if (cipher [i ].isalpha ()):

c += cipher [i ]

return c

def count_IC (cipher ): #给定字符串计算其重合指数

count = [0 for i in range (26)]

郎庆田

L = len (cipher )

IC = 0.0

for i in range (len (cipher )):

if (cipher [i ].isupper ()):

count [ord (cipher [i ])-ord ('A')] += 1

elif (cipher [i ].islower ()):

count [ord (cipher [i ])-ord ('a')] += 1

for i in range (26):

IC += (count [i ]*(count [i ]-1))/(L *(L -1))

return IC

一滴清def count_key_len (cipher ,key_len ): #对字符串按输⼊个数进⾏分组，计算每⼀组的IC 值返回平均值

N = ['' for i in range (key_len )]

IC = [0 for i in range (key_len )]

MI Y ,Y ≈c (i j )P P =h =0∑25h −K i h −K j P P 5h =0∑25

h h +K −K i j ()s =ij K −K mod 26(i j )Y i Y j K =K ,K −11,K −4,K −13,K −9(11111)

K 1

IC =[0for i in range(key_len)]

for i in range(len(cipher)):

m = i % key_len

N[m]+= cipher[i]

for i in range(key_len):

IC[i]= count_IC(N[i])

#print(IC)

print("长度为%d时，平均重合指数为%.5f"%(key_an(IC)))

an(IC)

def length(cipher):#遍历确定最有可能的密钥长度返回密钥长度

key_len =0

mins =100

aver =0.0

for i in range(1,10):

k = count_key_len(cipher,i)

if(abs(k-0.065)<mins):

mins =abs(k-0.065)

key_len = i

aver = k

print("密钥长度为%d，此时重合指数每组的平均值为%.5f"%(key_len,aver))

return key_len

def count_MIC(c1,c2,n):#n=k1-k2为偏移量，计算c1,c2互重合指数MIC

count_1 =[0for i in range(26)]

count_2 =[0for i in range(26)]

L_1 =len(c1)

L_2 =len(c2)

MIC =0

for i in range(L_1):

if(c1[i].isupper()):

count_1[ord(c1[i])-ord('A')]+=1

elif(c1[i].islower()):

count_1[ord(c1[i])-ord('a')]+=1

for i in range(L_2):

if(c2[i].isupper()):

count_2[(ord(c2[i])-ord('A')+n+26)%26]+=1

elif(c2[i].islower()):

count_2[(ord(c2[i])-ord('a')+n+26)%26]+=1

for i in range(26):

MIC += count_1[i]*count_2[i]/(L_1*L_2)

return MIC

def count_n(c1,c2):#确定两个⼦串最优的相对偏移量n=k1-k2

n =0

mins =100

k =[0.0for i in range(26)]

for i in range(26):

k[i]= count_MIC(c1,c2,i)

#print(i,k[i])

if(abs(k[i]-0.065)<mins):

mins =abs(k[i]-0.065)

n = i

return n

def group_k(cipher,key_len):#完成分组操作并计算每⼀组与第⼀组的最优相对偏移量并返回 N =[''for i in range(key_len)]

MIC =[0for i in range(key_len)]

s =[0for i in range(key_len)]

for i in range(len(cipher)):#对密⽂进⾏分组

m = i % key_len

N[m]+= cipher[i]

for i in range(1,key_len):#计算与第⼀组之间的相对偏移量

s[i]= count_n(N[0],N[i])# s[i] = k1-k(i+1)

MIC[i]= count_MIC(N[0],N[i],s[i])# MIC[i] = MIC(1,i+1)

print("第1组和第%d组之间偏移为%d时，互重合指数为%.5f"%(i+1,s[i],MIC[i]))

print("第1组和第%d组之间偏移为%d时，互重合指数为%.5f"%(i+1,s[i],MIC[i])) return s

def miyao(key_len,s,k):#k为第⼀个⼦串的移位，输出密钥并返回密钥所有字母的下标 mi =[''for i in range(key_len)]

for i in range(key_len):

s[i]=-s[i]+k #k2=k1-n

mi[i]=chr((s[i]+26)%26+ord('a'))

print("第⼀个偏移量为%d，密钥为%s时"%(k,mi))

return s

欧洲甜樱桃def the_end(cipher,key_len,s):#输⼊密⽂密钥返回明⽂结果

plain =''

i =0

while( i <len(cipher)):

for j in range(key_len):

if(cipher[i].isupper()):

plain +=chr((ord(cipher[i])-ord('A')-s[j]+26)%26+ord('A'))

else:陈独秀之死

plain +=chr((ord(cipher[i])-ord('a')-s[j]+26)%26+ord('a'))

i+=1

if(i ==len(cipher)):

break

# print(plain)

return plain

if __name__ =="__main__":

fp =open("密⽂2.txt","r")

cipher =''

for i adlines():

cipher = cipher + i

fp.close()

cipher = alpha(cipher)

key_len = length(cipher)

s = group_k(cipher,key_len)

m = s.copy()

for k in range(26):

s = m.copy()

s = miyao(key_len,s,k)

plain = the_end(cipher,key_len,s)

print(plain[0:20])#输出部分明⽂确定偏移量k1

print("参考输出，请输⼊第⼀个⼦串的偏移量:",end='')

k =int(input())

m = miyao(key_len,m,k)

plain = the_end(cipher,key_len,m)

'''对英⽂⽂本进⾏分词'''

word = wordninja.split(plain)

plain =''

bt欧洲for i in range(len(word)):

plain += word[i]

plain +=' '

print("明⽂为\n"+plain)

部分输出截图：

参考⽂献

本文发布于:2024-09-22 22:24:10，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/178102.html

上一篇：发票真伪查询的常用方法

下一篇：指导性案例对网络犯罪的界定

标签：密钥重合指数长度确定计算

留言与评论（共有 0 条评论）