Vigenere加解密系統實現及唯密文破解

張宏偉 孔祥龍

摘要：Vigenere是一種以移位替換為基礎的周期替換密碼，不同于凱撒密碼的單表替換，它是一種多表替換加密算法實現Vigenere加密、解密系統并分析和評估該算法的安全性。該文通過編程實現唯密文破譯系統，能夠破譯密鑰為2～4個字符的Vigenere密文，并分析如何加快破譯過程。

關鍵詞：Vigenere;加密;解密

中圖分類號：TP309.7? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）11-0041-02

1 算法思想

Vigenere是一種以移位替換為基礎的周期替換密碼[1]，不同于凱撒密碼[2]的單表替換，它是一種多表替換加密算法，其加密過程如下：

1） 給定明文，例如：BUYYOUTUBE

2） 給定密鑰，例如：GOOGLE

3） 將明文中的字母從左到右依次用對應的密鑰位向后移動得到的字母代替，例如：B移動G位（G的字母順序為6） ，對應的字母為H（B往后移動6位對應H） ;U移動O位;Y移動O位;依次類推，密鑰用完后再從密鑰開始處循環，經加密后密文為：HIMEZYZIPK。

解密和加密過程相反，把密文按照密鑰對應的位向左移動，得到明文。

唯密文破解步驟如下：

1） 確定密鑰長度（使用Kasiski測算方法或計算重合指數[3]）

Kasiski測算的依據是假設密鑰很短，如果在明文中相同的字母間距正好是密鑰長度的整數倍，則這兩個明文中相同的字母加密后的密文也相同，通過計算明文中重復子串的距離（是密鑰長度的整數倍） ，求它們的最大公約數即可獲取密鑰的長度。

重合指數即基于一個原理[1]：一篇有意義的文章中出現2個相同字母的概率為0.0678，而一篇隨機抽取單詞組成的文章概率為0.038。

假設密鑰長度為n，加密時將明文分成n列，每一列都是用密鑰的同一個字母進行加密，這樣的一列可以等價于單表替換的情況，每一列求重合指數應為0.0678，而不同的兩列使用不同的密鑰加密，它們的結果接近于隨機文章概率0.038。所以可以計算每一列的重合指數，如果所有列的重合指數都接近0.0678，則此時的密鑰長度就是正確的。

某文章重合指數=i=azFi×（Fi-1）N×（N-1）

[Fi]是字母[i]在文章中出現的次數，[i]的取值從[a]到[z]，[N]是文章的長度。

可以結合重合指數和Kasiski測算確定密鑰的長度。

2） 確定密鑰字符間距

確定密鑰長度后，可以使用暴力破解方法，窮舉每一種可能。但是實際使用并不現實，試想如果密鑰長度為5，則可能的密鑰組合就有265=11881376種。

可以通過計算重合指數精確的算出密鑰字母間的距離，原理如下：假設密鑰長度為n，則明文被分為n列，每一列使用密鑰中相同的一位進行加密，相鄰列則使用不同的密鑰加密。不妨假設第一列使用c加密，第二列使用f加密，把第一列和第二列合并計算重合指數肯定不會是0.0678，因為它們使用不同密鑰加密，如果把第二列的字母依次移動1、2、3……26分別和第一列計算重合指數，共計算26次。因為第二列移動了26次，窮盡了所有可能的方式，如果第二列和第一例使用同一個字母加密，則它們的重合指數為0.0678，這時移動的次數就是密鑰第一個字母和第二個字母的間距，依次可以計算出密鑰中所有字母的間距。

3） 確定可能的26個密鑰

密鑰首字母依次取a，b，c……z;后邊的字母利用第2步的間距計算，可以得到26個密鑰，其中有一個就是要求解的密鑰。

2 安全性分析和密文破解優化

多表替換密碼下[4]，原來明文中的統計特性通過多個表的平均作用被隱藏起來，多表替換密碼的破譯要比單表替換密碼[5]破譯難得多。

