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

2019-6-6謝謝觀賞現(xiàn)代密碼學(xué)理論與實(shí)踐

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

第2章傳統(tǒng)加2019-6-6謝謝觀賞2/81PartOne–SymmetricCiphersRoadMapforPartOneChp.2,ClassicalEncryptionTechniquesChp.3,BlockCipherandtheDataEncryptionStandardChp.4,FiniteFieldsChp.5,AdvancedEncryptionStandardChp.6,MoreonSymmetricCiphersChp.7,ConfidentialityUsingSymmetricEncryption2019-6-6謝謝觀賞2/81PartOne–Symme2019-6-6謝謝觀賞3/81Chapter2–

ClassicalEncryptionTechniquesManysavagesatthepresentdayregardtheirnamesasvitalpartsofthemselves,andthereforetakegreatpainstoconcealtheirrealnames,lesttheseshouldgivetoevil-disposedpersonsahandlebywhichtoinjuretheirowners.

—TheGoldenBough,SirJamesGeorgeFrazer2019-6-6謝謝觀賞3/81Chapter2–

C2019-6-6謝謝觀賞4/81密碼學(xué)的演變歷史(1)

WilliamFriedman1918,WilliamFriedman’sTheIndexofCoincidenceanditsApplicationsinCryptographyWilliamFrederickFriedman(Sept.24,1891–Nov.12,1969)美國(guó)陸軍密碼專(zhuān)家。1930年代，他領(lǐng)導(dǎo)了陸軍的一個(gè)研究部門(mén)SignalsIntelligenceService(SIS)，其中一部分服務(wù)一直延續(xù)到五十年代。三十年代晚期，在他的指導(dǎo)下，F(xiàn)rankRowlett破解了日本人的PURPLE加密機(jī)(紫密)，截獲了日本的大量外交和軍事的秘密。2019-6-6謝謝觀賞4/81密碼學(xué)的演變歷史(1)

W2019-6-6謝謝觀賞5/81密碼學(xué)的演變歷史(2)香農(nóng)的貢獻(xiàn)1948年,ClaudeShannon’s發(fā)表“TheCommunicationTheoryofSecrecySystem”，成為現(xiàn)代密碼學(xué)理論基礎(chǔ)。1949年，Shannon在其著名的“信息論”發(fā)表一年之后，又發(fā)表了論文“保密系統(tǒng)的通信理論”，首次將密碼學(xué)研究置于堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)上。該理論的重大貢獻(xiàn)在于：建立了通信保密/密碼學(xué)嚴(yán)格的理論基礎(chǔ)；證明了一次一密(one-timepad)的密碼系統(tǒng)是完善保密的，導(dǎo)致了對(duì)流密碼的研究和應(yīng)用；提出分組密碼設(shè)計(jì)應(yīng)該遵循的準(zhǔn)則，如擴(kuò)散性和混淆性；證明了消息冗余使得破譯者統(tǒng)計(jì)分析成功的理論值(唯一解距離)2019-6-6謝謝觀賞5/81密碼學(xué)的演變歷史(2)香農(nóng)2019-6-6謝謝觀賞6/81密碼學(xué)的演變歷史(2)ClaudeElwoodShannon(Apr.30,1916–Feb.24,2001),美國(guó)電氣工程師和數(shù)學(xué)家，被譽(yù)為信息論之父"thefatherofinformationtheory".香農(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)為是迄今最重要的碩士論文。1949-1967，密碼學(xué)研究處于沉寂時(shí)期2019-6-6謝謝觀賞6/81密碼學(xué)的演變歷史(2)Cla2019-6-6謝謝觀賞7/81密碼學(xué)的演變歷史(3)

Feistel,WhitfieldDiffie,MatinHellman1971,IBM發(fā)明LucifferCipher,128位密鑰作分組加密。這項(xiàng)發(fā)明是由HorstFeistel(Jan.30,1915–Nov.14,1990)領(lǐng)導(dǎo)的，他是密碼學(xué)家，當(dāng)時(shí)在IBM負(fù)責(zé)設(shè)計(jì)加密器，他的工作最終激發(fā)了70年代DataEncryptionStandard(DES)的研發(fā)高潮1976-1977，美國(guó)國(guó)家標(biāo)準(zhǔn)局正式公布實(shí)施DES1975,WhitfieldDiffie和MatinHellman,發(fā)表ANewDirectioninCryptography,首次提出適應(yīng)網(wǎng)絡(luò)保密通信的公開(kāi)密鑰思想，揭開(kāi)現(xiàn)代密碼學(xué)研究的序幕，具有劃時(shí)代的意義2019-6-6謝謝觀賞7/81密碼學(xué)的演變歷史(3)

Fe2019-6-6謝謝觀賞8/81密碼學(xué)的演變歷史(4)

R.S.A.,AbbasElGamal,LaiXuejia

1977-1978，RonaldRivest,AdiShamir,LenAdleman第一次提出公開(kāi)密鑰密碼系統(tǒng)的實(shí)現(xiàn)方法RSA1981，成立InternationalAssociationforCryptologyResearch1985，AbbasElGamal提出概率密碼系統(tǒng)ElGamal方法1990-1992，LaiXuejiaandJames:IDEA,TheInternationalDataEncryptionAlgorithm2000,AES,AdvancedEncryptionStandard2019-6-6謝謝觀賞8/81密碼學(xué)的演變歷史(4)

