古典密碼學(xué)理論分析

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

[關(guān)鍵詞]密碼 加密 破解 古典密碼理論 算法

中圖分類號(hào)：B81文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671－7597（2009）0320186－02

一、引言

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

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

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

二、古典密碼學(xué)的主要代表人物

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

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

3．阿辛地。阿辛地對古典密碼學(xué)的貢獻(xiàn)是成功的破解了凱撒密碼。

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

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

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

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

三、古典密碼學(xué)的主要算法

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

2．公元前5世紀(jì)，古希臘斯巴達(dá)出現(xiàn)原始的密碼器，用一條帶子纏繞在一根木棍上，沿木棍縱軸方向?qū)懞妹魑模庀聛淼膸ё由暇椭挥须s亂無章的密文字母。解密者只需找到相同直徑的木棍，再把帶子纏上去，沿木棍縱軸方向即可讀出有意義的明文。這是最早的換位密碼術(shù)。

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

明文：veni,vidi,vici

密文：YHAL,YLGL,YLFL

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

明文：abcdefghijklmnopqrstuvwxyz

密文：defghijkImnopqrstuvwxyzabc

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

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

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

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

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

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

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

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

（1）多名碼代替

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

（2）多音碼代替

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

（3）多表代替

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

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

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

四、總結(jié)

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

參考文獻(xiàn)：

[1]馮運(yùn)波、楊義先，密碼學(xué)的發(fā)展與演變[J].信息網(wǎng)絡(luò)安全，2001年，07期.

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

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

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

作者簡介：

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