密碼學(xué)探究及幾種古典密碼的整合

1、密碼學(xué)探究及幾種古典密碼的整合胡月四川教育學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)2005級(jí)2班 指導(dǎo)教師：李濱摘 要：隨著計(jì)算機(jī)以及科技的高速發(fā)展，密碼學(xué)已經(jīng)充斥到了我們生活中的各 個(gè)角落，例如：經(jīng)濟(jì)、醫(yī)療、網(wǎng)絡(luò)、個(gè)人隱私、軍事等等。對(duì)于這樣一門在生活 中無(wú)處不接觸的學(xué)科，多點(diǎn)了解是好的。所以為了提高人們對(duì)密碼學(xué)的理解，以 及為能進(jìn)一步研究近代密碼學(xué)，古典密碼學(xué)就起著基石的作用。本文通過(guò)介紹密 碼學(xué)的“隱性”美，以及它簡(jiǎn)要的發(fā)展史，提高人們認(rèn)識(shí)密碼學(xué)的興趣。緊接著 依靠理論用例子詳細(xì)研討幾種典型的古典密碼體制相互整合之后的加密運(yùn)算，其 中要明確每一種體制中明文、密文、密鑰之間的關(guān)系，為對(duì)近代密碼的學(xué)習(xí)起一 個(gè)

2、很好的過(guò)渡作用。最后簡(jiǎn)要分析密碼學(xué)的前景。關(guān)鍵詞：明文；密文；密鑰；單表古典密碼體制；多表古典密碼體制；加密運(yùn)算password explore and study the integration of several classicalpasswordhu yuesichuan college of education mathematics and applied mathematics 2005 2 classes supervising teacher: li binabstract: with the computer, as well as the rapid developmen

3、t of science and technology, the password has been filled to the study of our lives in every corner, such as: economic, medical, network, privacy, military and so on. for such a life is everywhere in contact with the subjects, many points are well know. so in order to enhance people's understand

4、ing of cryptography, as well as to further research in modern cryptography, classical cryptography will play the role of the cornerstone. in this paper, through introduction of cryptography "hidden” the united states, as well as its brief history of the development, raising awareness of interes

5、t in cryptography to rely on theory followed by a detailed introduction of several typical examples of classical cryptosystem after integrate encryption algorithms, which must be clear of each system explicitly, ciphertext, key relationship between the password for the study of modern an the role of

6、 a good transition. finally a brief analysis of the prospects of cryptography.key words: explicit; ciphertext; key; single table classical cryptosystem; many forms of classical cryptography; encryption algorithms密碼學(xué)一詞，因?yàn)椤懊堋弊值拇嬖冢惋@得很是神秘莫測(cè)。而人木身就有著 探求神秘事物的強(qiáng)烈欲望，所以要提起對(duì)這門學(xué)科的興趣并不是件難事兒。愛(ài)倫 坡曾經(jīng)說(shuō)過(guò)：“密碼可破!人類的智慧不

7、可能造成這樣的密碼，使得人類木身的才 智即使運(yùn)用得當(dāng)也無(wú)法破開(kāi)它！”這句話在一方面就很成功的將密碼學(xué)由“隱性” 的美轉(zhuǎn)化為了 “顯性”的美。人說(shuō)：揭開(kāi)神秘面紗看到被隱藏的美，這就是所謂 的藝術(shù)過(guò)程。那么在密碼學(xué)加密到解密的這一轉(zhuǎn)化，無(wú)疑就是一種完美的藝術(shù)。 為了能更好的理解密碼學(xué)及密碼體制的整合，以下給出了（1）密碼學(xué)的發(fā)展歷 程（2）從不同角度看密碼學(xué)的美（3）對(duì)幾種典型的古典密碼體制進(jìn)行介紹（4） 幾種典型古典密碼體制的整合（5）簡(jiǎn)要分析密碼學(xué)的前景以及其重要性。本文根據(jù)以上想法一一論述，給出了一個(gè)全新的占典密碼學(xué)的認(rèn)識(shí)理解框 架。k 密碼學(xué)的發(fā)展歷程密碼學(xué)在公元前400多年就已經(jīng)產(chǎn)生了，

