密碼學(xué)基礎(chǔ)知識(shí)課件

夫?qū)W須靜也，才須學(xué)也，非學(xué)無(wú)以廣才，非志無(wú)以成學(xué)。——諸葛亮夫?qū)W須靜也，才須學(xué)也，非學(xué)無(wú)以廣才，非志無(wú)以1概述密碼學(xué)密碼編碼學(xué)密碼分析學(xué)概述密碼學(xué)2

作用：

機(jī)密性鑒別完整性抗抵賴(lài)作用：3

密碼學(xué)文獻(xiàn)的發(fā)展歷程：1918年，F(xiàn)riedman《重合指數(shù)及其在密碼學(xué)中的應(yīng)用》。1918年，Heberm的轉(zhuǎn)輪機(jī)1949年，Shannon《保密系統(tǒng)的通信理論》1967年，Kahn《破譯者》1971年，F(xiàn)eistel的Lucifer密碼學(xué)文獻(xiàn)的發(fā)展歷程：4

1975年，Diffie&Hellman提出公開(kāi)密鑰密碼學(xué)，《密碼學(xué)的新方向》1977年，DES成為聯(lián)邦信息處理標(biāo)準(zhǔn)1978年，MIT的RSA算法。1985年，ElGamal體制（離散對(duì)數(shù)）；Koblitz&Miller提出橢圓曲線(xiàn)密碼學(xué)?1995年，Hoffstein，Pipher，Siverman發(fā)明NTRU密碼1975年，Diffie&Hellman提出公開(kāi)密鑰密5

密碼學(xué)之前，信息安全的保護(hù)主要是通過(guò)物理和行政手段實(shí)現(xiàn)的。密碼學(xué)最早多用于外交情報(bào)和軍事領(lǐng)域?，F(xiàn)代密碼學(xué)家通常是理論數(shù)學(xué)家。密碼學(xué)之前，信息安全的保護(hù)主要是通過(guò)物理和行政手段實(shí)現(xiàn)的。6

第一階段：手工計(jì)算第二階段：機(jī)械和電動(dòng)機(jī)械第三階段：電子和計(jì)算機(jī)第一階段：7內(nèi)容1.保密與保密系統(tǒng)2.古典密碼技術(shù)3.密碼體制4.密碼分析5.加密方式內(nèi)容1.保密與保密系統(tǒng)8一、保密與保密系統(tǒng)保密學(xué)：研究信息系統(tǒng)安全保密的科學(xué)。

一、保密與保密系統(tǒng)保密學(xué)：研究信息系統(tǒng)安全保密的科學(xué)。91.保密系統(tǒng)模型圖一個(gè)密碼體制由五元組（P，C，K，E，D）構(gòu)成。1.保密系統(tǒng)模型圖10SymmetricCipherModelSymmetricCipherModel11BasicTerminologyplaintext-theoriginalmessageciphertext-thecodedmessagecipher-algorithmfortransformingplaintexttociphertextkey-infousedincipherknownonlytosender/receiverencipher(encrypt)-convertingplaintexttociphertextdecipher(decrypt)-recoveringciphertextfromplaintextcryptography-studyofencryptionprinciples/methodscryptanalysis(codebreaking)-thestudyofprinciples/methodsofdecipheringciphertextwithoutknowingkeycryptology-thefieldofbothcryptographyandcryptanalysisBasicTerminologyplaintext-t122.密碼設(shè)計(jì)準(zhǔn)則保密系統(tǒng)抗擊密碼分析，應(yīng)滿(mǎn)足：1）系統(tǒng)即使達(dá)不到理論上是不可破的，也應(yīng)當(dāng)為實(shí)際上是不可破的。2）Kerckhoff原則。系統(tǒng)的保密性不依賴(lài)于對(duì)加密體制或算法的保密，而依賴(lài)于密鑰。3）加密和解密算法適用于所有密鑰空間中的元素。4）系統(tǒng)便于實(shí)現(xiàn)和使用方便。

2.密碼設(shè)計(jì)準(zhǔn)則保密系統(tǒng)抗擊密碼分析，應(yīng)滿(mǎn)足：13Kerckhoff六項(xiàng)準(zhǔn)則在19世紀(jì)對(duì)軍事密碼體制提出六項(xiàng)準(zhǔn)則：密碼體制即便不是在理論上不可破，也應(yīng)該是實(shí)際上不可破的。體制的泄露不應(yīng)該給通信者帶來(lái)麻煩?！璌erckhoff六項(xiàng)準(zhǔn)則在19世紀(jì)對(duì)軍事密碼體制提出六項(xiàng)準(zhǔn)143.保密系統(tǒng)的通信理論明文密碼系統(tǒng)的熵惟一解距離UD3.保密系統(tǒng)的通信理論明文15Plaintext明文Entropy:一條信息的信息量通過(guò)熵來(lái)度量。是對(duì)信息或不確定性的數(shù)學(xué)度量，通過(guò)概率分布的函數(shù)來(lái)計(jì)算。語(yǔ)言信息率：r=H(M)/NN相當(dāng)大時(shí)，標(biāo)準(zhǔn)英語(yǔ)的語(yǔ)言信息率在1.0-1.5/字母之間。語(yǔ)言絕對(duì)信息率：假定每一個(gè)字符串是等可能的，對(duì)每個(gè)字母編碼的最大位數(shù)。Plaintext明文Entropy:一條信息的信息量通過(guò)熵16

英文R=logL=log26=4.7位/字母ThomasCover采用隨機(jī)估算技術(shù)得到的信息率為1.3位/字符。自然語(yǔ)言具有高冗余度。D=R-r=3.4位/字母。英語(yǔ)語(yǔ)言是75%冗余。Huffman一條ASCII消息，每字節(jié)消息含有與英語(yǔ)相等的1.3位的消息，她的冗余信息為6.7位，相當(dāng)于每位ASCII文本有0.84位冗余英文R=logL=log26=4.7位/字母17

