密碼與解密模型

1、Password as a technology in the military and political struggle, has a thousand years of history. Since human beings have a war, password naturally appears.From 4000 thousands years ago to 14th century BC, they used artificial means to encrypt ，called classical cryptography .Around the 16th century,

2、 as the basic system, a mechanical means of encryption to make a secret password table and the secret codes has made cryptography developed.DES(data encryption standard ) and public key system were two exotic blooming flowers on the cryptography groud.These two almost came at the same time, the form

3、er was promoted by IBM and the later came from a famous scientific paper “New Directions in Crytagraphy” by Diffie W. and Hellman M.E.密碼學(xué)的基本概念 密碼學(xué)基本模型發(fā)送方接收方Encryption加密Decryption解密加密：c= EK (m)解密：m= DK (c)不安全信道密碼分析（Cryptanalysis）Plaintext 明文Key解密密匙Key加密密匙Plaintext 明文Ciphertext 密 文 明文用明文用M M（MessageMe

4、ssage，消息）或，消息）或P P（PlaintextPlaintext，明文），明文）表示，它可能是比特流、文本文件、位圖、數(shù)字化的表示，它可能是比特流、文本文件、位圖、數(shù)字化的語音流或者數(shù)字化的視頻圖像等。語音流或者數(shù)字化的視頻圖像等。 密文用密文用C C（CipherCipher）表示，也是二進制數(shù)據(jù)，有時和）表示，也是二進制數(shù)據(jù)，有時和M M一樣大，有時稍大。通過壓縮和加密的結(jié)合，一樣大，有時稍大。通過壓縮和加密的結(jié)合，C C有可能有可能比比P P小些。小些。 加密函數(shù)加密函數(shù)E E作用于作用于M M得到密文得到密文C C，用數(shù)學(xué)公式表示為：，用數(shù)學(xué)公式表示為：E E（M M）=C=

5、C。解密函數(shù)。解密函數(shù)D D作用于作用于C C產(chǎn)生產(chǎn)生M M，用數(shù)據(jù)公式表示，用數(shù)據(jù)公式表示為：為：D D（C C）=M=M。先加密后再解密消息，原始的明文將。先加密后再解密消息，原始的明文將恢復(fù)出來，恢復(fù)出來，D D（E E（M M）=M=M必須成立。必須成立。置換密碼是一個最容易實現(xiàn)而且最為人們熟悉的密碼，它只需要把每個字母由某個其他字母來替換而形成密文。替換的規(guī)律可以是隨機的或者是系統(tǒng)的?？偣灿?6！種可能的密碼！Gaius Julius Caesar公元前51年初，深冬。高盧，畢布拉克德(現(xiàn)法國境內(nèi)伯夫雷山)，凱撒的營帳。深夜，羅馬共和國高盧行省長它儒略.凱撒，正在一張羊皮上寫著什么。

6、他的身影被跳動的燈火映在帳篷上，高大而搖曳。他的臉略嫌狹長，但棱角分明，專注的神色中透著與生俱來的自負。他在寫他的“隨記”，也就是后來流傳于世的高盧戰(zhàn)記。戎馬生涯的凱撒本沒有余暇來寫什么隨記，但是過去的幾年中，與他在高盧的顯赫戰(zhàn)績相比，政治上的事態(tài)發(fā)展可不那么如意。羅馬執(zhí)政宮克拉蘇斯在同帕爾提亞人(在今土庫曼斯坦南部和伊朗東北部)的作戰(zhàn)中被俘。熔化了的黃金溶液灌進了他的喉嚨這個當(dāng)年殘酷鎮(zhèn)壓斯巴達克斯起義的劊子手，如今向他嗜如生命的黃金鑄在了一起，這對凱撒來說是一件好事少了一個政敵，但更是一件壞事羅馬“三巨頭”之間的平衡被打破了，活著的兩巨頭，他和龐培，不得不面臨決斗。凱撒從來沒有看得起過克拉蘇