8、破譯者一書(shū)中說(shuō)“人類使用 密碼的歷史幾乎與使用文字的時(shí)間一樣長(zhǎng)”。所以密碼學(xué)的起源要追溯到人類剛 剛岀現(xiàn)，嘗試去學(xué)習(xí)如何通信的時(shí)候。為了確保通信的機(jī)密，最先是有意識(shí)的使 用一些簡(jiǎn)單的方法來(lái)加密信息，通過(guò)一些（密碼）象形文字相互傳達(dá)信息。接著 由于文字的出現(xiàn)和使用，確保通信的機(jī)密性就成為一種藝術(shù)，古代發(fā)明了不少加 密信息和傳達(dá)信息的方法，例如：烽火是一種傳遞軍情的方法，古代的兵符是來(lái) 傳達(dá)信息的密令，暗語(yǔ)，行話等，這些都促進(jìn)了密碼學(xué)的發(fā)展。在19世紀(jì)末和20卅紀(jì)初期，密碼學(xué)才正式成為一門科學(xué)。由于軍事、數(shù)學(xué)、 通訊等相關(guān)技術(shù)的發(fā)展，特別是兩次世界大戰(zhàn)中對(duì)軍事信息保密傳遞和破獲敵方 信息的需求，密

9、碼學(xué)得到了空前的發(fā)展，并廣泛的用于軍事情報(bào)部門的決策。而 到目前，密碼學(xué)已經(jīng)在無(wú)形中滲透進(jìn)了你我的生活。2、不同角度看密碼學(xué)軍事上：歷史上許多信息的隱藏和傳輸方式都是為了滿足情報(bào)作戰(zhàn)的需要而 發(fā)展和成熟起來(lái)的，有些信息的隱藏設(shè)計(jì)的和當(dāng)巧妙。在第二次世界大戰(zhàn)間，一 位女鋼琴家常用為聯(lián)軍做慰問(wèn)演出的機(jī)會(huì)獲取情報(bào)，再按事先規(guī)泄的密碼巧妙地 將其編成樂(lè)譜，并在電臺(tái)演奏時(shí)將重耍情報(bào)通過(guò)琴聲傳遞出去。通過(guò)簡(jiǎn)單的密碼 技術(shù)加工后，一切都變的很神奇。情報(bào)從聯(lián)軍耳邊溜走，卻沒(méi)人察覺(jué)，這就是密 碼學(xué)的妙用了。當(dāng)然類似這種情況的（如密寫技術(shù)）在戰(zhàn)爭(zhēng)年代用的相當(dāng)多。偵探方面：看過(guò)福爾摩斯探案集的人應(yīng)該會(huì)有印彖，那就是

10、在跳舞的人 中出現(xiàn)的'小人密碼。故事里，睿智的福爾摩斯秉著事出必有因，不可能憑空 放一些不同的小人在那的原則，在理論上通過(guò)侮個(gè)字母出現(xiàn)的頻率高低，確定了 每個(gè)小人所代表的和應(yīng)字母，從而破解了這個(gè)密碼，得到圖畫(huà)中隱含的信息從而 獲得破案的線索。雖然這個(gè)故事是虛構(gòu)的，但其中卻包含著豐富的密碼學(xué)知識(shí)。戲曲方面：滬劇無(wú)雙緣屮“早迎無(wú)雙”的故事。無(wú)雙為了讓表哥明 白自己的心意，寫詩(shī)一首：早妝未罷暗凝眉， 迎戶愁看紫燕飛， 無(wú)力冋天春已老， 雙棲畫(huà)棟不如歸。詩(shī)中每句的首字即組成“早迎無(wú)雙”，很好的表達(dá)了她此時(shí)期待的心情。這也是 所謂的藏頭詩(shī)，在我們今天看來(lái)，其實(shí)就是運(yùn)用了簡(jiǎn)單的密碼學(xué)知識(shí)。同樣有一

