基于字母頻率的單表替換密碼破譯算法*

吳俊斌　吳　晟　吳興蛟

(昆明理工大學(xué)信息工程與自動化學(xué)院　昆明　650500)

?

基于字母頻率的單表替換密碼破譯算法*

吳俊斌吳晟吳興蛟

(昆明理工大學(xué)信息工程與自動化學(xué)院昆明650500)

摘要替換式加密根據(jù)加密構(gòu)成方式可分為移位、仿射、隨機(jī)三類。論文對替換式加密的密文進(jìn)行破譯求解,主要依靠字母頻率分布。對于移位采用對比統(tǒng)計(jì)字母的各移位數(shù),在此基礎(chǔ)之上確定移位數(shù)眾數(shù)從而作為最終移位數(shù)。對于仿射、隨機(jī)而言,不能簡單獲得所有位置的各個(gè)位移數(shù)。故而只有在此基礎(chǔ)上,依據(jù)大數(shù)據(jù)樣本高穩(wěn)定性的特點(diǎn),確定文中出現(xiàn)概率居前兩位的字符與統(tǒng)計(jì)中前兩位字符對應(yīng)。在此基礎(chǔ)上,采用歐幾里得輾轉(zhuǎn)除余法求解仿射。隨機(jī)加密則采用數(shù)據(jù)字典進(jìn)行查找分析。最后得到解密明文。最后的求解結(jié)果是,對于移位、仿射由于加密較為簡單且變化有規(guī)律所以求解準(zhǔn)確率較高,而隨機(jī)需要對比計(jì)算,故而速度以及準(zhǔn)確率有較大的不確定性,同時(shí)需求時(shí)間較長。

關(guān)鍵詞替換式加密; 密文破譯; 字母統(tǒng)計(jì)規(guī)律; 輾轉(zhuǎn)除余法; 移位加密

Class NumberTP309.7

1　引言

單字母替換加密是替換式密碼編碼中最簡單的一種形式,根據(jù)加密構(gòu)成方式又可將其細(xì)分為移位、仿射、隨機(jī)三類[1]。同時(shí)根據(jù)加密替換表的不同而分為了單表替換式和多表替換。其中,單表替換方式特點(diǎn)較為突出,是每個(gè)字母都映射一個(gè)唯一的與之對應(yīng)的字母,這樣就存在了相應(yīng)的破譯規(guī)律。依據(jù)其特點(diǎn)結(jié)合英文字符統(tǒng)計(jì)頻率進(jìn)行處理。對密文進(jìn)行相應(yīng)的破譯。三種不同的加密方式各有其相應(yīng)特點(diǎn)。結(jié)合字母頻率同時(shí)結(jié)合各個(gè)不同加密方式的特點(diǎn)對此進(jìn)行破譯[2]。

2　單字母替換加密

2.1移位加密

移位加密是其中一種最簡單的加密方式。其主要加密過程符合以下公式:

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

(1)

其中Z26表示26個(gè)字母集合;m為加密前的字符;Ek(m)為加密后的字符;K為移位數(shù)。

2.2仿射加密

仿射密碼(affine cipher)作為單表替換密碼的一個(gè)加密方式,它相對于移位密碼單一參數(shù)復(fù)雜度相對變強(qiáng)。仿射密碼為一種線性變換。其中,仿射密碼的明文空間和密文空間與移位密碼是相同的,但是加密的密鑰空間為雙參數(shù)[3]。

在此假設(shè)明文元素集為M,密文元素集為C,密鑰空間K,26個(gè)字母分別與0、1、2…對應(yīng),E為加密集合,D為解密集合,明文空間為Z26,gcd()為輾轉(zhuǎn)相除函數(shù),有以下關(guān)系:

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

(2)

其中單個(gè)字母的加密過程為

E(x)=(k1m+k2)mod26

(3)

2.3隨機(jī)替換加密

隨機(jī)密碼的加密主要是運(yùn)用字母對照表進(jìn)行加密,將不同字母隨機(jī)映射為不同的對應(yīng)關(guān)系,通過不同的對應(yīng)關(guān)系的處理,從而對文章進(jìn)行加密。隨機(jī)加密過程關(guān)鍵在于對于字符表的構(gòu)建。其中E(x)為加密后的順序字符,randperm為隨機(jī)生成函數(shù),也就是生成不重復(fù)的一組隨機(jī)值?？蓸?gòu)想于公式生成[4]。

E(x)=96+randperm(26)

(4)

生成新的對應(yīng)關(guān)系之后,將其與字符表順序?qū)?yīng)即可。就是所給出的字符對應(yīng)關(guān)系表。此舉便可完成隨機(jī)加密。

2.4加密實(shí)現(xiàn)與仿真

1) 先將原文用標(biāo)點(diǎn)符號進(jìn)行分割,存放在Matlab的cell單元里面,這樣將原文切割成一個(gè)個(gè)的短句。

