1、第2章 密碼學(xué)概論古典密碼學(xué)對(duì)稱密碼體制公鑰密碼體制日暮蒼山蘭舟小日暮蒼山蘭舟小 本無落霞綴清泉 去年葉落緣分定 死水微漾人卻亡隱寫術(shù)加密系統(tǒng)模型密碼學(xué)發(fā)展階段1949年之前密碼學(xué)是一門藝術(shù)19491975年密碼學(xué)成為科學(xué)1976年以后密碼學(xué)的新方向公鑰密碼學(xué)第1階段古典密碼(1/3)密碼學(xué)還不是科學(xué)，而是藝術(shù)出現(xiàn)一些密碼算法和加密設(shè)備密碼算法的基本手段是代換(substitution)和置換(permutation)，針對(duì)的是字符簡(jiǎn)單的密碼分析手段出現(xiàn)主要特點(diǎn)：數(shù)據(jù)的安全基于算法的保密20世紀(jì)早期密碼機(jī)第1階段古典密碼(2/3)第1階段古典密碼(3/3)1883年Kerchoffs第一次明確

2、提出了編碼的原則：加密算法應(yīng)建立在算法的公開不影響明文和密鑰的安全。這一原則已得到普遍承認(rèn)，成為判定密碼強(qiáng)度的衡量標(biāo)準(zhǔn)，實(shí)際上也成為傳統(tǒng)密碼和現(xiàn)代密碼的分界線。第2階段 19491975(1/1)計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能相關(guān)技術(shù)的發(fā)展1949年Shannon的“The Communication Theory of Secret Systems”提出了兩種“安全”，即“理論安全”和“實(shí)際安全”，證明了要達(dá)到“理論安全”，密鑰的長(zhǎng)度必須長(zhǎng)于或等于明文的長(zhǎng)度1967年David Kahn的The Codebreakers1971-73年IBM Watson實(shí)驗(yàn)室的Horst Feist

3、el等幾篇技術(shù)報(bào)告主要特點(diǎn)：數(shù)據(jù)的安全基于密鑰而不是算法的保密 第3階段 19761977年DES正式成為標(biāo)準(zhǔn)80年代出現(xiàn)“過渡性”的“Post DES”算法，如IDEA、RCx、CAST等90年代對(duì)稱密鑰密碼進(jìn)一步成熟 Rijndael、RC6、MARS、Twofish、 Serpent等出現(xiàn)2001年Rijndael成為DES的替代者(AES)第3階段 19761976年：Diffie & Hellman 的 “New Directions in Cryptography” 提出了不對(duì)稱密鑰密1977年Rivest,Shamir & Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲

4、線等其他公鑰算法主要特點(diǎn)：公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡芑靖拍?1/4)密碼學(xué)(Cryptology): 是研究信息系統(tǒng)安全保密的科學(xué).密碼編碼學(xué)(Cryptography): 主要研究對(duì)信息進(jìn)行編碼,實(shí)現(xiàn)對(duì)信息的隱蔽.密碼分析學(xué)(Cryptanalytics):主要研究加密消息的破譯或消息的偽造.基本概念(2/4)明文( Plaintext)：消息的初始形式；密文( CypherText)：加密后的形式加密算法(Encryption Algorithm):對(duì)明文進(jìn)行加密操作時(shí)所采用的一組規(guī)則稱作加密算法(Encryption Algorithm).解密算法(Decr

5、yption Algorithm):接收者對(duì)密文解密所采用的一組規(guī)則稱為解密算法(Decryption Algorithm)密鑰(Key):加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的,分別稱為加密密鑰(Encryption Key) 和解密密鑰(Decryption Key).基本概念(3/4)記：明文記為P且P為字符序列， P=P1,P2,Pn密文記為C, C=C1,C2,Cn明文和密文之間的變換記為 C=E(P)及P=D(C)其中 C表示密文，E為加密算法；P為明文，D為解密算法我們要求密碼系統(tǒng)滿足：P=D(E(P)需要密鑰的加密算法，記為：C=E(K,P),即密文消息同時(shí)依賴于

6、初始明文和密鑰的值。實(shí)際上，E是一組加密算法，而密鑰則用于選擇其中特定的一個(gè)算法。加密與解密的密鑰相同，即：P=D(K,E(K,P)加密與解密的密鑰不同，則：P=D(KD,E(KE,P)基本概念(4/4)密碼編碼系統(tǒng)分類保密內(nèi)容密鑰數(shù)量明文處理的方式保密內(nèi)容受限制的（restricted)算法算法的保密性基于保持算法的秘密 基于密鑰（key-based)的算法算法的保密性基于對(duì)密鑰的保密密鑰數(shù)量對(duì)稱密碼算法（symmetric cipher)加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個(gè)易于推出另一個(gè)又稱秘密密鑰算法或單密鑰算法非對(duì)稱密鑰算法（asymmetric cipher)加密密鑰和解密