R.2019-6-6謝謝觀賞9/81Cryptology(保密學(xué))，源自希臘語(yǔ)(Greek) Kryptós:hidden;logos:word,是密碼學(xué)和密碼處理過(guò)程的研究Cryptography:TheScienceandStudyofSecretWriting，密碼編碼學(xué)Cryptanalysis:TheScienceandStudyofSecretBreaking，密碼破譯學(xué)Cipher:Asecretmethodofwriting加密方法Encipher(encipherment),encryption:將明文轉(zhuǎn)換成密文的過(guò)程Decipher(decipherment),decryption:將密文還原成明文的過(guò)程Plaintext(cleartext):原始的可讀數(shù)據(jù)，明文Ciphertext(Cryptogram):加密后的不可解讀之文件，密文Key:密鑰，對(duì)加密與解密過(guò)程進(jìn)行控制的參數(shù)E(m):EncryptionTransformation加密變換D(c):DecryptionTransformation解密變換密碼學(xué)基本術(shù)語(yǔ)Terminologies2019-6-6謝謝觀賞9/81Cryptology(保密學(xué)2019-6-6謝謝觀賞10/81什么是密碼？簡(jiǎn)單地說(shuō)它就是一組含有參數(shù)K的變換E。設(shè)已知消息m，通過(guò)變換Ek得密文C，這個(gè)過(guò)程稱(chēng)為加密，E為加密算法，k不同，密文C亦不同。傳統(tǒng)的保密通信機(jī)制：EncipherPlaintextCiphertextKeysDecipherC=Ek(m)發(fā)方：m收方：mkk（公共信道）加密E解密D（秘密信道）簡(jiǎn)單加密系統(tǒng)模型2019-6-6謝謝觀賞10/81EncipherPlain2019-6-6謝謝觀賞11/81理論安全，或無(wú)條件安全TheoreticalSecure(orPerfectSecure)

攻擊者無(wú)論截獲多少密文，都無(wú)法得到足夠的信息來(lái)唯一地決定明文。Shannon用理論證明：欲達(dá)理論安全，加密密鑰長(zhǎng)度必須大于等于明文長(zhǎng)度，密鑰只用一次，用完即丟，即一次一密，One-timePad，不實(shí)用。實(shí)際安全，或計(jì)算上安全PracticalSecure(orComputationallySecure)

如果攻擊者擁有無(wú)限資源，任何密碼系統(tǒng)都是可以被破譯的；但是在有限的資源范圍內(nèi)，攻擊者都不能通過(guò)系統(tǒng)的分析方法來(lái)破解系統(tǒng)，則稱(chēng)這個(gè)系統(tǒng)是計(jì)算上安全的或破譯這個(gè)系統(tǒng)是計(jì)算上不可行(ComputationallyInfeasible)。理論安全和實(shí)際安全2019-6-6謝謝觀賞11/81理論安全，或無(wú)條件安全Th2019-6-6謝謝觀賞12/81加密的基本概念密碼體制加密系統(tǒng)采用的基本工作方式稱(chēng)為密碼體制，密碼體制的基本要素是密碼算法和密鑰。密碼算法是一些公式、法則或程序；密鑰是密碼算法中的控制參數(shù)。加密系統(tǒng)可以用數(shù)學(xué)符號(hào)來(lái)描述：

S＝{P,C,K,E,D} P：明文空間 C：密文空間 K：密鑰空間

E：加密變換 D：解密變換k∈K，則有C＝Ek(P)，P＝Dk(C)＝Dk(Ek(P))，或者Dk＝Ek-1，且Ek＝Dk-1。2019-6-6謝謝觀賞12/81加密的基本概念密碼體制2019-6-6謝謝觀賞13/81對(duì)稱(chēng)密碼體制(SymmetricSystem,One-keySystem,Secret-keySystem)

加密密鑰和解密密鑰相同，或者一個(gè)密鑰可以從另一個(gè)導(dǎo)出，能加密就能解密，加密能力和解密能力是結(jié)合在一起的，開(kāi)放性差。非對(duì)稱(chēng)密碼體制(AsymmetricSystem,Two-keySystem,Public-keySystem)

加密密鑰和解密密鑰不相同，從一個(gè)密鑰導(dǎo)出另一個(gè)密鑰是計(jì)算上不可行的，加密能力和解密能力是分開(kāi)的，開(kāi)放性好。對(duì)稱(chēng)密碼體制和非對(duì)稱(chēng)密碼體制2019-6-6謝謝觀賞13/81對(duì)稱(chēng)密碼體制(Symmet2019-6-6謝謝觀賞14/81序列密碼如果密文不僅與最初給定的算法和密鑰有關(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)度的密文。序列密碼體制和分組密碼體制2019-6-6謝謝觀賞14/81序列密碼序列密碼體制和分組2019-6-6謝謝觀賞15/81確定型密碼體制和概率密碼體制確定型：當(dāng)明文和密鑰確定后，密文也就唯一地確定了；概率型：當(dāng)明文和密鑰確定后，密文通過(guò)客觀隨機(jī)因素從一個(gè)密文集合中產(chǎn)生，密文形式不確定，稱(chēng)為概率型密碼體制。單向函數(shù)型密碼體制和雙向變換型密碼體制單向函數(shù)型密碼體制適用于不需要解密的場(chǎng)合，容易將明文加密成密文，如哈希函數(shù)；雙向變換型密碼體制可以進(jìn)行可逆的加密、解密變換。其他加密體制2019-6-6謝謝觀賞15/81確定型密碼體制和概率密碼體2019-6-6謝謝觀賞16/81現(xiàn)代密碼學(xué)的基本原則設(shè)計(jì)加密系統(tǒng)時(shí)，總是假定密碼算法是可以公開(kāi)的，需要保密的是密鑰。一個(gè)密碼系統(tǒng)的安全性不在算法的保密，而在于密鑰，即Kerckhoff原則。對(duì)加密系統(tǒng)的要求系統(tǒng)應(yīng)該是實(shí)際上安全的(practicalsecure)，截獲密文或已知明文－密文對(duì)時(shí)，要決定密鑰或任意明文在計(jì)算上是不可行的。加密解密算法適用于密鑰空間中的所有元素。系統(tǒng)易于實(shí)現(xiàn)，使用方便。系統(tǒng)的安全性不依賴于對(duì)加密體制或加密算法的保密，而依賴于密鑰。系統(tǒng)的應(yīng)用不應(yīng)使通信網(wǎng)絡(luò)的效率過(guò)分降低?，F(xiàn)代密碼學(xué)基本原則及加密系統(tǒng)要求2019-6-6謝謝觀賞16/81現(xiàn)代密碼學(xué)的基本原則現(xiàn)代密2019-6-6謝謝觀賞17/81對(duì)稱(chēng)加密系統(tǒng)由以下五部分組成Plaintext：明文Encryptionalgorithm：加密算法Key： 密鑰Ciphertext：密文Decryptionalgorithm：解密算法加密算法必須足夠強(qiáng)大，使破譯者不能僅根據(jù)密文破譯消息收發(fā)雙方必須在某種安全的形式下獲得密鑰并必須保證密鑰的安全2.1

對(duì)稱(chēng)密碼系統(tǒng)的模型2019-6-6謝謝觀賞17/81對(duì)稱(chēng)加密系統(tǒng)由以下五部分組2019-6-6謝謝觀賞18/81傳統(tǒng)密碼的簡(jiǎn)化模型2019-6-6謝謝觀賞18/81傳統(tǒng)密碼的簡(jiǎn)化模型2019-6-6謝謝觀賞19/81對(duì)稱(chēng)密碼系統(tǒng)的要求使用對(duì)稱(chēng)密碼系統(tǒng)有兩個(gè)基本要求一個(gè)強(qiáng)加密算法一個(gè)只有發(fā)送方和接收方知道的秘密密鑰 Y=EK(X) X=DK(Y)必須假定加密算法是公開(kāi)的因此必須有安全的途徑或信道分發(fā)密鑰2019-6-6謝謝觀賞19/81對(duì)稱(chēng)密碼系統(tǒng)的要求使用對(duì)稱(chēng)2019-6-6謝謝觀賞20/81傳統(tǒng)密碼體制的模型Y=Ek(X)X=Dk(Y)2019-6-6謝謝觀賞20/81傳統(tǒng)密碼體制的模型Y=2019-6-6謝謝觀賞21/81密碼編碼學(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))明文的處理方式：分組加密和流加密密碼分析學(xué)(Cryptanalysis)密碼分析：試圖破譯密文得到明文或試圖獲得密鑰的過(guò)程為密碼分析，密碼破譯的策略取決于加密方法及可供破譯者使用的信息。窮舉攻擊：對(duì)密文嘗試所有可能的密鑰，直到把它轉(zhuǎn)化為可讀的有意義的明文，至少要嘗試1/2種所有可能的密鑰。Cryptology密碼學(xué)2019-6-6謝謝觀賞21/81密碼編碼學(xué)(Cryptog2019-6-6謝謝觀賞22/81對(duì)加密信息的攻擊類(lèi)型唯密文攻擊onlyknowalgorithmandciphertext,isstatistical,knoworcanidentifyplaintext已知明文攻擊know/suspectplaintextandciphertext選擇明文攻擊selectplaintextandobtainciphertext選擇密文攻擊selectciphertextandobtainplaintext選擇文本攻擊selectplaintextorciphertexttoen/decrypt2019-6-6謝謝觀賞22/81對(duì)加密信息的攻擊類(lèi)型唯密文2019-6-6謝謝觀賞23/812019-6-6謝謝觀賞23/812019-6-6謝謝觀賞24/81窮舉攻擊總是可以簡(jiǎn)單地嘗試每一個(gè)可能的密鑰窮舉攻擊是最基本的攻擊，難度與密鑰長(zhǎng)度成正比平均來(lái)說(shuō)要獲得成功必須嘗試所有可能密鑰的一半2019-6-6謝謝觀賞24/81窮舉攻擊總是可以簡(jiǎn)單地嘗試2019-6-6謝謝觀賞25/812.2

代換密碼(Substitution)代換法是將明文字母替換成其他字母、數(shù)字或符號(hào)的加密方法如果把明文看成是二進(jìn)制序列的話，代換就是用密文位串來(lái)代換明文位串代換法改變明文內(nèi)容的表示形式，保持內(nèi)容元素之間相對(duì)位置不變已知最早的代換密碼是由JuliusCaesar發(fā)明的愷撒密碼CaesarCipher，對(duì)字母表中的每個(gè)字母用它之后的第3個(gè)字母來(lái)代換。例如：meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWB2019-6-6謝謝觀賞25/812.2代換密碼(Subs2019-6-6謝謝觀賞26/812.2.1CaesarCipherCaesar實(shí)際上是一種單表代換密碼明文字母用密文字母表中對(duì)應(yīng)字母代替，例：明文字母表P＝{p0,p1,…,pn-1}密文字母表C＝{c0,c1,…,cn-1}密鑰為正整數(shù)k，加密：i+k≡j(modn)

解密：j-k≡i(modn)CaesarCipher，加密：C=E(p)=(p+k)mod26

解密：p=D(C)=(C-k)mod26,0－A；1－B；…；25－Z2019-6-6謝謝觀賞26/812.2.1Caesar2019-6-6謝謝觀賞27/81CaesarCipher定義如下變換abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC讓每個(gè)字母等價(jià)于一個(gè)數(shù)值abcdefghijklm0123456789101112nopqrstuvwxyZ13141516171819202122232425Caesar密碼可以表示如下C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)，這里k

=32019-6-6謝謝觀賞27/81CaesarCipher2019-6-6謝謝觀賞28/81對(duì)Caesar密碼的攻擊如果已知某給定密文是Caesar密碼，窮舉攻擊是很容易實(shí)現(xiàn)的，因?yàn)橹灰?jiǎn)單地測(cè)試所有25種可能的密鑰Caesar密碼的三個(gè)重要特征使我們可以采用窮舉攻擊分析方法已知加密和解密算法所需測(cè)試的密鑰只有25個(gè)明文所用的語(yǔ)言是已知的，且其意義易于識(shí)別比如，破解密文PHHWPHDIWHUWKHWRJDSDUWB，或者，GCUAVQDTGCM2019-6-6謝謝觀賞28/81對(duì)Caesar密碼的攻擊2019-6-6謝謝觀賞29/812019-6-6謝謝觀賞29/812019-6-6謝謝觀賞30/81對(duì)Caesar密碼的攻擊如果明文所用語(yǔ)言不為我們所知，則明文輸出不可識(shí)別，而且輸入可能按某種方式經(jīng)過(guò)縮寫(xiě)或壓縮，則識(shí)別就更加困難例如2019-6-6謝謝觀賞30/81對(duì)Caesar密碼的攻擊如2019-6-6謝謝觀賞31/812.2.2MonoalphabeticCipher單表代換密碼單表代換密碼不只是25種可能的密鑰，而是允許任意代換，增加密鑰空間每個(gè)明文字母可以隨機(jī)映射到任意一個(gè)密文字母，密文行是26個(gè)字母的任意置換，那么有26!或大于4x1026種可能的密鑰，每條消息用一個(gè)字母表加密這樣密鑰有26個(gè)字母長(zhǎng)Plain:abcdefghijklmnopqrstuvwxyzCipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA

