現(xiàn)代密碼學(xué)理論與實踐第2章傳統(tǒng)加密技術(shù)

1、現(xiàn)代密碼學(xué)理論與實踐第2章 傳統(tǒng)加密技術(shù)Fourth Edition by William Stallings楊壽保syanghttp:/syang2012年9月8/28/2022Cryptography and Network Security - 2Part OneSymmetric CiphersRoad Map for Part OneChp.2, Classical Encryption TechniquesChp.3, Block Cipher and the Data Encryption StandardChp.4, Finite FieldsChp.5, Advanced E

2、ncryption StandardChp.6, More on Symmetric CiphersChp.7, Confidentiality Using Symmetric Encryption8/28/20222Cryptography and Network Security - 2Chapter 2 Classical Encryption TechniquesMany savages at the present day regard their names as vital parts of themselves, and therefore take great pains t

3、o conceal their real names, lest these should give to evil-disposed persons a handle by which to injure their owners. The Golden Bough, Sir James George Frazer8/28/20223Cryptography and Network Security - 2密碼學(xué)的演變歷史(1) William Friedman1918, William Friedmans The Index of Coincidence and its Applicati

4、ons in CryptographyWilliam Frederick Friedman (Sept. 24,1891 Nov. 12, 1969) 美國陸軍密碼專家。1930年代，他領(lǐng)導(dǎo)了陸軍的一個研究部門Signals Intelligence Service (SIS)，其中一部分服務(wù)一直延續(xù)到五十年代。三十年代晚期，在他的指導(dǎo)下，F(xiàn)rank Rowlett 破解了日本人的PURPLE加密機(jī)(紫密)，截獲了日本的大量外交和軍事的秘密。8/28/20224Cryptography and Network Security - 2密碼學(xué)的演變歷史(2) 香農(nóng)的貢獻(xiàn)1948年, Claude

5、 Shannons發(fā)表 “The Communication Theory of Secrecy System”， 成為現(xiàn)代密碼學(xué)理論基礎(chǔ)。1949年，Shannon在其著名的“信息論” 發(fā)表一年之后，又發(fā)表了論文“保密系統(tǒng)的通信理論”， 首次將密碼學(xué)研究置于堅實的數(shù)學(xué)基礎(chǔ)上。 該理論的重大貢獻(xiàn)在于：建立了通信保密/密碼學(xué)嚴(yán)格的理論基礎(chǔ)； 證明了一次一密(one-time pad)的密碼系統(tǒng)是完善保密的，導(dǎo)致了對流密碼的研究和應(yīng)用； 提出分組密碼設(shè)計應(yīng)該遵循的準(zhǔn)則，如擴(kuò)散性和混淆性； 證明了消息冗余使得破譯者統(tǒng)計分析成功的理論值(唯一解距離) 8/28/20225Cryptography an

6、d Network Security - 2密碼學(xué)的演變歷史(2)Claude Elwood Shannon (Apr. 30, 1916 Feb. 24, 2001), 美國電氣工程師和數(shù)學(xué)家，被譽為信息論之父 the father of information theory.香農(nóng)之有名在于他以1948年發(fā)表的那篇曠世論文而奠定了現(xiàn)代信息論基礎(chǔ)。其實早在1937年，當(dāng)21歲的香農(nóng)還是MIT的碩士研究生時，他便在他的碩士論文中論述了布爾代數(shù)的電子實現(xiàn)和應(yīng)用，可以構(gòu)建和解決任何邏輯的和數(shù)字的關(guān)系，因此奠定了數(shù)字計算機(jī)和數(shù)字電路設(shè)計理論的基礎(chǔ)。他的碩士論文一直被認(rèn)為是迄今最重要的碩士論文。 194

7、9-1967，密碼學(xué)研究處于沉寂時期8/28/20226Cryptography and Network Security - 2密碼學(xué)的演變歷史(3)Feistel, Whitfield Diffie, Matin Hellman1971, IBM發(fā)明Luciffer Cipher, 128位密鑰作分組加密。這項發(fā)明是由Horst Feistel(Jan.30, 1915Nov.14,1990)領(lǐng)導(dǎo)的，他是密碼學(xué)家，當(dāng)時在IBM負(fù)責(zé)設(shè)計加密器，他的工作最終激發(fā)了70年代Data Encryption Standard (DES)的研發(fā)高潮1976-1977，美國國家標(biāo)準(zhǔn)局正式公布實施DES1

8、975, Whitfield Diffie 和 Matin Hellman, 發(fā)表A New Direction in Cryptography, 首次提出適應(yīng)網(wǎng)絡(luò)保密通信的公開密鑰思想，揭開現(xiàn)代密碼學(xué)研究的序幕，具有劃時代的意義8/28/20227Cryptography and Network Security - 2密碼學(xué)的演變歷史(4)R.S.A., Abbas El Gamal, Lai Xuejia 1977-1978，Ronald Rivest, Adi Shamir, Len Adleman第一次提出公開密鑰密碼系統(tǒng)的實現(xiàn)方法RSA1981，成立International As

9、sociation for Cryptology Research1985，Abbas El Gamal提出概率密碼系統(tǒng)ElGamal方法1990-1992，Lai Xuejia and James: IDEA, The International Data Encryption Algorithm2000, AES, Advanced Encryption Standard8/28/20228Cryptography and Network Security - 2Cryptology(保密學(xué))，源自希臘語(Greek)Krypts: hidden; logos: word, 是密碼學(xué)和密碼