自然語(yǔ)言的高冗余度為密碼分析提供了一個(gè)重要工具。它最重要也是最基本的特征：?jiǎn)蝹€(gè)字母出現(xiàn)的頻率。自然語(yǔ)言的高冗余度為密碼分析提供了一個(gè)重要工具。18密碼系統(tǒng)的熵由密鑰空間大小來(lái)衡量H(K)=logK一般來(lái)說(shuō)，熵越大，破譯它越困難。密鑰：盡量使密鑰源為無(wú)記憶均勻分布源。密碼系統(tǒng)的熵由密鑰空間大小來(lái)衡量19

密文的統(tǒng)計(jì)特征由明文和密鑰的統(tǒng)計(jì)特征完全決定。收到的密文越長(zhǎng)，分析者找到密鑰或明文的可能性越大，為確信分析者可找到唯一的密鑰，理論上S至少將要多長(zhǎng)。密文的統(tǒng)計(jì)特征由明文和密鑰的統(tǒng)計(jì)特征完全決定。20惟一解距離UD在給定足夠的計(jì)算時(shí)間下，分析者能唯一計(jì)算出密鑰所需密文的平均值。惟一解距離UnicityDistance[碼量]：使一個(gè)具有無(wú)限計(jì)算能力的攻擊者能夠恢復(fù)惟一的加密密鑰所需要的最小密文量（字符數(shù)）。在達(dá)到惟一解距離時(shí)，密鑰曖昧度趨近于零。臨界值S=H(K)/[loge-H(m)]稱(chēng)為UD。惟一解距離UD在給定足夠的計(jì)算時(shí)間下，分析者能唯一計(jì)算出密鑰21UD定義為使得偽密鑰的期望值等于零的n的值。當(dāng)密文字符大于UD時(shí)，這種密碼就存在一個(gè)解，而當(dāng)密文字符小于UD時(shí)，就會(huì)出現(xiàn)多個(gè)可能的解。它利用信息論描述了被截獲的密文量和成功攻擊的可能性之間的關(guān)系。UD定義為使得偽密鑰的期望值等于零的n的值。22UDShannon指出：惟一解距離可以保證當(dāng)其太小時(shí)，密碼系統(tǒng)是不安全的，但并不保證當(dāng)其較大時(shí)，密碼系統(tǒng)就是安全的。惟一解距離不是對(duì)密碼分析需要多少密文的度量，而是對(duì)存在唯一合理的密碼分析所需密文數(shù)量的指標(biāo)。惟一解距離與冗余度成反比，當(dāng)冗余度接近于零時(shí)，一個(gè)普通的密碼系統(tǒng)也可能是不可破的。UDShannon指出：惟一解距離可以保證當(dāng)其太小時(shí)，密碼系23UD一般而言，惟一解距離越長(zhǎng)，密碼系統(tǒng)越好。無(wú)窮大時(shí)為理想保密。UD一般而言，惟一解距離越長(zhǎng)，密碼系統(tǒng)越好。無(wú)窮大時(shí)為理想保24密碼分析利用自然語(yǔ)言的冗余度來(lái)減少可能的明文數(shù)目。語(yǔ)言的冗余度越大，它就越容易被攻擊。最重要也是最基本的特征：?jiǎn)蝹€(gè)字母出現(xiàn)的頻率。一個(gè)好的加密算法是一種混合變換，它將有意義的小區(qū)域中的有意義的消息相當(dāng)均勻地分布到在整個(gè)消息空間中。密碼分析利用自然語(yǔ)言的冗余度來(lái)減少可能的明文數(shù)目。254.密碼系統(tǒng)的安全性是密碼學(xué)研究的一個(gè)重要課題有兩種定義“安全性”的方法：基于信息論的方法（經(jīng)典方法）基于計(jì)算復(fù)雜性理論的方法（現(xiàn)代方法）4.密碼系統(tǒng)的安全性是密碼學(xué)研究的一個(gè)重要課題26

基于信息論的方法：用密文中是否蘊(yùn)含明文的信息作為標(biāo)準(zhǔn)。

基于計(jì)算復(fù)雜性理論的方法：是考慮信息是否能有效地被提取出來(lái)。

27現(xiàn)代密碼學(xué)的基礎(chǔ)傳統(tǒng)的密碼學(xué)和公鑰密碼學(xué)的基礎(chǔ)是信息論和計(jì)算復(fù)雜性理論信息理論密碼學(xué)計(jì)算復(fù)雜性理論密碼學(xué)

現(xiàn)代密碼學(xué)的基礎(chǔ)傳統(tǒng)的密碼學(xué)和公鑰密碼學(xué)的基礎(chǔ)是28

信息論告訴我們，所有的密碼算法（OTP除外）都能被破譯。復(fù)雜性理論告訴我們，何時(shí)能被破譯。信息論告訴我們，所有的密碼算法（OTP除外）都能被破譯。29信息理論密碼學(xué)Shannon用不確定性和惟一解距離度量了密碼系統(tǒng)（體制）的安全性。信息理論密碼學(xué)Shannon用不確定性和惟一解距離度量了密碼30密碼系統(tǒng)的安全性：

理論保密：完全保密理想保密實(shí)際保密：計(jì)算安全（可證明安全性）密碼系統(tǒng)的安全性：31理論安全經(jīng)典方法無(wú)條件安全性基于信息論的密碼學(xué)信息理論密碼學(xué)：用信息論的觀點(diǎn)和方法研究密碼系統(tǒng)模型的建立、密碼的安全性及破譯等，它所研究的安全性準(zhǔn)則，假定密碼分析者的計(jì)算資源，不受限制理論安全經(jīng)典方法32完全保密理論上不可破譯的密碼體制。必要條件：明文數(shù)、密鑰數(shù)和密文數(shù)都相等的密碼體制，將每個(gè)明文變換成每個(gè)密文都恰好有一個(gè)密鑰，所有的密鑰都是等可能的。Shannon從理論上證明：僅當(dāng)可能的密鑰數(shù)目至少與可能的消息數(shù)目一樣多時(shí)，完全保密才是有可能的。完全保密理論上不可破譯的密碼體制。必要條件：明文數(shù)、密鑰數(shù)33完全保密僅有一次一密（OTP）亂碼本的密碼系統(tǒng)可獲得完全保密。One-TimePad在要求無(wú)條件安全的軍事和外交環(huán)境中有著很重要的作用。完全保密僅有一次一密（OTP）亂碼本的密碼系統(tǒng)可獲得完全保密34

