古典密碼學理論分析

[摘要]密碼學有悠久而迷人的歷史。研究古典密碼學的起源與發(fā)展，介紹主要的代表人物，對古典密碼學中的典型算法進行分析。

[關鍵詞]密碼 加密 破解 古典密碼理論 算法

中圖分類號：B81文獻標識碼：A文章編號：1671－7597（2009）0320186－02

一、引言

“人類使用密碼的歷史幾乎與使用文字的時間一樣長”《破譯者》。

密碼學(Cryptograph)，一詞來源于古希臘語Kruptos(hidden)+graphein(to write)，準確的現(xiàn)代術語是“密碼編制學”簡稱“編密學”，與之相對的專門研究如何破解密碼的學問稱之為“密碼分析學”。密碼學則包括密碼編制學和密碼分析學這兩個相互獨立又相互依存的分支。

密碼學經歷了從古典密碼學到現(xiàn)代密碼學的演變。許多古典密碼雖然已經經受不住現(xiàn)代手段的攻擊，但是它們對現(xiàn)代密碼學的研究是功不可沒的，其思想至今仍然被廣泛使用[1]。

二、古典密碼學的主要代表人物

1．費斯圖。他的圓盤理論是古典密碼學的主要代表之一，在粘土圓盤的表面刻上帶有空格的字母，成為最初人類的加密方式，這種方式至今還無人能破戒。

2．凱撒。凱撒密碼是把字母用該字母的后面三個字母代替。但這種密碼容易被破解。

3．阿辛地。阿辛地對古典密碼學的貢獻是成功的破解了凱撒密碼。

4．萊昂·巴蒂斯塔。多表密碼理論的創(chuàng)始人，發(fā)明了比替代密碼更加先進的多表密碼加密方法，是古典密碼學發(fā)展的一個重大的進步。

5．維吉尼亞。維吉尼亞是古典密碼理論發(fā)展上的一個重要里程碑，他的理論又被稱為多字母編碼。

6．亞瑟·謝爾比烏斯，理查德·里特。他們發(fā)明了“奇謎機”，把多表加密理論成功的用機械原理實現(xiàn)，為以后計算機加密開創(chuàng)了先河。

這些人物是古典密碼發(fā)展中的推動性人物，他們不但使古典密碼理論不斷的向前發(fā)展，更為以后密碼學的發(fā)展奠定了基礎，無疑貢獻是巨大的。

三、古典密碼學的主要算法

1．人類最早的文字歷史可以追溯到公元前2000年公元前1650年的費斯圖(Phaistos)圓盤，一種直徑約為160mm的Cretan-Mnoan粘土圓盤，表面有明顯字間空格的字母，至今還沒有破解。加密作為保障數(shù)據(jù)安全的一種方式，埃及人是最先使用特別的象形文字作為信息編碼的，隨著時間推移，巴比倫、美索不達米亞和希臘文明都開始使用一些方法來保護他們的書面信息。古希臘墓碑的名文志、隱寫術都是古老的加密方法，這種加密方法已體現(xiàn)了密碼學的若干要素，但只能限制在一定范圍內使用[2]。

2．公元前5世紀，古希臘斯巴達出現(xiàn)原始的密碼器，用一條帶子纏繞在一根木棍上，沿木棍縱軸方向寫好明文，解下來的帶子上就只有雜亂無章的密文字母。解密者只需找到相同直徑的木棍，再把帶子纏上去，沿木棍縱軸方向即可讀出有意義的明文。這是最早的換位密碼術。

3．人類第一次有史料記載的加密信息的使用是公元前58年到公元前51年，朱里葉斯·凱撒（公元前101公元前44年）征服了高盧，他的《高盧戰(zhàn)記》里記載了因對通信官不信任，而與部下所用的密碼凱撒密碼。凱撒密碼是把字母表中的每個字母用該字母后面第三個字母進行代替。例如，我們可以從明文得到密文（veni,vidi,vici,“我來，我見，我征服”是凱撒征服本都王法那西斯后向羅馬元老院宣告的名言）[2]：