10、處理過程的研究Cryptography: The Science and Study of Secret Writing，密碼編碼學(xué)Cryptanalysis: The Science and Study of Secret Breaking，密碼破譯學(xué)Cipher: A secret method of writing 加密方法Encipher (encipherment), encryption: 將明文轉(zhuǎn)換成密文的過程Decipher (decipherment), decryption: 將密文還原成明文的過程Plaintext (cleartext): 原始的可讀數(shù)據(jù)，明文Ciphe

11、rtext (Cryptogram): 加密后的不可解讀之文件，密文Key: 密鑰，對加密與解密過程進(jìn)行控制的參數(shù)E(m): Encryption Transformation 加密變換D(c): Decryption Transformation 解密變換密碼學(xué)基本術(shù)語 Terminologies8/28/20229Cryptography and Network Security - 2什么是密碼？簡單地說它就是一組含有參數(shù)K的變換E。設(shè)已知消息m，通過變換Ek得密文C，這個過程稱為加密，E為加密算法，k不同，密文C亦不同。傳統(tǒng)的保密通信機(jī)制：EncipherPlaintextCipher

12、textKeysDecipherC=Ek(m)發(fā)方： m收方：mkk（公共信道）加密E解密D（秘密信道）簡單加密系統(tǒng)模型8/28/202210Cryptography and Network Security - 2理論安全，或無條件安全Theoretical Secure (or Perfect Secure) 攻擊者無論截獲多少密文，都無法得到足夠的信息來唯一地決定明文。Shannon用理論證明：欲達(dá)理論安全，加密密鑰長度必須大于等于明文長度，密鑰只用一次，用完即丟，即一次一密，One-time Pad，不實用。實際安全，或計算上安全Practical Secure (or Computa

13、tionally Secure) 如果攻擊者擁有無限資源，任何密碼系統(tǒng)都是可以被破譯的；但是在有限的資源范圍內(nèi)，攻擊者都不能通過系統(tǒng)的分析方法來破解系統(tǒng)，則稱這個系統(tǒng)是計算上安全的或破譯這個系統(tǒng)是計算上不可行(Computationally Infeasible)。 理論安全和實際安全8/28/202211Cryptography and Network Security - 2加密的基本概念密碼體制加密系統(tǒng)采用的基本工作方式稱為密碼體制，密碼體制的基本要素是密碼算法和密鑰。密碼算法是一些公式、法則或程序；密鑰是密碼算法中的控制參數(shù)。加密系統(tǒng)可以用數(shù)學(xué)符號來描述：SP, C, K, E, DP