7、密鑰不相同，從一個(gè)很難推出另一個(gè)又稱公開密鑰算法（public-key cipher) 公開密鑰算法用一個(gè)密鑰進(jìn)行加密, 而用另一個(gè)進(jìn)行解密其中的加密密鑰可以公開,又稱公開密鑰（public key)，簡(jiǎn)稱公鑰。解密密鑰必須保密,又稱私人密鑰（private key)私鑰，簡(jiǎn)稱私鑰明文處理方式分組密碼（block cipher)將明文分成固定長(zhǎng)度的組，用同一密鑰和算法對(duì)每一塊加密，輸出也是固定長(zhǎng)度的密文。流密碼（stream cipher)又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文。對(duì)稱密碼又名： 傳統(tǒng)加密 / 單鑰加密/私鑰加密 發(fā)送方和接收方共享同一個(gè)密鑰幾乎所有的經(jīng)典加密算法都是這

8、種類型在70年代公鑰密碼體制被發(fā)明之前這是唯一的密碼類型。對(duì)稱密碼簡(jiǎn)化模型對(duì)稱密碼要求對(duì)稱密碼要安全使用有兩個(gè)要求:加密算法足夠強(qiáng)密鑰僅為發(fā)送者和接受者知道Y = EK(X)X = DK(Y)加密算法是開放的,大家都知道.所以安全性取決于密鑰有安全的通道發(fā)放密鑰。密碼編碼學(xué)特征:所使用的加密運(yùn)算代換(替換) / 置換密鑰數(shù)量單密鑰 或私鑰 /兩個(gè)密鑰或公鑰處理明文的方法分組 / 流密碼分析試圖破譯單條消息試圖識(shí)別加密的消息格式，以便借助直接的解密算法破譯后續(xù)的消息試圖找到加密算法中的普遍缺陷(無須截取任何消息)密碼分析的條件與工具已知加密算法截取到明文、密文中已知或推測(cè)的數(shù)據(jù)項(xiàng)數(shù)學(xué)或統(tǒng)計(jì)工具和

9、技術(shù)語言特性計(jì)算機(jī)技巧與運(yùn)氣攻擊傳統(tǒng)密碼方法密碼分析學(xué)窮舉攻擊密碼分析類型窮舉攻擊試遍所有密鑰直到有一個(gè)合法的密鑰能夠把密文還原成為明文,就是窮舉攻擊.Brute Force Search窮舉攻擊與密鑰的長(zhǎng)度正比 假設(shè)知道或者能夠辨認(rèn)是否明文更多定義無條件安全：無論提供的密文有多少，如果由一個(gè)加密方案產(chǎn)生的密文中包含的信息不足以唯一地決定對(duì)應(yīng)的明文除了一次一密的方案外，沒有無條件安全的算法安全性體現(xiàn)在：破譯的成本超過加密信息的價(jià)值破譯的時(shí)間超過該信息有用的生命周期滿足這兩個(gè)條件: 計(jì)算上是安全的第2.1章 經(jīng)典加密技術(shù)替代置換轉(zhuǎn)子機(jī)替代明文的字母由其它字母或數(shù)字或符號(hào)代替若該明文被視為一個(gè)比特

10、序列，則替代涉及到用密文比特模式代替明文比特模式Caesar 密碼已知最早的代換加密算法由 Julius Caesar 發(fā)明首先用于軍事中Ci=E(Pi)=Pi+3例子:meet me after the toga partyPHHW PH DIWHU WKH WRJD SDUWBCaesar Cipher定義替換如下:a b c d e f g h i j k l m n o p q r s t u v w x y zD E F G H I J K L M N O P Q R S T U V W X Y Z A B C給每個(gè)字母賦一個(gè)數(shù)a b c d e f g h i j k l m0 1