11、個(gè)例子就是周星馳主演的電影唐們虎點(diǎn)秋香中，唐伯虎進(jìn)華府 簽的那一份契約。他利用古人讀書(shū)喜歡豎讀的這一習(xí)慣，很好的將自己的目的寫 進(jìn)了契約中，是怎么樣的呢？最后大家都知道橫讀剛好是“我為秋香”，這里也 有點(diǎn)藏頭詩(shī)的感覺(jué)。從以上可以很好的看出密碼學(xué)的妙用。密碼學(xué)其實(shí)是一門很有趣且實(shí)用的 學(xué)科，特別是在現(xiàn)今隨著互聯(lián)網(wǎng)的廣泛運(yùn)用，密碼學(xué)更是深入具中，或者可以不 夸張的說(shuō)他己經(jīng)成為人們生活中不可缺的一部分。密碼學(xué)既然如此重要，那么現(xiàn)在就保持一顆渴望探求的心，繼續(xù)我們的“歷 程。3、幾種典型的古典密碼體制的介紹 基本概念：原始的信息稱為明文；所有可能的明文集合稱為明文空間。明文經(jīng)過(guò)加密變換，得到另外一種看

12、起來(lái)似乎與原有信息不相關(guān)的表達(dá)，稱為密 文；所有可能的密文集合，稱為密文空間。密文可通過(guò)解密變換得到和應(yīng)的明文。密碼體制包含：明文空間，密文空間，密 鑰，加密變換和解密變換。為了避免文字的贅述，下面都在舉例子的同時(shí)介紹該種密碼體制的加密方法。3. 1單表代換密碼(caesar密碼，標(biāo)準(zhǔn)字頭密碼)最早的代換密碼是由julius caesar發(fā)明的caesar密碼。例1： 是i w訂1 go to beijing用caesar密碼將明文加密得到密文是 什么？解：分析：用caesar密碼加密，即明文中每一個(gè)字母都用其后的第三個(gè)字母 來(lái)f替,(caesar密碼的加密方法)那么就有i tl, wtzgt

13、j代替之后得到密文為：l zloo jr wr ehlmlqj注意：在這里字母表是循環(huán)的，即認(rèn)為緊隨z之后的字母是a 我們讓每個(gè)字母等價(jià)于一個(gè)數(shù)值：abcdefgh jk1m0123456789101112n0pqrstuvwxyz13141516171819202122232425（表1）通過(guò)以上例子可以看出對(duì)于每個(gè)明文字母p代換成c ,這樣的移位可以用數(shù)學(xué) 公式：c=e (3, p)二(p+3) mod26來(lái)表示，因?yàn)檫@里移位可以是任意整數(shù)k,這 樣就可以將caesar密碼推廣到更一般的算法:c=e (k, p) = (p+k) mod26(lwk w25)。因?yàn)閏aesar密碼需測(cè)試的密

14、鑰只有25個(gè)，是遠(yuǎn)不夠安全的，如果允許任意 代換，那么密鑰空間將會(huì)人人增加，這就產(chǎn)生了一種名為：標(biāo)準(zhǔn)字頭密碼體制 標(biāo)準(zhǔn)字頭密碼體制是利用一個(gè)密鑰字來(lái)構(gòu)造代換作為密鑰。例2： china為密鑰字，用標(biāo)準(zhǔn)字頭密碼體制將明文meet me at the usual pl ace 加密得到的密文是什么？解：分析：首先應(yīng)該寫出標(biāo)準(zhǔn)字頭密碼體制中明文字母與密文字母的對(duì)應(yīng)關(guān) 系。(方法就是在明文為字母表，對(duì)應(yīng)的密文以china為首，其斤就以字母表中 字母的順序?qū)?，注意與china中重復(fù)的字母就省略不寫)如卜表：明文字母a bed e f g h i j k 1 m n o p q r s t u v w x

15、 y z密文字母chinabdefgj k 1 m o p q r s t u v w x y z（表2）現(xiàn)在就可以看到m對(duì)應(yīng)l, e對(duì)應(yīng)ak對(duì)應(yīng)j,所以加密后得到的密文為laat la ct tea usuck pkeia3. 2playfair密碼體制playfair體制是由英國(guó)著名科學(xué)家一 “wheatston電橋”的設(shè)計(jì)者charles wheatston 發(fā)明的。playfair體制的密仞是一個(gè)5*5的矩陣p=（pij）5+5,該矩陣使用一個(gè)關(guān)鍵詞 （密鑰）來(lái)構(gòu)造，矩陣構(gòu)造方法是：從左到右，從上到下依次填入關(guān)鍵詞的字母 （去除覓復(fù)的字母），然后再以字母表順序依次填入其他字母。字母i和