14、：明文空間 C：密文空間K：密鑰空間 E：加密變換D：解密變換 kK，則有CEk(P)，PDk(C)Dk(Ek(P)， 或者DkEk-1，且EkDk-1。8/28/202212Cryptography and Network Security - 2對稱密碼體制(Symmetric System, One-key System, Secret-key System) 加密密鑰和解密密鑰相同，或者一個密鑰可以從另一個導(dǎo)出，能加密就能解密，加密能力和解密能力是結(jié)合在一起的，開放性差。非對稱密碼體制(Asymmetric System, Two-key System, Public-key Syst

15、em) 加密密鑰和解密密鑰不相同，從一個密鑰導(dǎo)出另一個密鑰是計算上不可行的，加密能力和解密能力是分開的，開放性好。對稱密碼體制和非對稱密碼體制8/28/202213Cryptography and Network Security - 2序列密碼如果密文不僅與最初給定的算法和密鑰有關(guān)，同時也與明文位置有關(guān)(是所處位置的函數(shù))，則稱為序列密碼體制。加密以明文比特為單位，以偽隨機(jī)序列與明文序列模2加后，作為密文序列。分組密碼如果經(jīng)過加密所得到的密文僅與給定的密碼算法和密鑰有關(guān)，與被處理的明文數(shù)據(jù)在整個明文中的位置無關(guān)，則稱為分組密碼體制。通常以大于等于64位的數(shù)據(jù)塊為單位，加密得相同長度的密文。序

16、列密碼體制和分組密碼體制8/28/202214Cryptography and Network Security - 2確定型密碼體制和概率密碼體制確定型：當(dāng)明文和密鑰確定后，密文也就唯一地確定了；概率型：當(dāng)明文和密鑰確定后，密文通過客觀隨機(jī)因素從一個密文集合中產(chǎn)生，密文形式不確定，稱為概率型密碼體制。單向函數(shù)型密碼體制和雙向變換型密碼體制單向函數(shù)型密碼體制適用于不需要解密的場合，容易將明文加密成密文，如哈希函數(shù)；雙向變換型密碼體制可以進(jìn)行可逆的加密、解密變換。其他加密體制8/28/202215Cryptography and Network Security - 2現(xiàn)代密碼學(xué)的基本原則設(shè)計加

17、密系統(tǒng)時，總是假定密碼算法是可以公開的，需要保密的是密鑰。一個密碼系統(tǒng)的安全性不在算法的保密，而在于密鑰，即Kerckhoff原則。對加密系統(tǒng)的要求 系統(tǒng)應(yīng)該是實際上安全的(practical secure)，截獲密文或已知明文密文對時，要決定密鑰或任意明文在計算上是不可行的。加密解密算法適用于密鑰空間中的所有元素。系統(tǒng)易于實現(xiàn)，使用方便。系統(tǒng)的安全性不依賴于對加密體制或加密算法的保密，而依賴于密鑰。系統(tǒng)的應(yīng)用不應(yīng)使通信網(wǎng)絡(luò)的效率過分降低?，F(xiàn)代密碼學(xué)基本原則及加密系統(tǒng)要求8/28/202216Cryptography and Network Security - 2對稱加密系統(tǒng)由以下五部分組成

18、Plaintext： 明文Encryption algorithm：加密算法Key： 密鑰Ciphertext：密文Decryption algorithm：解密算法加密算法必須足夠強(qiáng)大，使破譯者不能僅根據(jù)密文破譯消息收發(fā)雙方必須在某種安全的形式下獲得密鑰并必須保證密鑰的安全2.1 對稱密碼系統(tǒng)的模型8/28/202217Cryptography and Network Security - 2傳統(tǒng)密碼的簡化模型8/28/202218Cryptography and Network Security - 2對稱密碼系統(tǒng)的要求使用對稱密碼系統(tǒng)有兩個基本要求一個強(qiáng)加密算法一個只有發(fā)送方和接收方知道

19、的秘密密鑰Y = EK(X)X = DK(Y)必須假定加密算法是公開的因此必須有安全的途徑或信道分發(fā)密鑰8/28/202219Cryptography and Network Security - 2傳統(tǒng)密碼體制的模型Y = Ek(X)X = Dk(Y)8/28/202220Cryptography and Network Security - 2密碼編碼學(xué)(Cryptography)密碼編碼系統(tǒng)根據(jù)以下三個獨立方面進(jìn)行分類用于將明文轉(zhuǎn)換為密文的操作類型：代換和置換所使用的密鑰的數(shù)量和方式：對稱密碼體制(單鑰系統(tǒng)、秘密密鑰系統(tǒng))非對稱密碼體制(雙鑰系統(tǒng)、公開密鑰系統(tǒng))明文的處理方式：分組加密和

20、流加密密碼分析學(xué)(Cryptanalysis)密碼分析：試圖破譯密文得到明文或試圖獲得密鑰的過程為密碼分析，密碼破譯的策略取決于加密方法及可供破譯者使用的信息。窮舉攻擊：對密文嘗試所有可能的密鑰，直到把它轉(zhuǎn)化為可讀的有意義的明文，至少要嘗試1/2種所有可能的密鑰。Cryptology 密碼學(xué)8/28/202221Cryptography and Network Security - 2對加密信息的攻擊類型唯密文攻擊 only know algorithm and ciphertext, is statistical, know or can identify plaintext 已知明文攻擊

21、know/suspect plaintext and ciphertext選擇明文攻擊 select plaintext and obtain ciphertext選擇密文攻擊 select ciphertext and obtain plaintext選擇文本攻擊 select plaintext or ciphertext to en/decrypt8/28/202222Cryptography and Network Security - 28/28/202223Cryptography and Network Security - 2窮舉攻擊總是可以簡單地嘗試每一個可能的密鑰 窮舉攻擊

22、是最基本的攻擊，難度與密鑰長度成正比 平均來說要獲得成功必須嘗試所有可能密鑰的一半8/28/202224Cryptography and Network Security - 22.2 代換密碼(Substitution)代換法是將明文字母替換成其他字母、數(shù)字或符號的加密方法如果把明文看成是二進(jìn)制序列的話，代換就是用密文位串來代換明文位串代換法改變明文內(nèi)容的表示形式，保持內(nèi)容元素之間相對位置不變已知最早的代換密碼是由Julius Caesar發(fā)明的愷撒密碼Caesar Cipher，對字母表中的每個字母用它之后的第3個字母來代換。例如：meet me after the toga partyP

23、HHW PH DIWHU WKH WRJD SDUWB8/28/202225Cryptography and Network Security - 22.2.1 Caesar CipherCaesar實際上是一種單表代換密碼明文字母用密文字母表中對應(yīng)字母代替，例：明文字母表 Pp0, p1, , pn-1密文字母表 Cc0, c1, , cn-1密鑰為正整數(shù)k，加密：i+k j (mod n) 解密：j-k i (mod n)Caesar Cipher，加密：C = E(p)=(p+k) mod 26 解密：p = D(C)=(C-k) mod 26, 0A；1B；25Z8/28/202226

24、Cryptography and Network Security - 2Caesar 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讓每個字母等價于一個數(shù)值a b c d e f g h i j k l m0 1 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 25Caesar密碼可以表示如下

25、C = E(p) = (p + k) mod (26)p = D(C) = (C - k) mod (26)，這里k =38/28/202227Cryptography and Network Security - 2對Caesar密碼的攻擊 如果已知某給定密文是Caesar密碼，窮舉攻擊是很容易實現(xiàn)的，因為只要簡單地測試所有25種可能的密鑰Caesar密碼的三個重要特征使我們可以采用窮舉攻擊分析方法已知加密和解密算法所需測試的密鑰只有25個明文所用的語言是已知的，且其意義易于識別比如，破解密文PHHW PH DIWHU WKH WRJD SDUWB，或者，GCUA VQ DTGCM8/28/

26、202228Cryptography and Network Security - 28/28/202229Cryptography and Network Security - 2對Caesar密碼的攻擊如果明文所用語言不為我們所知，則明文輸出不可識別，而且輸入可能按某種方式經(jīng)過縮寫或壓縮，則識別就更加困難例如8/28/202230Cryptography and Network Security - 22.2.2 Monoalphabetic Cipher單表代換密碼單表代換密碼不只是25種可能的密鑰，而是允許任意代換，增加密鑰空間 每個明文字母可以隨機(jī)映射到任意一個密文字母，密文行是26

27、個字母的任意置換，那么有26!或大于4x1026種可能的密鑰，每條消息用一個字母表加密 這樣密鑰有26個字母長 Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext: ifwewishtoreplacelettersCiphertext: WIRFRWAJUHYFTSDVFSFUUFYA 8/28/202231Cryptography and Network Security - 2單表代換密碼的安全性分析只要密文字符是26個字母的一個排列即可。單表代換密碼中每條消息用一個字母表加密這樣有26

28、! = 4x1026種可能的密鑰，超過 400,000,000,000,000,000,000,000,0004x1026 = 400萬億億 這比DES的密鑰空間大10個數(shù)量級，看起來是安全的，應(yīng)該可以抵御窮舉攻擊，其實不然 這是因為語言的一些規(guī)律和特性8/28/202232Cryptography and Network Security - 2語言的冗余性和密碼攻擊人類的語言是有冗余性的 比如從“th lrd s m shphrd shll nt wnt”中我們可以大概猜出些什么字母使用的頻率是不一樣的 英文字母E是使用最頻繁的，然后是T, R, N, I, O, A, S等 有些字母使用

29、得很少，如Z, J, K, Q, X 這樣可以得到英文字母使用頻率分布表同時，統(tǒng)計雙字母組合和三字母組合的使用頻率也是非常有用的 8/28/202233Cryptography and Network Security - 2英文字母的相對使用頻率8/28/202234Cryptography and Network Security - 2英文字母使用頻率用于密碼分析關(guān)鍵的一點，單表代換不能改變相關(guān)字母出現(xiàn)的頻率 這是由阿拉伯科學(xué)家在公元九世紀(jì)就分析發(fā)現(xiàn)了所以，只要統(tǒng)計密文中字母出現(xiàn)的頻率，與已知的統(tǒng)計值做比較就可以分析出相應(yīng)明文字母了如果Caesar密碼中字母呈現(xiàn)出通常的峰值和低谷，那么單

30、表代換也會呈現(xiàn)相同的特性，比如：峰值在：A-E-H-I, N-O, R-S-T低谷在：J-K, Q, X-Z雙字母、三字母出現(xiàn)特性表也會有助于破譯密文8/28/202235Cryptography and Network Security - 2單表代換密碼攻擊舉例給定密文:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ統(tǒng)計相關(guān)字母出現(xiàn)的次數(shù) (see textbook)可以猜測P和Z是e和t，ZW是t

31、h，這樣ZWP就是the這樣反復(fù)試驗并不斷修正錯誤，最后可得： it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow8/28/202236Cryptography and Network Security - 22.2.3 Playfair密碼單表代換盡管有大量的密鑰，也不能提供足夠的安全性，因為密文中殘留了大量的明文結(jié)構(gòu)，一種解決辦法是引進(jìn)多表代換密碼。Playfa

32、ir密碼是最著名的多表代換密碼，它把明文中的雙字母音節(jié)作為一個單元轉(zhuǎn)換成密文的雙字母音節(jié)。Playfair密碼是由英國科學(xué)家Charles Wheatstone在1854年發(fā)明的，用了他的朋友Baron Playfair的名字命名。Playfair算法基于一個由密鑰詞構(gòu)成的5x5字母矩陣8/28/202237Cryptography and Network Security - 2Playfair密碼的密鑰矩陣假定使用的密鑰詞是MONARCHY先在5x5矩陣中填上密鑰詞，去掉重復(fù)字母 再將剩余的字母按字母表的順序從左至右、從上至下填在矩陣剩下的格子中，I和J當(dāng)作一個字母MONARCHYBDEF

33、GI/JKLPQSTUVWXZ8/28/202238Cryptography and Network Security - 2Playfair密碼的加密對明文按如下規(guī)則一次加密兩個字母 如果該字母對的兩個字母是相同的，則在其中插入一個填充字母，如 x, “balloon”加密成“ba lx lo on” 落在同一行的明文字母對中的字母由其右邊的字母來代換，每行中最右的字母用該行最左邊的第一個字母來代換, 如 “ar”加密成“RM” 落在同一列的明文字母對中的字母由其下面的字母來代換，每列中最下面的一個字母用該列最上面的第一個字母來代換, 如 “mu”加密成“CM” 其他的每組明文字母對中的字母

34、按如下方式代換：該字母所在行為密文所在行，另一字母所在列為密文所在列，如 “hs”變換成“BP”，“ea”代換為“IM”或“JM” (as desired) 8/28/202239Cryptography and Network Security - 2Playfair密碼的安全性Playfair密碼安全性比單表代換大為提高因為有26個字母，因此有26 x 26 = 676字母對，對單個字母對進(jìn)行判斷要困難得多。 單個字母的相對頻率比字母對的相對頻率在統(tǒng)計規(guī)律上要好，利用頻率分析字母對就更困難些，需要676輸入的頻率表來進(jìn)行分析。被廣泛地使用了許多年，包括在一戰(zhàn)和二戰(zhàn)時期。英國軍隊使用了一個世

35、紀(jì)，曾保證是安全的，但1915年被德軍破譯。1941年起，德軍和蓋世太保使用雙表playfair，1944年秋季被英國的Bletchey Park破譯。 因為它的密文仍然完好地保留了明文語言的大部分結(jié)構(gòu)特征，它仍然是相對容易攻破的，幾百個字母的密文就足夠分析出規(guī)律了。8/28/202240Cryptography and Network Security - 2字母出現(xiàn)的相對頻率“明文”曲線畫出7萬個字母的頻率分布，對文中出現(xiàn)的每個字母計數(shù)，結(jié)果除以字母e的出現(xiàn)次數(shù)。加密后的曲線體現(xiàn)了加密后字母頻率分布被掩蓋的程度，如果完全被掩蓋，則應(yīng)該是一條水平線。8/28/202241Cryptograp

36、hy and Network Security - 22.2.4 Hill密碼1929年數(shù)學(xué)家Lester Hill發(fā)明Hill密碼將m個連續(xù)的明文字母替換成m個密文字母，這由m個線性方程決定，每個字母指定一個數(shù)值 (a=0, b=1, , z=25)，假如m為3：c1=(k11p1+k12p2+k13p3) mod 26c2=(k21p1+k22p2+k23p3) mod 26c3=(k31p1+k32p2+k33p3) mod 26用列向量和矩陣表示為 或 C=KP mod 26 C和P是長度為3的列向量，分別代表密文和明文 K是一個3x3矩陣，代表加密密鑰，運算按模26執(zhí)行8/28/20

37、2242Cryptography and Network Security - 2Hill密碼明文paymoremoney，加密密鑰為明文前三個字母用向量15 0 24表示，則照此轉(zhuǎn)換剩下字母，可得密文LNSHDLEWMTRW解密需要用到矩陣K的逆K-1，由KK-1=I 定義，I是單位矩陣8/28/202243Cryptography and Network Security - 2Hill密碼KK-1 =I 可以驗證如下Hill密碼系統(tǒng)可以表示如下C=E(K, P)=KP mod 26P=D(K, C)=K-1C mod 26=K-1KP=P8/28/202244Cryptography a

38、nd Network Security - 22.2.5 Polyalphabetic Ciphers多表代換密碼改進(jìn)簡單的單表代換的方法是在明文消息中采用不同的單表代換，這就是多表代換密碼poly-alphabetic substitution ciphers 因為需要猜測更多的字母表，并且頻率分布特性也變得平坦了，所以使得密碼破譯更加困難使用一密鑰詞對每個明文字母選擇一個字母表來加密依次使用每個字母表 如果到了密鑰詞最后一個字母，則從頭開始繼續(xù)8/28/202245Cryptography and Network Security - 2Vigenre密碼最簡單的多表代換密碼是Vigenr

39、e密碼，它其實是多重Caesar密碼 26個密碼水平放置，最左邊是密鑰字母，頂部排列的是明文的標(biāo)準(zhǔn)字母表加密一條消息需要與消息一樣長的密鑰，密鑰是密鑰詞的重復(fù)，比如，密鑰詞為K = k1 k2 . kd 加密：給定密鑰字母x和明文字母y，密文字母是位于x行和y列的那個字母密鑰詞的第i 字母，表明使用第i個字母表，輪流使用字母表，如果到了消息的第d個字母時則從頭再做 解密：密鑰字母決定行，行里密文字母所在列的頂部字母就是明文字母 8/28/202246Cryptography and Network Security - 28/28/202247Cryptography and Network

40、Security - 2Example寫下明文 在明文之上重復(fù)寫下密鑰像使用Caesar cipher密鑰那樣使用每一個密鑰字母，加密每一個明文字母比如，使用密鑰deceptivekey: deceptivedeceptivedeceptiveplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ8/28/202248Cryptography and Network Security - 2Vigenre密碼的安全性每一個明文字母可以有多個密文字母對應(yīng)，這樣字母使用的頻率特性減弱了，但是沒有完全消

41、失攻擊者首先要分析密文是否是用單表代換加密的，即通過簡單的測試密文的統(tǒng)計特性如果認(rèn)為是用Vigenre密碼加密的，破譯能否取得進(jìn)展將取決于能否判定密鑰詞的長度，要通過發(fā)現(xiàn)重復(fù)序列來判斷如果密鑰詞長度是N，那么密碼實際上包含了N個單表代換密鑰詞的周期性可以用與明文信息一樣長的不重復(fù)密鑰詞來消除，如“密鑰自動生成系統(tǒng)”，但是密文和明文具有相同頻率分布特性，仍然是易受攻擊的最終措施是選擇與明文毫無統(tǒng)計關(guān)系且和它一樣長的密鑰8/28/202249Cryptography and Network Security - 2Kasiski Method to break Vigenre卡西斯基方法破解Vig

42、enre破解Vigenre的方法是由Charles Babbage(巴貝奇)和Friedrich Kasiski(卡西斯基)分別發(fā)現(xiàn)的密文中的重復(fù)性可以暗示出密鑰詞長度 如果兩個相同明文序列之間的距離是密鑰詞長度的整數(shù)倍，那么產(chǎn)生的密文序列也是相同的前例中“red”的兩次出現(xiàn)相隔9個字母，因此得到了兩個相同密文序列VTW這時攻擊者就可以猜測密鑰詞的長度是3或者9這樣攻擊者可以像先前攻擊單表密碼那樣分別進(jìn)行攻擊密鑰詞的周期性可以用與明文信息一樣長的不重復(fù)密鑰詞來消除，Autokey Cipher8/28/202250Cryptography and Network Security - 2Aut

43、okey Cipher最理想的是讓密鑰和要加密的消息一樣長Vigenre提出了autokey cipher，密鑰詞keyword放在消息前面作為密鑰key前綴知道了密鑰詞能夠破譯密文的前面一些字母，據(jù)此可以解密密文消息的其余部分 但是這種方法仍然具有字母使用的頻率特性可供分析例如，給定密鑰詞：deceptivekey: deceptivewearediscoveredsavplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA8/28/202251Cryptography and Network

44、Security - 22.2.6 One-Time Pad一次一密Joseph Mauborgne提出使用與消息一樣長且無重復(fù)的隨機(jī)密鑰來加密消息，密鑰只對一個消息加解密，之后棄之不用；每條新消息都需要與其等長的新密鑰，這就是一次一密，它是不可攻破的。一次一密運算基于二進(jìn)制數(shù)據(jù)而非字母加密：ci = pi ki, pi是明文第i個二進(jìn)制位， ki是密鑰第i個二進(jìn)制位，ci是密文第i個二進(jìn)制位， 是異或運算密文是通過對明文和密鑰的逐位異或而成的，根據(jù)異或運算的性質(zhì)，解密過程為pi = ci ki, 給出任何長度與密文一樣的明文，都存在著一個密鑰產(chǎn)生這個明文。如果用窮舉法搜索所有可能的密鑰，會得

45、到大量可讀、清楚的明文，但是無法確定哪個才是真正所需的，因而這種密碼不可破。一次一密的兩個限制產(chǎn)生大規(guī)模隨機(jī)密鑰有實際困難密鑰的分配和保護(hù)無法保證8/28/202252Cryptography and Network Security - 22.3 Transposition Ciphers置換密碼置換密碼改變明文內(nèi)容元素的相對位置，保持內(nèi)容的表現(xiàn)形式不變通常稱為transposition或者permutation密碼 通過重新安排消息字母的位置來隱藏明文信息，而不是用其他字母來代換明文字母這種方法是很容易破譯的，因為密文擁有與明文一樣的字母頻率統(tǒng)計特性 8/28/202253Cryptogr

46、aphy and Network Security - 2一維變換矩陣轉(zhuǎn)置二維變換圖形轉(zhuǎn)置DNATSREDNUUOYNAC明文：can you understand密文：codtaueanurnynsd輸入輸出UUOYNACSREDNNATD密文明文明文：can you understand密文：dnsuaruteodynnacTransposition or permutation置換密碼8/28/202254Cryptography and Network Security - 2柵欄技術(shù) Rail Fence cipher按照對角線的順序?qū)懗雒魑?，按行的順序讀出作為密文如加密 meet

