基于正向最大匹配算法的密碼破譯*

吳興蛟　吳　晟

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

?

基于正向最大匹配算法的密碼破譯*

吳興蛟吳晟

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

摘要論文運用基于正向最大匹配算法的破譯方式,進行分詞。同時基于單詞頻率進行差錯更改及控制。其中主要步驟如下: 1) 編制符合要求的密文; 2) 進行替換解密; 3) 基于詞庫分詞,同時進行差錯仿真; 4) 構建句子。首先基于編碼原理進行密文編寫,同時進行隨機差錯制造。最后將分析后的結果存入文本,處理之后得到部分與原文進行對比,發現其錯誤率較低。故而所得模型其可靠度較高。文章主要工作在于構建一個較為可靠的具有較強普適性的基于字符頻率的最大正向分詞模型。同時在此基礎上建立其余模型共同解決問題。

關鍵詞英文分詞; 字符頻率; 字典優化; 替換解密; 正向最大匹配

Class NumberTP309.7

1引言

基于單字母替換加密的密文,密文中不存在間隔或是標點,僅僅是一串很長的英文字符串。同時在日常傳輸過程中會碰到各種復雜的環境,在通過這些環境的時候,往往密文會受到來自環境干擾:可能在傳輸過程中的字符串中的字符隨機丟失、在傳輸之后在其中添加如字符、或是更改字符串內的字符[1]。這樣的話,在獲得這一類干擾后的密文后,要還原它原本的文段,處理如此大的數據,就需要設計一定的算法[2～3],通過計算機來解密匹配[4]。

明文是由26個字母的單詞所構成的文段,并且文段是通過了單字母替換加密密文,加密之后沒有間隔和標點,所以所生成的密文是一段很長的字符串。然后這段連續的字符串在傳輸的過程收到了一定的干擾,字符串中字符出現丟失,插入或者更改。要求需要:設計合理效率的數學模型,處理破譯受到干擾的密文,修復其中的錯誤突變,分割出單詞,還原文段。

2解密模型的建立

本文將受干擾密文的破解還原轉化為離散數學求解問題,由于所獲得的密文是沒有間隔和標點的字符串,并且字符串有一定的變異(添加字符,刪除字符,更改字符)。故首先需要先破解翻譯密文得到相應的原文字母,其次針對干擾的變異和沒有標點間隔,需要對字符串從左到右的字母與數據庫進行匹配比對,從而檢索獲得并分割出單詞[5]。

此模型的建立包括:

· 基于字母頻率的密文字母還原；

· 干擾概率極限；

· 字典庫的優化處理；

· 基于單詞頻率的字符串分割；

· 基于最大匹配算法的單詞匹配。

以下為對各模型的詳細描述。

2.1基于字母頻率的密文字母還原

1) 英文字母頻率

對于一個較長的文段,其中每個字母的出現頻率是不一樣的,經過統計之后不難得到(參見圖1——引自Algoritmy網站),e的出現頻率是最高的,然后嘗試將密文中,出現頻率最高的字母替換成字母e,以此類推,對密文的進行替換,對一些字母進行一定的假設,最終獲得加密后的原文。

圖1　英文中字母頻率

2) 移位密碼解密

由于通過移位加密后的明文和密文都是環Z26集合的元素。同時在移位的過程中,大于25就沒有意義了,所以移到26位的時候為0,移到27位為1,依次類推,所以再怎么移動,結果都在環Z26集合當中。

假設明文元素集為M,密文元素集為C,密鑰空間K(即移位的位數集合),然后26個字母分別與0，1，2，…，E為加密集合,D為解密集合。

加密過程:

(1)

解密過程:

(2)

所以由上面的分析可以將通過頻率一一對應之后已經生成的初期的解密文段,與密文原始的字母比較移位了多少位,從而獲得k的值。由于文段的特殊性關系,所以k的數值會有所不同,那么通過統計學原理[6]獲得其中k的出現次數最多的作為解碼k值,通過解碼過程更準確地獲取完整的、正確的明文。而且它的正確率可以達到100%。

3) 基于輾轉相除法的仿射密碼解碼

假設明文元素集為M,密文元素集為C,密鑰空間K,26個字母分別與0，1，2，…，E為加密集合,D為解密集合,明文空間為Z26,gcd()為輾轉相除法:

(3)

