單字母替換密碼的破譯模型

趙龍乾+陳金瓊+朱嚴

摘 要： 本文主要以矩陣理論為基礎，運用置換密碼、概率分析與希爾密碼算法，建立了基于希爾算法破譯單字母替換式密碼的數學模型，編寫出了具體的自動破譯程序。

關鍵詞： 替換密碼 希爾密碼 置換矩陣

替換式密碼，又名取代加密法，是密碼學中按規律把文字加密的一種方式[1]-[5]。在密碼學研究領域中，密碼破譯是其重要內容之一，也是信息安全研究的熱點方向之一。本文主要研究單字母替換密文的破譯問題。使用矩陣理論[6]，建立了希爾密碼[7]破譯單字母替換式密碼的數學模型，得到了密文中獲取正確秘鑰方法，進而運用希爾密碼，置換密碼，概率分析，以及可拓評價法，設計出了一套算法自動破譯給定單字母替換式密碼，并給出了評價該破譯能力的標準。

1.基于希爾算法的單字母替換式密碼破譯設計

基本假設：

（1）加密矩陣的階數較小；

（2）破譯的明文已獲取；

（3）明文的長度在合理的范圍之內足夠長；

模型或算法中的記號表示如下：

P—明文；Q—暗文；A—加密矩陣；i—個數；

希爾密碼是運用基本矩陣論原理的替換密碼。每個字母當做26進制數字：A=0，B=1，C=2......一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果MOD26。

1.2希爾算法

上節中所建立的希爾密碼破譯單字母替換式密碼的數學模型，其本質就是進行矩陣運算，利用英文替換密碼的編碼的希爾算法進行求解，步驟如下：

Step1：將一串經過單字母替換式方法加密后的暗文中的a-z（或A-Z）進行26進制數編碼：a—0，b—1，c—2……x—23，y—24，z—25。英文字母編碼組成暗文矩陣。

Step2：通過概率分析將猜測出的加密矩陣經過模逆算法[8]進行模逆運算，然后按照（1）式與Step得到的暗文矩陣經過實矩陣相乘[9]得到P矩陣，即明文矩陣1。

Step3：將破譯出的明文矩陣P進行定性評估，如果明文矩陣1不正確，再重新猜測加密矩陣A，并重新操作Step1的操作，直到得到對應的正確加密矩陣所A對應的正確明文P，即明文矩陣n。如果明文矩陣1正確，則直接輸出。

2.仿真結果

輸入一串字符串，本次仿真以“the banana is very big I very like”27個字母為例作為明文P。假使經過某種加密方式，可以得到暗文“ungnsdgdpagkenvqgeqfjvupgul”，則暗文矩陣Q如圖1所示：

3.結語

本文利用希爾算法破譯單字母替換式密碼。希爾算法與概率分析相結合大大地提高了結果的準確性和可靠性。本文所設計的單字母替換式密碼破譯模型不僅適用于密碼破譯，而且可以運用于其他領域，如文件加密等，使用價值高，實用性強。

參考文獻：

[1]王昭，段云所，陳鐘.數據加密算法的原理與應用[J].網絡安全技術與應用，2001（2）：58-64.

[2]秦志光.密碼算法的現狀和發展研究[J].計算機應用，2004，24（2）：1-4.

[3]許霞.數據加密算法的研究與應用[D].西安建筑科技大學，2009.

[4]張肖，王薇.替換式密碼算法及其破譯能力的分析[J].科學與財富，2015（27）：242-242.

[5]李振華.替換密碼算法在C++中的實現[J].科技廣場，2009（3）：157-158.

[6]付麗，丁慧.代數在密碼學中的應用[J].通化師范學院學報，2014（2）：29-31.

[7]亓傳偉.簡便高效的希爾密碼[J].電腦編程技巧與維護，2007（9）：77-79.

[8]陳海進.奇數模模逆算法對偶數模的推廣[J].計算機應用與軟件，2005，05：100-101.

[9]徐士良.C常用算法程序集[M].第三版，北京：清華大學出版社，2001-01.36-37.

基金項目：安徽省高等學校專業綜合改革試點項目（2014zy138）；安徽省大學生創新訓練項目（201513619003）資助