明文：veni,vidi,vici

密文：YHAL,YLGL,YLFL

既然字母表是循環(huán)的，因此Z后面的字母是A。能夠通過列出所有可能性定義如下所示的變換：

明文：abcdefghijklmnopqrstuvwxyz

密文：defghijkImnopqrstuvwxyzabc

如果為每一個字母分配一個數(shù)值，并用字母P替代，每個密文字母用字母C替代則該算法能表示如下：

C=E(p)=(p+3)mod26

移位可以是任何量，因此通用的凱撒密碼算法是：

C=E(p)=(p+k)mod26

其中k在1到25的范圍取值。對應解密算法是：

p=D(C)=(C-k)mod26

但這樣單一的字母替代法容易被攻破，九世紀阿拉伯人首先發(fā)現(xiàn)了破解簡單“替代密碼”的方法：因為字母替代法反映了原來字母表的頻率數(shù)據(jù)，你只需要去計算每一個密碼字所出現(xiàn)的頻率，然后與英文字母在日常應用中出現(xiàn)的頻率做比對。譬如頻率最大的英文字母是E，那在密碼信息中經常出現(xiàn)密碼字很有可能就是E，在對相近頻率的字母進行代人測算后，很容易就破解出真實信息。16世紀英國伊麗莎白女王時期，蘇格蘭瑪麗女王被囚禁，在獄中仍通過密碼書信與外面保持聯(lián)系。企圖勾結親信貴族發(fā)動謀反，不料英格蘭國務大臣掌握了那套密碼術，一下把謀反者們全部逮捕，并把瑪麗女王送上了斷頭臺?，旣惻跤玫木幋a法就是這樣的方法：只是將每一個英文字母系統(tǒng)性地以不同的字母進行對應取代。

為改進這種加密方法，先后出現(xiàn)了多種變種算法，比如：

（1）多名碼代替

就是將明文字母表中的字符映射為密文字母表中的多個字符。多名碼簡單代替早在1401年就由DuchyMantua公司使用。在英文中，元音字母出現(xiàn)頻率最高，降低對應密文字母出現(xiàn)頻率的一種方法就是使用多名碼，如e可能被密文5,13或25替代。

（2）多音碼代替

就是將多個明文字符代替為一個密文字符。比如將字母“i”和“J”對應為“K”，“v”和“w”代替為“L”。最古老的這種多字母加密始見于1563年由波他的《密寫評價》(De furtiois literarumnods)一書。

（3）多表代替

即由多個簡單代替組成，也就是使用了兩個或兩個以上的代替表。比如使用有5個簡單代替表的代替密碼，明文的第一個字母用第一個代替表，第二個字母用第二個表，第三個字母用第三個表，以此類推，循環(huán)使用這五張代替表。多表代替密碼由萊昂·巴蒂斯塔于1568年發(fā)明，著名的維吉尼亞密碼、博福特密碼和希爾密碼均是多表代替密碼。其中，16世紀法國外交官Blaise de Vigenere(1523-1596)維吉尼亞密碼法(Vigenere cypher)的發(fā)明在密碼史上是一個重要里程碑，它的原理是在26個字母矩陣中在約定某個關鍵詞的前提下，對訊息字母進行編碼，每個字母變成和關鍵詞一樣長度的矩陣中所對應的字母，因此這一編碼又被稱為多字母(poly-alphabetic)編碼。這使得頻率分析法對此束手無措，當時堪稱無敵。直到幾百年后1863年一位名叫Kasiski的普魯士少校首次從關鍵詞的長度著手將它破解?，F(xiàn)代計算機模型的先驅巴貝奇(Charles Babbage)通過仔細分析編碼字母的結構也將其破獲，不過Vigener法至今仍有一定的適用性并對人類歷史的發(fā)展產生了重大影響[3]。