完全保密：（完善的或無(wú)條件的保密系統(tǒng)）給定密文y，明文為x的后驗(yàn)概率等于明文x的先驗(yàn)概率完全保密：35理想保密理論上不可譯的，它的惟一解距離UD趨向于無(wú)窮大的密碼體制。意味著語(yǔ)言的多余度趨向于零。當(dāng)然消除語(yǔ)言中的全部多余度事實(shí)上不可能。它是不實(shí)用的，但它揭示我們?cè)O(shè)計(jì)密碼體制（算法）時(shí)，應(yīng)盡量縮小多余度。明文信息加密前先進(jìn)行信源編碼。理想保密理論上不可譯的，它的惟一解距離UD趨向于無(wú)窮大的密碼36

一個(gè)完全保密的密碼系統(tǒng)必須是一個(gè)理想保密的密碼系統(tǒng)，但是一個(gè)理想保密的密碼系統(tǒng)不一定是一個(gè)完全保密的密碼系統(tǒng)。一個(gè)完全保密的密碼系統(tǒng)必須是一個(gè)理想保密的密碼系統(tǒng)，但是一37實(shí)際安全現(xiàn)代方法有條件安全性基于復(fù)雜性理論的密碼學(xué)復(fù)雜性理論密碼學(xué)：用復(fù)雜性理論的觀點(diǎn)和方法研究密碼系統(tǒng)模型的建立、密碼的安全性分析及破譯等。假定密碼分析者的計(jì)算資源是有限的，受到限制實(shí)際安全現(xiàn)代方法38實(shí)際安全實(shí)際安全性又稱(chēng)為計(jì)算上的安全性。計(jì)算安全性：涉及攻破密碼體制所做的計(jì)算上的努力?？勺C明安全性：安全性歸結(jié)為某個(gè)經(jīng)過(guò)深入研究的數(shù)學(xué)難題。實(shí)際安全實(shí)際安全性又稱(chēng)為計(jì)算上的安全性。39實(shí)際安全性主要考慮：計(jì)算能力（基本運(yùn)算次數(shù)、存儲(chǔ)量）破譯算法的有效性算法：求解某一問(wèn)題的、一步一步地執(zhí)行的計(jì)算過(guò)程。實(shí)際安全性主要考慮：40計(jì)算復(fù)雜性問(wèn)題的計(jì)算復(fù)雜性可解問(wèn)題的最有效算法的計(jì)算復(fù)雜性算法的計(jì)算復(fù)雜性運(yùn)行它所需的計(jì)算能力。常常用兩個(gè)變量來(lái)度量：時(shí)間復(fù)雜性T和空間復(fù)雜性S（或所需存儲(chǔ)空間）計(jì)算復(fù)雜性問(wèn)題的計(jì)算復(fù)雜性41

“計(jì)算上安全”：指利用已有的最好的方法破譯該系統(tǒng)所需要的努力超過(guò)了敵手的破譯能力（時(shí)間、空間、資金等）或破譯該系統(tǒng)的難度等價(jià)于解數(shù)學(xué)上的某個(gè)已知難題（計(jì)算復(fù)雜性）?！坝?jì)算上安全”：指利用已有的最好的方法破譯該系統(tǒng)所需要的努42計(jì)算復(fù)雜性計(jì)算復(fù)雜性理論是密碼系統(tǒng)安全性定義的理論基礎(chǔ)。算法：函數(shù)1（常數(shù)）、對(duì)數(shù)、n（線(xiàn)性函數(shù)）、二次函數(shù)、三次函數(shù)、多項(xiàng)式函數(shù)、亞指數(shù)、指數(shù)函數(shù)問(wèn)題：P、NP、NPC計(jì)算復(fù)雜性計(jì)算復(fù)雜性理論是密碼系統(tǒng)安全性定義的理論基礎(chǔ)。43時(shí)間復(fù)雜性一個(gè)算法的計(jì)算復(fù)雜性或有效性可以用執(zhí)行該算法所需的運(yùn)行時(shí)間和內(nèi)存空間來(lái)度量。時(shí)間復(fù)雜性有兩種定義方法：

1。用圖靈機(jī)表示一個(gè)算法

2。該算法的比特運(yùn)算次數(shù)時(shí)間復(fù)雜性一個(gè)算法的計(jì)算復(fù)雜性或有效性可以用執(zhí)行該算法所需44

計(jì)算上保密：理論上可破，實(shí)際上難破，而不是不可破。計(jì)算上保密：45密碼體制安全性準(zhǔn)則計(jì)算安全性：可證明安全性：無(wú)條件安全性：密碼體制安全性準(zhǔn)則計(jì)算安全性：465.密碼編碼系統(tǒng)分類(lèi)：密碼編碼系統(tǒng)分類(lèi)：明文轉(zhuǎn)換為密文操作的類(lèi)型?替代

?置換密鑰數(shù)量?單鑰

?雙鑰明文處理方式?分組密碼