16、j被算 做一個(gè)字母。例3：以how are you為密鑰，用playfair密碼對(duì)明文i wil 1 go to（表3）第一步：將明文進(jìn)行分組iw il lg ot ob ei ji ng第三步：根據(jù)矩陣寫出對(duì)應(yīng)密文tw t ga il tdp ng->vn即加密后得到的密文為：gadpndyoaybdkkvn加密方法如下： 明文字母在同一行，對(duì)應(yīng)的密文分別是緊靠其右端的字母。 明文字母在同一列，對(duì)應(yīng)的密文分別是緊靠其下方的字母。 明文字母既不在同一行，也不在同一列，則密文是由明文兩字母確定的矩形 的具他兩角的字母。 明文兩字母相同，則插入一個(gè)字母（比如q,需要事先約定）于重復(fù)字母之 間

17、，并用前述方法處理。 明文字母數(shù)為奇數(shù)時(shí)，在明文的末端添加某個(gè)事先約定的字母作為填充。 注意：第一列看作是最后一列的右方，第一行看作是最后一行的下方，如此形成 循環(huán)。playfair密碼與簡(jiǎn)單的單一字母代替法密碼相比有了很大進(jìn)步。第一，雖 僅有26個(gè)字母，但有676種雙字母組合，因此識(shí)別各種雙字母要困難得多。第 二，各個(gè)字母組的頻率要比單字母呈現(xiàn)出大得多的范圍，使得頻率分析困難得多。 但是，playfair密碼還是相對(duì)容易攻破（幾百字的密文通常就夠了），因?yàn)樗匀皇乖S多明文語(yǔ)言的結(jié)構(gòu)保存完好，能夠被密碼分析者利用。3.3 hill密碼體制h訂1密碼是另一種多表代換密碼，它是1929年，由數(shù)學(xué)家

18、lester hill發(fā) 明的。加密算法將ni個(gè)連續(xù)的明文字母替換成ni個(gè)密文字母，這是由ni個(gè)線性方 程決定的。在方程中每個(gè)字母被指定為一個(gè)數(shù)值（a=0, b=l.z=25）例如： m二3時(shí)該密碼體制可以描述為：c|= (kipi+k2p2+ki3p3)mod26c2=(1<21卩+1<22卩2+1<23卩3)010(126c3=(k3ipi+k32p2+k33p3)mod26用列向量和矩陣表示如下:*31k32mod26c=kpmod26其屮c和p是長(zhǎng)度為3的列向量分別代表密文和明文，k是-個(gè)3*3矩陣，代表 加密密鑰。注：在用hill密碼進(jìn)行加密的過(guò)程中，密鑰的選擇可以

19、是2*2矩陣，3*3矩 陣，4*4矩陣，特別的，矩陣的階數(shù)越高越難被破解。通過(guò)前面的敘述可以看到在playfair密碼體制中涉及將明文分組，hill密碼 體制屮有密鑰矩陣的約束（將明文轉(zhuǎn)化為密文時(shí)）。以上例子都是特殊形式：在 上述例子中用playfair密碼體制時(shí)，明文字母數(shù)為偶數(shù)，這樣兩個(gè)一組剛好分完, 在用到hill密碼體制加密時(shí)，明文字母數(shù)也是偶數(shù)（或某數(shù)的整倍數(shù)），這樣密 鑰矩陣就能將明文完全轉(zhuǎn)化為密文。但在現(xiàn)實(shí)中，明文字母數(shù)不可能都為偶數(shù)， 這樣就產(chǎn)生了一一啞元。3. 4啞元在密碼體制中的運(yùn)用:3. 4. 1 playfair 密碼體制例4：對(duì)明"i will go&quo

20、t;用playfair體制進(jìn)行加密，密鑰為china is a beautiful cityo分析:明文字母數(shù)為奇數(shù)，為便于分組，就事先約定在明文末尾加一個(gè)特定字母a (通常都選用此方法)，這樣就解決了明文字母數(shù)為奇數(shù)的情況。當(dāng)然使 明文字母數(shù)由奇數(shù)變?yōu)榕紨?shù)的方法有很多，不過(guò)要注意的是加的這一字母一定要 事先約定，并且這一字母無(wú)特別意義，稱其為啞元素。解：根據(jù)密鑰得到對(duì)應(yīng)字母矩陣表為：chi/jnasbeutf1ydgkffl0pqrvwxz（表4）將明文分組為：iw illg oa依照playfail體制的加密方法對(duì)應(yīng)密文為：yvhyyfqi3.4.2 h訂1密碼體制例5：將明文“gothe

