如何使用python實現維吉尼亞算法

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

1 Virginia加密算法、解密算法

Vigenenre密碼是最著名的多表代換密碼，是法國著名密碼學家Vigenenre發明的。Vigenenre密碼使用一個詞組作為密鑰，密鑰中每一個字母用來確定一個代換表，每一個密鑰字母被用來加密一個明文字母，第一個密鑰字母加密第一個明文字母，第二個密鑰字母加密第二個明文字母，等所有密鑰字母使用完后，密鑰再次循環使用，于是加解密前需先將明密文按照密鑰長度進行分組。

密碼算法可表示如下：。

設明文串為：

M=m1m2…mn，mi∈charset, n是明文長度

秘鑰為：

K=k1k2…kd，ki∈charset, d是秘鑰長度

密文為：

C=c1c2…cn，ci∈charset, n是密文長度

加密算法:

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

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

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

解密算法：

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

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

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

加解密代碼如下

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
  # 判斷字符是否為英文字符，不是則直接向后面追加且繼續
  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
  # 判斷字符是否為英文字符，不是則直接向后面追加且繼續
  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)
 # 讀取測試文本文檔
 message = open("test.txt","r+").read()
 print("讀取測試文本文檔:test.txt")
 print("開始加密！")
 # 輸入key
 key = input("請輸入密鑰：")
 # 進入加密算法
 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()
 # 進入解密算法
 print("開始解密！")
 Plaintext = VigenereDecrypto.VigenereDecrypto(Ciphertext, key)
 P = open("PlainText.txt", "w+")
 # 寫入解密文本文檔
 P.write(Plaintext)
 P.close()
 print("解密后得到的明文是 : \n" + Plaintext)
if __name__=="__main__":
 main()

2重合指數法

2.1重合指數

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

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

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

這個數據稱為這份密文的重合指數，記為IC(Y)

2.2重合指數法原理

26個英文字母出現頻率表                                                                 重合指數公式

（1）根據頻率表，我們可以計算出英語文本的重合指數為0.065。

（2）利用重合指數推測密鑰長度的原理在于，對于一個由凱撒密碼加密的序列，由于所有字母的位移程度相同，所以密文的重合指數應等于原文語言的重合指數。

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

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

（5）因為0.065和0.038相差較遠，所以我們一般能夠確定密鑰字的長度，或者說我們能夠確定由 Kasiski 測試法得到的密鑰字的長度的正確性。

3擬重合指數測試法

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

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

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

代碼實現

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
  #統計每個分組的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
 #得到密鑰長度后從新按密鑰長度分片計算
 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')
 
# 統計次數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
#計算擬重合指數
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
 #轉換為只有大寫字母的字符串
 for t in s:
  if 65 <= ord(t) <= 90:
   zff += t
 #統計每個字母出現的次數
 for cisu in zff:
  tongjinichonghe[ord(cisu) - 65] += 1
 #求出每個凱撒加密的解密，根據擬重合指數找到正確的密鑰
 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
  # 判斷字符是否為英文字符，不是則直接向后面追加且繼續
  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()

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