如何使用python實(shí)現(xiàn)維吉尼亞算法

小編給大家分享一下如何使用python實(shí)現(xiàn)維吉尼亞算法，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

1 Virginia加密算法、解密算法

Vigenenre密碼是最著名的多表代換密碼，是法國(guó)著名密碼學(xué)家Vigenenre發(fā)明的。Vigenenre密碼使用一個(gè)詞組作為密鑰，密鑰中每一個(gè)字母用來確定一個(gè)代換表，每一個(gè)密鑰字母被用來加密一個(gè)明文字母，第一個(gè)密鑰字母加密第一個(gè)明文字母，第二個(gè)密鑰字母加密第二個(gè)明文字母，等所有密鑰字母使用完后，密鑰再次循環(huán)使用，于是加解密前需先將明密文按照密鑰長(zhǎng)度進(jìn)行分組。

密碼算法可表示如下：。

設(shè)明文串為：

M=m1m2…mn，mi∈charset, n是明文長(zhǎng)度

秘鑰為：

K=k1k2…kd，ki∈charset, d是秘鑰長(zhǎng)度

密文為：

C=c1c2…cn，ci∈charset, n是密文長(zhǎng)度

加密算法:

cj+td=(mj+td+kj ) mod 26

j=1…d,  t=0…ceiling(n/d)-1

其中ceiling(x)函數(shù)表示不小于x最小整數(shù)

解密算法：

mj+td=(cj+td -kj ) mod 26

j=1…d, t=0…ceiling(n/d)-1

其中ceiling(x)函數(shù)表示不小于x最小整數(shù)

加解密代碼如下

def VigenereEncrypto(message, key):
 msLen = len(message)
 keyLen = len(key)
 message = message.upper()
 key = key.upper()
 raw = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"# 明文空間
 # 定義加密后的字符串
 ciphertext = ""
 # 開始加密
 for i in range(0, msLen):
  # 輪詢key的字符
  j = i % keyLen
  # 判斷字符是否為英文字符，不是則直接向后面追加且繼續(xù)
  if message[i] not in raw:
   ciphertext += message[i]
   continue
  encodechr = chr((ord(message[i]) - ord("A") + ord(key[j]) - ord("A")) % 26 + ord("A"))
  # 追加字符
  ciphertext += encodechr
 # 返回加密后的字符串
 return ciphertext
if __name__ == "__main__":
 message = "Hello, World!"
 key = "key"
 text = VigenereEncrypto(message, key)
 print(text)
def VigenereDecrypto(ciphertext, key):
 msLen = len(ciphertext)
 keyLen = len(key)
 key = key.upper()
 raw = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"# 密文空間
 plaintext = ""
 for i in range(0, msLen):# 開始解密
  # 輪詢key的字符
  j = i % keyLen
  # 判斷字符是否為英文字符，不是則直接向后面追加且繼續(xù)
  if ciphertext[i] not in raw:
   plaintext += ciphertext[i]
   continue
  decodechr = chr((ord(ciphertext[i]) - ord("A") - ord(key[j]) - ord("A")) % 26 + ord("A"))
  # 追加字符
  plaintext += decodechr
 # 返回加密后的字符串
 return plaintext
if __name__=="__main__":
 ciphertext = "RIJVS, AMBPB!"
 key = "key"
 text = VigenereDecrypto(ciphertext, key)
 print(text)
import VigenereDecrypto
import VigenereEncrypto
def main():
 info = '''==========********=========='''# 開始加密
 print(info, "\n------維吉尼亞加密算法------")
 print(info)
 # 讀取測(cè)試文本文檔
 message = open("test.txt","r+").read()
 print("讀取測(cè)試文本文檔:test.txt")
 print("開始加密！")
 # 輸入key
 key = input("請(qǐng)輸入密鑰：")
 # 進(jìn)入加密算法
 CipherText = VigenereEncrypto.VigenereEncrypto(message, key)
 # 寫入密文文本文檔
 C = open("CipherText.txt", "w+")
 C.write(CipherText)
 C.close()
 print("加密后得到的密文是: \n" + CipherText)
 # 開始解密
 print(info, "\n------維吉尼亞解密算法------")
 print(info)
 # 讀取加密文本文檔
 print("讀取密文文本文檔：CipherText.txt")
 Ciphertext = open("CipherText.txt", "r+").read()
 # 進(jìn)入解密算法
 print("開始解密！")
 Plaintext = VigenereDecrypto.VigenereDecrypto(Ciphertext, key)
 P = open("PlainText.txt", "w+")
 # 寫入解密文本文檔
 P.write(Plaintext)
 P.close()
 print("解密后得到的明文是 : \n" + Plaintext)