2) 然后短句用空格為標(biāo)識進(jìn)行分割,存放在Matlab的cell單元里面,這樣獲得單詞。

3) 最后將單詞隔離成一個(gè)一個(gè)的單詞,這樣原文變成一個(gè)以字母有單位的字符集合。

4) 對應(yīng)表2,將a字母對應(yīng)0,b字母對應(yīng)1,依次類推,將字母數(shù)字化。

5) [見以下不同步驟]。

6) 之后就是還原文段,根據(jù)原文每個(gè)字母的長度還原這個(gè)字符集合的單詞、空格和標(biāo)點(diǎn)。

7) 到此,密文文段生成,包含空格和標(biāo)點(diǎn)。

對于5)而言,不同的加密方式步驟不同。

(1)移位加密:依照移位密碼的原理,每一個(gè)字母都加上一個(gè)相同的k值,超過25位之后,移到26位的時(shí)候?yàn)?,移到27位為1,依次類推,一一對應(yīng),就可以將原文的所有字母置換成了其他的字母,這里加密成功。

(2)仿射加密:設(shè)置等比位移向量。每次遞增不同步長值[5]。

(3)隨機(jī)加密:先生成對應(yīng)的字母對應(yīng)表,然后使用替換方式加密每個(gè)字符。

3　字母頻率

各個(gè)字母在各類文本材料中出現(xiàn)的頻率,統(tǒng)計(jì)后得出的值統(tǒng)稱為字母頻率[6]。其得出有益于得到密文中的基本對應(yīng)關(guān)系,從而降低破譯難度。關(guān)于字母頻率的統(tǒng)計(jì)數(shù)據(jù)一般有以下幾個(gè)項(xiàng)目:美國康奈爾大學(xué)數(shù)學(xué)探索項(xiàng)目(Math Explorer’s Project)對40000個(gè)單詞進(jìn)行的統(tǒng)計(jì)分析;牛津大學(xué)出版社分析的簡明牛津詞典的詞條統(tǒng)計(jì);Algoritmy網(wǎng)站進(jìn)行的統(tǒng)計(jì)分析。幾個(gè)網(wǎng)站的分析結(jié)果大同小異,在此引用Algoritmy網(wǎng)站分析結(jié)果作為依據(jù)。

圖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個(gè)字母分類為五個(gè)區(qū)間。

根據(jù)其柱狀圖的明顯區(qū)間分別確定四個(gè)閾值點(diǎn):10%、5%、4%。1%。由四個(gè)閾值可以確定五個(gè)區(qū)間。在10%以上為極高頻率;在區(qū)間5%～10%為高等頻率;在區(qū)間4%～5%為中等頻率;在區(qū)間1%～4%為低等頻率;在1%以下為極低頻率。

表1　字母頻率分類

通過表1可以看出,極高頻率與較高頻率之間存在著明顯的區(qū)間,所以取值的話取前兩個(gè)就可以了。

4　基于字母頻率的單表替換密碼解密

4.1移位解密

為了對字母進(jìn)行相應(yīng)的移位解密,故而對字母順序進(jìn)行如表2排序。

表2　字母排序表

由于通過移位加密后的明文和密文都是環(huán)Z26集合的元素。同時(shí)在移位的過程中,大于25就沒有意義了,所以移到26位的時(shí)候?yàn)?,移到27位為1,依次類推,所以再怎么移動,結(jié)果都在環(huán)Z26集合當(dāng)中。

此處做出假設(shè),明文元素集為M,密文元素集為C,密鑰空間K(即:移位的位數(shù)集合),然后26個(gè)字母分別與0、1、2…對應(yīng),E為加密集合,D為解密集合,解密公式為

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

(5)

所以由上面的分析可以將通過頻率一一對應(yīng)之后已經(jīng)生成的初期的解密文段,與密文原始的字母比較移位了多少位,從而獲得k的值。

4.2仿射解密

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

(6)

(7)

從式(7)可以看出,k1=1的時(shí)候即為移位密碼,而k2則稱作乘法密碼[7～8]。

k1的乘法逆元素只存在k1與26互質(zhì)條件下。所以可以得到?jīng)]有k1的限制,那么有可能就無法解密。這樣就輕易地獲得了解密方程逆于加密方程:

=xmodm

(8)

從上面對仿射密碼的分析了解,同時(shí)由上一節(jié)獲得的最高頻率的字母作為e,第二高頻率的字母為t,就可以對一段經(jīng)過單字母加密的密文進(jìn)行解密了。

已知最高頻率的字母m1與e對應(yīng),第二高頻率的字母m2與t相對應(yīng),同時(shí)通過表2匹配后,e=4,t=19,根據(jù)加密過程可以獲得以下方程組:(其中假設(shè)key為對應(yīng)字母在字母表的下標(biāo)):

(9)

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

(10)

根據(jù)上面的式子可知,密文中m1和m2的值與現(xiàn)有原文進(jìn)行匹配便可知道,所以這里只有兩個(gè)未知數(shù)k1和k2,通過式(9)、式(10)進(jìn)行求解。