47、me after the toga party:m e m a t r h t g p r y e t e f e t e o a a t可以得到密文MEMATRHTGPRYETEFETEOAAT8/28/202255Cryptography and Network Security - 2Row Transposition Ciphers行置換密碼一個更復(fù)雜的方案是把消息一行一行地寫成矩形塊，然后按列讀出，但是把列的次序打亂，列的次序就是算法的密鑰，例如：Key: 4 3 1 2 5 6 7Plaintext: a t t a c k p o s t p o n e d u n t i l

48、t w o a m x y zCiphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ可以采用多步置換來得到相對較高的安全性 8/28/202256Cryptography and Network Security - 2乘積密碼Product Ciphers單純的代換或者置換密碼是不安全的，因為語言的特性因此可以考慮連續(xù)使用若干這樣的密碼使其難以破解，但是：兩次代換只生成更復(fù)雜的代換兩次置換只生成更復(fù)雜的置換如果在一次代換之后跟一次置換，可以生成一種新的更難破解的密碼，這就是乘積密碼乘積密碼是從古典密碼通往現(xiàn)代密碼的橋梁8/28/202257Cryptography

49、and Network Security - 22.4 Rotor Machines轉(zhuǎn)輪密碼機(jī)在現(xiàn)代密碼系統(tǒng)出現(xiàn)之前，轉(zhuǎn)輪密碼機(jī)是最為廣泛使用的多重加密器，尤其是在第二次世界大戰(zhàn)中。German Enigma, Japanese Purple, Allied Hagelin轉(zhuǎn)輪密碼機(jī)實現(xiàn)了一個非常復(fù)雜、變化多端的代換密碼。轉(zhuǎn)輪機(jī)使用一組相互獨立的旋轉(zhuǎn)圓筒，可以通過電脈沖，每個圓筒有26個輸入和26個輸出，每個輸入僅與一個輸出相連，一個圓筒就定義了一個單表代換。每按下一個鍵，圓筒旋轉(zhuǎn)一個位置，內(nèi)部連線相應(yīng)改變，就定義了不同的單表代換密碼，經(jīng)過26個明文字母，圓筒回到初始狀態(tài)，就得到一個周期為26