?序列密碼5.密碼編碼系統(tǒng)分類(lèi)：密碼編碼系統(tǒng)分類(lèi)：47Cryptographycancharacterizeby:typeofencryptionoperationsusedsubstitution/transposition/productnumberofkeysusedsingle-keyorprivate/two-keyorpublicwayinwhichplaintextisprocessedblock/streamCryptographycancharacterizeb48“Purple”紫碼1941.12.7日本偷襲珍珠港1942.1美成功破譯JN-251942.4美轟炸日東京、神戶(hù)等1942.5.7-8巴布亞新幾內(nèi)亞的莫爾茲比港PortMoresby（印尼）1942中途島之戰(zhàn)4.18“山本五十六”飛機(jī)降落時(shí)被擊落“Purple”紫碼1941.12.7日本偷襲珍珠港49二、古典密碼技術(shù)1.代替密碼：?jiǎn)伪泶婷艽a、Playfair、Hill、Vigenere、OTP2.置換密碼：3.乘積密碼：4.轉(zhuǎn)輪機(jī)5.隱寫(xiě)術(shù)二、古典密碼技術(shù)1.代替密碼：?jiǎn)伪泶婷艽a、501.SubstitutionCipherswherelettersofplaintextarereplacedbyotherlettersorbynumbersorsymbolsorifplaintextisviewedasasequenceofbits,thensubstitutioninvolvesreplacingplaintextbitpatternswithciphertextbitpatterns1.SubstitutionCipherswherel51代替密碼單表代替密碼多名碼代替密碼多字母代替密碼多表代替密碼代替密碼單表代替密碼521）單表代替密碼單表代替密碼例如“凱撒”密碼古羅馬軍隊(duì)用由JuliusCaesar發(fā)明明文字母ABCDEFGHIKLMNOPQRSTVXYZ密文字母DEFGHIKLMNOPQRSTVXYZABC注：拉丁文不用J，U，W1）單表代替密碼單表代替密碼53CaesarCipherearliestknownsubstitutioncipherbyJuliusCaesarfirstattesteduseinmilitaryaffairsreplaceseachletterby3rdletteronexample:meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWBCaesarCipherearliestknownsu54CaesarCiphercandefinetransformationas:abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCmathematicallygiveeachletteranumberabcdefghijklm0123456789101112nopqrstuvwxyZ13141516171819202122232425thenhaveCaesarcipheras:C=E(p)=(p+k)mod(26)p=D(C)=(C–k)mod(26)CaesarCiphercandefinetransf55CryptanalysisofCaesarCipheronlyhave26possibleciphersAmapstoA,B,..Zcouldsimplytryeachinturnabruteforcesearch

givenciphertext,justtryallshiftsoflettersdoneedtorecognizewhenhaveplaintexteg.breakciphertext"GCUAVQDTGCM"CryptanalysisofCaesarCipher56Monoalphabetic單表代替

Cipherratherthanjustshiftingthealphabetcouldshuffle(jumble)thelettersarbitrarilyeachplaintextlettermapstoadifferentrandomciphertextletterhencekeyis26letterslongPlain:abcdefghijklmnopqrstuvwxyzCipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYAMonoalphabetic單表代替Cipherrathe57MonoalphabeticCipherSecuritynowhaveatotalof26!=4x10^26keyswithsomanykeys,mightthinkissecurebutwouldbe!!!WRONG!!!

problemislanguagecharacteristics單表代替密碼不能掩蓋明文語(yǔ)言的所有統(tǒng)計(jì)特性。MonoalphabeticCipherSecurity58LanguageRedundancyandCryptanalysishumanlanguagesareredundant

eg"thlrdsmshphrdshllntwnt"lettersarenotequallycommonlyusedinEnglisheisbyfarthemostcommonletterthenT,R,N,I,O,A,Sotherlettersarefairlyrarecf.Z,J,K,Q,Xhavetablesofsingle,double&tripleletterfrequenciesLanguageRedundancyandCrypta59EnglishLetterFrequenciesEnglishLetterFrequencies60UseinCryptanalysiskeyconcept-monoalphabeticsubstitutionciphersdonotchangerelativeletterfrequenciesdiscoveredbyArabianscientistsin9thcenturycalculateletterfrequenciesforciphertextcomparecounts/plotsagainstknownvaluesifCaesarcipherlookforcommonpeaks/troughspeaksat:A-E-Itriple,NOpair,RSTtripletroughsat:JK,X-Zformonoalphabeticmustidentifyeachlettertablesofcommondouble/triplelettershelpUseinCryptanalysiskeyconcep61安全性取決于密文在多大程度上保留了明文語(yǔ)言的語(yǔ)法模式和結(jié)構(gòu)。理想的字母頻率分布情況：如果頻率分配的信息完全給加密過(guò)程給隱藏了，那么密文的頻率曲線(xiàn)應(yīng)該是一條水平的線(xiàn)。減少密文中殘留明文語(yǔ)言結(jié)構(gòu)的基本方法：1）對(duì)明文中的多個(gè)字母一起加密

2）采用多表代替密碼安全性取決于密文在多大程度上保留了明文語(yǔ)言的語(yǔ)法模式和結(jié)構(gòu)。62ExampleCryptanalysisgivenciphertext:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQcountrelativeletterfrequencies(seetext)guessP&ZareeandtguessZWisthandhenceZWPistheproceedingwithtrialanderrorfinallyget:itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscowExampleCryptanalysisgivencip63

單表代替密碼移位代替密碼E(i)=i+k=jmodq乘數(shù)密碼E(i)=ik=jmodqk與q互素線(xiàn)性同余密碼(仿射密碼AffineCipher)E(i)=ik1+k0=jmodqk1與q互素多表代替密碼

單表代替密碼642）PlayfairCiphernoteventhelargenumberofkeysinamonoalphabeticcipherprovidessecurityoneapproachtoimprovingsecuritywastoencryptmultiplelettersthePlayfairCipherisanexampleinventedbyCharlesWheatstonein1854,butnamedafterhisfriendBaronPlayfair2）PlayfairCiphernoteventhe65