英文明文空間為26個字母,單個字母的加密過程為

E(x)=(k1m+k2)mod26

(4)

k1的值必須使得a與m互質。解密方程為

(5)

其中，k1-1為k1取模26的模反元素,關系公式為:

(6)

從上式可以看出,k1=1的時候即為移位密碼,而k2則稱作乘法密碼。

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

D(E(x))=k-11(E(x)-k2)modm

=xmodm

(7)

從上面對仿射密碼的分析了解,同時由上一節獲得的最高頻率的字母作為e,第二高頻率的字母為t,這些知識就可以對一段經過單字母加密的密文進行解密了。

已知最高頻率的字母m1與e對應,第二高頻率的字母m2與t相對應,同時通過表1匹配后,e為4,t為19,根據加密過程可以獲得以下方程組(其中假設key為對應字母在字母表的下標):

(8)

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

(9)

根據上式可知,密文中m1和m2的值現有原文進行匹配便可知道,所以這里只有兩個未知數k1和k2,通過這兩個式子用計算進行求解。

這樣求可以求出密鑰空間K(k1,k2)。接下來通過解密過程,對全段密文進行解密,便可獲得原文。已知密鑰空間K(k1,k2),所以它的正確率可以達到100%。

2.2基于詞庫匹配的隨機替換密碼解密

同基于字母頻率的移位密碼解密一樣,對密文進行字母的出現頻率統計,并與圖1英文中字母頻率圖進行匹配。根據圖1可以發現,e出現的頻率為12.702%,出現頻率極高,其次t出現頻率為9.056%,出現也是頻率也是很高的,而且同時e和t之間的差距很大,在一段較長的文段中就很有代表性。再通過統計學原理,出現頻率越高的字母與之對應的關系越高,具有很強穩定性。可以選擇密文統計中最高頻率的字母作為e,第二高頻率的字母為t。分別篩選出字典庫中e、t為首字母的單詞,以此進行匹配,從而找到單詞中其他單詞的對應關系,最終獲得26個字母的密文和原文的對應關系,從而解密原文。

2.3干擾概率極限

根據問題所知,字符串中的字符隨機丟失的概率為p1,在傳輸之后在其中添加如字符的概率為p2,更改字符串內字符的概率為p3,正常傳輸的概率為1-p1-p2-p3,但是這些干擾的概率總和需要控制在一定的閾值范圍內,需要建模計算出干擾頻率的極限值,這樣才能控制之后模型的破譯方法及能力。

英文密文的字母還原是基于字母頻率完成,并且都用到了其中出現頻率最高的兩個字母e和t進行建模。然而從圖1英文中字母頻率可知,e出現頻率為12.702%,t出現的頻率為9.056%,作為出現頻率第三大的字母a出現頻率為8.167%,為了避免由于干擾而致使解碼所用到的出現頻率最高的兩個字母出現突變,不因為干擾致t的頻率增加超越e,或者a的頻率增加超越t之類,都會致使密文字母還原出現錯誤,所以干擾頻率必須滿足式(10):

∑p1,p2,p3

(10)

2.4字典庫的優化處理

前文已經通過算法破解獲得了原文段的字母,但是由于之前的密文是沒有間隔和標點,字母都是連在一起的字符串,還原字母之后也同樣字母是連續的,閱讀者無法看到每一個單詞,無法閱讀。同時由于密文是受到過干擾,密文字符串中存在字母丟失、字母增加、字母更改,還原同樣存在著這些問題[7]。

要解決這兩點問題,就需要將字符串的字母元素集與數據字典庫進行匹配,解出并分割出每一個單獨的單詞,同時將其中的遍地的字母還原,形成正確的文段。

通過題目中的資料獲得美國當代英語語料庫(COCA)的單詞字典,由于它分成了很多的文件,接下來就要對這個字典進行處理。首先將所有的單詞匯總到一個文件中;其次由于存在重復的,就用算法把重復的單詞去除,優化字典的數量,使今后的檢索效率提高[8]。

為了再次提高字典庫的檢索效率,再將字典庫中的單詞按首字母a,b,c,d…進行分割成26組,這樣的話只用知道首字母就可以直接找到對應的單詞集合,大大降低了全文檢索的速度。

假設大字典為D,以首字母分割后的字典表為da,db,dc,…,dz且滿足:

D={d1,d2,d3,…,dn}

(11)

