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

吳俊斌　吳　晟　吳興蛟

(昆明理工大學信息工程與自動化學院　昆明　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