基于字母频率的单表替换密码破译算法*

吴俊斌　吴　晟　吴兴蛟

(昆明理工大学信息工程与自动化学院　昆明　650500)



基于字母频率的单表替换密码破译算法*

吴俊斌吴晟吴兴蛟

(昆明理工大学信息工程与自动化学院昆明650500)

摘要替换式加密根据加密构成方式可分为移位、仿射、随机三类。论文对替换式加密的密文进行破译求解,主要依靠字母频率分布。对于移位采用对比统计字母的各移位数,在此基础之上确定移位数众数从而作为最终移位数。对于仿射、随机而言,不能简单获得所有位置的各个位移数。故而只有在此基础上,依据大数据样本高稳定性的特点,确定文中出现概率居前两位的字符与统计中前两位字符对应。在此基础上,采用欧几里得辗转除余法求解仿射。随机加密则采用数据字典进行查找分析。最后得到解密明文。最后的求解结果是,对于移位、仿射由于加密较为简单且变化有规律所以求解准确率较高,而随机需要对比计算,故而速度以及准确率有较大的不确定性,同时需求时间较长。

关键词替换式加密; 密文破译; 字母统计规律; 辗转除余法; 移位加密

Class NumberTP309.7

1　引言

单字母替换加密是替换式密码编码中最简单的一种形式,根据加密构成方式又可将其细分为移位、仿射、随机三类[1]。同时根据加密替换表的不同而分为了单表替换式和多表替换。其中,单表替换方式特点较为突出,是每个字母都映射一个唯一的与之对应的字母,这样就存在了相应的破译规律。依据其特点结合英文字符统计频率进行处理。对密文进行相应的破译。三种不同的加密方式各有其相应特点。结合字母频率同时结合各个不同加密方式的特点对此进行破译[2]。

2　单字母替换加密

2.1移位加密

移位加密是其中一种最简单的加密方式。其主要加密过程符合以下公式:

E={E:Z26→Z26,Ek(m)=m+k(mod26)|m∈M}

(1)

其中Z26表示26个字母集合;m为加密前的字符;Ek(m)为加密后的字符;K为移位数。

2.2仿射加密

仿射密码(affine cipher)作为单表替换密码的一个加密方式,它相对于移位密码单一参数复杂度相对变强。仿射密码为一种线性变换。其中,仿射密码的明文空间和密文空间与移位密码是相同的,但是加密的密钥空间为双参数[3]。

在此假设明文元素集为M,密文元素集为C,密钥空间K,26个字母分别与0、1、2…对应,E为加密集合,D为解密集合,明文空间为Z26,gcd()为辗转相除函数,有以下关系:

K={(k1,k2)|k1,k2∈Z26,gcd(k1,26)=1}

(2)

其中单个字母的加密过程为

E(x)=(k1m+k2)mod26

(3)

2.3随机替换加密

随机密码的加密主要是运用字母对照表进行加密,将不同字母随机映射为不同的对应关系,通过不同的对应关系的处理,从而对文章进行加密。随机加密过程关键在于对于字符表的构建。其中E(x)为加密后的顺序字符,randperm为随机生成函数,也就是生成不重复的一组随机值。可构想于公式生成[4]。

E(x)=96+randperm(26)

(4)

生成新的对应关系之后,将其与字符表顺序对应即可。就是所给出的字符对应关系表。此举便可完成随机加密。

2.4加密实现与仿真

1) 先将原文用标点符号进行分割,存放在Matlab的cell单元里面,这样将原文切割成一个个的短句。

2) 然后短句用空格为标识进行分割,存放在Matlab的cell单元里面,这样获得单词。

3) 最后将单词隔离成一个一个的单词,这样原文变成一个以字母有单位的字符集合。

4) 对应表2,将a字母对应0,b字母对应1,依次类推,将字母数字化。

5) [见以下不同步骤]。

6) 之后就是还原文段,根据原文每个字母的长度还原这个字符集合的单词、空格和标点。

7) 到此,密文文段生成,包含空格和标点。

对于5)而言,不同的加密方式步骤不同。

(1)移位加密:依照移位密码的原理,每一个字母都加上一个相同的k值,超过25位之后,移到26位的时候为0,移到27位为1,依次类推,一一对应,就可以将原文的所有字母置换成了其他的字母,这里加密成功。

(2)仿射加密:设置等比位移向量。每次递增不同步长值[5]。

(3)随机加密:先生成对应的字母对应表,然后使用替换方式加密每个字符。

3　字母频率