50、的多表代換密碼。3個圓筒的轉(zhuǎn)輪機(jī)就有263=17576個不同的代換字母表8/28/202258Cryptography and Network Security - 2Enigma：密碼學(xué)界劃時代的豐碑 /index.php?doc-view-131925 (科技中國介紹德國發(fā)明家亞瑟謝爾比烏斯)Enigma(轉(zhuǎn)輪密碼機(jī))在密碼學(xué)界里，絕對是劃時代的豐碑。它所凝聚成的不是一座豐碑，而是兩座：研究并制造出Enigma是一座，研究并破解Enigma是另一座。只要稍微了解一下Enigma的歷史，我們就會被其中閃耀的人類智慧之美所折服；而如果要向這樣輝煌的智慧敬獻(xiàn)花環(huán)的話，主要應(yīng)該獻(xiàn)給三個人：首先是德

51、國人亞瑟謝爾比烏斯(Arthur Scherbius)；其次是波蘭人馬里安雷耶夫斯基(Marian Rejewski)；然后是英國人阿蘭圖靈(Alan Turing)。德國人發(fā)明了Enigma；波蘭人初步破解了簡單的Enigma；而英國人徹底終結(jié)了最高難度的Enigma。8/28/202259Cryptography and Network Security - 2亞瑟謝爾比烏斯和Enigma1918年，德國發(fā)明家亞瑟謝爾比烏斯(Arthur Scherbius)和理查德里特Ritter創(chuàng)辦了一家新技術(shù)應(yīng)用公司，利用現(xiàn)代化的電氣技術(shù)，來取代手工編碼加密方法，發(fā)明了一種能夠自動編碼的機(jī)器。謝爾比