為了滿足之后的最大匹配算法(Maximum Matching),還需要再對字典庫進行優化。用分成的26組,各個首字母的單詞組計算出各單詞的長度,然后由長到短的順序進行排列,生成最終的優化字典庫。如下為字典庫優化的流程圖。

圖2　字典庫優化的流程圖

2.5基于單詞頻率的字符串分割

對于一篇文段,其中每個單詞的出現頻率都是不一樣的,經過統計之后不難得到。以下為英語最常用單詞列表中的內容是基于牛津在線和牛津英語詞典對牛津英語語料庫中超過10億的單詞所作的分析研究。抽取出單詞出現頻率最高的前15單詞[9]:

表1　Top15單詞頻率分類

圖3　Top15單詞頻率統計

從以上圖表的統計結果中可以得出在英文文段中單詞the的出現頻率是最高。這里使用頻率出現最高的單詞the作為斷句標準進行分割,用它的理由在于:

1) 首先由于文段長度過長的緣故,要在字典庫中進行逐一匹配的話,提高它的匹配效率,就要將很長的字符串分段,降低了每一段的字母數量,使每一次的字典匹配效率提高;

2) 同時使用出現頻率最高的單詞作為斷句標準的話,由于密文是受到過一定程度上的干擾的,里面存在字母突變異常,使用頻率高的單詞分割連續很長的字符串的話,還能在一定程度上降低分割字符串受到的干擾,具有一定的穩定性。

下圖為舉例說明:(見圖4分割字符串)

圖4　分割字符串

從圖4可知,將thegirlisbeautifultheyloveher這樣一段長字符串,用出現頻率最大單詞the作為分割標準,分割成成了theyloveher和thegirlisbeautiful兩段較為短的字符串,分割之后的字符串與字典庫進行比較的效率將大大提高,每次檢索時間會大大降低。

假設,長字符串為S,分割后的子字符串為s1,s2,s3…，且滿足:

S={s1,s2,s3,…,sn}

(12)

2.6基于正向最大匹配算法的單詞匹配

最大匹配算法是基于字符串匹配的分詞方法[8],它包括了正向最大匹配算法、逆向最大匹配算法、雙向匹配算法等。它的主要算法處理是分割出單字母串,用它與字典庫進行匹配,如果其中一個字母串存在于字典庫就記錄下來,否則增加或減少一個字母,再與字典庫進行匹配,一直剩下一個單詞為止。

經過之前模型獲得密文分析,破解出原文段字母,且通過單詞頻率分割了字符串,接下來就需要對所獲的每段字符串進行單詞匹配,分割出單詞,并且糾正其中出現的干擾錯誤。為了分出單詞設計了基于正向最大匹配算法[10](Forward Maximum Matching)的單詞匹配模型[11]。

使用基于正向最大匹配算法(Forward Maximum Matching)的算法思路:

1) 因為長字符串S經過了分割,取其中第一段s1,截取這段的首字母;

2) 已經獲得的以首字母為組的單詞表,是由單詞長度從長到短的排列的,通過上一步獲得的首字母,載入對應字母的單詞表d1;

3) 將單詞長度從長到短排列的單詞表d1的第一個單詞取出來,與原文段片段s1中字母從左到右檢索匹配;

4) 從最長的單詞開始匹配,如果原文片段s1中出現了可以完全匹配的單詞,就截取這個單詞,進行保存;

5) 將原文片段s1中已經匹配的這前這幾個字母去掉,剩下的字母繼續返回第2)步執行;

6) 直到原文片段s1沒有字母可以匹配,或是剩下的字母無法從字典庫中找到對應單詞,停止當前原文片段s1的檢索,此時已經將原文片段s1中的單詞基本檢索出來,可以用空格將這些字母進行分割了;

7) 到此已經結束第一段s1檢索,接下來檢索第二片段s2,以此類推直至完成所有片段的還原處理,這樣就可以將所有破解還原出原文文段,單詞之間存在間隔,可以供人們一定程度上的閱讀了。

圖5為基于正向最大匹配算法的單詞匹配流程。

圖5　基于正向最大匹配算法的單詞匹配流程

3處理結果

最后貼出原文字段以及分詞以后的字段進行效果比對,算法采用Matlab編程實現。

由上可見,除去符號以外,其分詞正確率較高。

