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

1、現(xiàn)代密碼學(xué)理論與實(shí)踐第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) 美國(guó)陸軍密碼專(zhuān)家。1930年代，他領(lǐng)導(dǎo)了陸軍的一個(gè)研究部門(mén)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é)研究置于堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)上。 該理論的重大貢獻(xiàn)在于：建立了通信保密/密碼學(xué)嚴(yán)格的理論基礎(chǔ)； 證明了一次一密(one-time pad)的密碼系統(tǒng)是完善保密的，導(dǎo)致了對(duì)流密碼的研究和應(yīng)用； 提出分組密碼設(shè)計(jì)應(yīng)該遵循的準(zhǔn)則，如擴(kuò)散性和混淆性； 證明了消息冗余使得破譯者統(tǒng)計(jì)分析成功的理論值(唯一解距離) 8/28/20225Cryptography an

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

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

8、975, Whitfield Diffie 和 Matin Hellman, 發(fā)表A New Direction in Cryptography, 首次提出適應(yīng)網(wǎng)絡(luò)保密通信的公開(kāi)密鑰思想，揭開(kāi)現(xiàn)代密碼學(xué)研究的序幕，具有劃時(shí)代的意義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第一次提出公開(kāi)密鑰密碼系統(tǒng)的實(shí)現(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é))，源自希臘語(yǔ)(Greek)Krypts: hidden; logos: word, 是密碼學(xué)和密碼

10、處理過(guò)程的研究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)換成密文的過(guò)程Decipher (decipherment), decryption: 將密文還原成明文的過(guò)程Plaintext (cleartext): 原始的可讀數(shù)據(jù)，明文Ciphe

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

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

13、tionally Secure) 如果攻擊者擁有無(wú)限資源，任何密碼系統(tǒng)都是可以被破譯的；但是在有限的資源范圍內(nèi)，攻擊者都不能通過(guò)系統(tǒng)的分析方法來(lái)破解系統(tǒng)，則稱(chēng)這個(gè)系統(tǒng)是計(jì)算上安全的或破譯這個(gè)系統(tǒng)是計(jì)算上不可行(Computationally Infeasible)。 理論安全和實(shí)際安全8/28/202211Cryptography and Network Security - 2加密的基本概念密碼體制加密系統(tǒng)采用的基本工作方式稱(chēng)為密碼體制，密碼體制的基本要素是密碼算法和密鑰。密碼算法是一些公式、法則或程序；密鑰是密碼算法中的控制參數(shù)。加密系統(tǒng)可以用數(shù)學(xué)符號(hào)來(lái)描述：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對(duì)稱(chēng)密碼體制(Symmetric System, One-key System, Secret-key System) 加密密鑰和解密密鑰相同，或者一個(gè)密鑰可以從另一個(gè)導(dǎo)出，能加密就能解密，加密能力和解密能力是結(jié)合在一起的，開(kāi)放性差。非對(duì)稱(chēng)密碼體制(Asymmetric System, Two-key System, Public-key Syst

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

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

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

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

19、的秘密密鑰Y = EK(X)X = DK(Y)必須假定加密算法是公開(kāi)的因此必須有安全的途徑或信道分發(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ù)以下三個(gè)獨(dú)立方面進(jìn)行分類(lèi)用于將明文轉(zhuǎn)換為密文的操作類(lèi)型：代換和置換所使用的密鑰的數(shù)量和方式：對(duì)稱(chēng)密碼體制(單鑰系統(tǒng)、秘密密鑰系統(tǒng))非對(duì)稱(chēng)密碼體制(雙鑰系統(tǒng)、公開(kāi)密鑰系統(tǒng))明文的處理方式：分組加密和

20、流加密密碼分析學(xué)(Cryptanalysis)密碼分析：試圖破譯密文得到明文或試圖獲得密鑰的過(guò)程為密碼分析，密碼破譯的策略取決于加密方法及可供破譯者使用的信息。窮舉攻擊：對(duì)密文嘗試所有可能的密鑰，直到把它轉(zhuǎn)化為可讀的有意義的明文，至少要嘗試1/2種所有可能的密鑰。Cryptology 密碼學(xué)8/28/202221Cryptography and Network Security - 2對(duì)加密信息的攻擊類(lèi)型唯密文攻擊 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窮舉攻擊總是可以簡(jiǎn)單地嘗試每一個(gè)可能的密鑰 窮舉攻擊

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

23、HHW PH DIWHU WKH WRJD SDUWB8/28/202225Cryptography and Network Security - 22.2.1 Caesar CipherCaesar實(shí)際上是一種單表代換密碼明文字母用密文字母表中對(duì)應(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讓每個(gè)字母等價(jià)于一個(gè)數(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對(duì)Caesar密碼的攻擊 如果已知某給定密文是Caesar密碼，窮舉攻擊是很容易實(shí)現(xiàn)的，因?yàn)橹灰?jiǎn)單地測(cè)試所有25種可能的密鑰Caesar密碼的三個(gè)重要特征使我們可以采用窮舉攻擊分析方法已知加密和解密算法所需測(cè)試的密鑰只有25個(gè)明文所用的語(yǔ)言是已知的，且其意義易于識(shí)別比如，破解密文PHHW PH DIWHU WKH WRJD SDUWB，或者，GCUA VQ DTGCM8/28/

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

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

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

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

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

31、h，這樣ZWP就是the這樣反復(fù)試驗(yàn)并不斷修正錯(cuò)誤，最后可得： 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密碼單表代換盡管有大量的密鑰，也不能提供足夠的安全性，因?yàn)槊芪闹袣埩袅舜罅康拿魑慕Y(jié)構(gòu)，一種解決辦法是引進(jìn)多表代換密碼。Playfa

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

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

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