52、烏斯給自己所發(fā)明的電氣編碼機(jī)械取名“恩尼格瑪”(Enigma，意為啞謎)。恩尼格瑪密碼機(jī)是一種用于加密與解密文件的密碼機(jī)。確切地說，恩尼格瑪是一系列相似的轉(zhuǎn)子機(jī)械的統(tǒng)稱，包括了一系列不同的型號。恩尼格瑪密碼機(jī)可以簡單分為三個部分：鍵盤、轉(zhuǎn)子和顯示器。8/28/202260Cryptography and Network Security - 2亞瑟謝爾比烏斯和Enigma轉(zhuǎn)輪機(jī)是Vigenere 密碼的一種實現(xiàn)。每個轉(zhuǎn)輪是字母的任意組合，有26個位置，并且完成一種簡單代替。例如：一個轉(zhuǎn)輪可能被用線連起來以完成用“F”代替“A”，用“U”代替“B”，用“L”代替“C”等等，而轉(zhuǎn)輪的輸出端連接到相

53、鄰的下一轉(zhuǎn)輪的輸入端。例如，在4個轉(zhuǎn)輪的密碼機(jī)中，第一個轉(zhuǎn)輪可能用“F”代替“A”， 第二個轉(zhuǎn)輪可能用“Y”代替“F”， 第三個轉(zhuǎn)輪可能用“E”代替“Y”， 第四個轉(zhuǎn)輪可能用“C”代替“E”，“C”應(yīng)該是輸出密文。那么當(dāng)轉(zhuǎn)輪移動后，下一次代替將不同了。為使機(jī)器更安全，可以把幾個轉(zhuǎn)輪和移動的齒輪結(jié)合起來。因為所有轉(zhuǎn)輪以不同的速度移動，n個轉(zhuǎn)輪的機(jī)器的周期是26n。為進(jìn)一步阻止密碼分析，有些轉(zhuǎn)輪機(jī)在每個轉(zhuǎn)輪上還有不同的位置號。恩尼格瑪一般有三個轉(zhuǎn)輪，從五個轉(zhuǎn)輪中選擇。轉(zhuǎn)輪機(jī)中有一塊稍微改變明文序列的插板，有一個反射輪導(dǎo)致每個轉(zhuǎn)輪對每一個明文字母操作兩次。8/28/202261Cryptograph