2019-6-6謝謝觀賞31/812.2.2Monoalp2019-6-6謝謝觀賞32/81單表代換密碼的安全性分析只要密文字符是26個(gè)字母的一個(gè)排列即可。單表代換密碼中每條消息用一個(gè)字母表加密這樣有26!=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ī)律和特性2019-6-6謝謝觀賞32/81單表代換密碼的安全性分析只2019-6-6謝謝觀賞33/81語(yǔ)言的冗余性和密碼攻擊人類(lèi)的語(yǔ)言是有冗余性的比如從“thlrdsmshphrdshllntwnt”中我們可以大概猜出些什么字母使用的頻率是不一樣的英文字母E是使用最頻繁的，然后是T,R,N,I,O,A,S等有些字母使用得很少，如Z,J,K,Q,X這樣可以得到英文字母使用頻率分布表同時(shí)，統(tǒng)計(jì)雙字母組合和三字母組合的使用頻率也是非常有用的2019-6-6謝謝觀賞33/81語(yǔ)言的冗余性和密碼攻擊人類(lèi)2019-6-6謝謝觀賞34/81英文字母的相對(duì)使用頻率2019-6-6謝謝觀賞34/81英文字母的相對(duì)使用頻率2019-6-6謝謝觀賞35/81英文字母使用頻率用于密碼分析關(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)出通常的峰值和低谷，那么單表代換也會(huì)呈現(xiàn)相同的特性，比如：峰值在：A-E-H-I,N-O,R-S-T低谷在：J-K,Q,X-Z雙字母、三字母出現(xiàn)特性表也會(huì)有助于破譯密文2019-6-6謝謝觀賞35/81英文字母使用頻率用于密碼分2019-6-6謝謝觀賞36/81單表代換密碼攻擊舉例給定密文:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ統(tǒng)計(jì)相關(guān)字母出現(xiàn)的次數(shù)(seetextbook)可以猜測(cè)P和Z是e和t，ZW是th，這樣ZWP就是the這樣反復(fù)試驗(yàn)并不斷修正錯(cuò)誤，最后可得：

itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow2019-6-6謝謝觀賞36/81單表代換密碼攻擊舉例給定密2019-6-6謝謝觀賞37/812.2.3Playfair密碼單表代換盡管有大量的密鑰，也不能提供足夠的安全性，因?yàn)槊芪闹袣埩袅舜罅康拿魑慕Y(jié)構(gòu)，一種解決辦法是引進(jìn)多表代換密碼。Playfair密碼是最著名的多表代換密碼，它把明文中的雙字母音節(jié)作為一個(gè)單元轉(zhuǎn)換成密文的雙字母音節(jié)。Playfair密碼是由英國(guó)科學(xué)家CharlesWheatstone在1854年發(fā)明的，用了他的朋友BaronPlayfair的名字命名。Playfair算法基于一個(gè)由密鑰詞構(gòu)成的5x5字母矩陣2019-6-6謝謝觀賞37/812.2.3Playfai2019-6-6謝謝觀賞38/81Playfair密碼的密鑰矩陣假定使用的密鑰詞是MONARCHY先在5x5矩陣中填上密鑰詞，去掉重復(fù)字母再將剩余的字母按字母表的順序從左至右、從上至下填在矩陣剩下的格子中，I和J當(dāng)作一個(gè)字母MONARCHYBDEFGI/JKLPQSTUVWXZ2019-6-6謝謝觀賞38/81Playfair密碼的密鑰2019-6-6謝謝觀賞39/81Playfair密碼的加密對(duì)明文按如下規(guī)則一次加密兩個(gè)字母

