錢宇環(huán) 范洪博

（昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院 昆明 650500）

1 引言

替換式密碼是密碼學(xué)中按規(guī)律將文字加密的一種方式［1］。替換式密碼中可以用不同字母數(shù)為一單元，例如每一個(gè)或兩個(gè)字母為一單元，然后再作加密。密文接收者解密時(shí)需用原加密方式解碼才可取得原文本。單字母加密是實(shí)際中經(jīng)常采用的一種，可以利用移位、仿射等方式實(shí)現(xiàn)。由于拼音文字中字的組成為有限的字母，以英語(yǔ)為例只有26個(gè)字母，組成可能的單元數(shù)較少，因此使用替換式密碼相對(duì)較為容易，而且亦可使用簡(jiǎn)單機(jī)械進(jìn)行加密；相反，非拼音文字如中文則因單元數(shù)非常大難以使用一般加密方式，必需建立密碼本，然后逐字替換。更何況某些非拼音文字中字字皆由不同大小的字根來(lái)組字，較難轉(zhuǎn)換，因此使用替換式密碼的示例比較少［2］。

密文是利用單字母加密方法加密的，加密后，單詞之間的間隔和標(biāo)點(diǎn)符號(hào)全部被刪去。在傳輸過(guò)程中，密文存在被丟失、添加和篡改字符的可能。本文對(duì)此設(shè)計(jì)了一個(gè)能夠自動(dòng)化破譯密文的算法。該算法能夠有效地避免錯(cuò)誤字符對(duì)真實(shí)字符的影響，破譯時(shí)誤識(shí)別的概率很低，下文將詳細(xì)介紹該算法。

2 破譯算法設(shè)計(jì)

2.1LZW算法原理

LZW算法的基本原理［3～4］是根據(jù)原始文本文件中的不同字符，創(chuàng)建一個(gè)編碼表。編碼表中有兩個(gè)屬性，一個(gè)是字符本身，還有一個(gè)是字符的索引，然后用編碼表中的字符的索引來(lái)替代原始文本文件中的相應(yīng)字符，來(lái)減少原始數(shù)據(jù)大小。

當(dāng)對(duì)大量真實(shí)文本進(jìn)行壓縮的時(shí)候，由于英語(yǔ)固有的語(yǔ)法特性和詞匯特性，那些被索引替換的字串往往都是一個(gè)單詞或者一個(gè)詞組，它是具有真實(shí)語(yǔ)義的，對(duì)于那些無(wú)意義的字串在編碼表中出現(xiàn)的頻率會(huì)很小，所以當(dāng)利用LZW對(duì)那些疑似明文進(jìn)行壓縮的時(shí)候，那些錯(cuò)誤的明文里面的字串大多是無(wú)意義的，壓縮的時(shí)候基本不被編碼表中的索引所替換。而正確的明文里面會(huì)有大量有意義的字串在編碼表中得到匹配，所以經(jīng)過(guò)壓縮后的文本長(zhǎng)度相較錯(cuò)誤的壓縮明文會(huì)短了很多。

2.2 破譯算法

首先，根據(jù)大量英文文獻(xiàn)統(tǒng)計(jì)得到的英文字頻表［5～6］，可以得出一般英文文獻(xiàn)中字母的頻率分布。如下表1。

表1 英文字頻表

該英文字頻表即為后面算法設(shè)計(jì)的參照表，它代表了真實(shí)文本中字母的頻率分布。

由上述表格，可以將不同頻率的字母分為以下幾組，如表2。算法流程圖如圖1所示。

表2 不同頻率的字母分組

圖1 破譯算法流程圖

算法詳細(xì)步驟如下：

第一步：得到密文后，統(tǒng)計(jì)密文中的字母頻率。

這里針對(duì)coca的語(yǔ)料庫(kù)里面w_acad_1990.txt進(jìn)行測(cè)試。先對(duì)該文本文件進(jìn)行加密，

圖2為明文和加密后的密文。

圖2 明文（左）與密文（右）

經(jīng)過(guò)程序統(tǒng)計(jì)得到密文的字頻如圖3。

這里由假設(shè)知密文有一定概率經(jīng)過(guò)噪聲的干擾，但是噪聲和文本之間是相互獨(dú)立的［5］，而且假設(shè)噪聲不會(huì)超過(guò)一定的限度，所以對(duì)字母的頻率的影響不是很大，可以由噪聲對(duì)字母影響的概率計(jì)算出受干擾之后的字頻［7］。

以字符e為例來(lái)進(jìn)行說(shuō)明。已知在英文文章中，沒(méi)有干擾的情況下各字符出現(xiàn)的頻率為Px，字符e出現(xiàn)的概率記為Pe，文章中的字符個(gè)數(shù)記為N。在有噪聲干擾情況下傳輸字符時(shí)，丟碼率為P1，增碼率為P2，誤碼率為P3。正常傳輸?shù)母怕蕿?-P1-P2-P3。根據(jù)以上信息，可以計(jì)算出字符e出現(xiàn)的頻率。

圖3 密文的字母頻率

1）在誤碼率P3的情況下，e字符出現(xiàn)的概率為Pe'：

Pe'=Pe*P3（1-1/26）+（1-Pe）*P1*（1/26）

2）在增碼率P2，丟碼率P1的情況下，e字符出現(xiàn)的概率Pe'：

Pe'=［Pe*N*P2*（1/26）］/N*（1+P2-P3）

第二步：由第一步中得到的密文的字母頻率，對(duì)其字母進(jìn)行分組［8］，分組的依據(jù)如下（頻率f）：

極高頻率字母組（f＞10）

次高頻率字母組（6＜f＜10）

中等頻率字母組（4＜f＜6）

較低頻率字母組（1.5＜f＜4）