54、y and Network Security - 2Enigma三個轉(zhuǎn)輪的連接示意8/28/202262Cryptography and Network Security - 2Enigma的使用使用恩尼格瑪通訊時，發(fā)信人首先調(diào)節(jié)三個轉(zhuǎn)子的初始方向，這個轉(zhuǎn)子的初始方向就是密鑰，是收發(fā)雙方預(yù)先約定好的。然后依次鍵入明文，并把顯示器上燈泡閃亮的字母依次記下來，最后把記錄下的字母按照順序用正常的電報方式發(fā)送出去。收信方收到電文后，只要也使用一臺恩尼格瑪，按照原來的約定，把轉(zhuǎn)子的方向調(diào)整到和發(fā)信方相同的初始方向上，然后依次鍵入收到的密文，顯示器上自動閃亮的字母就是明文了。使用恩尼格瑪解密和加密的過程完

55、全一樣，這就是反射器的作用，同時反射器的一個副作用就是一個字母永遠(yuǎn)也不會被加密成它自己，因為反射器中一個字母總是被連接到另一個不同的字母。8/28/202263Cryptography and Network Security - 2Enigma的破解波蘭數(shù)學(xué)家和密碼學(xué)家雷耶夫斯基波蘭數(shù)學(xué)家和密碼學(xué)家馬里安雷耶夫斯基(Marian Adam Rejewski, 1905年8月26日1980年2月13日)，20世紀(jì)30年代領(lǐng)導(dǎo)波蘭密碼學(xué)家率先對德國使用的Enigma密碼進(jìn)行了系統(tǒng)性的研究和破譯。雷耶夫斯基首次將嚴(yán)格的數(shù)學(xué)化方法應(yīng)用到密碼破譯領(lǐng)域，這在密碼學(xué)的歷史上是一個重要成就。雷耶夫斯基等人在

