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

張宏偉 孔祥龍

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

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

中圖分類號(hào)：TP309.7? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）11-0041-02

1 算法思想

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

1） 給定明文，例如：BUYYOUTUBE

2） 給定密鑰，例如：GOOGLE

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

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

唯密文破解步驟如下：

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

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

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

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

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

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

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

2） 確定密鑰字符間距

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

可以通過計(jì)算重合指數(shù)精確的算出密鑰字母間的距離，原理如下：假設(shè)密鑰長(zhǎng)度為n，則明文被分為n列，每一列使用密鑰中相同的一位進(jìn)行加密，相鄰列則使用不同的密鑰加密。不妨假設(shè)第一列使用c加密，第二列使用f加密，把第一列和第二列合并計(jì)算重合指數(shù)肯定不會(huì)是0.0678，因?yàn)樗鼈兪褂貌煌荑€加密，如果把第二列的字母依次移動(dòng)1、2、3……26分別和第一列計(jì)算重合指數(shù)，共計(jì)算26次。因?yàn)榈诙幸苿?dòng)了26次，窮盡了所有可能的方式，如果第二列和第一例使用同一個(gè)字母加密，則它們的重合指數(shù)為0.0678，這時(shí)移動(dòng)的次數(shù)就是密鑰第一個(gè)字母和第二個(gè)字母的間距，依次可以計(jì)算出密鑰中所有字母的間距。

3） 確定可能的26個(gè)密鑰

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

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

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

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

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

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

3 程序設(shè)計(jì)

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

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

def VigenereDecode（p，k）： #Vigenere解密函數(shù)，傳入兩個(gè)參數(shù)，p是密文，k是密鑰

i=j=0? ? ? ? ? ? ? ? #i，j是讀取密文和密鑰中每個(gè)字母的游標(biāo)

plen = len（p）? ? ? ? #獲取密文長(zhǎng)度

klen = len（k）? ? ? ? #獲取密鑰長(zhǎng)度

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

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

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

if j >= klen ：? #密文長(zhǎng)度大于密鑰長(zhǎng)度，需要多次重復(fù)使用密鑰解密

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

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

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 測(cè)試加解密過程

使用如下測(cè)試案例，分別對(duì)密鑰長(zhǎng)度為2、3、4進(jìn)行測(cè)試。

RobisacommercialsaturationdiverforGlobalDiversinLouisianaHeperformsunderwaterrepairsonoffshoredrillingrigsBelowisanemailhesen

使用測(cè)試案例，密鑰采用te進(jìn)行加密，運(yùn)行效果如圖1所示。

使用測(cè)試案例，密鑰采用tes進(jìn)行加密，運(yùn)行效果如圖2所示。

使用測(cè)試案例，密鑰采用test進(jìn)行加密，運(yùn)行效果如圖3所示。

解密過程使用密文為：RobisacommercialsaturationdiverforGlobalDiver，密鑰為：test進(jìn)行解密，運(yùn)行效果如圖4所示。

參考文獻(xiàn)：

[1] 胡作玄.密碼中的數(shù)學(xué)[J].百科知識(shí)，2007（16）：11.

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

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

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

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

收稿日期：2021-12-20

作者簡(jiǎn)介：張宏偉（1989—） ，男，山西大同人，中級(jí)，學(xué)士，研究方向?yàn)榫W(wǎng)絡(luò)安全、應(yīng)急處置;孔祥龍（1988—） ，男，內(nèi)蒙古烏蘭察布人，中級(jí)，碩士，研究方向?yàn)槊艽a學(xué)、計(jì)算機(jī)原理。