由于文章分詞所采用的詞與其編碼方式無關,故而采用移位作為主要代表,其他兩種方式類比得到。

4結語

模型采用正向最大匹配算法進行單詞匹配,同時采用的是優化以后的字典,對于檢索時間大大縮短,同時此次采用字典覆蓋面較為廣,涵蓋了142687個單詞組成。對于詞典的擴展性有效地給予了提升。針對于不同的加密算法分別給予了不同的解決方式,同時對于雜亂的無標記的英文分詞有一定的應用價值。對于探索此類問題有一定作用。同時探究了在排序算法計算時,Excel使用比其他成型算法更加高效。在字符串分詞程序中適時投入了結束符“#”,有效降低了檢索的時間。相對于基于理解和統計的算法來說,正向最大匹配算法復雜度比較小,技術實現比較容易,僅需要建立詞表即可。但是對歧義識別比較差,分詞的準確性不高。在實際中不能僅僅簡單地使用正向最大匹配算法,還需要對其進行改進,可以和逆向匹配算法一起使用,這樣可以提高歧義的識別,使準確度更高。

參 考 文 獻

[1] Paul Garrett.密碼學導論[M].北京:機械工業出版社,2013:1-48.

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

[2] 屈婉玲.算法設計與分析[M].北京:清華大學出版社,2011:1-20.

QU Wanling. Algorithm design and analysis[M]. Beijing: Tsinghua University Press,2011:1-20.

[3] 王紅梅.算法設計與分析[M].北京:清華大學出版社,2013:1-28.

WANG Hongmei. Algorithm design and analysis[M]. Beijing: Tsinghua University Press,2013:1-28.

[4] 雷新鋒.密碼協議分析的邏輯方法[M].北京:科學出版社,2013:1-12.

Lei Xinfeng. Password logic method of protocol analysis[M]. Beijing: Science Press,2013:1-12.

[5] 劉奕群.搜索引擎技術基礎[M].北京:清華大學出版社,2010:97-100.

LIU Yiqun. Search engine technology[M]. Beijing: Tsinghua University Press,2010:97-100.

[6] 威廉·費勒.概率論及其應用[M].北京:人民郵電出版社,2008:1-9.

William ferrer. Probability theory and its application[M]. Beijing: People’s Posts and Telecommunications Publishing House,2008:1-9.

[7] 李超.密碼函數的安全性指標分析[M].北京:科學出版社,2011:23-35.

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

[8] Willianm Stallings.密碼編碼學與網絡安全——原理與實踐[M].北京:電子工業出版社,2012:1-67.

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

[9] 維基百科,字母頻率[EB/OL]. http://zh.wikipedia.org/wiki/英語最常用單詞,2015/5/17.

Frequency of wikipedia, letters[EB/OL]. http://zh.wikipedia.org/wiki/ English is the most common words, 2015/5/17.

[10] 王瑞雷.一種改進的中文分詞正向最大匹配算法[J].計算機應用與軟件,2011(3):195-197.

WANG Ruilei. An improved Chinese word segmentation is maximum matching algorithm[J]. Computer Application and Software,2011(3):195-197.

[11] 姜啟源.數學建模[M].北京:高等教育出版社,2011:1-103.

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

Password Cracking Based on Positive Maximum Matching Algorithm

WU XingjiaoWU Sheng

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

AbstractIn this paper, a method of decipher based on the maximum matching method is used for word segmentation, and the method based on the word frequency is used for error change and control. The main steps are as follows: 1. Compile the required cipher text. 2. Replace the decryption. 3. Segment words based on lexicon, meanwhile performs error simulation. 4. Construct sentences. First, a cipher is written based on codingtheory at the same time random errors are made. Then, the analyzed results are saved in the text, and it’s found that its low error rate after compared the processed plaintext and the original, so the resulting model is high reliability. The mian goal of this paper is to create a reliability maximum forward word segmentation model based on character frequency which has storng universality, meanwhile, on the basis of this, the other models are established to solve the problem.

Key WordsEnglish word segmentation, character frequency, dictionary optimization, replace decryption, positive maximum matching

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

作者簡介:吳興蛟,男,碩士研究生,研究方向:軟件工程、算法設計、程序設計。吳晟,男,教授,碩士生導師,研究方向:信息安全,算法研究等。

中圖分類號TP309.7

DOI:10.3969/j.issn.1672-9722.2016.05.032