Vigenere加解密系統(tǒng)實現(xiàn)及唯密文破解

張宏偉 孔祥龍

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

關(guān)鍵詞：Vigenere;加密;解密

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

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

1 算法思想

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

1） 給定明文，例如：BUYYOUTUBE

2） 給定密鑰，例如：GOOGLE

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

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

唯密文破解步驟如下：

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

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

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

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

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

[Fi]是字母[i]在文章中出現(xiàn)的次數(shù)，[i]的取值從[a]到[z]，[N]是文章的長度。

可以結(jié)合重合指數(shù)和Kasiski測算確定密鑰的長度。

2） 確定密鑰字符間距

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

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

3） 確定可能的26個密鑰

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

2 安全性分析和密文破解優(yōu)化

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

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

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

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

3 程序設(shè)計

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

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

def VigenereDecode（p，k）： #Vigenere解密函數(shù)，傳入兩個參數(shù)，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 ：? #密文長度大于密鑰長度，需要多次重復(fù)使用密鑰解密

j = j % klen? #重復(fù)取密鑰

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] 胡作玄.密碼中的數(shù)學[J].百科知識，2007（16）：11.

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

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

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

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

收稿日期：2021-12-20

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