甚低頻率字母組（f＜1.5）

根據(jù)以上準(zhǔn)則，對(duì)密文進(jìn)行分組，如圖4所示。

圖4 不同頻率字母的分組

第三步：由第二步中得出的字母分組，對(duì)每個(gè)分組求其全排列。得出可能的排列數(shù)。如圖5所示。

圖5 每個(gè)分組的全排列數(shù)

第四步：根據(jù)不同的排列情況，制作出相應(yīng)的疑似密碼表，由于數(shù)量眾多，這里不一一列舉，

第五步：根據(jù)對(duì)應(yīng)的疑似密碼表可以生成若干的疑似明文。

第六步：利用LZW算法對(duì)大量真實(shí)文本進(jìn)行壓縮［9～10］，并截取其中的壓縮編碼表。

LZW算法流程圖如圖6所示。

圖6 LZW算法流程圖

圖6中precode為臨時(shí)前向編碼索引。

經(jīng)過(guò)對(duì)大量真實(shí)文本，例如近十年的華爾街日?qǐng)?bào)或者經(jīng)濟(jì)學(xué)人，對(duì)其進(jìn)行壓縮之后可以得到一個(gè)LZW編碼表。在下一步中就要利用這個(gè)表來(lái)對(duì)明文進(jìn)行驗(yàn)證。

第七步：利用上一步得到的LZW編碼表對(duì)前面得到若干疑似明文進(jìn)行壓縮，最終長(zhǎng)度最短的即為真實(shí)明文。

3 結(jié)果分析

實(shí)驗(yàn)選取了四組不同的文本進(jìn)行對(duì)比，分別為英文論文、新聞、書籍、小說(shuō)，主要測(cè)試內(nèi)容為破譯算法的準(zhǔn)確度，即明文與破譯后的文本相似度，實(shí)驗(yàn)結(jié)果如下表3所示。

表3 不同材料的破譯準(zhǔn)確度

可以看出在論文的測(cè)試當(dāng)中，準(zhǔn)確率明顯不如其他三項(xiàng)，經(jīng)過(guò)分析得出，論文中存在的專業(yè)術(shù)語(yǔ)比較多，所以基于頻率分析的算法不能準(zhǔn)確地還原這些不常見的詞匯，使得破譯過(guò)程中可能會(huì)存在一定的誤差。其他一些材料則可以保持比較高的準(zhǔn)確度。

4 結(jié)語(yǔ)

本文中提出的是基于LZW壓縮的頻率分析的算法，經(jīng)過(guò)文中的理論和實(shí)驗(yàn)分析，壓縮算法在效率上是非常高的。該算法實(shí)際應(yīng)用中會(huì)存在一定的缺陷，在分組的過(guò)程中，如果有兩個(gè)相似字母正好處于分界的地方，使得它們?cè)诓煌慕M，就有可能得出錯(cuò)誤的密碼表，即便后面采用了準(zhǔn)確性非常高的LZW壓縮編碼來(lái)進(jìn)行驗(yàn)證，也不能得出正確的明文，所以這里是有待改進(jìn)的地方。

［1］Paul Garrett.密碼學(xué)導(dǎo)論［M］.北京：機(jī)械工業(yè)出版社，2013：1-48.Paul Garrett.Cryptography guidance［M］.Beijing：Me?chanical Industry Publishing House，2003：1-48.

［2］雷新鋒.密碼協(xié)議分析的邏輯方法［M］.北京：科學(xué)出版社，2013：1-12.LEI Xinfeng.Password logic method of protocol analysis［M］.Beijing：Science Press，2013：1-12.

［3］KhalidSayood，薩尤得，賈洪峰.數(shù)據(jù)壓縮導(dǎo)論［M］.北京：人民郵電出版社，2014.KhalidSayood，JIA Hongfeng.Introduction to Data Com?pression［M］.Beijing：Posts&Telecom Press，2014.

［4］吳家安.數(shù)據(jù)壓縮技術(shù)及應(yīng)用［M］.北京：科學(xué)出版社，2009.WU Jiaan.Data compression technology and application［M］.Beijing：Science Press，2009.

［5］維基百科，字母頻率［EB/OL］.http：//zh.wikipedia.org/wi?ki/英語(yǔ)最常用單詞2015/5/17.Frequency of Wikipedia，letters［EB/OL］.http：//zh.wikipe?dia.org/wiki/English is the most common words，2015/5/17.

［6］劉嘉勇.英語(yǔ)密碼學(xué)［M］.北京：清華大學(xué)出版社，2008：1-37.LIU Jiayong.Applied cryptography［M］.Beijing：Tsinghua University Press，2008：1-37.

［7］吳干華.基于頻率分析的代替密碼破譯方法及其程序?qū)崿F(xiàn)［J］.福建電腦，2006（9）：125-125.WU Ganhua.Replacement password decipher based on frequency analysis and its program implementation［J］.Fujian computer，2006（9）：125-125.

［8］Willianm Stallings.密碼編碼學(xué)與網(wǎng)絡(luò)安全——原理與實(shí)踐［M］.北京：電子工業(yè)出版社，2012：1-67.Willianm Stallings.Password encoding and network securi?ty—principle and practice［M］.Beijing：Electronic Indus?try Press，2012：1-67.

［9］Abraham Sinkov.初等密碼分析學(xué)—數(shù)學(xué)方法［J］.信息安全與通信保密，1980（3）：51-82.Abraham Sinkov.Primary cryptanalysis-mathematical method［J］.Information security and communication con?fidentiality，1980（3）：51-82.

［10］姜啟源.數(shù)學(xué)建模［M］.北京：高等教育出版社，2011：1-53.JIANG Qiyuan.Mathematical modeling［M］.Beijing：Higher Education Press，2011：1-53.