如果密文足夠長、密鑰很短的情況下，密文中出現相同片段的概率幾乎為1，而這個相同片段很大概率是由于明文相同而它們間距又是密鑰長度整數倍導致的，很容易求得密鑰的長度。再有，文章的重合指數特性并沒有因為采用多表替換而消失，密文中同樣保留了這一特性，結合上述兩種方法，肯定能準確求出密鑰的長度。確定密鑰長度后，再利用重合指數算出密鑰字母間距，密文就被輕松破譯了。

綜上，安全的方法應該是明文盡量不要有重復字母，密鑰盡量長，如果密鑰長度和明文一樣長，則就做到了一字一密，理論上是絕對安全的。

密文破解時，在得知密鑰長度后，可以利用重合指數（而非窮舉密鑰） 獲得密鑰字母間距，從而只需要測試26個密鑰即可，大大提高了破解效率。

3 程序設計

參見：《Vigenere ED（加解密源碼） .py》和《Vigenere（密文破解源碼） .py》，使用Python 3.6及以上編程語言實現。

Vigenere ED（加解密源碼） 核心代碼如下：

def VigenereDecode（p，k）： #Vigenere解密函數，傳入兩個參數，p是密文，k是密鑰

i=j=0? ? ? ? ? ? ? ? #i，j是讀取密文和密鑰中每個字母的游標

plen = len（p）? ? ? ? #獲取密文長度

klen = len（k）? ? ? ? #獲取密鑰長度

newp = list（p）? ? ? ?#字符串不能修改單個字母，將p打成列表，可以單個修改字母

while i < plen：? ? ? #遍歷密文

if newp[i].isalpha（） ： #如果是字母則解密

if j >= klen ：? #密文長度大于密鑰長度，需要多次重復使用密鑰解密

j = j % klen? #重復取密鑰

if newp[i].lower（） < k[j].lower（） ： #加密后的字母在密鑰字母前，說明加密時和26進行過模運算

newp[i] = chr（（（ord（newp[i].lower（））-ord（'a'））+26-（ord（k[j].lower（））-ord（'a'）））+ord（'a'）） #解密

else ：

newp[i] = chr（（（ord（newp[i].lower（））-ord（'a'））-（ord（k[j].lower（））-ord（'a'）））+ord（'a'）） #解密

i+=1

j+=1

else：? ?#非字母，不做任何改變

i+=1

c = ''.join（newp）? #將list拼裝為字符串，此為明文

print（'明文：'，c）? ?#輸出明文

print（''）

4 測試加解密過程

使用如下測試案例，分別對密鑰長度為2、3、4進行測試。

RobisacommercialsaturationdiverforGlobalDiversinLouisianaHeperformsunderwaterrepairsonoffshoredrillingrigsBelowisanemailhesen

使用測試案例，密鑰采用te進行加密，運行效果如圖1所示。

使用測試案例，密鑰采用tes進行加密，運行效果如圖2所示。

使用測試案例，密鑰采用test進行加密，運行效果如圖3所示。

解密過程使用密文為：RobisacommercialsaturationdiverforGlobalDiver，密鑰為：test進行解密，運行效果如圖4所示。

參考文獻：

[1] 胡作玄.密碼中的數學[J].百科知識，2007（16）：11.

[2] 張石生，陳玉清.增生型映象方程研究的重合指數方法[J].數學年刊A輯（中文版），1993，14（5）：579-583.

[3] 何曉琴，陸一南.一種新式Vigenere密碼的破譯和研究[J].計算機科學，2013，40（12）：208-210.

[4] 韓磊.一種隨機密碼表庫多表替換字符加密思想[J].科技傳播，2011，3（13）：229，222.

[5] 王朝陽，張遠.單表代替密碼技術在表意文字加密中的應用——應用動態變化的文字映射表[J].科技創新與應用，2015（36）：47-48.

收稿日期：2021-12-20

作者簡介：張宏偉（1989—） ，男，山西大同人，中級，學士，研究方向為網絡安全、應急處置;孔祥龍（1988—） ，男，內蒙古烏蘭察布人，中級，碩士，研究方向為密碼學、計算機原理。