陳純

南京農業(yè)大學浦口校區(qū)

破譯密文自動化算法及衡量破譯算法的破譯能力探討

陳純

南京農業(yè)大學浦口校區(qū)

密碼學是研究編制密碼和破譯密碼的技術科學。其包括多種密碼編譯破譯方法，替換式密碼就是其中之一。本文針對替換式密碼設計出長短密文下的兩種數(shù)學模型來破譯密文，并設計出一個衡量破譯能力的標準，來評價破譯的能力。本文充分利用MAT?LAB、excel等多種語言的特性，進行綜合編程及數(shù)據(jù)統(tǒng)計，對數(shù)據(jù)進行了分析處理，并設計簡單易懂的算法使破譯準確性更高。

密文破解；頻率分析；曲線擬合；歐式距離度量；離散數(shù)學

一、引言

替換式密碼是將文中出現(xiàn)的字符一對一地替換成其他的符號。單字母替換加密，即以每一個字母為一個單位，將每個字母替換成另外的字母或者另外的符號。較為復雜的形式是以多個字母為一個單元，整體替換成其他的字符。這個映射方法被稱為密碼表，拿到密碼表的人就能夠將密碼破譯成明文。本題背景假設明文是由現(xiàn)代通常使用的英語寫成的并已經獲取了一些由單字母加密方法加密的密文，要求建立合理的數(shù)學模型設計算法來自動化的破譯密文并設計一個衡量破譯能力的標準，來評價破譯的能力。

二、模型建立

2.1 頻率分析模型

首先采用頻率分析模型，提取特征。頻率分析在數(shù)學、物理學和信號處理中是一種分解函數(shù)、波形、或者信號的頻率組成，以獲取頻譜的方法。在密碼學中，頻率分析是指研究字母或者字母組合在文本中出現(xiàn)的頻率。應用頻率分析可以破解古典密碼。由于在每種語言中，冗長的文章中的字母表現(xiàn)出一種可對之進行分辨的頻率，因此由MATLAB分析大量英文文章中字母a～z及密文中字母a～z的出現(xiàn)頻率（包括高頻詞、低頻詞及稀頻詞）。

2.1.1 窮舉法

窮舉法的基本思想是根據(jù)題目的部分條件確定答案的大致范圍，并在此范圍內對所有可能的情況逐一驗證，直到全部情況驗證完畢。若某個情況驗證符合題目的全部條件，則為本問題的一個解；若全部情況驗證后都不符合題目的全部條件，則本題無解。當然如果破譯一個有6位以上而且有可能擁有大小寫字母的密碼用普通的家用電腦可能會用掉幾個月甚至更多的時間去計算，其組合方法可能有幾千萬種組合,這樣長的時間顯然是不能接受的,因此采取下面一種方法。

2.1.2 單字母替代映射法

xij為一篇密文中，第i個單詞中的第j個字母；根據(jù)普遍適用情況，模型中短密碼：篇幅長度m≤100，每個單詞長度n≤30，即數(shù)學模型如下所示：

①單詞中最常用首字母

②單詞中最常見尾字母

③單詞中最常見的兩個連續(xù)相同字母

④單詞中字母e后面經常連接的字母

⑤只含有一個字母的單詞

⑥含有兩個字母的單詞

2.2 設計衡量破譯能力的標準

2.2.1 頻率分析模型

依據(jù)上所建立的頻率分析模型，在同一加密方法得到的密文中選取10段長度不同的密文段；

2.2.2 回歸分析模型[2]

建立回歸分析模型中加權平均偏差；

2.2.3 離散數(shù)學模型

運用離散數(shù)學模型繪制散點；

2.2.4 曲線擬合模型

采用上述曲線擬合模型求得誤差關系式并檢驗破譯準確度。

三、模型的求解

3.1 按照上述模型，首先提取分類特征

3.1.1 隨機選擇三段英語文章及三段密文。

3.1.2 設計MATLAB程序求解出三篇英文文章中字母a～z及密文中字母a～z的出現(xiàn)頻率。見附錄程序6-1。

3.1.3 數(shù)據(jù)經過SPSS軟件統(tǒng)計

3.2 用歐式距離度量法選擇特征向量

利用?（Xk,Xl）=(Xk-Xl)2（1）式判斷選擇距離最小的26組（Xk,Xl）值。為此，我們要解決以下問題：

距離最小相似性度問題。即要選出在k從1逐步取值到26的情況下（1）式達到最小的組別。我們發(fā)現(xiàn)當特征數(shù)k從1逐步取值到26時，并不意味著取相對應的l能使（1）式達到最小。因此考慮到誤差的影響，我們由MATLAB經過多組實驗使相似度更高。

3.3 由具體數(shù)據(jù)繪制散點圖

由上散點圖分布及相似性度量分析可知，普通英文文章和密文中26個字母出現(xiàn)的頻率依次對應。明文和暗文一一映射。

[1]姜啟源.數(shù)學建模：高教出版社，2005年

[2]姜啟源.大學數(shù)學實驗：北京：清華大學出版社，2005年

[3]肖華勇.實用數(shù)學建模與軟件應用：西安：西北工業(yè)大學，2008年