如果該字母對(duì)的兩個(gè)字母是相同的，則在其中插入一個(gè)填充字母，如‘x’,“balloon”加密成“balxloon”落在同一行的明文字母對(duì)中的字母由其右邊的字母來(lái)代換，每行中最右的字母用該行最左邊的第一個(gè)字母來(lái)代換,如“ar”加密成“RM”落在同一列的明文字母對(duì)中的字母由其下面的字母來(lái)代換，每列中最下面的一個(gè)字母用該列最上面的第一個(gè)字母來(lái)代換,如“mu”加密成“CM”其他的每組明文字母對(duì)中的字母按如下方式代換：該字母所在行為密文所在行，另一字母所在列為密文所在列，如“hs”變換成“BP”，“ea”代換為“IM”或“JM”(asdesired)2019-6-6謝謝觀賞39/81Playfair密碼的加密2019-6-6謝謝觀賞40/81Playfair密碼的安全性Playfair密碼安全性比單表代換大為提高因?yàn)橛?6個(gè)字母，因此有26x26=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è)世紀(jì)，曾保證是安全的，但1915年被德軍破譯。1941年起，德軍和蓋世太保使用雙表playfair，1944年秋季被英國(guó)的BletcheyPark破譯。因?yàn)樗拿芪娜匀煌旰玫乇Ａ袅嗣魑恼Z(yǔ)言的大部分結(jié)構(gòu)特征，它仍然是相對(duì)容易攻破的，幾百個(gè)字母的密文就足夠分析出規(guī)律了。2019-6-6謝謝觀賞40/81Playfair密碼的安全2019-6-6謝謝觀賞41/81字母出現(xiàn)的相對(duì)頻率“明文”曲線畫(huà)出7萬(wàn)個(gè)字母的頻率分布，對(duì)文中出現(xiàn)的每個(gè)字母計(jì)數(shù)，結(jié)果除以字母e的出現(xiàn)次數(shù)。加密后的曲線體現(xiàn)了加密后字母頻率分布被掩蓋的程度，如果完全被掩蓋，則應(yīng)該是一條水平線。2019-6-6謝謝觀賞41/81字母出現(xiàn)的相對(duì)頻率“明文”2019-6-6謝謝觀賞42/812.2.4Hill密碼1929年數(shù)學(xué)家LesterHill發(fā)明Hill密碼將m個(gè)連續(xù)的明文字母替換成m個(gè)密文字母，這由m個(gè)線性方程決定，每個(gè)字母指定一個(gè)數(shù)值(a=0,b=1,…,z=25)，假如m為3：c1=(k11p1+k12p2+k13p3)mod26c2=(k21p1+k22p2+k23p3)mod26c3=(k31p1+k32p2+k33p3)mod26用列向量和矩陣表示為或C=KPmod26

C和P是長(zhǎng)度為3的列向量，分別代表密文和明文

K是一個(gè)3x3矩陣，代表加密密鑰，運(yùn)算按模26執(zhí)行2019-6-6謝謝觀賞42/812.2.4Hill密碼12019-6-6謝謝觀賞43/81Hill密碼明文paymoremoney，加密密鑰為明文前三個(gè)字母用向量[15024]表示，則照此轉(zhuǎn)換剩下字母，可得密文LNSHDLEWMTRW解密需要用到矩陣K的逆K-1，由KK-1=I定義，I是單位矩陣2019-6-6謝謝觀賞43/81Hill密碼明文paymo2019-6-6謝謝觀賞44/81Hill密碼KK-1=I可以驗(yàn)證如下Hill密碼系統(tǒng)可以表示如下C=E(K,P)=KPmod26P=D(K,C)=K-1Cmod26=K-1KP=P2019-6-6謝謝觀賞44/81Hill密碼2019-6-6謝謝觀賞45/812.2.5PolyalphabeticCiphers

多表代換密碼改進(jìn)簡(jiǎn)單的單表代換的方法是在明文消息中采用不同的單表代換，這就是多表代換密碼poly-alphabeticsubstitutionciphers因?yàn)樾枰聹y(cè)更多的字母表，并且頻率分布特性也變得平坦了，所以使得密碼破譯更加困難使用一密鑰詞對(duì)每個(gè)明文字母選擇一個(gè)字母表來(lái)加密依次使用每個(gè)字母表如果到了密鑰詞最后一個(gè)字母，則從頭開(kāi)始繼續(xù)2019-6-6謝謝觀賞45/812.2.5Polyalp2019-6-6謝謝觀賞46/81Vigenère密碼最簡(jiǎn)單的多表代換密碼是Vigenère密碼，它其實(shí)是多重Caesar密碼26個(gè)密碼水平放置，最左邊是密鑰字母，頂部排列的是明文的標(biāo)準(zhǔn)字母表加密一條消息需要與消息一樣長(zhǎng)的密鑰，密鑰是密鑰詞的重復(fù)，比如，密鑰詞為K=k1k2...kd

加密：給定密鑰字母x和明文字母y，密文字母是位于x行和y列的那個(gè)字母密鑰詞的第i

字母，表明使用第i個(gè)字母表，輪流使用字母表，如果到了消息的第d個(gè)字母時(shí)則從頭再做解密：密鑰字母決定行，行里密文字母所在列的頂部字母就是明文字母

2019-6-6謝謝觀賞46/81Vigenère密碼最簡(jiǎn)單2019-6-6謝謝觀賞47/812019-6-6謝謝觀賞47/812019-6-6謝謝觀賞48/81Example寫(xiě)下明文在明文之上重復(fù)寫(xiě)下密鑰像使用Caesarcipher密鑰那樣使用每一個(gè)密鑰字母，加密每一個(gè)明文字母比如，使用密鑰deceptivekey:deceptivedeceptivedeceptiveplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ2019-6-6謝謝觀賞48/81Example寫(xiě)下明文2019-6-6謝謝觀賞49/81Vigenère密碼的安全性每一個(gè)明文字母可以有多個(gè)密文字母對(duì)應(yīng)，這樣字母使用的頻率特性減弱了，但是沒(méi)有完全消失攻擊者首先要分析密文是否是用單表代換加密的，即通過(guò)簡(jiǎn)單的測(cè)試密文的統(tǒng)計(jì)特性如果認(rèn)為是用Vigenère密碼加密的，破譯能否取得進(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)的密鑰2019-6-6謝謝觀賞49/81Vigenère密碼的安全2019-6-6謝謝觀賞50/81KasiskiMethodtobreak

Vigenère