這樣可以求出密鑰空間K(k1,k2)。接下來通過解密過程,對全段密文進(jìn)行解密,便可獲得原文。

4.3隨機(jī)替換解密

對于隨機(jī)加密算法而言,其加密是通過明文和替換表組合完成,沒有其規(guī)律可言,所以在求解的時(shí)候可使用COCA美國當(dāng)代英語語料庫的詞典對生成的單詞進(jìn)行詞頻和句子合理性分析。由于密文是由單字母進(jìn)行加密的,這樣明確了替換表的類型,通過利用針對單表替代密碼的方法進(jìn)行破譯處理。

1) 將密文中含有最高頻率的字母和第二高頻率字母的單詞分別存儲在集合Ce和Ct中;

2) 將字典中含有e和t字母的單詞分別存儲在集合Dice和Dict中;

3) 匹配捕獲的密文單詞集合Ce與字典單詞集合Dice中單詞長度相同的存儲在對應(yīng)關(guān)聯(lián)表Te中,同時(shí)匹配捕獲的密文單詞Ct與字典單詞集合Dict中長度相同的存儲在對應(yīng)關(guān)聯(lián)表Tt中;

4) 再對獲得的關(guān)聯(lián)表Te中篩選密文單詞變?yōu)閑所在位置與對應(yīng)字典中單詞e所在位置相同的關(guān)系集合Re,同理篩選出密文單詞變?yōu)閠所在位置與對應(yīng)字典中單詞t所在位置相同的關(guān)系集合Rt;

5) 將獲得的集合Re中密文字母對應(yīng)最少的一組,根據(jù)統(tǒng)計(jì)學(xué)的原理,一般出現(xiàn)的為單詞最長的字母,這樣就可以確定密文的單詞可以映射為字典中的單詞,并可以找到出e以為其他字母的關(guān)系。同理,可以獲得集合Rt中密文字母對應(yīng)最少的一組,同樣可以找到出e以為其他字母的關(guān)系。

6) 依次找到更多的單詞進(jìn)行匹配查找,從而獲得26個(gè)字母的密文和原文的對應(yīng)關(guān)系,從而解密原文。

5　結(jié)語

該模型是基于字母頻率的解密方式[9～11],在對于字母頻率不足以匹配規(guī)律的短文章的處理之上有其自身的不足。在對于移位模型的求解之中,采用的是求眾數(shù)的方式確定移位數(shù),在統(tǒng)計(jì)過程中較為穩(wěn)定,但是其耗時(shí)較大,可考慮在統(tǒng)計(jì)的基礎(chǔ)上,對于其考慮匹配對數(shù)給予優(yōu)化。對于仿射加密,采用的主要方式是公式的逆向求解,在過程中所存在的問題是對于取模以后的還原。對此可考慮結(jié)合頻率來求解得到兩組對應(yīng)關(guān)系求解,此關(guān)系對于密文字母頻率依賴較大。對于隨機(jī)加密,所采用的是數(shù)據(jù)字典的匹配以及搜索,在求解過程中,數(shù)據(jù)字典的尺寸與求解的準(zhǔn)確度具有較大關(guān)系,此次采用5K詞的詞典進(jìn)行求解,在以后可以考慮采用更大的字典進(jìn)行匹配。從而達(dá)到更高的匹配率。

參 考 文 獻(xiàn)

[1] Paul Garrett.密碼學(xué)導(dǎo)引[M].北京:機(jī)械工業(yè)出版社,2003:1-48.

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

[2] 劉嘉勇.應(yīng)用密碼學(xué)[M].北京:清華大學(xué)出版社,2008:1-37.

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

[3] 李超.密碼函數(shù)的安全性指標(biāo)分析[M].北京:科學(xué)出版社,2011:23-35.

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

[4] Willianm Stallings.密碼編碼學(xué)與網(wǎng)絡(luò)安全——原理與實(shí)踐[M].北京:電子工業(yè)出版社,2012:1-67.

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

[5] 王如濤.仿射密碼的實(shí)現(xiàn)[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].現(xiàn)代計(jì)算機(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] 威廉·費(fèi)勒.概率論及其應(yīng)用[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] 鄭東.密碼學(xué)——密碼算法與協(xié)議[M].北京:電子工業(yè)出版社,2009:1-25.

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

[11] 姜啟源.數(shù)學(xué)建模[M].北京:高等教育出版社,2011:1-53.

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

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

作者簡介:吳俊斌,男,研究方向:算法設(shè)計(jì)、程序設(shè)計(jì)。吳晟,男,教授,碩士生導(dǎo)師,研究方向:信息安全,數(shù)據(jù)挖掘,算法研究等。吳興蛟,男,碩士研究生,研究方向:軟件工程、算法設(shè)計(jì)、程序設(shè)計(jì)。

中圖分類號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