21、re”用劍體制加密,密鑰為e加010分析：明文字母數(shù)為奇數(shù)，而密鑰矩陣為二階，即使說(shuō)在將明文轉(zhuǎn)化為密文 時(shí)，一次轉(zhuǎn)化兩個(gè)字母，這樣必然單出一字母，那么這里就引進(jìn)啞元，將明文“go there" > “go there (e)”，這里末尾的e沒(méi)有實(shí)際意義。兩個(gè)字母go用向量表示為6 14則有_6_60_mod26=_8_142600解：明文前k=iath用向量表不為197，_190_8_mod26=_450_8_197 =11er一 4 17,有 k40'mod26二_250_16417二 oqmod26=14ec4 4,有 k4012016=oq即加密后所得密文為:ia

22、iioqoq4、幾種密碼體制整合的相關(guān)例子4. 1 playfair體制與caesar體制的整合例1:明文為：i have complete faith in what he said用playfair體制進(jìn)彳亍加密，這里 密鑰為：china is a beautiful city,加密后乂用caesar體制進(jìn)行加密，最終得到密 文為什么？解：第一次加密：根據(jù)密仞：china is a beautiful city得到字母矩陣表為:chi/jnasbeutf1ydgkm0pqrvwxz（表1）先將明文分組：ih av ec om pl et ef ai th in wh at he sa id

23、對(duì)應(yīng)密文為：ni hz si po md us sy cn ba na vi tg ib tc ny第二次加密：再對(duì)密文進(jìn)行caesar加密，就是將每個(gè)密文字母用其后的第三個(gè)字母代替，得到最終密文為：qlkcvlsrpgxvvbfqdeqdylwjlewfqb4. 2 playfair體制與hill體制的整合例2：明文為：i can speak french and german先對(duì)其進(jìn)行h訂1加密，此時(shí)12 10 5_密鑰設(shè)為：k= 10 5 2然后再進(jìn)行playfair加密：此時(shí)密20 10 1鑰設(shè)為：how are you ,那么進(jìn)行兩次加密后得到的密文為什么？ 解：第一次加密：_8明文

24、的前三個(gè)字母用向量8,2,0表示，則有：k 2011690mod261801212 =mmy2412man用向量表示為：12 0 13,有：k 013'209t146mod26 =1625319=bqt照此方式轉(zhuǎn)換所有的字母，可得整段明文對(duì)應(yīng)的密文是： mmyvqnuimqnodybptdpkvbqt第一次加密：密鑰為：how are you對(duì)應(yīng)的字母矩陣表為：h0wareyubcdrgi/jk1mnpqstvxz（表2）將第一次加密得到的密文進(jìn)行分組：mw yv qn ui mq no dy bp td 對(duì)應(yīng)密文為：no ut lp bg nl mw fe ix sfpk vb qtqi xu mz所以最終的密文就為：noutlpbgnlmwfeixsfqixumz4. 3 playfair體制與h訂1體制的整合（含啞元）例3：將明文“g。there”用hil】體制加密,密鑰為k£為（見(jiàn)例5）, 將所得密文再用playfair體制加密，密鑰為how are you,得到最終密文為什 么？解：第一次加密：出例5得到第一次加密后的密文為：iaiioqoq第二次加密：由密鑰how are you得到對(duì)應(yīng)的字母矩陣表為：h0wareyubcdfgi/jk1mnpqstvxz（表3）將 iaiioqoq 分組得到：ia ii oq