各个字母在各类文本材料中出现的频率,统计后得出的值统称为字母频率[6]。其得出有益于得到密文中的基本对应关系,从而降低破译难度。关于字母频率的统计数据一般有以下几个项目:美国康奈尔大学数学探索项目(Math Explorer’s Project)对40000个单词进行的统计分析;牛津大学出版社分析的简明牛津词典的词条统计;Algoritmy网站进行的统计分析。几个网站的分析结果大同小异,在此引用Algoritmy网站分析结果作为依据。

图1　英文中字母频率

通过图1可以看出字母频率由大到小的排列为

e>t>a>o>i>n>s>h>r>d>l>c>u>m>w>f>g>y>p>b>v>k>j>x>q>z

通过表1也可以通过近似值可以将26个字母分类为五个区间。

根据其柱状图的明显区间分别确定四个阈值点:10%、5%、4%。1%。由四个阈值可以确定五个区间。在10%以上为极高频率;在区间5%～10%为高等频率;在区间4%～5%为中等频率;在区间1%～4%为低等频率;在1%以下为极低频率。

表1　字母频率分类

通过表1可以看出,极高频率与较高频率之间存在着明显的区间,所以取值的话取前两个就可以了。

4　基于字母频率的单表替换密码解密

4.1移位解密

为了对字母进行相应的移位解密,故而对字母顺序进行如表2排序。

表2　字母排序表

由于通过移位加密后的明文和密文都是环Z26集合的元素。同时在移位的过程中,大于25就没有意义了,所以移到26位的时候为0,移到27位为1,依次类推,所以再怎么移动,结果都在环Z26集合当中。

此处做出假设,明文元素集为M,密文元素集为C,密钥空间K(即:移位的位数集合),然后26个字母分别与0、1、2…对应,E为加密集合,D为解密集合,解密公式为

D={D:Z26→Z26,Dk(c)=c-k(mod26)|c∈C}

(5)

所以由上面的分析可以将通过频率一一对应之后已经生成的初期的解密文段,与密文原始的字母比较移位了多少位,从而获得k的值。

4.2仿射解密

基于以上加密公式。解密方程为

(6)

(7)

从式(7)可以看出,k1=1的时候即为移位密码,而k2则称作乘法密码[7～8]。

k1的乘法逆元素只存在k1与26互质条件下。所以可以得到没有k1的限制,那么有可能就无法解密。这样就轻易地获得了解密方程逆于加密方程:

=xmodm

(8)

从上面对仿射密码的分析了解,同时由上一节获得的最高频率的字母作为e,第二高频率的字母为t,就可以对一段经过单字母加密的密文进行解密了。

已知最高频率的字母m1与e对应,第二高频率的字母m2与t相对应,同时通过表2匹配后,e=4,t=19,根据加密过程可以获得以下方程组:(其中假设key为对应字母在字母表的下标):

(9)

代入e=4,t=19得到:

(10)

根据上面的式子可知,密文中m1和m2的值与现有原文进行匹配便可知道,所以这里只有两个未知数k1和k2,通过式(9)、式(10)进行求解。

这样可以求出密钥空间K(k1,k2)。接下来通过解密过程,对全段密文进行解密,便可获得原文。

4.3随机替换解密

对于随机加密算法而言,其加密是通过明文和替换表组合完成,没有其规律可言,所以在求解的时候可使用COCA美国当代英语语料库的词典对生成的单词进行词频和句子合理性分析。由于密文是由单字母进行加密的,这样明确了替换表的类型,通过利用针对单表替代密码的方法进行破译处理。

1) 将密文中含有最高频率的字母和第二高频率字母的单词分别存储在集合Ce和Ct中;

2) 将字典中含有e和t字母的单词分别存储在集合Dice和Dict中;

3) 匹配捕获的密文单词集合Ce与字典单词集合Dice中单词长度相同的存储在对应关联表Te中,同时匹配捕获的密文单词Ct与字典单词集合Dict中长度相同的存储在对应关联表Tt中;

4) 再对获得的关联表Te中筛选密文单词变为e所在位置与对应字典中单词e所在位置相同的关系集合Re,同理筛选出密文单词变为t所在位置与对应字典中单词t所在位置相同的关系集合Rt;

5) 将获得的集合Re中密文字母对应最少的一组,根据统计学的原理,一般出现的为单词最长的字母,这样就可以确定密文的单词可以映射为字典中的单词,并可以找到出e以为其他字母的关系。同理,可以获得集合Rt中密文字母对应最少的一组,同样可以找到出e以为其他字母的关系。

6) 依次找到更多的单词进行匹配查找,从而获得26个字母的密文和原文的对应关系,从而解密原文。

5　结语