7、斯。這個只會獻媚的小人死不足惜，但龐培絕不能小看，不然的話凱撒當(dāng)年也不會把自己的女兒尤麗姬嫁給龐培。要知道，龐培比凱撒還要大8歲?，F(xiàn)在，尤麗婭已經(jīng)去世，他們之間除了你死我活己無任何瓜葛。龐培以羅馬唯一執(zhí)政官的地位優(yōu)勢，正在元老院里向他發(fā)動強大的政治攻勢他必須宣傳自己，他必須向元老院陳述自己的功績，但同時又必須表現(xiàn)出一種謙遜、客觀的態(tài)度，不能帶有任何自吹自擂的痕跡。為此，他在這部隨記中，處處用第三人稱稱呼自己，通篇都用異常平靜、簡潔的筆調(diào)敘說戰(zhàn)事的經(jīng)過。 這時他正寫到卷五，說的是公元前54年，他的愛將西塞羅突然遭到維爾納人的圍攻，情況緊急，“于是，他以極大的酬報說服了一個高盧騎兵，送一封信去給西

8、塞羅。送去的信是用希臘文寫的，免得它被敵人截住后得知我軍的計劃”寫到這時，他停了一下，似在考慮更好的措詞。一絲狡猾的微笑從臉上掠過，他繼續(xù)寫了下去時間無情地飛馳，轉(zhuǎn)眼就過了近2000年，凱撒的高盧戰(zhàn)記以其翔實的敘事、清純的文風(fēng)，成為研究羅馬歷史、拉丁文學(xué)和軍事史不可或缺的學(xué)術(shù)資料。1979年，我國商務(wù)印書館將高盧戰(zhàn)記譯成中文，作為“漢譯世界學(xué)術(shù)名著叢書”中的一種出版，譯者任炳湘先生打開這本中文譯本，翻到第124頁，我們看到了上面引述的那樁派人送信給西塞羅的事。然而，治學(xué)嚴謹?shù)淖g者在這里發(fā)現(xiàn)了問題，他注道：“言下之意，似乎高盧人不懂希臘語，即令書信被截去，也不會泄露自己的計劃。但在本書卷一25節(jié)

9、中曾說到在厄爾維幾人營中發(fā)現(xiàn)用希臘文寫的統(tǒng)計數(shù)字，又說高盧人無論公私文件都用希臘文書寫，似乎有矛盾?！睂Υ耍g者的推測是：“也許上面兩節(jié)指的是高盧人用希臘字母書寫自己的語言，這一節(jié)所說的是真正的希臘文。”譯者的質(zhì)疑可說是切中要害，然而譯者的推測卻仍讓人疑云難消。敵營中就沒有一人認識真正的希臘文？他們就不能去找一個希臘人來識這封信(如果他們截住了這封信的話)?足智多謀的凱撒會不考慮這些明擺著的可能而鋌而走險？是不是可以有另外的解釋?確實有另外一種解釋：如果記讓一位密碼學(xué)家來進行推測，他會毫不猶豫地認為凱撒送去的這封信是用密碼寫的!因為任何一本講述密碼學(xué)歷史的著作，都會提到凱撒對軍事密碼學(xué)的貢獻。

10、凱撒在其軍事行動中使用了密碼，這在密碼學(xué)界已不是密碼。置換密碼置換密碼Caesar Caesar 密碼密碼 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCCaesar was a great soldierCaesar was a great soldier密碼本密碼本密文密文Fdhvdu zdv d juhdw vroglhuFdhvdu zdv d juhdw vroglhu明文明文密文密文CAESAR CAESAR 密碼密碼 ：