if __name__=="__main__":
 main()

2重合指數(shù)法

2.1重合指數(shù)

設(shè)x=X1X2...Xn是一個(gè)含有n個(gè)字符的字符串，x的重合指數(shù)記為Ic(x),定義為x中兩個(gè)隨機(jī)元素相同的概率。

設(shè)y是一個(gè)長(zhǎng)度為n密文，即y=y1y2...ym,其中y是密文字母,同樣來求從中抽到兩個(gè)相同字母的概率是多少。為此,設(shè)NA為字母A在這份密文中的頻數(shù),設(shè)Nb為字母B在這份密文中的頻數(shù),依此類推

從n個(gè)密文字母中抽取兩個(gè)字母的方式有?_?^2=n(n-1)/2,而其中NA個(gè)A組成一對(duì)A的方式有CNA2= NA(NA-1)/2，于是從y中抽到兩個(gè)字母都為A的概率為[NA(NA -1)]/[n(n-1)]，..因此,從y中抽到兩個(gè)相同字母的概率為  (∑?〖??(???1)〗)/(?(??1))

這個(gè)數(shù)據(jù)稱為這份密文的重合指數(shù)，記為IC(Y)

2.2重合指數(shù)法原理

26個(gè)英文字母出現(xiàn)頻率表                                                                 重合指數(shù)公式

（1）根據(jù)頻率表，我們可以計(jì)算出英語(yǔ)文本的重合指數(shù)為0.065。

（2）利用重合指數(shù)推測(cè)密鑰長(zhǎng)度的原理在于，對(duì)于一個(gè)由凱撒密碼加密的序列，由于所有字母的位移程度相同，所以密文的重合指數(shù)應(yīng)等于原文語(yǔ)言的重合指數(shù)。

（3）假設(shè)y=y1 y2...yn是由  Vigenere 密碼得到的長(zhǎng)度為n的密文。將y按列排成一個(gè)m*(n/ m)的矩形陣列，各行分別記為y1，y2...ym.如果m確實(shí)是密鑰字的長(zhǎng)度，則yi中的各個(gè)密文字母都是由同一個(gè)密鑰的移位加密方式得到的。矩陣的每一行對(duì)應(yīng)于子串yi，1≤i≤m。

（4）另一方面，如果m不是密鑰字的長(zhǎng)度，則 yi中的各個(gè)密文字母將是由不同密鑰以移位加密方式得到的， yi 中的各個(gè)密文字母看起來更隨機(jī)一些。對(duì)于一個(gè)隨機(jī)的英文字母串，其重合指數(shù)為0.038。

（5）因?yàn)?.065和0.038相差較遠(yuǎn)，所以我們一般能夠確定密鑰字的長(zhǎng)度，或者說我們能夠確定由 Kasiski 測(cè)試法得到的密鑰字的長(zhǎng)度的正確性。

3擬重合指數(shù)測(cè)試法

擬重合指數(shù)測(cè)試法：首先子密文段重各個(gè)字母的頻率進(jìn)行統(tǒng)計(jì)（記為fi, i∈a – z），查看字母頻率分布統(tǒng)計(jì)概率(記pi)，計(jì)算子密文段長(zhǎng)度為n，使用公式：

計(jì)算出M0，然后對(duì)子密文段移位25次，同樣按照上述方法求出M1 — M25的值

根據(jù)重合指數(shù)的定義知：一個(gè)有意義的英文文本，M ≈0.065，所以利用這個(gè)規(guī)律，就可以確定秘鑰中的每一個(gè)字母

代碼實(shí)現(xiàn)