该模型是基于字母频率的解密方式[9～11],在对于字母频率不足以匹配规律的短文章的处理之上有其自身的不足。在对于移位模型的求解之中,采用的是求众数的方式确定移位数,在统计过程中较为稳定,但是其耗时较大,可考虑在统计的基础上,对于其考虑匹配对数给予优化。对于仿射加密,采用的主要方式是公式的逆向求解,在过程中所存在的问题是对于取模以后的还原。对此可考虑结合频率来求解得到两组对应关系求解,此关系对于密文字母频率依赖较大。对于随机加密,所采用的是数据字典的匹配以及搜索,在求解过程中,数据字典的尺寸与求解的准确度具有较大关系,此次采用5K词的词典进行求解,在以后可以考虑采用更大的字典进行匹配。从而达到更高的匹配率。

参 考 文 献

[1] Paul Garrett.密码学导引[M].北京:机械工业出版社,2003:1-48.

Paul Garrett. Cryptography guidance[M]. Beijing: Mechanical Industry Publishing House,2003:1-48.

[2] 刘嘉勇.应用密码学[M].北京:清华大学出版社,2008:1-37.

LIU Jiayong. Applied cryptography[M]. Beijing: Tsinghua University Press,2008:1-37.

[3] 李超.密码函数的安全性指标分析[M].北京:科学出版社,2011:23-35.

LI Chao. Password function index analysis[M]. Beijing: Science Press,2011:23-35.

[4] Willianm Stallings.密码编码学与网络安全——原理与实践[M].北京:电子工业出版社,2012:1-67.

Willianm Stallings. Password encoding and network security — principle and practice[M]. Beijing: Electronic Industry Press,2012:1-67.

[5] 王如涛.仿射密码的实现[J].信息安全与通信保密,2013(1):75-77.

WANG Rutao. The realization of the affine password[J]. Journal of Information Security and Communications Confidential,2013(1):75-77.

[6] 百度百科.字母频率[EB/OL]. http://baike.baidu.com/link?url=oo2XSI2zzr7cJ0P_9YPPN5vv_uKO67lvHjPisrSB9g-fGFerg7hzN93S-YrQLP-Mnp2BZZVsisR1Rx2ZYLLR2q,2015/7/7.

[7] 胥亮.基于仿射和流密码的图像置乱算法[J].现代计算机,2006(3):83-85.

XU Liang. Based on the affine and stream cipher algorithm of image[J]. Modern Computer,2006(3):83-85.

[8] 威廉·费勒.概率论及其应用[M].北京:人民邮电出版社,2008.

Feiler William. Probability theory and its application[M]. Beijing: People’s Posts and Telecommunications Press,2008.

[9] 彭代慧.MATLAB 2013使用教程[M].北京:高等教育出版社,2014:1-303.

PENG Daihui. MATLAB 2013 using the tutorial[M]. Beijing: Higher Education Press,2014:1-303.

[10] 郑东.密码学——密码算法与协议[M].北京:电子工业出版社,2009:1-25.

ZHENG Dong. Cryptography — cryptographic algorithms and protocols[M]. Beijing: Electronic Industry Press,2009:1-25.

[11] 姜启源.数学建模[M].北京:高等教育出版社,2011:1-53.

JIANG Qiyuan. Mathematical modeling[M]. Beijing: Higher Education Press,2011:1-53.

收稿日期:2015年10月12日,修回日期:2015年11月27日

作者简介:吴俊斌,男,研究方向:算法设计、程序设计。吴晟,男,教授,硕士生导师,研究方向:信息安全,数据挖掘,算法研究等。吴兴蛟,男,硕士研究生,研究方向:软件工程、算法设计、程序设计。

中图分类号TP309.7

DOI:10.3969/j.issn.1672-9722.2016.04.005

Password Breaking Algorithm of Single Table Replacement Based on Frequency of Letters

WU JunbinWU ShengWU Xingjiao

(School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming650500)

AbstractReplace cryptographic methods can be divided according to the encryption constitute a shift, affine, random categories. This paper replacement formula to decipher the encrypted ciphertext solvd mainly rely on the frequency distribution of the letters. For rotate each shift using the comparative statistics letters to determine the number of shifts plural on this basis so as the final number of shifts. For affine, random, you can not simply get all the various shifts in the number of locations. Only on this basis, therefore, the characteristics of high stability based on a large sample of data to determine the probability and statistics ranking the first two characters in the first two characters in the corresponding text appears. On this basis, the use of more than Euclid removed except Solving affine. Random encryption is used to find the data dictionary analysis. Finally get decrypted plaintext. The final result is solved for the shift, affine since the encryption is relatively simple to solve and change regularly so high accuracy rate, and need to compare a random basis, and therefore have a greater speed and accuracy uncertainty, while demand time than long.

Key Wordsreplace encryption, cipher decoding, letters statistical rule, Euclidean algorithm, shift encryption