破譯密文自動(dòng)化算法及衡量破譯算法的破譯能力探討

陳純

南京農(nóng)業(yè)大學(xué)浦口校區(qū)

破譯密文自動(dòng)化算法及衡量破譯算法的破譯能力探討

陳純

南京農(nóng)業(yè)大學(xué)浦口校區(qū)

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

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

一、引言

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

二、模型建立

2.1 頻率分析模型

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

2.1.1 窮舉法

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

2.1.2 單字母替代映射法

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

①單詞中最常用首字母

②單詞中最常見尾字母

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

④單詞中字母e后面經(jīng)常連接的字母

⑤只含有一個(gè)字母的單詞

⑥含有兩個(gè)字母的單詞

2.2 設(shè)計(jì)衡量破譯能力的標(biāo)準(zhǔn)

2.2.1 頻率分析模型

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

2.2.2 回歸分析模型[2]

建立回歸分析模型中加權(quán)平均偏差；

2.2.3 離散數(shù)學(xué)模型

運(yùn)用離散數(shù)學(xué)模型繪制散點(diǎn)；

2.2.4 曲線擬合模型

采用上述曲線擬合模型求得誤差關(guān)系式并檢驗(yàn)破譯準(zhǔn)確度。

三、模型的求解

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

3.1.1 隨機(jī)選擇三段英語文章及三段密文。

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

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

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

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

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

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

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

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

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

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