卡西斯基方法破解Vigenère破解Vigenère的方法是由Charles

Babbage(巴貝奇)和FriedrichKasiski(卡西斯基)分別發(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)消除，AutokeyCipher2019-6-6謝謝觀賞50/81KasiskiMetho2019-6-6謝謝觀賞51/81AutokeyCipher最理想的是讓密鑰和要加密的消息一樣長(zhǎng)Vigenère提出了autokey

cipher，密鑰詞keyword放在消息前面作為密鑰key前綴知道了密鑰詞能夠破譯密文的前面一些字母，據(jù)此可以解密密文消息的其余部分但是這種方法仍然具有字母使用的頻率特性可供分析例如，給定密鑰詞：deceptivekey:deceptivewearediscoveredsavplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA2019-6-6謝謝觀賞51/81AutokeyCiphe2019-6-6謝謝觀賞52/812.2.6One-TimePad一次一密JosephMauborgne提出使用與消息一樣長(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ì)得到大量可讀、清楚的明文，但是無(wú)法確定哪個(gè)才是真正所需的，因而這種密碼不可破。一次一密的兩個(gè)限制產(chǎn)生大規(guī)模隨機(jī)密鑰有實(shí)際困難密鑰的分配和保護(hù)無(wú)法保證2019-6-6謝謝觀賞52/812.2.6One-Tim2019-6-6謝謝觀賞53/812.3TranspositionCiphers

置換密碼置換密碼改變明文內(nèi)容元素的相對(duì)位置，保持內(nèi)容的表現(xiàn)形式不變通常稱(chēng)為transposition或者permutation密碼通過(guò)重新安排消息字母的位置來(lái)隱藏明文信息，而不是用其他字母來(lái)代換明文字母這種方法是很容易破譯的，因?yàn)槊芪膿碛信c明文一樣的字母頻率統(tǒng)計(jì)特性2019-6-6謝謝觀賞53/812.3Transposi2019-6-6謝謝觀賞54/81一維變換－矩陣轉(zhuǎn)置二維變換－圖形轉(zhuǎn)置DNATSREDNUUOYNAC明文：canyouunderstand密文：codtaueanurnynsd輸入輸出UUOYNACSREDNNATD密文明文明文：canyouunderstand密文：dnsuaruteodynnacTranspositionorpermutation

置換密碼2019-6-6謝謝觀賞54/81一維變換－矩陣轉(zhuǎn)置DNAT2019-6-6謝謝觀賞55/81柵欄技術(shù)RailFencecipher按照對(duì)角線的順序?qū)懗雒魑?，按行的順序讀出作為密文如加密meetmeafterthetogaparty:mematrhtgpryetefeteoaat可以得到密文MEMATRHTGPRYETEFETEOAAT2019-6-6謝謝觀賞55/81柵欄技術(shù)RailFen2019-6-6謝謝觀賞56/81RowTranspositionCiphers

行置換密碼一個(gè)更復(fù)雜的方案是把消息一行一行地寫(xiě)成矩形塊，然后按列讀出，但是把列的次序打亂，列的次序就是算法的密鑰，例如：Key:4312567Plaintext:attackpostponeduntiltwoamxyzCiphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZ可以采用多步置換來(lái)得到相對(duì)較高的安全性

2019-6-6謝謝觀賞56/81RowTransposi2019-6-6謝謝觀賞57/81乘積密碼ProductCiphers單純的代換或者置換密碼是不安全的，因?yàn)檎Z(yǔ)言的特性因此可以考慮連續(xù)使用若干這樣的密碼使其難以破解，但是：兩次代換只生成更復(fù)雜的代換兩次置換只生成更復(fù)雜的置換如果在一次代換之后跟一次置換，可以生成一種新的更難破解的密碼，這就是乘積密碼乘積密碼是從古典密碼通往現(xiàn)代密碼的橋梁2019-6-6謝謝觀賞57/81乘積密碼ProductC2019-6-6謝謝觀賞58/812.4RotorMachines轉(zhuǎn)輪密碼機(jī)在現(xiàn)代密碼系統(tǒng)出現(xiàn)之前，轉(zhuǎn)輪密碼機(jī)是最為廣泛使用的多重加密器，尤其是在第二次世界大戰(zhàn)中。GermanEnigma,JapanesePurple,AlliedHagelin轉(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的多表代換密碼。3個(gè)圓筒的轉(zhuǎn)輪機(jī)就有263=17576個(gè)不同的代換字母表2019-6-6謝謝觀賞58/812.4RotorMac2019-6-6謝謝觀賞59/81Enigma：密碼學(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è)人：首先是德國(guó)人亞瑟·謝爾比烏斯(ArthurScherbius)；其次是波蘭人馬里安·雷耶夫斯基(MarianRejewski)；然后是英國(guó)人阿蘭·圖靈(AlanTuring)。德國(guó)人發(fā)明了Enigma；波蘭人初步破解了簡(jiǎn)單的Enigma；而英國(guó)人徹底終結(jié)了最高難度的Enigma。2019-6-6謝謝觀賞59/81Enigma：密碼學(xué)界劃時(shí)2019-6-6謝謝觀賞60/81亞瑟·謝爾比烏斯和Enigma1918年，德國(guó)發(fā)明家亞瑟·謝爾比烏斯(ArthurScherbius)和理查德·里特Ritter創(chuàng)辦了一家新技術(shù)應(yīng)用公司，利用現(xiàn)代化的電氣技術(shù)，來(lái)取代手工編碼加密方法，發(fā)明了一種能夠自動(dòng)編碼的機(jī)器。謝爾比烏斯給自己所發(fā)明的電氣編碼機(jī)械取名“恩尼格瑪”(Enigma，意為啞謎)。恩尼格瑪密碼機(jī)是一種用于加密與解密文件的密碼機(jī)。確切地說(shuō)，恩尼格瑪是一系列相似的轉(zhuǎn)子機(jī)械的統(tǒng)稱(chēng)，包括了一系列不同的型號(hào)。恩尼格瑪密碼機(jī)可以簡(jiǎn)單分為三個(gè)部分：鍵盤(pán)、轉(zhuǎn)子和顯示器。2019-6-6謝謝觀賞60/81亞瑟·謝爾比烏斯和Enig2019-6-6謝謝觀賞61/81亞瑟·謝爾比烏斯和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)輪的輸出端連接到相鄰的下一轉(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è)明文字母操作兩次。2019-6-6謝謝觀賞61/81亞瑟·謝爾比烏斯和Enig2019-6-6謝謝觀賞62/81Enigma

三個(gè)轉(zhuǎn)輪的連接示意2019-6-6謝謝觀賞62/81Enigma

三個(gè)轉(zhuǎn)輪的連2019-6-6謝謝觀賞63/81Enigma的使用使用恩尼格瑪通訊時(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ò)程完全一樣，這就是反射器的作用，同時(shí)反射器的一個(gè)副作用就是一個(gè)字母永遠(yuǎn)也不會(huì)被加密成它自己，因?yàn)榉瓷淦髦幸粋€(gè)字母總是被連接到另一個(gè)不同的字母。2019-6-6謝謝觀賞63/81Enigma的使用使用恩尼2019-6-6謝謝觀賞64/81Enigma的破解

