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—） ，男，内蒙古乌兰察布人，中级，硕士，研究方向为密码学、计算机原理。