56、二戰(zhàn)期間破譯了大量來自德國的信息，成為整個二戰(zhàn)期間盟國破譯德軍Enigma密碼的基礎(chǔ)。雷耶夫斯基與波蘭數(shù)學(xué)家杰爾茲羅佐基和亨里克佐加爾斯基并稱為密碼研究領(lǐng)域的“波蘭三杰”。2000年7月17日，波蘭政府向雷耶夫斯基、羅佐基和佐加爾斯基追授波蘭最高勛章。2001年4月21日，雷耶夫斯基、羅佐基和佐加爾斯基紀(jì)念基金在波蘭華沙設(shè)立，基金會在華沙和倫敦設(shè)置了紀(jì)念波蘭數(shù)學(xué)家的銘牌。 8/28/202264Cryptography and Network Security - 2Enigma的破解英國倫敦附近的柏雷屈里莊園密碼學(xué)校8/28/202265Cryptography and Network Se

57、curity - 2Enigma的破解計算機(jī)科學(xué)之父阿蘭圖靈 阿蘭麥席森圖靈 Alan Mathison Turing(1912年6月23日-1954年6月7日)是英國著名的數(shù)學(xué)家和邏輯學(xué)家，被稱為計算機(jī)科學(xué)之父、人工智能之父，是計算機(jī)邏輯的奠基者，提出了“圖靈機(jī)”和“圖靈測試”等重要概念。1936年英國政府在白金漢郡的柏雷屈里莊園設(shè)立代碼及加密學(xué)校(GC&CS ,Government Code and Cipher School)，集結(jié)了一大批為破譯ENIGMA作出卓越貢獻(xiàn)的人們，圖靈發(fā)明了綽號為“炸彈” (Bombes)的解密機(jī)器，被看成一位天才解密分析專家，而于1945年獲政府的最高獎大

58、英帝國榮譽勛章(O.B.E.勛章)。人們認(rèn)為，通用計算機(jī)的概念就是阿蘭麥席森圖靈提出來的 戰(zhàn)爭結(jié)束，柏雷屈里莊園被關(guān)閉，“炸彈”被拆毀，所有戰(zhàn)時有關(guān)密碼分析和破譯的檔案資料都被銷毀，直到1967年波蘭出版第一本關(guān)于波蘭破譯ENIGMA方面的書，以及1974年溫特伯坦姆寫的超級機(jī)密The Ultra Secret一書出版，人們才知道圖靈在解密分析方面的杰出貢獻(xiàn)。8/28/202266Cryptography and Network Security - 2計算機(jī)科學(xué)之父阿蘭圖靈在圖靈的設(shè)計思想指導(dǎo)下，1950年制出了ACE“自動計算機(jī)”樣機(jī)，1958年制成大型ACE機(jī)。早在1947年，圖靈就提出

59、過自動程序設(shè)計的思想，1950年，他提出關(guān)于機(jī)器思維的問題，他的論文“計算機(jī)和智能(Computing machinery and intelligence)引起了廣泛的注意和深遠(yuǎn)的影響。 1954年，圖靈因食用浸過氰化物溶液的蘋果死亡。為了紀(jì)念他對計算機(jī)科學(xué)的巨大貢獻(xiàn)，美國計算機(jī)協(xié)會ACM從1966年起設(shè)立一年一度的“圖靈獎”，以表彰在計算機(jī)科學(xué)中做出突出貢獻(xiàn)的人。 2009年9月10日，在三萬民眾的聯(lián)名請愿下，英國當(dāng)時的首相戈登.布朗正式代表英國政府向圖靈因為同性戀被定罪并導(dǎo)致其自殺公開道歉。但英國政府在2012年拒絕了為其追贈死后赦免狀的請愿。 The Code Book作者賽門辛的鏈接

60、：破解納粹的秘密 Decoding Nazi Secrets： http:/1/syang/8/28/202267Cryptography and Network Security - 2Enigma的破解恩尼格瑪加密的關(guān)鍵就在于轉(zhuǎn)子的初始方向。當(dāng)然如果敵人收到了完整的密文，還是可以通過不斷試驗轉(zhuǎn)動轉(zhuǎn)子方向來找到這個密鈅，特別是如果破譯者同時使用許多臺機(jī)器進(jìn)行這項工作，那么所需要的時間就會大大縮短。對付這樣暴力破譯法(即一個一個嘗試所有可能性的方法)，可以通過增加轉(zhuǎn)子的數(shù)量來對付，因為只要每增加一個轉(zhuǎn)子，就能使試驗的數(shù)量乘上26倍！由于增加轉(zhuǎn)子就會增加機(jī)器的體積和成本，恩尼格瑪密碼機(jī)的三個轉(zhuǎn)子