波蘭數(shù)學(xué)家和密碼學(xué)家雷耶夫斯基波蘭數(shù)學(xué)家和密碼學(xué)家馬里安·雷耶夫斯基(MarianAdamRejewski,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è)重要成就。雷耶夫斯基等人在二戰(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é)家的銘牌。

2019-6-6謝謝觀賞64/81Enigma的破解

波蘭數(shù)2019-6-6謝謝觀賞65/81Enigma的破解

英國(guó)倫敦附近的柏雷屈里莊園密碼學(xué)校2019-6-6謝謝觀賞65/81Enigma的破解

英國(guó)倫2019-6-6謝謝觀賞66/81Enigma的破解

計(jì)算機(jī)科學(xué)之父阿蘭·圖靈

阿蘭·麥席森·圖靈AlanMathisonTuring(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,GovernmentCodeandCipherSchool)，集結(jié)了一大批為破譯ENIGMA作出卓越貢獻(xiàn)的人們，圖靈發(fā)明了綽號(hào)為“炸彈”(Bombes)的解密機(jī)器，被看成一位天才解密分析專(zhuān)家，而于1945年獲政府的最高獎(jiǎng)—大英帝國(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ī)密TheUltraSecret》一書(shū)出版，人們才知道圖靈在解密分析方面的杰出貢獻(xiàn)。2019-6-6謝謝觀賞66/81Enigma的破解

計(jì)算機(jī)2019-6-6謝謝觀賞67/81計(jì)算機(jī)科學(xué)之父阿蘭·圖靈在圖靈的設(shè)計(jì)思想指導(dǎo)下，1950年制出了ACE“自動(dòng)計(jì)算機(jī)”樣機(jī)，1958年制成大型ACE機(jī)。早在1947年，圖靈就提出過(guò)自動(dòng)程序設(shè)計(jì)的思想，1950年，他提出關(guān)于機(jī)器思維的問(wèn)題，他的論文“計(jì)算機(jī)和智能(Computingmachineryandintelligence)引起了廣泛的注意和深遠(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)浮！禩heCodeBook》作者賽門(mén)辛的鏈接：破解納粹的秘密

DecodingNaziSecrets：

1/~syang/2019-6-6謝謝觀賞67/81計(jì)算機(jī)科學(xué)之父阿蘭·圖靈在2019-6-6謝謝觀賞68/81Enigma的破解恩尼格瑪加密的關(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)子是可以拆卸下來(lái)并互相交換位置，這樣一來(lái)初始方向的可能性一下就增加了六倍。假設(shè)三個(gè)轉(zhuǎn)子的編號(hào)為1、2、3，那么它們可以被放成123-132-213-231-312-321這六種不同位置，當(dāng)然這時(shí)收發(fā)密文的雙方除了要約定轉(zhuǎn)子自身的初始方向，還要約好這六種排列中的一種。2019-6-6謝謝觀賞68/81Enigma的破解恩尼格瑪2019-6-6謝謝觀賞69/81Enigma的破解除了轉(zhuǎn)子方向和排列位置，恩尼格瑪還有一道保障安全的關(guān)卡，在鍵盤(pán)和第一個(gè)轉(zhuǎn)子之間有塊連接板。通過(guò)這塊連接板可以用一根連線把某個(gè)字母和另一個(gè)字母連接起來(lái)，這樣這個(gè)字母的信號(hào)在進(jìn)入轉(zhuǎn)子之前就會(huì)轉(zhuǎn)變?yōu)榱硪粋€(gè)字母的信號(hào)。這種連線最多可以有六根，后期的恩尼格瑪甚至達(dá)到十根連線，這樣就可以使6對(duì)字母的信號(hào)兩兩互換，其他沒(méi)有插上連線的字母則保持不變。當(dāng)然連接板上的連線狀況也是收發(fā)雙方預(yù)先約定好的。轉(zhuǎn)子之間的相互位置、轉(zhuǎn)子的初始方向，以及連接板的連線狀況組成了恩尼格瑪三道牢不可破的保密防線，其中連接板是一個(gè)簡(jiǎn)單替換密碼系統(tǒng)，而不停轉(zhuǎn)動(dòng)的轉(zhuǎn)子，雖然數(shù)量不多，但卻是點(diǎn)睛之筆，使整個(gè)系統(tǒng)變成了復(fù)式替換系統(tǒng)。連接板雖然只是簡(jiǎn)單替換卻能使可能性數(shù)目大大增加，在轉(zhuǎn)子的復(fù)式作用下進(jìn)一步加強(qiáng)了保密性。2019-6-6謝謝觀賞69/81Enigma的破解除了轉(zhuǎn)子2019-6-6謝謝觀賞70/81Enigma的破解讓我們來(lái)算一算經(jīng)過(guò)這樣處理，要想通過(guò)“暴力破譯法”還原明文，需要試驗(yàn)多少種可能性：三個(gè)轉(zhuǎn)子不同的方向組成了26ｘ26ｘ26＝17576種可能性；三個(gè)轉(zhuǎn)子間不同的相對(duì)位置為6種可能性；連接板上兩兩交換6對(duì)字母的可能性則是異常龐大，有100391791500種；于是一共有17576ｘ6ｘ100391791500，其結(jié)果大約為10,000,000,000,000,000！即一億億種可能性！這樣龐大的可能性，即便能動(dòng)員大量的人力物力，要想靠“暴力破譯法”來(lái)逐一試驗(yàn)可能性，幾乎是不可能的。而收發(fā)雙方，則只要按照約定的轉(zhuǎn)子方向、位置和連接板連線狀況，就可以非常輕松簡(jiǎn)單地進(jìn)行通訊了。這就是“恩尼格瑪”密碼機(jī)的保密原理。