應(yīng)用：第一次世界大戰(zhàn)中英軍就使用它作為陸軍的標(biāo)準(zhǔn)加密體制，在第二次世界大戰(zhàn)中，美軍極其他一些盟軍用它來(lái)進(jìn)行加密。應(yīng)用：66PlayfairKeyMatrixa5X5matrixoflettersbasedonakeywordfillinlettersofkeyword(sansduplicates)fillrestofmatrixwithotherletterseg.usingthekeywordMONARCHYMONARCHYBDEFGIKLPQSTUVWXZPlayfairKeyMatrixa5X5matri67EncryptingandDecryptingplaintextencryptedtwolettersatatime:ifapairisarepeatedletter,insertafillerlike'X', eg."balloon"encryptsas"balxloon"ifbothlettersfallinthesamerow,replaceeachwithlettertoright(wrappingbacktostartfromend), eg.“ar"encryptsas"RM"ifbothlettersfallinthesamecolumn,replaceeachwiththeletterbelowit(againwrappingtotopfrombottom),eg.“mu"encryptsto"CM"otherwiseeachletterisreplacedbytheoneinitsrowinthecolumnoftheotherletterofthepair,eg.“hs"encryptsto"BP",and“ea"to"IM"or"JM"(asdesired)EncryptingandDecryptingplain68SecurityofthePlayfairCiphersecuritymuchimprovedovermonoalphabeticsincehave26x26=676digramswouldneeda676entryfrequencytabletoanalyse(verses26foramonoalphabetic)andcorrespondinglymoreciphertextwaswidelyusedformanyyears(eg.US&BritishmilitaryinWW1)itcanbebroken,givenafewhundredletterssincestillhasmuchofplaintextstructureSecurityofthePlayfairCiphe69PolyalphabeticCiphersanotherapproachtoimprovingsecurityistousemultiplecipheralphabetscalledpolyalphabeticsubstitutionciphers多表代替密碼makescryptanalysisharderwithmorealphabetstoguessandflatterfrequencydistributionuseakeytoselectwhichalphabetisusedforeachletterofthemessageuseeachalphabetinturnrepeatfromstartafterendofkeyisreachedPolyalphabeticCiphersanother703.Hill代數(shù)法利用線(xiàn)性變換的方法，但在Z26上進(jìn)行。代數(shù)法（Hill密碼）ABCDEFGHIJKLM4825292016517302213NOPQRSTUVWXYZ24621152319127111811410A-Z取值0-25。3.Hill代數(shù)法利用線(xiàn)性變換的方法，但在Z26上進(jìn)行。71

加密：y1=8x1+6x2+9x3+5x4y2=6x1+9x2+5x3+10x4y3=5x1+8x2+4x3+9x4y4=10x1+6x2+11x3+4x4e.g.HELPx1=H=5x2=E=9x3=L=22x4=P=21加密后y1=397mod26=7y2=15y3=10y4=14密文為UQZY加密：y1=8x1+6x2+9x3+5x472

解密：x1=23y1+20y2+5y3+1y4x2=2y1+11y2+18y3+1y4x3=2y1+20y2+6y3+25y4x4=25y1+2y2+22y3+25y4解密：x1=23y1+20y2+5y3+1y473

Hill的優(yōu)點(diǎn)：完全隱蔽了單字母頻率特性。Hill的矩陣越大，所隱蔽的頻率信息越多。Hill密碼既不是一種純換位密碼，也不是一種純代替密碼。大多數(shù)“現(xiàn)代”密碼算法都是將換位密碼和代替密碼算法有機(jī)的結(jié)合。Hill密碼算法具有線(xiàn)性的缺點(diǎn)。

Hill的優(yōu)點(diǎn)：完全隱蔽了單字母頻率特性。Hill的矩陣越74應(yīng)用Hill密碼由數(shù)學(xué)家LesterSHill1929年研制。在第二次世界大戰(zhàn)中，該密碼被用來(lái)對(duì)無(wú)線(xiàn)電呼叫信號(hào)進(jìn)行加密，加密和解密均通過(guò)機(jī)械設(shè)備（而非電子設(shè)備）來(lái)完成。較易被已知明文破解。應(yīng)用Hill密碼由數(shù)學(xué)家LesterSHill1929754）VigenèreCiphersimplestpolyalphabeticsubstitutioncipheristheVigenèreCipher最簡(jiǎn)單、最著名effectivelymultiplecaesarcipherskeyismultipleletterslongK=k1k2...Kdithletterspecifiesithalphabettouseuseeachalphabetinturnrepeatfromstartafterdlettersinmessagedecryptionsimplyworksinreverse4）VigenèreCiphersimplestpoly76

代換規(guī)則集由26個(gè)類(lèi)似Caesar密碼的代換表組成。依賴(lài)于密鑰詞的長(zhǎng)度代換規(guī)則集由26個(gè)類(lèi)似Caesar密碼的代換表組成。77Examplewritetheplaintextoutwritethekeywordrepeatedaboveituseeachkeyletterasacaesarcipherkeyencryptthecorrespondingplaintextletteregusingkeyworddeceptivekey:deceptivedeceptivedeceptiveplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJExamplewritetheplaintextout78Aidssimpleaidscanassistwithen/decryptionaSaint-CyrSlideisasimplemanualaidaslidewithrepeatedalphabetlineupplaintext'A'withkeyletter,eg'C'thenreadoffanymappingforkeylettercanbendroundintoacipherdisk