def main():
 fo=open("cipher.txt","r")
 s=fo.read()
 s=str(s)
 fo.close()
 ic=0
 max_num=len(s)//26
 # while ic<0.06:
 #def fenzu():
 #分組
 aves=[0]*max_num
 for i in range(1,max_num):
  count = 0
  zicuan=[]
  for t in range (i):
   fz=s[t:len(s):i]
   zicuan+=[fz]
   count+=1
   #print(count,'韓庚韓庚韓庚',zicuan)
  for js in range (i):
   zicuan[js]=zicuan[js].upper()
  ics=[0]*count
  #統(tǒng)計(jì)每個(gè)分組的IC值
  for r in range(count):
   ics[r]=tongjicisu(zicuan[r])
  ave =sum(ics)/count
  print('第{}次分片的IC值是{}'.format(i,ave))
  aves[i-1]=ave
 #找到最可能的密鑰分組
 key_index=1
 max = 1
 for i in range(max_num):
  max1=abs(aves[i]-0.065)
  if max1<max:
   max=max1
   key_index=i+1
 print('key_length',key_index)
 key = [None]*key_index
 #得到密鑰長(zhǎng)度后從新按密鑰長(zhǎng)度分片計(jì)算
 zicuan2 = []
 for t in range(key_index):
  fz = s[t:len(s):key_index]
  zicuan2 += [fz]
 for i in range(key_index):
  key[i]=decode(zicuan2[i])
 print(key)
 di = {}.fromkeys(key)
 key=di.keys()
 keys=""
 for i in key:
  keys+=i
 
 print(keys,"密鑰")
 mc = VigenereDecrypto(s,keys)
 print(mc,'ecewew')
 
# 統(tǒng)計(jì)次數(shù)IC值
def tongjicisu(s):
 tongjicisu = [0] * 26
 zff = ""
 ic=-0
 for t in s:
  if 65 <= ord(t) <= 90:
   zff += t
 for cisu in zff:
  tongjicisu[ord(cisu) - 65] += 1
 for i in range (len(tongjicisu)):
  xic=tongjicisu[i]*(tongjicisu[i]-1)/len(zff)/(len(zff)-1)
  ic+=xic
 return ic
 
def decode(s):
 nicos=[0]*26
 for i in range(26):
  nicos[i]=tongjinichonghe(i,s)
 list1=sorted(nicos)
 num = nicos.index(list1[-1])
 ch = chr(num+65)
 #print(ch)
 return ch
#計(jì)算擬重合指數(shù)
def tongjinichonghe(key,s):
 sniic=0
 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]
 tongjinichonghe = [0] * 26
 zff = ""
 #ic=-0
 #轉(zhuǎn)換為只有大寫字母的字符串
 for t in s:
  if 65 <= ord(t) <= 90:
   zff += t
 #統(tǒng)計(jì)每個(gè)字母出現(xiàn)的次數(shù)
 for cisu in zff:
  tongjinichonghe[ord(cisu) - 65] += 1
 #求出每個(gè)凱撒加密的解密，根據(jù)擬重合指數(shù)找到正確的密鑰
 list0=tongjinichonghe
 list1=[0]*26
 for i in range (26):
  list1[i]=list0[(i+key)%26]
 tongjinichonghe=list1
 for i in range (len(tongjinichonghe)):
  niic=tongjinichonghe[i]/len(tongjinichonghe)*p[i]
  sniic+=niic
 return sniic
 
def VigenereDecrypto(ciphertext, key):
 msLen = len(ciphertext)
 keyLen = len(key)
 key = key.upper()
 raw = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"# 密文空間
 plaintext = ""
 for i in range(0, msLen):# 開始解密
  # 輪詢key的字符
  j = i % keyLen
  # 判斷字符是否為英文字符，不是則直接向后面追加且繼續(xù)
  if ciphertext[i] not in raw:
   plaintext += ciphertext[i]
   continue
  decodechr = chr((ord(ciphertext[i]) - ord("A") - ord(key[j]) - ord("A")) % 26 + ord("A"))
  # 追加字符
  plaintext += decodechr
 # 返回加密后的字符串
 return plaintext
 
if __name__ == '__main__':
 main()

看完了這篇文章，相信你對(duì)“如何使用python實(shí)現(xiàn)維吉尼亞算法”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！