35、紀(jì)，曾保證是安全的，但1915年被德軍破譯。1941年起，德軍和蓋世太保使用雙表playfair，1944年秋季被英國(guó)的Bletchey Park破譯。 因?yàn)樗拿芪娜匀煌旰玫乇Ａ袅嗣魑恼Z(yǔ)言的大部分結(jié)構(gòu)特征，它仍然是相對(duì)容易攻破的，幾百個(gè)字母的密文就足夠分析出規(guī)律了。8/28/202240Cryptography and Network Security - 2字母出現(xiàn)的相對(duì)頻率“明文”曲線畫(huà)出7萬(wàn)個(gè)字母的頻率分布，對(duì)文中出現(xiàn)的每個(gè)字母計(jì)數(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個(gè)連續(xù)的明文字母替換成m個(gè)密文字母，這由m個(gè)線性方程決定，每個(gè)字母指定一個(gè)數(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是長(zhǎng)度為3的列向量，分別代表密文和明文 K是一個(gè)3x3矩陣，代表加密密鑰，運(yùn)算按模26執(zhí)行8/28/20

37、2242Cryptography and Network Security - 2Hill密碼明文paymoremoney，加密密鑰為明文前三個(gè)字母用向量15 0 24表示，則照此轉(zhuǎn)換剩下字母，可得密文LNSHDLEWMTRW解密需要用到矩陣K的逆K-1，由KK-1=I 定義，I是單位矩陣8/28/202243Cryptography and Network Security - 2Hill密碼KK-1 =I 可以驗(yàn)證如下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)簡(jiǎn)單的單表代換的方法是在明文消息中采用不同的單表代換，這就是多表代換密碼poly-alphabetic substitution ciphers 因?yàn)樾枰聹y(cè)更多的字母表，并且頻率分布特性也變得平坦了，所以使得密碼破譯更加困難使用一密鑰詞對(duì)每個(gè)明文字母選擇一個(gè)字母表來(lái)加密依次使用每個(gè)字母表 如果到了密鑰詞最后一個(gè)字母，則從頭開(kāi)始繼續(xù)8/28/202245Cryptography and Network Security - 2Vigenre密碼最簡(jiǎn)單的多表代換密碼是Vigenr

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

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

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

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

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

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

45、到大量可讀、清楚的明文，但是無(wú)法確定哪個(gè)才是真正所需的，因而這種密碼不可破。一次一密的兩個(gè)限制產(chǎn)生大規(guī)模隨機(jī)密鑰有實(shí)際困難密鑰的分配和保護(hù)無(wú)法保證8/28/202252Cryptography and Network Security - 22.3 Transposition Ciphers置換密碼置換密碼改變明文內(nèi)容元素的相對(duì)位置，保持內(nèi)容的表現(xiàn)形式不變通常稱(chēng)為transposition或者permutation密碼 通過(guò)重新安排消息字母的位置來(lái)隱藏明文信息，而不是用其他字母來(lái)代換明文字母這種方法是很容易破譯的，因?yàn)槊芪膿碛信c明文一樣的字母頻率統(tǒng)計(jì)特性 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按照對(duì)角線的順序?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行置換密碼一個(gè)更復(fù)雜的方案是把消息一行一行地寫(xiě)成矩形塊，然后按列讀出，但是把列的次序打亂，列的次序就是算法的密鑰，例如：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可以采用多步置換來(lái)得到相對(duì)較高的安全性 8/28/202256Cryptography and Network Security - 2乘積密碼Product Ciphers單純的代換或者置換密碼是不安全的，因?yàn)檎Z(yǔ)言的特性因此可以考慮連續(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ī)實(shí)現(xiàn)了一個(gè)非常復(fù)雜、變化多端的代換密碼。轉(zhuǎn)輪機(jī)使用一組相互獨(dú)立的旋轉(zhuǎn)圓筒，可以通過(guò)電脈沖，每個(gè)圓筒有26個(gè)輸入和26個(gè)輸出，每個(gè)輸入僅與一個(gè)輸出相連，一個(gè)圓筒就定義了一個(gè)單表代換。每按下一個(gè)鍵，圓筒旋轉(zhuǎn)一個(gè)位置，內(nèi)部連線相應(yīng)改變，就定義了不同的單表代換密碼，經(jīng)過(guò)26個(gè)明文字母，圓筒回到初始狀態(tài)，就得到一個(gè)周期為26

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

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

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

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

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

55、全一樣，這就是反射器的作用，同時(shí)反射器的一個(gè)副作用就是一個(gè)字母永遠(yuǎn)也不會(huì)被加密成它自己，因?yàn)榉瓷淦髦幸粋€(gè)字母總是被連接到另一個(gè)不同的字母。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é)家率先對(duì)德國(guó)使用的Enigma密碼進(jìn)行了系統(tǒng)性的研究和破譯。雷耶夫斯基首次將嚴(yán)格的數(shù)學(xué)化方法應(yīng)用到密碼破譯領(lǐng)域，這在密碼學(xué)的歷史上是一個(gè)重要成就。雷耶夫斯基等人在

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

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

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

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

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