密碼學基礎知識課件

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

作用：

機密性鑒別完整性抗抵賴作用：3

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

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

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

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

一、保密與保密系統(tǒng)保密學：研究信息系統(tǒng)安全保密的科學。91.保密系統(tǒng)模型圖一個密碼體制由五元組（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.密碼設計準則保密系統(tǒng)抗擊密碼分析，應滿足：1）系統(tǒng)即使達不到理論上是不可破的，也應當為實際上是不可破的。2）Kerckhoff原則。系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。3）加密和解密算法適用于所有密鑰空間中的元素。4）系統(tǒng)便于實現(xiàn)和使用方便。

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

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

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

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

基于信息論的方法：用密文中是否蘊含明文的信息作為標準。

基于計算復雜性理論的方法：是考慮信息是否能有效地被提取出來。

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

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

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

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

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

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

“計算上安全”：指利用已有的最好的方法破譯該系統(tǒng)所需要的努力超過了敵手的破譯能力（時間、空間、資金等）或破譯該系統(tǒng)的難度等價于解數(shù)學上的某個已知難題（計算復雜性）?！坝嬎闵习踩保褐咐靡延械淖詈玫姆椒ㄆ谱g該系統(tǒng)所需要的努42計算復雜性計算復雜性理論是密碼系統(tǒng)安全性定義的理論基礎。算法：函數(shù)1（常數(shù)）、對數(shù)、n（線性函數(shù)）、二次函數(shù)、三次函數(shù)、多項式函數(shù)、亞指數(shù)、指數(shù)函數(shù)問題：P、NP、NPC計算復雜性計算復雜性理論是密碼系統(tǒng)安全性定義的理論基礎。43時間復雜性一個算法的計算復雜性或有效性可以用執(zhí)行該算法所需的運行時間和內(nèi)存空間來度量。時間復雜性有兩種定義方法：

1。用圖靈機表示一個算法

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

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

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

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

?序列密碼5.密碼編碼系統(tǒng)分類：密碼編碼系統(tǒng)分類：47Cryptographycancharacterizeby:typeofencryptionoperationsusedsubstitution/transposition/productnumberofkeysusedsingle-keyorprivate/two-keyorpublicwayinwhichplaintextisprocessedblock/streamCryptographycancharacterizeb48“Purple”紫碼1941.12.7日本偷襲珍珠港1942.1美成功破譯JN-251942.4美轟炸日東京、神戶等1942.5.7-8巴布亞新幾內(nèi)亞的莫爾茲比港PortMoresby（印尼）1942中途島之戰(zhàn)4.18“山本五十六”飛機降落時被擊落“Purple”紫碼1941.12.7日本偷襲珍珠港49二、古典密碼技術1.代替密碼：單表代替密碼、Playfair、Hill、Vigenere、OTP2.置換密碼：3.乘積密碼：4.轉(zhuǎn)輪機5.隱寫術二、古典密碼技術1.代替密碼：單表代替密碼、501.SubstitutionCipherswherelettersofplaintextarereplacedbyotherlettersorbynumbersorsymbolsorifplaintextisviewedasasequenceofbits,thensubstitutioninvolvesreplacingplaintextbitpatternswithciphertextbitpatterns1.SubstitutionCipherswherel51代替密碼單表代替密碼多名碼代替密碼多字母代替密碼多表代替密碼代替密碼單表代替密碼521）單表代替密碼單表代替密碼例如“凱撒”密碼古羅馬軍隊用由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單表代替密碼不能掩蓋明文語言的所有統(tǒng)計特性。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安全性取決于密文在多大程度上保留了明文語言的語法模式和結(jié)構(gòu)。理想的字母頻率分布情況：如果頻率分配的信息完全給加密過程給隱藏了，那么密文的頻率曲線應該是一條水平的線。減少密文中殘留明文語言結(jié)構(gòu)的基本方法：1）對明文中的多個字母一起加密

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

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

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

應用：第一次世界大戰(zhàn)中英軍就使用它作為陸軍的標準加密體制，在第二次世界大戰(zhàn)中，美軍極其他一些盟軍用它來進行加密。應用：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ù)法利用線性變換的方法，但在Z26上進行。代數(shù)法（Hill密碼）ABCDEFGHIJKLM4825292016517302213NOPQRSTUVWXYZ24621152319127111811410A-Z取值0-25。3.Hill代數(shù)法利用線性變換的方法，但在Z26上進行。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)點：完全隱蔽了單字母頻率特性。Hill的矩陣越大，所隱蔽的頻率信息越多。Hill密碼既不是一種純換位密碼，也不是一種純代替密碼。大多數(shù)“現(xiàn)代”密碼算法都是將換位密碼和代替密碼算法有機的結(jié)合。Hill密碼算法具有線性的缺點。

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

代換規(guī)則集由26個類似Caesar密碼的代換表組成。依賴于密鑰詞的長度代換規(guī)則集由26個類似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一次一密陸軍情報官Mauborgne建議使用與消息一樣長且無重復的隨機密鑰來加密消息一次一密的安全性完全取決于密鑰的隨機性存在兩個難點：

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

?密鑰的分配和保護主要應用于安全性要求很高的低帶寬信道。一次一密陸軍情報官Mauborgne建議使用與消息一樣長且842.TranspositionCiphers

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

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

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

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

ADFGVX明文：PRODUCTAKZWR1FCIPHERSD9B6CL5中間報文：FQ7JPGXFGAGVDVFXADGXV

GEVY3ANDGXFFGVGGAAGXGV8ODH02XU4ISTMADFGVX明文：P91

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

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

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

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

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

數(shù)字水印的應用：版權保護隱藏標識和標簽認證數(shù)據(jù)隱藏技術或隱寫術數(shù)字水印的應用：103

為將而不通天文，不識地理，不知奇門，不曉陰陽，不看陣圖，不明兵勢，（不懂信息安全，）是庸才也。

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

combined(XOR)withplaintextbitbybitrandomnessofstreamkeycompletelydestroysanystatisticallypropertiesinthemessageCi=MiXORStreamKeyi

whatcouldbesimpler!!!!butmustneverreusestreamkeyotherwisecanremoveeffectandrecovermessagesStreamCiphersprocessthemess109StreamCipherPropertiessomedesignconsiderationsare:longperiodwithnorepetitionsstatisticallyrandomdependsonlargeenoughkeylargelinearcomplexitycorrelationimmunityconfusiondiffusionuseofhighlynon-linearbooleanfunctionsStreamCipherPropertiessomed110

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

1）同步流密碼

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

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

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

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

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

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

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

122

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

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

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

1）保密通信

2）數(shù)字簽名

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

公開密鑰密碼體制：1）基于NP完全理論的背包體制。2）基于編碼理論的McEliece體制3）基于數(shù)論中大數(shù)分解問題的RSA體制離散對數(shù)D-H、ElGamal、Rabin、ECC等。公開密鑰密碼體制：124四、密碼分析“知彼知己者，百戰(zhàn)不殆”。目的：通過分析改變關于每個可能明文的可能性，最后，一個明文當然（至少非?？赡埽乃锌赡艿拿魑募现斜┞冻鰜怼２粫粽咴O計不出好密碼密碼分析：試圖從截獲的密文中推斷出密鑰或明文的過程。四、密碼分析“知彼知己者，百戰(zhàn)不殆”。125

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

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

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