4．1918年，德國發(fā)明家亞瑟·謝爾比烏斯(Arthur Scherbius)和他的朋友理查德·里特(Richard Ritter)創(chuàng)辦了謝爾比烏斯和里特公司并發(fā)明了著名的Enigma（希臘文，意指“謎一般神秘難解之事”）又稱“奇謎機”。實際上它是維吉尼亞密碼的一種實現(xiàn)。它主要利用機械運動和簡單電子線路：有一個鍵盤和若干轉輪，每個轉輪由絕緣的圓形膠板組成，膠板正反兩面邊緣線上有金屬凸塊，每個金屬凸塊上標有字母，字母的位置相互對齊。膠板正反兩面的字母用金屬連線接通，形成一個置換運算。不同的轉輪固定在一個同心軸上，它們可以獨立自由轉動，每個轉輪可選取一定的轉動速度。例如，一個轉輪可能被導線連通以完成用F代替A，用U代替B，用L代替C等等。

為了防止密碼分析，有的轉輪密碼機還在每個轉輪上設定不同的位置號，使得轉輪的位置、轉輪的數(shù)量、轉輪上的齒輪結合起來，增大機器的周期。一份德國報告稱：“謎”型機能產生220億種不同的密鑰組合，假如一個人日夜不停地工作，每分鐘測試二種密鑰的話，需要約4.2萬年才能將所有的密鑰可能組合試完。希特勒完全相信了這種密碼機的安全性，十年間，德國軍隊裝備了大約三萬臺Enigma。然而，英國獲知了“謎”型機的原理，啟用了數(shù)理邏輯天才、現(xiàn)代計算機設計思想的創(chuàng)始人，年僅26歲的圖靈(Alan Mathison Turing 1912-1954)。1939年8月，在圖靈領導下完成了一部針對“謎”型機的密碼破譯機，每秒鐘可處理2000個字符，人們給它起了個綽號叫“炸彈(Bomb)”。半年后，它幾乎可以破譯截獲德國的所有情報。后來又研制出一種每秒鐘可處理5000個字符的“巨人(Colossus)”型密碼破譯機，1943年投入使用。至此，同盟國幾乎掌握了希特勒德國的絕大多數(shù)軍事秘密，加速了德軍的失敗。同一時期，美國人使用的是瑞典人哈格林設計的哈格林密碼機（美國軍方稱為M-209），它是一種齒數(shù)可變的齒輪裝置，有六個密鑰輪，一個印字輪。太平洋戰(zhàn)爭中美軍破譯了日本海軍的密碼機，截獲了日本艦隊司令官山本五十六發(fā)給各指揮官的命令，在中途島徹底擊潰了日本海軍，不久又擊斃了山本五十六，形成了太平洋戰(zhàn)爭的決定性轉折[4]。

四、總結

20世紀中葉以前，由于條件所限，密碼技術的保密性基于加密算法的秘密，因此稱之為古典密碼體制或受限(restricted)的密碼算法。盡管古典密碼體制受到當時歷史條件的限制，沒有涉及非常高深或者復雜的理論，但在其漫長的發(fā)展演化過程中，已經充分表現(xiàn)出了現(xiàn)代密碼學的兩大基本思想“代替”和“換位”，而且還將數(shù)學的方法引入到密碼分析和研究中。這為后來密碼學成為系統(tǒng)的學科以及相關學科的發(fā)展奠定了堅實的基礎。

參考文獻：

[1]馮運波、楊義先，密碼學的發(fā)展與演變[J].信息網絡安全，2001年，07期.

[2] Richard Spillman著，葉阮健、曹英、張長富譯，經典密碼學與現(xiàn)代密碼學[M].北京：清華大學出版社，2005.

[3]Wade Trappe,Lawrence C.Washington（美）著，鄒紅霞、許鵬文譯，密碼學概論[M].北京：人民郵電出版社，2004.

[4]章照止，現(xiàn)代密碼學基礎[M].北京：北京郵電大學出版社，2004.

作者簡介：

于紅梅，女，漢族，山東省青島市人，碩士，高級講師，主要研究方向：信息安全、計算機軟件開發(fā)。