11、 c=( m+ 3) Mod 26c=( m+ 3) Mod 26A A B B C C D D E E F F G G H H I I J J K K0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010仿射變換密碼仿射變換密碼上面移位置換密碼的一個簡單變種就是仿射變換密碼，上面移位置換密碼的一個簡單變種就是仿射變換密碼，其數(shù)學(xué)表示為其數(shù)學(xué)表示為互素必需與模其中自然數(shù)mambapc)(mod在上面例子移位置換密碼下，明文中相鄰的字母對應(yīng)的在上面例子移位置換密碼下，明文中相鄰的字母對應(yīng)的密文字母也是相鄰的，如密文字母也是相鄰的，如A A和和B B對應(yīng)的密文字母

12、分別為對應(yīng)的密文字母分別為D D和和E,E,但在仿射變換下，但在仿射變換下， 對應(yīng)的密文字母分別為對應(yīng)的密文字母分別為F(F(3 3* *0+5)mod26=5=F0+5)mod26=5=F) )和和I I，它們有，它們有3 3個字母的間隔個字母的間隔(a=3)(a=3)26(mod53 pc11111(mod),1(mod),() (mod)apcbmamaaamapacbmamama仿射變換的解密公式可通過求解同余方程得到記整數(shù) 關(guān)于模 的同余逆為即對上式兩邊同乘得Remark:只有 與 互素，才可能存在 關(guān)于模 的同余逆假設(shè)下面是仿射變換加密的，試破譯此文假設(shè)下面是仿射變換加密的，試破譯

13、此文FSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHKFSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHKFSPVM RDSKA RLVUU RRIFE FKKAN EHOFZ FUKRE SVVSFSPVM RDSKA RLVUU RRIFE FKKAN EHOFZ FUKRE SVVS假設(shè)此問題由假設(shè)此問題由2626個英文字母組成，取個英文字母組成，取m=26.m=26.由于與由于與2626互素，互素，a a有有1212種種不同的取法，不同的取法，b b有有2626種不同的取法，所以放射變換有種不同的取法

14、，所以放射變換有1212* *26=32126=321種。種。可采取窮舉法來破譯?？刹扇「F舉法來破譯?？梢杂妙l率法，即密文中出現(xiàn)次數(shù)最多的字母與英文中最常見的字母可以用頻率法，即密文中出現(xiàn)次數(shù)最多的字母與英文中最常見的字母對應(yīng)。對應(yīng)。在密文中在密文中 在平常統(tǒng)計中在平常統(tǒng)計中F F：出現(xiàn)：出現(xiàn)1212次次 E E：出現(xiàn)頻率：出現(xiàn)頻率 13.04%13.04%R R：出現(xiàn)：出現(xiàn)1212次次 T T：出現(xiàn)頻率：出現(xiàn)頻率 13.04%13.04%S S：出現(xiàn)：出現(xiàn)9 9次次 Z Z：出現(xiàn)頻率：出現(xiàn)頻率 0.08%0.08%K K：出現(xiàn)：出現(xiàn)8 8次次 -1(5)(5),(17)(19),54(mod

15、 26)1719(mod 26)1215 (mod 26)a1512 (mod 26)7 12 (mod 26)6 (mod 26)FERTababa（1）如令對應(yīng)對應(yīng)得同余式這樣有：所以：a=6與26不互素，所以無法對密文解密。-1(17)(5),(18)(19),174(mod 26)1819(mod 26)115 (mod 26)a151(mod 26)7 1(mod 26)7 (mod 26)17-4 7 (mod 26)11(mod 26)15(mod 26)715(mod 26)159 (mod 26)RESTabababcppc （2）如令對應(yīng)對應(yīng)得同余式這樣有：所以：a=7我們

16、可得到加密公式:解密公式:GTGAE RCSGT KESRE GTGAE RCSGT KESRE RKLGU GXDER TMMT RKLGU GXDER TMMT利用上述解密公式對密文進行解密得到：利用上述解密公式對密文進行解密得到：這是一串沒有意義的字符串，解密失敗這是一串沒有意義的字符串，解密失敗最后破譯文為ANAME RICAN SECRE TAGEN TWILL MEETA NAFGH ANISTANMOL EINTH ECOFF EEBAR ATTHU RSDAY AFTER NOON即AN AMERICAN SECRET AGENT WILL MEET AN AFGHANISTA

17、N MOLE IN THE COFFEE BAR AT THURSDAY AFTERNOON破譯成功(3)如令R(17)對應(yīng)E(4)，K(10)對應(yīng)T(19)，得 同余式 17=4a+b(mod26) 10=19a+b(mod26),我們可以得到加密公式：c=3p+5(mod26),解密公式：p=3-1(c-5)(mod26)=9(c-5)(mod26)=9c+7(mod26)HILL密碼q Hill Hill2 2密碼中所用的數(shù)學(xué)手段是密碼中所用的數(shù)學(xué)手段是矩陣運算矩陣運算。q 加密過程：加密過程：1 1）將英文的）將英文的2626個字母個字母與與0 0到到2525之間的整數(shù)建立一一對應(yīng)之間

18、的整數(shù)建立一一對應(yīng)關(guān)系，稱為字母的關(guān)系，稱為字母的表值表值，然后根據(jù)明文字母的表值，將，然后根據(jù)明文字母的表值，將明文信息用數(shù)字表示。設(shè)明文信息只用明文信息用數(shù)字表示。設(shè)明文信息只用2626個大寫字母表個大寫字母表示，通訊雙方給出這示，通訊雙方給出這2626個字母的表值如下：個字母的表值如下：ABCDEFGHIJKLM 2345678910 11 12NOPQRSTUVW XYZ13 14 15 16 17 18 19 20 21 22 23 24 25多重圖系統(tǒng)q Hill Hill密碼中所用的數(shù)學(xué)手段是密碼中所用的數(shù)學(xué)手段是矩陣運算矩陣運算。q 加密過程：加密過程：1 1）將英文的）將英文

19、的2626個字母、個字母、空格和必要的標(biāo)點符號空格和必要的標(biāo)點符號與與1 1到到2929之間的整數(shù)建立一一對應(yīng)關(guān)系，稱為字符的之間的整數(shù)建立一一對應(yīng)關(guān)系，稱為字符的表值表值，然后，然后根據(jù)明文字符的表值，將明文信息用數(shù)字表示。設(shè)通訊根據(jù)明文字符的表值，將明文信息用數(shù)字表示。設(shè)通訊雙方給出這雙方給出這2929個字符的表值如下：個字符的表值如下：ABCDEFGHIGKLMNO123456789101112131415PQRSTUVWXYZ空格空格？！16171819202122232425262728292 2）選擇一個）選擇一個 n 階可逆整數(shù)方陣階可逆整數(shù)方陣A，稱為，稱為HillHilln

20、n密碼的加密碼的加密矩陣，它是加密體制的密矩陣，它是加密體制的“密鑰密鑰”，是加密的關(guān)鍵，是加密的關(guān)鍵，僅僅通訊雙方掌握通訊雙方掌握。3 3）將明文字母分組。）將明文字母分組。 HillHill2 2 使用的是二階矩陣，所以使用的是二階矩陣，所以將明文字母每將明文字母每2 2個一組（可以推廣至個一組（可以推廣至HillHilln n密碼），若最密碼），若最后僅有一個字母，則補充一個沒有實際意義的啞字母。后僅有一個字母，則補充一個沒有實際意義的啞字母。這樣使得每組都有這樣使得每組都有2 2個字母，查出每個字母的表值，構(gòu)個字母，查出每個字母的表值，構(gòu)成一個二維列向量成一個二維列向量 。4 4）令）

21、令 ，由，由 的兩個分量反查字符表值得到的的兩個分量反查字符表值得到的兩個字母即為密文字母。兩個字母即為密文字母。Aq 解密過程：加密過程的逆過程。解密過程：加密過程的逆過程。字符字符（明文）（明文）表值表值一組數(shù)一組數(shù)分組分組向量向量A A左左乘乘向量向量反查表值反查表值密文密文ILLILL密碼的數(shù)學(xué)模型密碼的數(shù)學(xué)模型例：設(shè)明文為“MEET求這段明文的 Hill2 密文。5021A將明文分為： ME ET1 35,52 0A2 34 5,2 51 0 02 92 31 6,2 51 3對應(yīng)的列向量為左乘矩陣后的向量關(guān)于取模對應(yīng)密文WYPM11.1, 2,.ABABBAI (mod m)AmB

22、Am(mod)mmmmZmZnZnBAm定義設(shè) 為一正整數(shù)，記整數(shù)集合對于一個元素屬于的 階方陣 ，若存在一個元素屬于的 階方陣 ，使得稱 為模 可逆。 為 的模 逆矩陣，記為1det( )det1AA (mod)mmZAmmAAZAmmAm命題2.元素屬于的方陣 模 可逆的充要條件是： 和沒有公共的素數(shù)因子。推論2.若方陣 的每個元素屬于，而且則 是模 可逆的，且它的逆矩陣就是 的模 逆矩陣。dcbaA)(mod)(11macbdbcadA設(shè)方陣 滿足命題8.1的條件容易驗證11()(mod)adbcadbcmAmAm其中是關(guān)于模 的同余逆。于是方程組在模 意義下的解為對上面例子對上面例子,

23、det(A)=5,det(A)=5,它與它與2929互素，所以滿足互素，所以滿足2 2 的條件，故的條件，故A A關(guān)于模關(guān)于模2929的逆為的逆為1152525(mod 29)6(mod 29)(521)0 10 130121 17(mod 29)(mod 29)060 6A因為 的同余逆11 17(mod)(mod 29)0 6Am解密公式為：對密文對密文UUQRUUQR進行解密得到進行解密得到1 172344813(mod 29)0 62515051 17162375(mod 29)0 6137820即明文MEETHillHill密碼的加密與解密過程類似于在密碼的加密與解密過程類似于在n

24、n維向量維向量空間中進行線性變換及其逆變換。每個明空間中進行線性變換及其逆變換。每個明文向量是一個文向量是一個Z Zm m上的上的n n維向量，乘以加密矩維向量，乘以加密矩陣并對陣并對m m取余，仍為取余，仍為Z Zm m上的一個上的一個n n維向量。由維向量。由于加密矩陣于加密矩陣A A為模為模m m的可逆矩陣，所以如果的可逆矩陣，所以如果知道了知道了n n個線性無關(guān)的個線性無關(guān)的n n維明文向量及其對維明文向量及其對應(yīng)的密文向量，就可以求出它的加密矩陣應(yīng)的密文向量，就可以求出它的加密矩陣A A及其模及其模m m的逆矩陣的逆矩陣A A-1-1(mod)(mod)公開密鑰系統(tǒng)Hill密碼的加密

25、和解密都只需要加密矩陣這個密鑰就可以了。這種系統(tǒng)稱為單密鑰系統(tǒng)。如果加密和解密使用兩個不同的密鑰，則稱為雙密鑰系統(tǒng)，也稱為公開密鑰系統(tǒng)。密鑰的擁有者將其中一個密鑰公開，另一個保密。雙密鑰系統(tǒng)（1）W.Diffie 和 M.Hellman最早提出 （2）R.L.Rivest, A.Shamir和 L.Adleman 提出第一個方法雙密鑰系統(tǒng)的程序是這樣的收方先告訴發(fā)方如何把情報制成密碼（敵人也聽到）發(fā)方依法發(fā)出情報的密文（敵人也可能收到密文）收方將密碼還原成原文（敵人卻解不開密文）公鑰密碼系統(tǒng)的加密原理 每個通信實體有一對密鑰（公鑰，私鑰）。公鑰公開，用于加密，私鑰保密，用作解密 A向B 發(fā)送消

26、息，用B的公鑰加密 B收到密文后，用自己的私鑰解密PlainText加密算法解密算法ABcipherPlainTextB的私鑰C的公鑰B的公鑰任何人向B發(fā)送信息都可以使用同一個密鑰(B的公鑰)加密沒有其他人可以得到B 的私鑰，所以只有B可以解密A A向向B B 發(fā)送消息，用發(fā)送消息，用A A的私鑰加密（簽名）的私鑰加密（簽名）B B收到密文后，用收到密文后，用A A的公鑰解密（驗證）的公鑰解密（驗證）PlainText加密算法解密算法cipherPlainTextABA的私鑰A的公鑰Ron Rivest, Adi Shamir , Leonard Ron Rivest, Adi Shamir

27、, Leonard AdlemanAdlemanRSARSA的安全性基于大數(shù)分解的難度的安全性基于大數(shù)分解的難度RSARSA在美國申請了專利（已經(jīng)過期），在其在美國申請了專利（已經(jīng)過期），在其他國家沒有他國家沒有RSARSA已經(jīng)成了事實上的工業(yè)標(biāo)準(zhǔn)，在美國除已經(jīng)成了事實上的工業(yè)標(biāo)準(zhǔn)，在美國除外外a a與與b b的最大公因數(shù)：的最大公因數(shù)：gcd (a, b)gcd (a, b)gcd(20, 24)=4 , gcd (15, 16)=1gcd(20, 24)=4 , gcd (15, 16)=1如果如果gcd(a, b)=1 gcd(a, b)=1 ，稱，稱a a與與b b 互素互素模運算模運

28、算 modmoda= q n +r 0rn ; q=a/n ;a= q n +r 0rn ; q=a/n ; x x 表示小于或等于表示小于或等于x x的最的最大整數(shù)大整數(shù)a=a/nn + (a mod n) , r = m mod n a=a/nn + (a mod n) , r = m mod n 如果如果 (a mod n )= (b mod n) (a mod n )= (b mod n) ，則稱則稱a a 與與b b 模模n n同余同余，記為記為 a a b mod n b mod n 例如，例如， 23 8 mod 5 , 8 1 mod 723 8 mod 5 , 8 1 mod

29、 7模運算是可交換的、可結(jié)合的、可分配的模運算是可交換的、可結(jié)合的、可分配的(a+b) mod n = (a mod n ) + (b mod n) ) mod n(a-b) mod n = ( (a mod n) (b mod n) ) mod n(ab) mod n = ( (a mod n ) （b mod n) ) mod n (a (b+c) ) mod n = （( a b) mod n + (a c) mod n）mod n 冪,模運算 ma mod n m2 mod n = (mm) mod n = (m mod n ) 2 mod n m4 mod n = (m2 mod n

30、 ) 2 mod n m8 mod n = ( (m2 mod n )2 mod n )2 mod n m25 mod n = (m m8 m16) mod n 歐拉函數(shù)歐拉函數(shù)(n) (n) n n是正整數(shù)，是正整數(shù)， (n) (n) 是比是比n n小且與小且與n n 互素的正整數(shù)的個數(shù)互素的正整數(shù)的個數(shù)(3)=|(3)=|1, 2| =21, 2| =2 (4)=|(4)=|1, 3| =21, 3| =2 (5)=|(5)=|1, 2, 3, 4 | =41, 2, 3, 4 | =4 (6)=|(6)=|1, 5| =41, 5| =4 (7)=|(7)=|1, 2, 3, 4, 5,