orexpandintoaVigenèreTableau(seetextTable2.3)Aidssimpleaidscanassistwit79SecurityofVigenèreCiphershavemultipleciphertextlettersforeachplaintextletterhenceletterfrequenciesareobscuredbutnottotallyloststartwithletterfrequenciesseeiflookmonoalphabeticornotifnot,thenneedtodeterminenumberofalphabets,sincethencanattacheachSecurityofVigenèreCiphersha80KasiskiMethodmethoddevelopedbyBabbage/Kasiskirepetitionsinciphertextgivecluestoperiodsofindsameplaintextanexactperiodapartwhichresultsinthesameciphertextofcourse,couldalsoberandomflukeegrepeated“VTW”inpreviousexamplesuggestssizeof3or9thenattackeachmonoalphabeticcipherindividuallyusingsametechniquesasbeforeKasiskiMethodmethoddeveloped81AutokeyCipherideallywantakeyaslongasthemessageVigenèreproposedtheautokeycipherwithkeywordisprefixedtomessageaskeyknowingkeywordcanrecoverthefirstfewlettersusetheseinturnontherestofthemessagebutstillhavefrequencycharacteristicstoattackeg.givenkeydeceptivekey:deceptivewearediscoveredsavplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLAAutokeyCipherideallywantak825）One-TimePad(一次一密)ifatrulyrandomkeyaslongasthemessageisused,thecipherwillbesecurecalledaOne-Timepadisunbreakablesinceciphertextbearsnostatisticalrelationshiptotheplaintextsinceforanyplaintext&anyciphertextthereexistsakeymappingonetoothercanonlyusethekeyoncethoughhaveproblemofsafedistributionofkey5）One-TimePad(一次一密)ifatruly83一次一密陸軍情報(bào)官M(fèi)auborgne建議使用與消息一樣長(zhǎng)且無(wú)重復(fù)的隨機(jī)密鑰來(lái)加密消息一次一密的安全性完全取決于密鑰的隨機(jī)性存在兩個(gè)難點(diǎn)：

?產(chǎn)生大規(guī)模隨機(jī)密鑰

?密鑰的分配和保護(hù)主要應(yīng)用于安全性要求很高的低帶寬信道。一次一密陸軍情報(bào)官M(fèi)auborgne建議使用與消息一樣長(zhǎng)且842.TranspositionCiphers

置換密碼nowconsiderclassicaltranspositionorpermutationciphersthesehidethemessagebyrearrangingtheletterorderwithoutalteringtheactuallettersusedcanrecognisethesesincehavethesamefrequencydistributionastheoriginaltext2.TranspositionCiphers置換密碼85

移位密碼古希臘的“天書(shū)”器械，公元前400年希臘人采用。斯巴達(dá)克人塞塔發(fā)明的。加密方法密鑰移位密碼86RowTranspositionCiphersamorecomplexscheme柵欄技術(shù)writelettersofmessageoutinrowsoveraspecifiednumberofcolumnsthenreorderthecolumnsaccordingtosomekeybeforereadingofftherowsKey:4312567Plaintext:attackpostponeduntiltwoamxyzCiphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZRowTranspositionCiphersamor87

代替密碼Substitution：明文字母被不同的密文字母所代替。置換密碼Transposition：Permutation保持明文的所有字母不變，只是利用置換打亂了明文字母的位置和次序。代替密碼Substitution：明文字母被不同的密文字母883.ProductCiphersciphersusingsubstitutionsortranspositionsarenotsecurebecauseoflanguagecharacteristicshenceconsiderusingseveralciphersinsuccessiontomakeharder,but:twosubstitutionsmakeamorecomplexsubstitutiontwotranspositionsmakemorecomplextranspositionbutasubstitutionfollowedbyatranspositionmakesanewmuchhardercipherthisisbridgefromclassicaltomodernciphers3.ProductCiphersciphersusing89

乘積密碼：以德軍第一次世界大戰(zhàn)中所使用的密碼為例：ADFGVX乘積密碼乘積密碼：90

ADFGVX明文：PRODUCTAKZWR1FCIPHERSD9B6CL5中間報(bào)文：FQ7JPGXFGAGVDVFXADGXV

GEVY3ANDGXFFGVGGAAGXGV8ODH02XU4ISTMADFGVX明文：P91

DEUTSCH密鑰2376514排列順序FGAGVDV密文：FXADGXVDXGXFFDGGXGGDGXFFGVVVVGVGFGGDFAGGAAGXGAAXADEUTSCH密鑰92

4.RotorMachinesbeforemodernciphers,rotormachinesweremostcommonproductcipherwerewidelyusedinWW2GermanEnigma,AlliedHagelin,JapanesePurpleimplementedaverycomplex,varyingsubstitutioncipherusedaseriesofcylinders,eachgivingonesubstitution,whichrotatedandchangedaftereachletterwasencryptedwith3cylindershave263=17576alphabets

4.RotorMachines93轉(zhuǎn)輪機(jī)轉(zhuǎn)輪機(jī)密碼系統(tǒng)（多層加密原理）多筒系統(tǒng)中，操作員每按一次輸入鍵，最后一個(gè)轉(zhuǎn)輪就旋轉(zhuǎn)一個(gè)引腳的位置。轉(zhuǎn)輪機(jī)由一系列獨(dú)立轉(zhuǎn)動(dòng)的圓柱體組成，每個(gè)圓柱體具有26個(gè)輸入引腳和26個(gè)輸出引腳，單個(gè)圓柱體定義了一個(gè)單字母替代。轉(zhuǎn)輪機(jī)轉(zhuǎn)輪機(jī)密碼系統(tǒng)（多層加密原理）94小結(jié)1.天書(shū)6.One-TimePad2.caesar7.置換密碼3.仿射8.乘積密碼4.Playfair9.Hill密碼5.Vigenère10.轉(zhuǎn)輪機(jī)小結(jié)1.天書(shū)6.One-Time95總結(jié)封閉性唯一性可逆性總結(jié)封閉性965.信息隱藏InformationHiding最大的優(yōu)點(diǎn)也就是它最大的缺點(diǎn)。信息隱藏又稱(chēng)信息偽裝。信息隱藏是一門(mén)古老的技術(shù)。信息隱藏主要分為：隱寫(xiě)術(shù)數(shù)字水印5.信息隱藏InformationHiding最大的優(yōu)點(diǎn)97