11、 2 3 4 5 6 7 8 9 10 11 12n o p q r s t u v w x y Z13 14 15 16 17 18 19 20 21 22 23 24 25則 Caesar 密碼如下進(jìn)行:C = E(p) = (p + k) mod (26)p = D(C) = (C k) mod (26)愷撒密碼的特點(diǎn)單字母密碼（簡(jiǎn)單替換技術(shù)）簡(jiǎn)單，便于記憶缺點(diǎn)：結(jié)構(gòu)過于簡(jiǎn)單，密碼分析員只使用很少的信息就可預(yù)言加密的整個(gè)結(jié)構(gòu)分析Caesar Cipher 僅有26種可能替換A 映射到 A,B,.Z 可以循環(huán)試驗(yàn) 使用 brute force search 僅僅需要能認(rèn)識(shí)明文即可例如. 解

12、密 ciphertext GCUA VQ DTGCM例:PHHW PH DIWHU WKH WRJD SDUWB1oggv og chvgt vjg vqic rctva2nffu nf bgufs uif uphb qbsuz3meet me after the toga party4ldds ld zesdq sgd snfz ozqsx5678925qiix qi ejxiv xli xske tevxc改進(jìn)：?jiǎn)伪泶鷵Q密碼不僅僅將字母移位 對(duì)字母進(jìn)行無規(guī)則的重新排列因此密鑰是 26 字母長(zhǎng) 明文: abcdefghijklmnopqrstuvwxyz 密文: DKVQFIBJWPESCX

13、HTMYAUOLRGZN明文文本: ifwewishtoreplaceletters密文文本: WIRFRWAJUHYFTSDVFSFUUFYA 任意替換：26！41026 可能的key，大于56位DES的密鑰空間。基于語言統(tǒng)計(jì)規(guī)律仍可破譯單表代換密碼單表代換密碼安全性共有 26! = 4 x 1026 密鑰 有這么多密鑰應(yīng)該安全了吧！!WRONG! 問題是人類語言的統(tǒng)計(jì)特性語言的冗余特性人類語言是冗余的 例如 th lrd s m shphrd shll nt wnt 每個(gè)字母被使用的頻率不相同 在英語中 e 是被用的最多的字母 接著是 T,R,N,I,O,A,S 其他的字母用的很少 。例如

14、 Z,J,K,Q,X 有單個(gè)字母，兩個(gè)字母和三個(gè)字母出現(xiàn)的頻率表 英語中字母出現(xiàn)的頻率密碼分析學(xué)中的應(yīng)用單表替換不改變統(tǒng)計(jì)特性 由阿拉伯科學(xué)家在9世紀(jì)發(fā)現(xiàn)這個(gè)規(guī)律計(jì)算密文中每個(gè)字母出現(xiàn)的頻率然后與已知的統(tǒng)計(jì)特性相比較 對(duì)于 Caesar 密碼來說尋找最常出現(xiàn)的和最不常出現(xiàn)的字母 最常出現(xiàn): E,T,R,N,I,O,A,S最不常出現(xiàn): JK, X-Z對(duì)于單表替換要確認(rèn)每個(gè)字母的對(duì)應(yīng)關(guān)系可以使用最常出現(xiàn)的那些單個(gè)字母，雙字母對(duì)和三字母對(duì)。解密例子給定密文:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQ

15、UZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ計(jì)算每個(gè)字母出現(xiàn)的相對(duì)頻率 猜測(cè) P & Z 對(duì)應(yīng) e & t假設(shè) ZW 是 th ，因此 ZWP 就是the繼續(xù)試驗(yàn)可以得到下面的明文:it was disclosed yesterday that several informal butdirect contacts have been made with politicalrepresentatives of the viet cong in moscow例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSX

16、AIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQPlayfair 密碼在單表替換中長(zhǎng)密鑰并沒有提供足夠的理想的安全性 增強(qiáng)安全性的一個(gè)途徑是對(duì)多個(gè)字母組合進(jìn)行加密 Playfair 密碼就是這樣做的由 Charles Wheatstone在 1854發(fā)明, 但是由他的朋友 Baron Playfair 名字命名Playfair 密鑰矩陣是一個(gè)由密鑰決定的55矩陣首先填入密鑰矩陣剩余部分填入其他的字母例如. 使用密鑰 MONARCHYMONARCHYBDEFGIKLPQSTUVWXZ加密和