2019-6-6謝謝觀賞70/81Enigma的破解讓我們來(lái)2019-6-6謝謝觀賞71/81解密德軍U艇密碼機(jī)1944年6月4日，美國(guó)海軍瓜達(dá)卡納爾號(hào)航空母艦和5艘驅(qū)逐艦組成的編隊(duì)，在非洲加那利群島附近海域?qū)Φ聡?guó)海軍U-505潛艇展開(kāi)圍捕，并繳獲了納粹德國(guó)專(zhuān)門(mén)用于U艇通訊聯(lián)系的絕密的密碼機(jī)恩尼格瑪和密碼本。從此，德軍的U型潛艇完全暴露在盟軍的反潛打擊之下，德國(guó)海軍的“狼群”作戰(zhàn)遭到徹底失敗，并由此改變了整個(gè)第二次世界大戰(zhàn)的結(jié)局。那部對(duì)二次大戰(zhàn)進(jìn)程產(chǎn)生過(guò)重要影響的德國(guó)海軍密碼機(jī)現(xiàn)在存放于美國(guó)中央情報(bào)局的檔案館。2019-6-6謝謝觀賞71/81解密德軍U艇密碼機(jī)1942019-6-6謝謝觀賞72/81破解納粹的Tunny密碼柏雷屈里莊園的三位英雄Alan.TuringWilliam.Tutte，數(shù)學(xué)家，破解了Tunny密碼Tommy.Flowers，電氣工程師，獨(dú)立造出了世界上第一臺(tái)計(jì)算機(jī)Colossus，用于破解Tunny密碼艾森豪威爾說(shuō)過(guò)，Tunny密碼的破解，使二戰(zhàn)至少縮短了兩年2019-6-6謝謝觀賞72/81破解納粹的Tunny密碼柏2019-6-6謝謝觀賞73/81Tunny密碼(Lorenz密碼)LorenzSZ40密碼機(jī)比Enigma復(fù)雜得多，但是使用簡(jiǎn)單，像電傳打字機(jī)那樣直接收發(fā)明文12個(gè)轉(zhuǎn)子，用兩個(gè)密鑰進(jìn)行兩次加密第1輪和第2輪各用5個(gè)轉(zhuǎn)子加密剩下兩個(gè)轉(zhuǎn)子生成“stutters”，向密鑰中添加更多冗余信息密鑰序列為23x26x29x31x37x41x43x47x51x53x59x61=1,600,000,000,000,000約1600萬(wàn)億種不同的組合Lorenz密碼的弱點(diǎn)如果兩條不同的消息使用相同的密鑰加密，那么就有可能將它們還原出來(lái)一個(gè)德軍發(fā)報(bào)員使用相同密鑰加密兩份稍有不同的4000字電文，使得英國(guó)人得到了破譯的機(jī)會(huì)2019-6-6謝謝觀賞73/81Tunny密碼(Loren2019-6-6謝謝觀賞74/81Tunny密碼的破譯(手工破譯)如果兩條不同的消息使用相同的密鑰加密A+K=N等式兩邊相加，消去K，得B+K=PA+B=N+P,令G=N+P現(xiàn)在的問(wèn)題是有沒(méi)有辦法把G拆分成A和B？數(shù)學(xué)上是無(wú)法做到的，但可以通過(guò)常識(shí)去猜測(cè)可能的答案把G和A相加，根據(jù)電傳碼表，G和A相加結(jié)果是B例2：RSEZLS是英國(guó)兩大城市名稱(chēng)之和，假設(shè)其中一個(gè)是LONDEN，字母相加，得OXFORD天才譯碼員JohnTiltman用10天時(shí)間分離出密鑰和明文，但是找不到破譯所有Tunny密碼的適用方法｛2019-6-6謝謝觀賞74/81Tunny密碼的破譯(手工2019-6-6謝謝觀賞75/81Tunny密碼的破譯(數(shù)學(xué)統(tǒng)計(jì)方法)WilliamTuttle的偉大貢獻(xiàn)分析Lorenz密碼機(jī)的結(jié)構(gòu)，從截獲的密電推斷密碼運(yùn)作方式，雖然根本沒(méi)有見(jiàn)過(guò)這種密碼機(jī)研究出破譯這種密碼的“1+2”統(tǒng)計(jì)學(xué)方法(1942年11月發(fā)明)，利用數(shù)學(xué)和統(tǒng)計(jì)學(xué)來(lái)破譯密碼TommyFlowers的偉大貢獻(xiàn)根據(jù)Tuttle提出的數(shù)學(xué)破譯原理制造出第一臺(tái)半編程型電子計(jì)算機(jī)Colossus來(lái)破譯Tunny密碼，參與7步破譯過(guò)程中的2步，其余5步仍由人工完成該機(jī)器能夠每秒5000個(gè)字符的速度讀入截獲的電文(5單位電傳機(jī)紙帶)，用電子管電路生成密鑰序列，根據(jù)Tuttle的數(shù)學(xué)原理進(jìn)行破譯2019-6-6謝謝觀賞75/81Tunny密碼的破譯(數(shù)學(xué)2019-6-6謝謝觀賞76/81致命的一擊：美日中途島海戰(zhàn)秘聞日本海軍早在1934年就開(kāi)始發(fā)展現(xiàn)代密碼體系，從德國(guó)購(gòu)買(mǎi)了一部“恩尼格馬”商用密碼機(jī)并加以改進(jìn)，造出了自己的密碼機(jī)，把它發(fā)展成為日本整個(gè)外交系統(tǒng)廣泛使用的戰(zhàn)略級(jí)密碼體制，這一體制被美國(guó)軍情人員命名為“紫密”(Purple)。1940年8月，英國(guó)通信情報(bào)處成功破譯了“紫密”。其實(shí)，“紫密”曾透露日軍可能會(huì)大規(guī)模襲擊珍珠港這一極為重大的軍事機(jī)密，可惜由于種種原因，這一機(jī)密在當(dāng)時(shí)并沒(méi)有引起美國(guó)軍政要人的重視。此后，日本海軍升級(jí)了整個(gè)密碼體系，使用“艦隊(duì)密碼體制”，高級(jí)司令部才能使用的戰(zhàn)略級(jí)密碼，被美國(guó)情報(bào)人員命名為“JN-25b”。1942年1月20日，日本海軍“伊號(hào)124”潛艇在澳大利亞海軍基地達(dá)爾文港外海鋪設(shè)水雷，遭美國(guó)海軍驅(qū)逐艦以及三艘澳大利亞快艇的圍攻，沉沒(méi)在50米深的海底。

美國(guó)海軍迅速派出熟練的潛水員潛入海底，在伊號(hào)124潛艇的殘骸里發(fā)現(xiàn)了一只保險(xiǎn)柜，從中找到一個(gè)密碼本，表面有鉛，遇水后沒(méi)有溶化。該密碼本被交到了夏威夷情報(bào)站站長(zhǎng)羅徹福特手上，他驚喜地發(fā)現(xiàn)，這就是讓他頭痛不已的日本“JN-25b”艦隊(duì)密碼體制。而此時(shí)，日本海軍并不知道“伊號(hào)124”潛艇是被擊沉的，還以為潛艇沉沒(méi)是意外事故。因此，一直照舊使用“JN-25b”。2019-6-6謝謝觀賞76/81致命的一擊：美日中途島海戰(zhàn)2019-6-6謝謝觀賞77/81致命的一擊：美日中途島海戰(zhàn)秘聞到1942年5月初，JN-25b密碼本已被美國(guó)夏威夷情報(bào)站還原了1/3，日本人往來(lái)的密電有90%的內(nèi)容都能正確譯出。5月20日，羅徹福特截獲并破譯出日本聯(lián)合艦隊(duì)司令下發(fā)給各部隊(duì)的長(zhǎng)篇電文，掌握了他們的作戰(zhàn)計(jì)劃。只是在計(jì)劃中，關(guān)于進(jìn)攻的目標(biāo)，日軍始終用一個(gè)代號(hào)“AF”來(lái)代替。這個(gè)“AF”究竟是哪里?經(jīng)過(guò)分析羅徹福特認(rèn)為，“AF”是指中途島。該島由周長(zhǎng)24公里的環(huán)礁組成，陸地面積約5平方公里。距日本2800海里，距夏成夷903海里。美國(guó)海軍在這里修建了航空和潛艇基地，以使之成為夏威夷群島的西北屏障。羅徹福特建議太平洋艦隊(duì)總司令尼米茲通過(guò)海底電話，命令中途島基地用明碼報(bào)告淡水設(shè)備故障，用水困難。還讓珍珠港的第14海軍軍區(qū)煞有介事地回電：已向中途島派出供水船。日軍很快就上鉤了，他們用密碼通知主力進(jìn)攻部隊(duì)攜帶更多的淡水凈化器。這就證明，日軍的下一個(gè)攻擊目標(biāo)正是中途島!1942年6月4日清晨，日本攻擊機(jī)群直撲中途島。可是，它們所能找到的轟炸目標(biāo)，只不過(guò)是空蕩的飛行跑道和幾座空機(jī)庫(kù)，島上所有的飛機(jī)此時(shí)都已經(jīng)飛上了高空，那些本應(yīng)該停在中途島上的飛機(jī)，此時(shí)已經(jīng)在飛往攻擊他們艦隊(duì)的路上。沒(méi)過(guò)多久，美軍的32架轟炸機(jī)僅用11分鐘，就先后擊沉了日軍的3艘航母。美軍大獲全勝，中途島戰(zhàn)役實(shí)質(zhì)上成了太平洋戰(zhàn)爭(zhēng)的轉(zhuǎn)折點(diǎn)。2019-6-6謝謝觀賞77/81致命的一擊：美日中途島海戰(zhàn)2019-6-6謝謝觀賞78/812.5Steganography隱寫(xiě)術(shù)隱寫(xiě)術(shù)不是加密技術(shù)隱寫(xiě)術(shù)可以隱藏信息的存在，密碼學(xué)則通過(guò)對(duì)文本信息的不同轉(zhuǎn)換而實(shí)現(xiàn)信息的不可讀字符標(biāo)記不可見(jiàn)墨水針刺打字機(jī)的色帶校正隱寫(xiě)術(shù)需要許多額外的開(kāi)銷(xiāo)來(lái)隱藏相對(duì)較少的信息2019-6-6謝謝觀賞78/812.5Steganogr2019-6-6謝謝觀賞79/812019-6-6謝謝觀賞79/812019-6-6謝謝觀賞80/81SummaryHaveconsidered:classicalciphertechniquesandterminologymonoalphabeticsubstitutioncipherscryptanalysisusingletterfrequenciesPlayfaircipherspolyalphabeticcipherstranspositionciphersproductciphersandrotormachinesstenography2019-6-6謝謝觀賞80/81SummaryHavec2019-6-6謝謝觀賞81/81復(fù)習(xí)思考題對(duì)網(wǎng)絡(luò)安全的攻擊主要有哪些？網(wǎng)絡(luò)安全服務(wù)的目標(biāo)是什么？什么是密碼？簡(jiǎn)單加密系統(tǒng)的模型是什么？什么是理論安全？什么是實(shí)際安全？什么是密碼體制？有哪幾類(lèi)密碼體制？現(xiàn)代密碼學(xué)的基本原則是什么？加密系統(tǒng)應(yīng)滿足哪些具體要求？作業(yè)題

WilliamStallings第四版書(shū)上第二章習(xí)題

2.4,2.6,2.9,2.10,2.11,2.14,2.15,2.21(dueSept.25,2012)2019-6-6謝謝觀賞81/81復(fù)習(xí)思考題對(duì)網(wǎng)絡(luò)安全的攻擊2019-6-6謝謝觀賞82/812019-6-6謝謝觀賞82/812019-6-6謝謝觀賞現(xiàn)代密碼學(xué)理論與實(shí)踐

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

第2章傳統(tǒng)加2019-6-6謝謝觀賞84/81PartOne–SymmetricCiphersRoadMapforPartOneChp.2,ClassicalEncryptionTechniquesChp.3,BlockCipherandtheDataEncryptionStandardChp.4,FiniteFieldsChp.5,AdvancedEncryptionStandardChp.6,MoreonSymmetricCiphersChp.7,ConfidentialityUsingSymmetricEncryption2019-6-6謝謝觀賞2/81PartOne–Symme2019-6-6謝謝觀賞85/81Chapter2–

ClassicalEncryptionTechniquesManysavagesatthepresentdayregardtheirnamesasvitalpartsofthemselves,andthereforetakegreatpainstoconcealtheirrealnames,lesttheseshouldgivetoevil-disposedpersonsahandlebywhichtoinjuretheirowners.

—TheGoldenBough,SirJamesGeorgeFrazer2019-6-6謝謝觀賞3/81Chapter2–

C2019-6-6謝謝觀賞86/81密碼學(xué)的演變歷史(1)

WilliamFriedman1918,WilliamFriedman’sTheIndexofCoincidenceanditsApplicationsinCryptographyWilliamFrederickFriedman(Sept.24,1891–Nov.12,1969)美國(guó)陸軍密碼專(zhuān)家。1930年代，他領(lǐng)導(dǎo)了陸軍的一個(gè)研究部門(mén)SignalsIntelligenceService(SIS)，其中一部分服務(wù)一直延續(xù)到五十年代。三十年代晚期，在他的指導(dǎo)下，F(xiàn)rankRowlett破解了日本人的PURPLE加密機(jī)(紫密)，截獲了日本的大量外交和軍事的秘密。2019-6-6謝謝觀賞4/81密碼學(xué)的演變歷史(1)

W2019-6-6謝謝觀賞87/81密碼學(xué)的演變歷史(2)香農(nóng)的貢獻(xiàn)1948年,ClaudeShannon’s發(fā)表“TheCommunicationTheoryofSecrecySystem”，成為現(xiàn)代密碼學(xué)理論基礎(chǔ)。1949年，Shannon在其著名的“信息論”發(fā)表一年之后，又發(fā)表了論文“保密系統(tǒng)的通信理論”，首次將密碼學(xué)研究置于堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)上。該理論的重大貢獻(xiàn)在于：建立了通信保密/密碼學(xué)嚴(yán)格的理論基礎(chǔ)；證明了一次一密(one-timepad)的密碼系統(tǒng)是完善保密的，導(dǎo)致了對(duì)流密碼的研究和應(yīng)用；提出分組密碼設(shè)計(jì)應(yīng)該遵循的準(zhǔn)則，如擴(kuò)散性和混淆性；證明了消息冗余使得破譯者統(tǒng)計(jì)分析成功的理論值(唯一解距離)2019-6-6謝謝觀賞5/81密碼學(xué)的演變歷史(2)香農(nóng)2019-6-6謝謝觀賞88/81密碼學(xué)的演變歷史(2)ClaudeElwoodShannon(Apr.30,1916–Feb.24,2001),美國(guó)電氣工程師和數(shù)學(xué)家，被譽(yù)為信息論之父"thefatherofinformationtheory".香農(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)為是迄今最重要的碩士論文。1949-1967，密碼學(xué)研究處于沉寂時(shí)期2019-6-6謝謝觀賞6/81密碼學(xué)的演變歷史(2)Cla2019-6-6謝謝觀賞89/81密碼學(xué)的演變歷史(3)

Feistel,WhitfieldDiffie,MatinHellman1971,IBM發(fā)明LucifferCipher,128位密鑰作分組加密。這項(xiàng)發(fā)明是由HorstFeistel(Jan.30,1915–Nov.14,1990)領(lǐng)導(dǎo)的，他是密碼學(xué)家，當(dāng)時(shí)在IBM負(fù)責(zé)設(shè)計(jì)加密器，他的工作最終激發(fā)了70年代DataEncryptionStandard(DES)的研發(fā)高潮1976-1977，