31、 6| =61, 2, 3, 4, 5, 6| =6(10)=|(10)=|1, 3, 7, 9| =41, 3, 7, 9| =4 (11)=|(11)=|1, 2,3,4,5,6, 7,8, 9,10| =101, 2,3,4,5,6, 7,8, 9,10| =10 如果如果p p是素數(shù)，則是素數(shù)，則(p)=p-1, (p)=p-1, 比如比如(2), (2), (5)(5)， (11)(11)如果如果p,q p,q 是素數(shù)，則是素數(shù)，則(pq)=(pq)=(p) (p) (q)(q) (p-1)(q-1) (p-1)(q-1) 。比如，比如，(10)= (10)= （2 2* *5 5）

32、= = （2 2） （5 5）=1=1* *4=44=4例如：例如： m=3, n=10; m=3, n=10; (10)=4(10)=4 m m(n)(n)=3=34 4=81 ; 81 mod 10 = 1=81 ; 81 mod 10 = 1 即即 81 1 mod 1081 1 mod 10 3 34+14+1 = 243 3 mod 10 = 243 3 mod 10 nmn mod 1)(nmmn mod 1)(歐拉定理歐拉定理 若整數(shù)若整數(shù)m 和和n 互素，則互素，則等價形式等價形式推論：給定兩個素數(shù)推論：給定兩個素數(shù)p, qp, q , , 兩個正整數(shù)兩個正整數(shù) n n, , m m ，使得，使得n=pq, 0mnn=pq, 0mn ； 則對于任則對于任意正整數(shù)意正整數(shù)k k ，下列關(guān)系