信息隱藏的特點(diǎn)：1.不破壞載體的正常使用。2.載體具有某種冗余性3.隱形性：4.穩(wěn)健性：信號(hào)處理變換5.通用性：圖象、視頻、音頻6.確定性：唯一的鑒別確定信息隱藏的特點(diǎn)：98Steganography（隱寫(xiě)術(shù)）analternativetoencryptionhidesexistenceofmessageusingonlyasubsetofletters/wordsinalongermessagemarkedinsomewayusinginvisibleinkhidinginLSBingraphicimageorsoundfilehasdrawbackshighoverheadtohiderelativelyfewinfobitsSteganography（隱寫(xiě)術(shù)）analternati99

藏頭詩(shī)不可見(jiàn)墨水優(yōu)點(diǎn)：可以應(yīng)用于通信雙方寧愿他們的秘密信息被發(fā)現(xiàn)而不愿其中的重要內(nèi)容丟失的情況。缺點(diǎn)：它需要大量額外的開(kāi)銷(xiāo)來(lái)隱藏相對(duì)較少的信息。藏頭詩(shī)100數(shù)字水印數(shù)字水印的三要素：水銀本身的結(jié)構(gòu)加載水印的地方或加載水印的策略水印的檢測(cè)數(shù)字水印數(shù)字水印的三要素：101信息隱藏的方法主要分為兩類(lèi)：空間域算法：最低有效位LSB方法變換域算法：離散傅立葉變換DFT方法離散余弦變換DCT方法離散小波變換DWT方法信息隱藏的方法主要分為兩類(lèi)：102

數(shù)字水印的應(yīng)用：版權(quán)保護(hù)隱藏標(biāo)識(shí)和標(biāo)簽認(rèn)證數(shù)據(jù)隱藏技術(shù)或隱寫(xiě)術(shù)數(shù)字水印的應(yīng)用：103

為將而不通天文，不識(shí)地理，不知奇門(mén)，不曉陰陽(yáng)，不看陣圖，不明兵勢(shì)，（不懂信息安全，）是庸才也。

——諸葛亮為將而不通天文，不識(shí)地理，不知奇門(mén)，不曉陰陽(yáng)104三、密碼體制單鑰體制（密碼保險(xiǎn)柜）雙鑰體制（郵箱）三、密碼體制單鑰體制（密碼保險(xiǎn)柜）105SymmetricEncryptionorconventional/private-key/single-keysenderandrecipientshareacommonkeyallclassicalencryptionalgorithmsareprivate-keywasonlytypepriortoinventionofpublic-keyin1970’sSymmetricEncryptionorconvent1061.單鑰體制加密密鑰和解秘密鑰相同。系統(tǒng)的安全性取決于密鑰的安全性密鑰管理是該體制設(shè)計(jì)和實(shí)現(xiàn)的主要課題。對(duì)明文加密有兩種方式：序列密碼（流密碼）：按字符逐位加密。分組密碼：將明文消息分組，逐組加密。1.單鑰體制加密密鑰和解秘密鑰相同。107序列密碼序列密碼示意圖序列密碼序列密碼示意圖108StreamCiphersprocessthemessagebitbybit(asastream)typicallyhavea(pseudo)randomstreamkey

combined(XOR)withplaintextbitbybitrandomnessofstreamkeycompletelydestroysanystatisticallypropertiesinthemessageCi=MiXORStreamKeyi

whatcouldbesimpler!!!!butmustneverreusestreamkeyotherwisecanremoveeffectandrecovermessagesStreamCiphersprocessthemess109StreamCipherPropertiessomedesignconsiderationsare:longperiodwithnorepetitionsstatisticallyrandomdependsonlargeenoughkeylargelinearcomplexitycorrelationimmunityconfusiondiffusionuseofhighlynon-linearbooleanfunctionsStreamCipherPropertiessomed110

序列（流）密碼一直是作為軍事和外交場(chǎng)合使用的主要密碼技術(shù)之一。序列（流）密碼一直是作為軍事和外交場(chǎng)合使用的主要密碼技術(shù)之111序列密碼體制的保密性完全取決于密鑰的隨機(jī)性。密碼強(qiáng)度完全依賴(lài)于密鑰序列產(chǎn)生器所形成序列的隨機(jī)性和不可預(yù)測(cè)性。核心問(wèn)題：密鑰序列生成器的設(shè)計(jì)。分類(lèi)：

1）同步流密碼

2）自同步流密碼序列密碼體制的保密性完全取決于密鑰的隨機(jī)性。112

同步流密碼SSC：加密變換是無(wú)記憶的，它是時(shí)變的。密鑰流獨(dú)立于明文。優(yōu)點(diǎn)：對(duì)主動(dòng)攻擊異常敏感，利于檢測(cè)無(wú)錯(cuò)誤傳播。缺點(diǎn)：一旦失步，同步后才恢復(fù)工作。重要技術(shù)課題：失步后如何重新同步。同步流密碼SSC：113

自同步序列密碼SSSC：密文不僅與當(dāng)前明文有關(guān)，而且與以前的輸入有關(guān)。優(yōu)點(diǎn)：自恢復(fù)同步性強(qiáng)化其抗統(tǒng)計(jì)分析的能力。缺點(diǎn)：不敏感、有限的錯(cuò)誤傳播自同步序列密碼SSSC：114

密鑰序列生成器輸出序列應(yīng)滿(mǎn)足：1）周期要足夠大，>10^502）偽隨機(jī)性好3）易于高速生成4）不可預(yù)測(cè)性一般要進(jìn)行統(tǒng)計(jì)檢驗(yàn)。實(shí)現(xiàn)：硬件、軟件or二者結(jié)合。密鑰序列生成器輸出序列應(yīng)滿(mǎn)足：115

例子：A5：歐洲數(shù)字蜂窩移動(dòng)電話(huà)系統(tǒng)GSM用于從用戶(hù)手機(jī)到基站的連接加密。RC-4：SSL/TLSWEPIEEE802.11無(wú)線(xiàn)LAN例子：116分組密碼將明文劃分為固定的數(shù)據(jù)組，以組為單位。優(yōu)點(diǎn)：不需要同步例：DESIDEAAESRSA分組密碼將明文劃分為固定的數(shù)據(jù)組，以組為單位。117