17、解密算法Playfair 密碼的安全性相對(duì)于單表替換密碼來說安全性增強(qiáng)了有 2626 = 676 字母對(duì) 需要對(duì) 676 字母對(duì)進(jìn)行分析 因此生成的密文更復(fù)雜 被廣泛的使用的了很多年 (例如. US & British military in WW1) 給定幾百個(gè)密文就能被破解 因?yàn)樗€是保留了明文的結(jié)構(gòu) 題目當(dāng)海軍上尉John F .Kennedy下令日本毀滅者擊沉美國(guó)巡邏艇PT-109時(shí)，澳大利亞的無線站截獲了一條用Playfair密碼加密的消息：KXJEY UREBE ZWEHE WRYTU HEYFSKREHE GOYFI WTTTU OLKSY CAJPOBOTEI ZONTX BY

18、BWT GONEY CUZWRGDSON SXBOU YWRHE BAAHY USEDQ密鑰為royal new zealand navy。請(qǐng)解密這條消息。Plyafair解答(1/4)加密步驟：1.填充55矩陣2.落在矩陣同一行的明文字母對(duì)由其右邊的字母代換3.落在矩陣同一列的明文字母對(duì)由其下面的字母代換4.其他的每組明文字母對(duì)按如下方式變換：它所在的行是該字母的行，列則為另一字母所在的列Plyafair解答(2/4)解密步驟：1.填充5*5矩陣2.落在矩陣同一行的明文字母對(duì)由其左邊的字母代換3.落在矩陣同一列的明文字母對(duì)由其上邊的字母代換4.其他的每組明文字母對(duì)按如下方式變換：它所在的行是

19、該字母的行，列則為另一字母所在的列Plyafair解答(3/4)密鑰： royal new zealand navy去掉空格，去掉重復(fù)字母：royalynewzdv構(gòu)造5*5矩陣R O Y A LN E W Z DV B C F GH I/J K M PQ S T U XPlyafair解答(4/4)明文分組，每?jī)蓚€(gè)一組：KX JE YU RE BE ZW EH EW RY TU HE YF SK RE HE GO YF IW TT TU OL KS YC AJ PO BO TE IZ ON TX BY BW TG ON EY CU ZW RG DS ON SX BO UY WR HE BA

20、AH YU SE DQ每組進(jìn)行解密：PT BO AT ON EO WE NI NE LO ST IN AC TI ON IN BL AC KE TT ST RA IT TW OM IL ES SW ME RE SU CO VE XC RE WO FT WE LV EX RE QU ES TA NY IN FO RM AT IO NX重新組合，得到：PT BOAT ONE OWE NINE LOST IN ACTION IN BLACKETT STRAIT TWO MILES SW MERESU COVE X CREW OF TWELVE X REQUEST ANY INFORMATION X多

21、表代換密碼另一種增強(qiáng)安全性的方法是 使用多表替換 破壞統(tǒng)計(jì)特性使用相關(guān)的單表代換規(guī)則用密鑰選擇決定使用那個(gè)代換表 Vigenre Cipher 明文密鑰 密文 a b c d e f g h i j k l m n o y zabcdefghijklmnoZA B C D E F G H I J K L M N O Y ZB C D E F G H I J K L M N O P Z AC D E F G H I J K L M N O P R A BD E F G H I J K L M N O P R S B CE F G H I J K L M N O P R S T C DF G H

22、I J K L M N O P R S T U D EG H I J K L M N O P R S T U V E F H I J K L M N O P R S T U V W F G I J K L M N O P R S T U V W X G H J K L M N O P R S T U V W X Y H I K L M N O P R S T U V W X Y Z I J L M N O P R S T U V W X Y Z A J K M N O P R S T U V W X Y Z A B K L N O P R S T U V W X Y Z A B C L M O

23、 P R S T U V W X Y Z A B C D M NZ A B C D E F G H I J K L M N X YVigenre Cipher維吉尼亞密本加密 舉例：若我們選用明文為：Vigenere ciphere，密鑰則選用以上26個(gè)字母所組成的任一單詞或詞組如：radio。見下表：相同字母加密為不同的密文(如字母e)不同的字母加密為相同的密文(如字母H)例子例如使用密鑰 deceptive密鑰: deceptivedeceptivedeceptive明文: wearediscoveredsaveyourself密文: ZICVTWQNGRZGVTWAVZHCQYGLMGJ Hill密碼C1=(K11P1+K12P2+K13P3)mod26C2=(K21P1+K22P2+K23P3)mod26C3=(K31P1+K32P2+K33P3)mod26C=KPHill完全隱藏了單字母的頻率，如果m=3，也隱藏了兩個(gè)字母的頻率攻擊：題目構(gòu)造一個(gè)用選擇明文破譯H