通常：m=n若n>m有數(shù)據(jù)擴(kuò)展n<m有數(shù)據(jù)壓縮算法應(yīng)滿(mǎn)足：1）分組長(zhǎng)度、密鑰量要足夠大2）由密鑰確定置換的方法要足夠復(fù)雜3）加解密運(yùn)算簡(jiǎn)單，易于軟硬件高速實(shí)現(xiàn)。此外，一般無(wú)數(shù)據(jù)擴(kuò)展。通常：m=n若n>m有數(shù)據(jù)擴(kuò)展1182.雙鑰密碼體制1975年Stanford大學(xué)的W.Diffie&M.Hellman在《密碼學(xué)的新方向》一文提出了公開(kāi)密鑰編碼學(xué)，他們懂得一種間接貢獻(xiàn)是引入了一個(gè)看來(lái)不易解決的問(wèn)題。他們提出：使用不同的加密密鑰和解密密鑰，由已知加密密鑰推導(dǎo)出解密密鑰在計(jì)算上是不可行的密碼體制。2.雙鑰密碼體制1975年Stanford大學(xué)的W.Di119

公鑰加密算法是基于數(shù)學(xué)函數(shù)（數(shù)論）的，而不是基于簡(jiǎn)單的比特位操作。公鑰加密是幾千年來(lái)在加密領(lǐng)域中第一次出現(xiàn)的真正的革命性進(jìn)展。對(duì)保密、密鑰分配、鑒別等諸多領(lǐng)域有深遠(yuǎn)的影響。公鑰加密算法是基于數(shù)學(xué)函數(shù)（數(shù)論）的，而不是基于簡(jiǎn)單的比特120Public-KeyCryptographyprobablymostsignificantadvanceinthe3000yearhistoryofcryptographyusestwokeys–apublic&aprivatekeyasymmetricsincepartiesarenotequalusescleverapplicationofnumbertheoreticconceptstofunctioncomplementsratherthanreplacesprivatekeycryptoPublic-KeyCryptographyprobabl121

122

公開(kāi)密鑰密碼體制產(chǎn)生原因：

1）常規(guī)密鑰密碼體制的密鑰分配問(wèn)題

2）數(shù)字簽名的需求使用情況

1）保密通信

2）數(shù)字簽名

3）密鑰交換公開(kāi)密鑰密碼體制產(chǎn)生原因：123

公開(kāi)密鑰密碼體制：1）基于NP完全理論的背包體制。2）基于編碼理論的McEliece體制3）基于數(shù)論中大數(shù)分解問(wèn)題的RSA體制離散對(duì)數(shù)D-H、ElGamal、Rabin、ECC等。公開(kāi)密鑰密碼體制：124四、密碼分析“知彼知己者，百戰(zhàn)不殆”。目的：通過(guò)分析改變關(guān)于每個(gè)可能明文的可能性，最后，一個(gè)明文當(dāng)然（至少非常可能）會(huì)從所有可能的明文集合中暴露出來(lái)。不會(huì)攻擊者設(shè)計(jì)不出好密碼密碼分析：試圖從截獲的密文中推斷出密鑰或明文的過(guò)程。四、密碼分析“知彼知己者，百戰(zhàn)不殆”。125

分析法：1.確定性分析1）差分攻擊2）線(xiàn)性攻擊2.統(tǒng)計(jì)分析窮舉分析：（野蠻、強(qiáng)行攻擊）非技術(shù)方法:分析法：126

密碼分析學(xué)：攻擊依賴(lài)于算法的性質(zhì)和明文的一般特征或某些明文-密文對(duì)。它企圖利用算法的特征來(lái)推導(dǎo)出特別的明文或使用的密鑰來(lái)。密碼分析學(xué)：127確定性分析法確定性分析法：利用一個(gè)或幾個(gè)已知量用數(shù)學(xué)關(guān)系式表示出所求未知量。關(guān)鍵：尋求已知量和未知量之間的關(guān)系。1）差分分析：2）線(xiàn)性分析：y=kx確定性分析法確定性分析法：利用一個(gè)或幾個(gè)已知量用數(shù)學(xué)關(guān)系式表128

對(duì)稱(chēng)體制:明文中結(jié)構(gòu)的痕跡或模式可能經(jīng)加密后在密文中仍然是可辨認(rèn)的。公鑰體制:密鑰對(duì)的數(shù)學(xué)性質(zhì)使得從一個(gè)密鑰推出另一個(gè)密鑰成為可能.對(duì)稱(chēng)體制:明文中結(jié)構(gòu)的痕跡或模式可能經(jīng)加密后在密文中仍129統(tǒng)計(jì)分析法利用明文的已知統(tǒng)計(jì)規(guī)律進(jìn)行破譯的方法。對(duì)密文統(tǒng)計(jì)分析總結(jié)規(guī)律，并與明文規(guī)律進(jìn)行對(duì)照比較。密碼分析成功的根本原因是明文中的冗余度。統(tǒng)計(jì)分析法利用明文的已知統(tǒng)計(jì)規(guī)律進(jìn)行破譯的方法。130統(tǒng)計(jì)分析法一般使用“分析-假設(shè)-推斷-證實(shí)（否定）”的四步作業(yè)法。Shannon提出挫敗統(tǒng)計(jì)分析的兩種方法：1）加密之前用Huffman編碼去除冗余度。2）用混亂和擴(kuò)散（乘積）來(lái)擴(kuò)散、混淆多余度。統(tǒng)計(jì)分析法一般使用“分析-假設(shè)-推斷-證實(shí)（否定）”的四步作131分析法基本數(shù)學(xué)工具：統(tǒng)計(jì)分析