《信息安全導(dǎo)論（以問題為導(dǎo)向）》全套教學(xué)課件

信息安全導(dǎo)論（以問題為導(dǎo)向）01古典密碼-第一部分02古典密碼-第二部分03現(xiàn)代分組密碼04公開密鑰密碼05報文鑒別與哈希函數(shù)06公鑰基礎(chǔ)設(shè)施PKI07身份認(rèn)證08Web與電子商務(wù)安全09區(qū)塊鏈1全套可編輯PPT課件

1古典密碼（1）-ClassicalEncryptionTechniques2全套可編輯PPT課件

1.古典密碼

1.1對稱密鑰密碼模型

SymmetricCipherModel3本課件是可編輯的正常PPT課件要解決的問題：通信保密安全需求SecurityRequirements安全服務(wù)SecurityServices保密性Confidentiality完整性Integrity可用性Availability4本課件是可編輯的正常PPT課件三個古典密碼系統(tǒng)羊皮傳書藏頭詩Caesar5本課件是可編輯的正常PPT課件羊皮傳書古希臘的斯巴達(dá)人將一條1厘米寬、20厘米左右長的羊皮帶，以螺旋狀繞在一根特定粗細(xì)的木棍上…...6本課件是可編輯的正常PPT課件藏頭詩明才子唐伯虎：我愛蘭江水悠悠，愛晚亭上楓葉稠。秋月溶溶照佛寺，香煙裊裊繞經(jīng)樓。明朝解縉祝某宰相壽辰進(jìn)詩：真真宰相,老老元臣,烏紗戴頂,龜鶴遐林.粗看"密文”,渾然詩句,頌揚兼祝愿,福祿壽全有;細(xì)究則密語藏頭,挖苦帶諷刺,詛咒"真老烏龜”7本課件是可編輯的正常PPT課件CaesarCipherearliestknownsubstitutioncipherbyJuliusCaesar

firstattesteduseinmilitaryaffairsexample:meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWB8本課件是可編輯的正常PPT課件Terminologiesplaintext-theoriginalmessageciphertext-thecodedmessagekey-infousedincipherknownonlytosender/receiverencipher(encrypt)-convertingplaintexttociphertextdecipher(decrypt)-recoveringplaintextfromciphertextcipher-algorithmfortransformingplaintexttociphertext9SymmetricCipherModel10DefinitionAcryptosystemisa5-tuple

(E,D,p,K,C),wherepisthesetofplaintexts,Kthesetofkeys,Cisthesetofciphertexts,E:M×KCisthesetofEncryptionalgorithms,D:C×KMisthesetofDecryptionalgorithms.111.古典密碼

1.2密碼學(xué)的基礎(chǔ)假設(shè)12三個古典系統(tǒng)的再討論Caesar羊皮傳書藏頭詩13CaesarCiphermeetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWBp,C,K,E,D?14CaesarCiphercandefinetransformationas:abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCmathematicallygiveeachletteranumberabcdefghijklm0123456789101112nopqrstuvwxyZ13141516171819202122232425thenhaveCaesarcipheras:C=E(p)=(p+k)mod(26)p=D(C)=(C–k)mod(26)15羊皮傳書E,D,p,C,K?16藏頭詩真真宰相,老老元臣,烏紗戴頂,龜鶴遐林.E,D,p,C,K?全詩為"密文”,其"密鑰”是每句詩的首字,可串接成義,作者的真意就隱藏在詩句的首字串接文("明文”)中.Steganography，隱寫術(shù)17RethinkingoftheModel18encipherdecipher(plaintextin-ciphertextout)ciphertextmsg(ciphertextin-plaintextout)(shouldunderstand

nothing

aboutthemsg)eavesdropperbla-blacmb-cmbbla-blaSharedKeyNeed

keyexchangeAliceandBobwanttoestablishasharedsecret(key)whenotherpeople(eavesdroppers)arelisteningHowto?inboundVs.outbound19AliceBobDiscursionsontheModel20Q1:Whyuseakey?Q2:Whichpartsshouldbekeptsecret?whichnot?Discussion模型合理嗎？什么當(dāng)保密；什么當(dāng)公開？19世紀(jì)荷蘭人A.Kerckhoffs就提出了一個在密碼學(xué)界被公認(rèn)為基礎(chǔ)的假設(shè)，也就是著名的“Kerckhoffs假設(shè)”：秘密必須全寓于密鑰。

OtherModels?2122Discussion“誰是我們的敵人，誰是我們的朋友，這個問題是革命的首要問題”——毛選易用性秘密全部寓于密鑰≠算法當(dāng)公開，要看應(yīng)用環(huán)境(商用，軍用，……)開放的系統(tǒng)更安全，??Terminologies(cont.)cryptography-studyofencryptionprinciples/methodscryptanalysis(codebreaking)-thestudyofprinciples/methodsofdecipheringciphertextwithoutknowingkeycryptology-thefieldofbothcryptographyandcryptanalysis23CryptographyCatalogThetypeofoperationsusedfortransforming

plaintexttociphertextSubstitution:eachelementintheplaintextismappedintoanotherelementTransposition:elementsintheplaintextarerearrangedProduct:multiplestagesofsubstitutionsandtranspositionsThenumberofthekeysusedSymmetric,single-key,secret-key,conventional

encryption:BothsenderandreceiverusethesamekeyAsymmetric,two-key,orpublic-key

encryption:thesenderandreceiveeachusesadifferentkey24CryptographyCatalogThewayinwhichtheplaintextisprocessedBlock:processestheinputoneblockofelementsatatime,producinganoutput

block

foreachinputblockStream:processestheinputelementscontinuously,producingoutputoneelementatatime,asitgoesalong.252.如何設(shè)計好的密碼算法？

攻擊->防御->改進(jìn)->更好的密碼算法->攻擊…螺旋式上升過程中領(lǐng)會密碼設(shè)計的關(guān)鍵問題262.如何設(shè)計好的密碼算法？

2.1

Caesar密碼與單字母表密碼

攻擊->防御->改進(jìn)->更好的密碼算法->攻擊…螺旋式上升過程中領(lǐng)會密碼設(shè)計的關(guān)鍵問題27SubstitutionTechniquesCaesarcipherEasytobreak!28CryptanalysisofCaesarCipherThereareonly25keystotryAmapstoA,B,..Zcouldsimplytryeachinturnabruteforcesearch

givenciphertext,justtryallshiftsoflettersThelanguageofPlaintextisknownandeasilyrecognizabledoneedtorecognizewhenhaveplaintexteg.breakciphertext"GCUAVQDTGCM"29MonoalphabeticCipherImprovementonCaesarCipherRatherthansubstitutingaccordingtoaregularpattern–anylettercanbesubstitutedforanyotherletter,aslongaseachletterhasauniquesubstituteletter,andviceversa.30MonoalphabeticCipherK: Plain:abcdefghijklmnopqrstuvwxyz Cipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA

hencekeyis26letterslong31MonoalphabeticCipherSecuritynowhaveatotalof26!=4x1026keyswithsomanykeys,mightthinkissecure

butwouldbe!!!WRONG!!!

problemislanguagecharacteristics32LanguageRedundancyandCryptanalysishumanlanguagesareredundant

lettersarenotequally

commonlyusedinEnglisheisbyfarthemostcommonletter,thenT,R,N,I,O,A,S

somelettersarefairlyrare,eg.Z,J,X,Qtablesofsingle,double&tripleletterfrequencies33FrequencyofLettersinEnglishText34UseinCryptanalysiskeyconcept-monoalphabeticsubstitutionciphersdonotchangerelativeletterfrequencies

discoveredbyArabianscientistsin9thcenturycalculateletterfrequenciesforciphertextcomparecounts/plotsagainstknownvaluesifCaesarcipherlookforcommonpeaks/troughspeaksat:A-E-Itriple,NOpair,RSTtripletroughsat:JK,X-Zformonoalphabeticmustidentifyeachlettertablesofcommondouble/triplelettershelp35CryptanalyticAttacks36對于對手而言最壞情況下，仍有一種攻擊方法可用BruteForceSearch，窮舉法BruteForceSearchalwayspossibletosimply

try

everykey

mostbasic

attack,proportionaltokeysizeassumeeitherknoworrecogniseplaintext37MoreDefinitionsunconditionalsecurity

nomatterhowmuch

computerpowerisavailable,theciphercannotbebrokensincetheciphertextprovidesinsufficientinformationtouniquelydeterminethecorrespondingplaintextcomputationalsecurity

givenlimited

computingresources(eg.timeneededforcalculationsisgreaterthanageofuniverse),theciphercannotbebroken

Unconditionalsecuritywouldbenice,buttheonlyknownsuchcipheristheone-timepad(later).Forallreasonable

encryptionalgorithms,havetoassumecomputationalsecuritywhereiteithertakestoolong,oristooexpensive,tobother

breakingthecipher.382.如何設(shè)計好的密碼算法？

2.2

Playfair密碼

攻擊->防御->改進(jìn)->更好的密碼算法->攻擊…螺旋式上升過程中領(lǐng)會密碼設(shè)計的關(guān)鍵問題39MonoalphabeticCipherSecuritynowhaveatotalof26!=4x1026keyswithsomanykeys,mightthinkissecure

butwouldbe!!!WRONG!!!

problemislanguagecharacteristics40提高單字母表密碼安全性兩個角度“多”對“一”

Playfair“一”對“多”

Vigenère41PlayfairCiphernoteventhelargenumberofkeysinamonoalphabeticcipherprovidessecurity

oneapproachtoimprovingsecuritywastoencryptmultiplelettersthePlayfairCipherisanexampleinventedbyCharlesWheatstonein1854,butnamedafterhisfriendBaronPlayfair

4243PlayfairKeyMatrixa5X5matrixoflettersbasedonakeywordfillinlettersofkeyword(sansduplicates)fillrestofmatrixwithotherletterseg.usingthekeywordMONARCHYMONARCHYBDEFGIKLPQSTUVWXZ44EncryptingandDecryptingplaintextencryptedtwolettersatatime:ifapairisarepeatedletter,insertafillerlike'X', eg."balloon"encryptsas"balxloon"ifbothlettersfallinthesame

row,replaceeachwithlettertoright(wrappingbacktostartfromend), eg.“ar"encryptsas"RM"ifbothlettersfallinthesame

column,replaceeachwiththeletterbelowit(againwrappingtotopfrombottom),eg.“mu"encryptsto"CM"otherwiseeachletterisreplacedbytheoneinitsrowinthecolumnof

theotherletterofthepair,eg.“hs"encryptsto"BP",and“ea"to"IM"or"JM"(asdesired)45SecurityofthePlayfairCiphersecuritymuchimproved

overmonoalphabeticsincehave26x26=676digramswouldneeda676entryfrequencytabletoanalyse(verses26foramonoalphabetic)andcorrespondinglymoreciphertextwaswidelyusedformanyyears(eg.US&BritishmilitaryinWW1)itcanbebroken,givenafewhundredletterssincestillhasmuchofplaintextstructure462.如何設(shè)計好的密碼算法？

2.3

Vigenère密碼

攻擊->防御->改進(jìn)->更好的密碼算法->攻擊…螺旋式上升過程中領(lǐng)會密碼設(shè)計的關(guān)鍵問題47PolyalphabeticCiphersanotherapproachtoimprovingsecurityistousemultiplecipheralphabets

calledpolyalphabetic

substitution

ciphers

makescryptanalysisharderwithmorealphabetstoguessandflatterfrequencydistributionuseakeytoselectwhichalphabetisusedforeachletterofthemessageuseeachalphabetinturnrepeatfromstartafterendofkeyisreached48VigenèreCiphersimplestpolyalphabeticsubstitutioncipheristheVigenèreCipher

effectivelymultiplecaesarcipherskeyismultipleletterslongK=k1k2...kdithletterspecifiesithalphabettouseuseeachalphabetinturnrepeatfromstartafterdlettersinmessagedecryptionsimplyworksinreverse49VigenèreCipher50PlaintextKeyExamplewritetheplaintextoutwritethekeywordrepeatedaboveituseeachkeyletterasacaesarcipherkeyencryptthecorrespondingplaintextletteregusingkeyworddeceptiveKey:deceptivedeceptivedeceptivePlaintext:wearediscoveredsaveyourselfCiphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ

51ExamplewritetheplaintextoutwritethekeywordrepeatedaboveituseeachkeyletterasacaesarcipherkeyencryptthecorrespondingplaintextletteregusingkeyworddeceptiveKey:deceptivedeceptivedeceptivePlaintext:wearediscoveredsaveyourselfCiphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ

52AutokeyCipherideallywantakeyaslongasthemessageVigenèreproposedtheautokeycipherwithkeywordisprefixedtomessageaskeyknowingkeywordcanrecoverthefirstfewlettersusetheseinturnontherestofthemessagebutstillhavefrequencycharacteristicstoattackeg.givenkeydeceptivekey:deceptivewearediscoveredsavPlaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA53SecurityofVigenèreCiphershavemultipleciphertextlettersforeachplaintextletterhenceletterfrequenciesareobscuredbutnottotallylostTheultimatedefenceagainstsuchacryptanalysisistochooseakeywordthatisaslongastheplaintextandhasno

statisticalrelationshiptoitAT&T,Vernamcipher542古典密碼（2）-ClassicalEncryptionTechniques553.對稱密鑰密碼的理論標(biāo)桿

56回顧：Vigenère的安全性分析havemultipleciphertextlettersforeachplaintextletterhenceletterfrequenciesareobscuredbutnottotallylostTheultimatedefenceagainstsuchacryptanalysisistochooseakeywordthatisaslongastheplaintextandhasno

statisticalrelationshiptoitAT&T,Vernamcipher57一次一密，One-TimePad如果密鑰和消息一樣長，且真正隨機，那么該密碼無條件安全。1918年，GillbertVernam提出密鑰與明文一樣長并且沒有統(tǒng)計關(guān)系的密鑰內(nèi)容，算法表述采用二進(jìn)制數(shù)據(jù):申請了專利Ci=Pi⊕KiPi=Ci⊕Ki58G.Vernam191859Ci=Pi⊕KiPi=Ci⊕KiShannon在他的1949年發(fā)表的經(jīng)典論文中已經(jīng)證明了一次一密的無條件安全性密鑰的分發(fā)是大問題，實用價值較弱ClaudeShannon信息論之父,84高齡去世,2001年1948年發(fā)表《AMathematicalTheoryofCommunication》奠定了現(xiàn)代信息論的基礎(chǔ)1949年，《CommunicationTheoryofSecrecySystems》(保密系統(tǒng)的通信理論)提出了保密系統(tǒng)的數(shù)學(xué)模型、隨機密碼、完善保密性等重要概念它的意義是使保密通信由藝術(shù)變成科學(xué)604.簡單的置換密碼

61置換密碼重新排列明文字母，達(dá)到信息加密的目的與替代密碼不同的是，原來明文中的字母同樣出現(xiàn)在密文中，順序打亂。古典的置換密碼例子：62RailFence密碼明文：meetmeafterthetogaparty順序打亂（本來應(yīng)該從左向右橫向?qū)?，現(xiàn)在是先縱向?qū)憙蓚€字母，再橫向?qū)懀?mematrhtgpryetefeteoaat密文：MEMATRHTGPRYETEFETEOAAT63行置換密碼略復(fù)雜的例子Key:4312567Plaintext:attackpostponeduntiltwoamxyzCiphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZ

64乘積密碼單次替代或置換方法構(gòu)造密碼技術(shù)并不安全因此考慮連續(xù)多次使用簡單的加密方法可以構(gòu)造更強的密碼：

兩次替代構(gòu)成一個更復(fù)雜的替代密碼兩次置換構(gòu)成一個更復(fù)雜的置換密碼替代與置換的疊加同樣……通向現(xiàn)代密碼技術(shù)的基本道路655.轉(zhuǎn)子機（RotorMachines）

－代表古典密碼最高峰的作品

66轉(zhuǎn)子機現(xiàn)代密碼出現(xiàn)前,轉(zhuǎn)子機是一種典型的乘積密碼-古典密碼的高峰非常普遍應(yīng)用于WW2德國Enigma,盟軍Hagelin,日本Purple非常復(fù)雜的多輪替代技術(shù)3個轉(zhuǎn)盤有：263=17576個密鑰67Enigma68Enigma-Rotors69Enigma70古典隱寫術(shù)藏頭詩隱形墨水……特點：大量冗余的信息隱藏相對很少的信息量71現(xiàn)代隱寫術(shù)的變遷數(shù)字化編碼后的多媒體信息：如圖像、聲音、視頻，甚至文本信息，對于人類的視覺、聽覺感知系統(tǒng)，都或多或少存在著一些冗余空間，而利用這些冗余空間，就可以進(jìn)行信息的秘密傳遞，同時不影響載體的視覺或聽覺效果，因此就可以實現(xiàn)信息的隱蔽傳遞。72信息隱藏技術(shù)偽裝式保密通信數(shù)字水印73偽裝式保密通信目前在這一研究領(lǐng)域中主要研究在圖像、視頻、聲音以及文本中隱藏信息。如：在一幅普通圖像中隱藏一幅機密圖像。在一段普通談話中隱藏一段機密談話或各種數(shù)據(jù)。在一段視頻流中隱藏各種信息等。文本中的冗余空間比較小，但利用文本的一些特點也可以隱藏一些信息。74數(shù)字水印一種基本的數(shù)字版權(quán)標(biāo)記手段數(shù)字水印是嵌入在數(shù)字作品中的一個版權(quán)信息，它可以給出作品的作者、所有者、發(fā)行者以及授權(quán)使用者等等版權(quán)信息?？梢宰鳛閿?shù)字作品的序列碼，用于跟蹤盜版者。753現(xiàn)代分組密碼-Modern

Block

Cipher以DES為例76本講內(nèi)容分組密碼流密碼77相對的概念本講內(nèi)容現(xiàn)代分組密碼設(shè)計的一般性原則DES加密算法78回顧：對稱密碼模型AliceBob79本講內(nèi)容現(xiàn)代分組密碼設(shè)計的一般性原則Shannon理論奠基Feistel結(jié)構(gòu)DES加密算法80乘積密碼單次替代或置換方法構(gòu)造密碼技術(shù)并不安全因此考慮連續(xù)多次使用簡單的加密方法可以構(gòu)造更強的密碼：

兩次替代構(gòu)成一個更復(fù)雜的替代密碼兩次置換構(gòu)成一個更復(fù)雜的置換密碼替代與置換的疊加同樣……通向現(xiàn)代密碼技術(shù)的基本道路81Shannon理論奠基Shannon提出利用擾亂（Confusion）和擴散（Diffusion）交替的方法來構(gòu)造乘積密碼密碼SPN：SubstitutionPermutationNetwork 替代-置換網(wǎng)絡(luò)目的是：使基于統(tǒng)計的分析方法不易或者不能實現(xiàn)Shannon理論是現(xiàn)代分組密碼算法的基礎(chǔ)82SPN的基本操作83SPN84SPN的雪崩效應(yīng)8586Feistel結(jié)構(gòu)由HorstFeistel發(fā)明目的是構(gòu)造可逆的乘積密碼把輸入的分組分成兩個部分進(jìn)行多輪的變換（替代和置換）輪函數(shù)是關(guān)鍵體現(xiàn)了Shannon的SPN理念87FeistelCipherStructure本講內(nèi)容現(xiàn)代分組密碼設(shè)計的一般性原則DES加密算法8889分組密碼以分組為加密/解密處理的最小單位-“多”對“一”分組：可以理解為連續(xù)的多個字母64-bits或更多分組密碼非常廣泛的應(yīng)用于現(xiàn)代加密系統(tǒng)90DataEncryptionStandard(DES)最廣泛使用的密碼系統(tǒng)1977年，被NBS(nowNIST)選為標(biāo)準(zhǔn)asFIPSPUB46分組64-bit，使用56-bitkey它的安全性曾引起了廣泛的爭論NBS(NationalBureauofStandards)NIST(NationalInstituteofStandardsandTechnology)美國國家標(biāo)準(zhǔn)局91DES算法的歷史1969年前后IBM的Feistel研究組的工作NIST1973年開始研究除國防部外的其它部門的計算機系統(tǒng)的數(shù)據(jù)加密標(biāo)準(zhǔn)，于1973年5月15日和1974年8月27日先后兩次向公眾發(fā)出了征求加密算法的公告加密算法要達(dá)到的目的有四點高質(zhì)量的數(shù)據(jù)保護，防止數(shù)據(jù)未經(jīng)授權(quán)的泄露和未被察覺的修改；具有相當(dāng)高的復(fù)雜性，使得破譯的開銷超過可能獲得的利益，同時又要便于理解和掌握；DES密碼體制的安全性應(yīng)該不依賴于算法的保密，其安全性僅以加密密鑰的保密為基礎(chǔ)；實現(xiàn)經(jīng)濟，運行有效，并且適用于多種完全不同的應(yīng)用92DES算法的原理DES算法的入口參數(shù)有三個：Key、Data、ModeKey為8個字節(jié)共64位，是DES算法的工作密鑰Data分組也為8個字節(jié)64位，被加密或被解密的數(shù)據(jù)Mode為DES的工作方式有兩種：加密或解密93DES算法概貌94DES算法的實現(xiàn)步驟DES算法實現(xiàn)加密需要三個步驟：第一步：變換明文。對給定的64位比特的明文x，首先通過一個置換IP表來重新排列x，從而構(gòu)造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位第二步：按照規(guī)則迭代。規(guī)則為Li=Ri-1Ri=Li⊕F(Ri-1,Ki)（i=1,2,3…16）95DES算法的實現(xiàn)步驟第二步：經(jīng)過第一步變換已經(jīng)得到L0和R0的值，其中符號⊕表示的數(shù)學(xué)運算是異或，F(xiàn)函數(shù)表示一種密碼變換，由S盒替代構(gòu)成，Ki是一些由密鑰編排函數(shù)產(chǎn)生的比特塊F和Ki將在后面介紹第三步：對L16R16利用IP-1作逆置換，就得到了密文y96（1）IP置換表和IP-1逆置換表輸入的64位數(shù)據(jù)按置換IP表進(jìn)行重新組合，并把輸出分為L0、R0兩部分，每部分各長32位，其置換IP表如表：5850123426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315797逆置換表IP-1

4084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917572598每一輪做什么99F函數(shù)詳解100子密鑰Ki的生成假設(shè)密鑰為K，長度為64位，但是其中第8、16、24、32、40、48、64用作奇偶校驗位，實際上密鑰長度為56位。K的下標(biāo)i的取值范圍是1到16，用16輪來構(gòu)造101子密鑰Ki的生成102DES算法的安全性1993年R.Session和M.Wiener給出了一個非常詳細(xì)的密鑰搜索機器的設(shè)計方案它基于并行的密鑰搜索芯片每個芯片每秒測試5×107個密鑰當(dāng)時這種芯片的造價是10.5美元5760個這樣的芯片組成的系統(tǒng)需要10萬美元系統(tǒng)平均1.5天即可找到密鑰，如果利用10個這樣的系統(tǒng)，費用是100萬美元，但搜索時間可以降到2.5小時103DES算法的安全性1997年1月28日，RSA公司在互聯(lián)網(wǎng)上開展了一項名為“密鑰挑戰(zhàn)”的競賽，懸賞一萬美元，破解一段用56比特密鑰加密的DES密文一位名叫RockeVerser的程序員設(shè)計了一個可以通過互聯(lián)網(wǎng)分段運行的密鑰窮舉搜索程序，組織實施了一個稱為DESHALL的搜索行動，成千上萬的志愿者加入在行動實施的第96天，即挑戰(zhàn)賽計劃公布的第140天，1997年6月17日晚上10點39分，美國鹽湖城Inetz公司的職員MichaelSanders成功地找到了密鑰，在計算機上顯示了明文：“Theunknownmessageis:Strongcryptographymakestheworldasaferplace”104AES,AdvancedEncryptionStandard需要DES的替代品理論上實踐上，窮舉法攻擊的成功3重-DES，但速度慢NIST發(fā)布新的密碼征求令，1997最終，2000年10月，Rijndael被選中成為AES2001年11月成為FIPSPUB197標(biāo)準(zhǔn)

128-bitdata,128/192/256-bitkeys105Quiz試總結(jié)設(shè)計一個好的對稱分組加密算法應(yīng)當(dāng)遵循哪些原則？請默寫畫出DES加密算法的流程圖。DES的加密算法與解密算法是一致的，因為算法的結(jié)構(gòu)本身保證了算法的可逆性，與F函數(shù)無關(guān)，請試著說明上述結(jié)論。1064公開密鑰密碼

PublicKeyCryptography107內(nèi)容提要對稱密鑰密碼的密鑰交換問題公鑰密碼模型提出設(shè)計公鑰密碼的基本要求數(shù)字簽名RSA算法公鑰密碼的特征總結(jié)Diffie-Hellman密鑰交換算法108內(nèi)容提要1、對稱密鑰密碼的密鑰交換問題109回顧：對稱密鑰密碼對稱的,單密鑰,秘密密鑰,傳統(tǒng)密碼:發(fā)送方加密和接收方解密使用同一個的密鑰該密鑰需要事先由發(fā)送方和接收方實現(xiàn)共享，是發(fā)送方和接收方共同的秘密如果密鑰泄露，則不安全（無法提供保密性服務(wù)）對稱：通信雙方是對等的110回顧：對稱密鑰密碼模型雙方共享的秘密：KeyAliceBob發(fā)送方接收方安全的信道

加密容易實現(xiàn)，但密鑰交換是個問題111內(nèi)容提要2、公鑰密碼模型提出112BobAlice每個人有兩個密鑰公鑰，Publickey——公開私鑰，Privatekey——保密公開密鑰(非對稱)密碼模型113BobAliceBob’sPublickeyAlice’sPublickeyBob’sPrivatekeyAlice’sPrivatekey非對稱密碼模型公開114BobAliceBob’sPublickeyAlice’sPublickeyBob’sPrivatekeyAlice’sPrivatekey非對稱密碼模型公開保密保密115用非對稱密碼實現(xiàn)“保密通信”BobAlice提供“保密通信”安全服務(wù)攻擊者116兩種密碼體制據(jù)使用的密鑰數(shù)量對稱的,單密鑰,秘密密鑰,傳統(tǒng)密碼技術(shù):發(fā)送方和接收方使用同一個的密鑰非對稱的,雙密鑰,公鑰密碼技術(shù):發(fā)送方和接收方使用不同的密鑰加密密鑰和解密密鑰分割開來,且無法由一個推出另一個,使得不僅可以公開密碼算法,而且加密密鑰也可公開（公告牌、號碼簿）117公開密鑰密碼人類文明史3000年以來，密碼技術(shù)一個新的篇章兩個密鑰–apublic&aprivatekey非對稱：通信雙方的地位不平等往往應(yīng)用數(shù)論的一些函數(shù)精心構(gòu)造補充而非取代對稱密鑰密碼技術(shù)缺點：公鑰密碼的主要弱點是加密和解密速度慢118歷史1976年，Diffie和Hellman在論文“密碼學(xué)新方向（NewDirectioninCryptography）”中首次提出了公開密鑰密碼體制的思想；Diffie和Hellman提出了第一個基于公開密鑰思想的密碼算法，稱為DH算法，此算法可以用于實現(xiàn)密鑰交換。1977年，Rivest、Shamir和Adleman三個人實現(xiàn)了公開密鑰密碼體制，現(xiàn)在稱為RSA算法，它是第一個既能用于密鑰交換、也能用于數(shù)據(jù)加密和數(shù)字簽名的算法。119內(nèi)容提要3、設(shè)計公鑰密碼的基本要求一個公開密鑰系統(tǒng)由六要素組成：明文公開密鑰（記作：PU或KU）私有密鑰（記作：KR或PR）加密算法密文解密算法公開密鑰加密系統(tǒng)參與方B容易通過計算產(chǎn)生出一對密鑰（公開密鑰KUb

，私有密鑰KRb

）發(fā)送方A很容易計算產(chǎn)生密文接收方B通過計算解密密文敵對方即使知道公開密鑰KUb

，要確定私有密鑰KRb

在計算上是不可行的敵對方即使知道公開密鑰KUb

和密文C，要確定明文M在計算上是不可行的密鑰對互相之間可以交換使用公開密鑰算法的基本要求公鑰密碼構(gòu)建在計算復(fù)雜性理論基礎(chǔ)之上122往往讓敵方求解目前仍未找到多項式時間算法的NP完全問題123內(nèi)容提要4、數(shù)字簽名124密鑰對互相之間可以交換使用：125數(shù)字簽名BobAlice提供“數(shù)字簽名”安全服務(wù)126公鑰密碼能提供的安全服務(wù)保密通信本課程最初提出的安全需求，先前講解的密碼方案主要用于解決這個問題密鑰交換數(shù)字簽名能夠檢驗加密數(shù)據(jù)的來源（認(rèn)證）能夠抗抵賴127公鑰密碼原理總結(jié)公開密鑰密碼技術(shù)涉及兩個密鑰:公鑰：

公開，任何人可以知道,用于加密明文，驗證簽名私鑰,僅有接收者/擁有者自己知道，用于解密，簽名非對稱的含義：密鑰的不對稱：加／解密的密鑰不同用于加密的不能解密，用于解密的不能加密128本講內(nèi)容5、RSA算法5.1密鑰生成1977年由MIT的Rivest,Shamir和Adleman

三人提出是一個分組加密方法目前被最廣泛地采用理論基礎(chǔ)是數(shù)論中的下述論斷:要求得兩個大素數(shù)的乘積是容易的,但要分解一個合數(shù)為兩個大素數(shù)的乘積,則在計算上幾乎是不可能的。RSA算法130RSA密鑰生成每個用戶執(zhí)行：（1）生成兩個大素數(shù)p和q。（2）計算這兩個素數(shù)的乘積n=p×q。（3）計算小于n并且與n互質(zhì)的整數(shù)的個數(shù)，即歐拉函數(shù)φ(n)=(p-1)(q-1)。（4）選擇一個隨機數(shù)e滿足1<e<φ(n)，并且e和φ(n)互質(zhì)，即gcd(e,φ(n))=1。（5）解方程e·d

≡1modφ(n)，求出d131RSA密鑰（6）保密d，p和q（銷毀），公開n和e。公鑰公開:PU={e,n}私鑰保密:PR={d,n}密鑰生成的計算量如何得到足夠大的隨機素數(shù)如何求解方程e·d

≡1modφ(n)132如何得到足夠大的隨機素數(shù)實際應(yīng)用所采用的方法是：首先，產(chǎn)生一個足夠大的隨機數(shù)，然后，通過采用一個概率多項式時間算法來檢測該隨機數(shù)是否為素數(shù)（即是否具有素性）。常用的兩個素性測試算法：Solovay-Strassen素性測試；Miller-Rabin素性測試。索洛維-斯特拉森求解方程e·d

≡1modφ(n)擴展的歐幾里德算法（輾轉(zhuǎn)相除法）134當(dāng)e＝1001，?(n)＝3837時

方程為x*1001=1(mod3837)

求解過程：

3837=3*1001+834

1001=1*834+167

834=4*167+166

167=166+1

所以

1=167-166

=167-(834-4*167)

=5*167-834

=5*(1001-834)-834

=5*1001-6*834

=5*1001-6*(3837-3*1001)

=23*1001-6*3837135本講內(nèi)容5、RSA算法5.2加解密算法136RSA使用公鑰公開:PU={e,n}私鑰保密:PR={d,n}加密一個報文M，發(fā)送方:獲取接收方的公鑰

PU={e,n}

計算:C=Memodn,where0≤M<n解密

密文C，接收方:用自己的私鑰

PR={d,n}

計算:M=Cdmodn

137RSA例子–密鑰挑選質(zhì)數(shù):p=17&q=11計算

n=?138RSA例子–密鑰挑選質(zhì)數(shù):p=17&q=11計算

n=pq=17x11=187計算?(n)=(p–1)(q-1)=16x10=160選擇e:

gcd(e,160)=1;不妨選e=7求解d:

ed=1mod160

且d

<160

d=23，顯然

23x7=161=10x160+1PublickeyPU={7,187}PrivatekeyPR={23,187}139RSA例子–加密/解密RSA加密/解密:M=88(注意:

88<187)加密:C=887mod187=11

解密:M=1123mod187=88

模指數(shù)運算簡化140在RSA密碼體制中，加密和解密運算都是模指數(shù)運算，即C=Memodn可以通過e-1次模乘來實現(xiàn)計算，然而，如果e非常大，其效率會很低下平方-乘算法可以把計算所需的模乘的次數(shù)降低1123mod187=[(111mod187)*(112mod187)*(114mod187)*(118mod187)*(118mod187)]mod187111mod187=11112mod187=121114mod187=14641mod187=55118mod187=214358881mod187=331123mod187=(11*121*55*33*33)mod187=79720245mod187=88求模指數(shù)實例142RSA注意RSA加密時，明文以分組的方式加密：每一個分組的比特數(shù)應(yīng)該小于log2n比特，即：M<n選取的素數(shù)p和q要足夠大，從而乘積n足夠大，在事先不知道p和q的情況下分解n是計算上不可行的。143本講內(nèi)容5、RSA算法5.3

RSA安全性討論144RSA算法的安全性在理論上,RSA的安全性取決于模n分解的困難性。若n被分解成功,則RSA被攻破。目前最快的分解因子算法其時間復(fù)雜性為并沒有證明分解大整數(shù)就是NP問題,并不能排除存在尚未發(fā)現(xiàn)的多項式時間算法。也沒有證明對RSA的攻擊的難度與分解n等價因此對RSA的攻擊的困難程度不比大數(shù)分解難目前，RSA的一些變種算法已被證明等價于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法?，F(xiàn)在人們已能分解多個十進(jìn)制位的大素數(shù)，因此，模數(shù)n必須選大一些。145RSA因數(shù)分解挑戰(zhàn)分解挑戰(zhàn)獎金于2007終止ChallengeNumber Prize($US) StatusRSA-576(174Digits) $10,000 Factored(Dec2003)RSA-640(193Digits) $20,000 Factored(Nov2005)RSA-704(212Digits) $30,000 Factored(July2012)RSA-768(232Digits) $50,000 Factored(Dec2009)RSA-896(270Digits) $75,000 NotFactoredRSA-1024(309Digits) $100,000 NotFactoredRSA-1536(463Digits) $150,000 NotFactoredRSA-2048(617Digits) $200,000 NotFactoredRSA-704 DecimalDigits:212

74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359146RSA-232(768bits)hasnotbeenfactoredsofar.1009881397871923546909564894309468582818233821955573955141120516205831021338528545374366109757154363664913380084917065169921701524733294389270280234380960909804976440540711201965410747553824948672771374075011577182305398340606162079147RSA算法的速度由于都是大數(shù)計算，RSA最快的情況也比DES慢許多倍，無論是軟件還是硬件實現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。RSA是被研究得最廣泛的公鑰算法，提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一148本講內(nèi)容6、公鑰密碼的特征總結(jié)公開密鑰算法設(shè)計需要有以下基本要求：加密與解密由不同的密鑰完成；知道加密算法，從加密密鑰得到解密密鑰在計算上是不可行的；兩個密鑰中任何一個都可以作為加密而另一個用作解密。公鑰密碼的特征公鑰密碼算法基礎(chǔ)單向函數(shù)

對于一個函數(shù)，如果對于其定義域上的任意x，都容易計算，同時，對于其值域中幾乎所有的取值

y

，計算其逆函數(shù)都是不可行的，則函數(shù)被稱為單向函數(shù)。

可以提供單向函數(shù)的三大數(shù)學(xué)難題大整數(shù)分解問題（簡稱IFP）；離散對數(shù)問題（簡稱DLP）；橢圓曲線離散對數(shù)問題（簡稱ECDLP）。

對于一個單向函數(shù)，如果其逆函數(shù)在已知某些輔助信息的情況下容易求解得出，則稱該單向函數(shù)為單向陷門函數(shù)。構(gòu)造公鑰密碼系統(tǒng)的關(guān)鍵是如何在求解某個單向函數(shù)的逆函數(shù)的NP完全問題中設(shè)置合理的“陷門”。單向陷門函數(shù)公鑰密碼算法除RSA算法以外，建立在不同計算難題上的其他公鑰密碼算法有：基于因子分解問題的Rabin算法；橢圓曲線公鑰算法；基于有限域中離散對數(shù)難題的ElGamal公鑰密碼算法基于“子集和”難題的Merkle-HellmanKnapsack（背包）公鑰密碼算法；等等153本講內(nèi)容7、Diffie-Hellman密鑰交換算法

Diffie-Hellman密鑰交換是第一個公鑰方案使用在一些常用安全協(xié)議或產(chǎn)品（例如SSH等）密鑰交換方案不能用于交換任意信息允許兩個用戶可以安全地建立一個共享的秘密信息，用于后續(xù)的通訊過程該秘密信息僅為兩個參與者知道算法的安全性依賴于有限域上計算離散對數(shù)的問題Diffie-Hellman密鑰交換算法：通信雙方/多方

選擇大素數(shù)p，以及p的一個原根a用戶A選擇一個隨機數(shù)Xa<p，計算Ya=aXamodp用戶B選擇一個隨機數(shù)Xb<p，計算Yb=aXbmodp每一方保密X值，而將Y值交換給對方即：X是私鑰，Y是公鑰Diffie-Hellman密鑰交換雙方獲得一個共享密鑰K＝aXaXbmodp對于用戶A，計算出K=YbXamodp用戶B，可計算出K=YaXbmodp攻擊者要獲得K，需要求解離散對數(shù)實際使用中，素數(shù)p以及p的原根a可由一方選擇后發(fā)給對方1575報文鑒別與哈希函數(shù)內(nèi)容提要安全服務(wù)與安全需求報文鑒別的安全需求對報文加密來實現(xiàn)報文鑒別報文鑒別碼哈希函數(shù)生日攻擊158內(nèi)容提要1、安全服務(wù)與安全需求159160復(fù)習(xí)：安全服務(wù)/安全需求我們的故事從哪里開始？

通信保密

：較早期的安全需求公開密鑰密碼對稱密鑰密碼提煉：安全服務(wù)/安全需求“通信保密”可以概括所有的安全需求嗎？

答：不能。信息安全需求有許多種，通信保密只是一種安全需求，我們對現(xiàn)實世界的安全需求提煉和歸類，用以下抽象名詞來概括典型的安全需求保密性（Confidentiality）完整性（Integrity）可用性（Availability）可認(rèn)證（Authentication）抗抵賴/抗否認(rèn)（Non-repudiation）161內(nèi)容提要2、報文鑒別的安全需求162安全需求分析的例子泄密流量分析修改內(nèi)容破壞數(shù)據(jù)包收到的先后順序不承認(rèn)發(fā)送過某個報文冒名頂替瀏覽器訪問網(wǎng)銀Web服務(wù)器應(yīng)用的安全需求163164報文鑒別的安全需求報文鑒別的三重含義（安全需求）:1）保護報文的完整性2）驗證發(fā)送者的身份3）抗抵賴：防止報文發(fā)送者抵賴

（解決爭議）將嘗試以下三種方案實現(xiàn)報文鑒別:報文加密報文鑒別碼(MAC)HASH（哈希）函數(shù)165報文鑒別的含義注意：不是所有的方案都能夠完整實現(xiàn)上述報文鑒別所包括的三個安全需求：1）需要仔細(xì)甄別2）訓(xùn)練密碼學(xué)思維；3）分析過程比結(jié)論重要：將嘗試以下三種方案實現(xiàn)報文鑒別:報文加密報文鑒別碼(MAC)HASH（哈希）函數(shù)166一些名詞的含意

報文vs.

明文

我們有時候不考慮保密性.報文鑒別（Message

Authentication）vs.身份認(rèn)證（Authentication）內(nèi)容提要3、對報文加密來實現(xiàn)報文鑒別3.1用對稱密鑰167168報文加密-對稱密鑰報文加密在提供保密性的同時，本身也能提供了某些報文鑒別的安全服務(wù)如果發(fā)送者使用對稱密鑰加密報文:接收者知道發(fā)送者創(chuàng)建了它（前提：接收者自己沒有創(chuàng)建過）因為現(xiàn)在只有發(fā)送者和接收者知道這個對稱密鑰知道報文內(nèi)容在通信過程中沒有被篡改發(fā)送者（Source）A接收者（Destination）B169報文加密-對稱密鑰接收到的密文可以解密為明文，但可能難以自動確定報文是否被篡改報文應(yīng)具有合適的結(jié)構(gòu)，冗余信息或校驗和來檢測報文是否被更改發(fā)送者（Source）A接收者（Destination）B170報文加密-對稱密鑰AB:

E(K,M)，或記作EK(M)保密性——只有A和B知道K一定程度的報文鑒別——只能來自于A——傳輸過程中沒被篡改 —需要有特定的格式/冗余不提供抗抵賴——接受者不能偽造報文——發(fā)送者不能否認(rèn)報文發(fā)送者（Source）A接收者（Destination）B內(nèi)容提要3、對報文加密來實現(xiàn)報文鑒別3.2用公開密鑰密碼171172報文加密-公鑰加密如果使用公鑰加密:無法實現(xiàn)報文鑒別所包括的任何一項安全服務(wù)因為任何人都知道公鑰僅能提供“保密性”發(fā)送者（Source）A接收者（Destination）B173報文加密-私鑰加密(簽名)如果使用私鑰加密:如果發(fā)送者使用私鑰加密，則不具有保密性因為任何人都知道公鑰然而可以實現(xiàn)報文鑒別所有的安全需求仍然需要冗余信息確認(rèn)報文是否被篡改發(fā)送者（Source）A接收者（Destination）B174報文加密-先私鑰后公鑰發(fā)送者用私鑰對報文簽名，然后使用接收者的公鑰加密同時提供保密性和報文鑒別的所有三種安全服務(wù)代價是需要使用兩個公鑰發(fā)送者（Source）A接收者（Destination）B175報文加密－公開密鑰總結(jié)

公鑰加密：僅提供保密性176報文加密－公開密鑰總結(jié)

私鑰加密：報文鑒別所有的三種安全服務(wù)177報文加密-私鑰加密(簽名)

發(fā)送者（Source）A接收者（Destination）B178報文加密－公開密鑰總結(jié)

先私鑰后公鑰加密：保密性、報文鑒別的所有三種服務(wù)內(nèi)容提要4、報文鑒別碼4.1報文鑒別碼的定義179180用加密實現(xiàn)報文鑒別的缺點Q:報文加密的缺點?開銷

加密整個報文，相當(dāng)于用整個報文作文報文鑒別碼較難實現(xiàn)自動的181報文鑒別碼(MAC)報文鑒別碼：固定長度的比特串（例如128個bit,等）由報文鑒別碼算法生成算法的輸入包括：報文和密鑰算法設(shè)計類似于對稱密鑰算法，但不可逆附加到報文上用于報文鑒別接收者對報文執(zhí)行相同方向的計算并檢查它是否與收到的MAC匹配確保報文來自聲稱的發(fā)送者且傳輸過程中沒被篡改182報文鑒別碼如圖所示MAC提供報文鑒別的完整性、發(fā)送者身份驗證兩種安全服務(wù)183報文鑒別碼為什么用MAC?有時候只需要報文鑒別有時需要長時間保存數(shù)據(jù)的完整性(例如：檔案)注意MAC不是數(shù)字簽名內(nèi)容提要4、報文鑒別碼4.2報文鑒別碼的用法184185報文鑒別碼的用法

(a)報文鑒別的1，2兩項安全服務(wù)發(fā)送者（Source）A接收者（Destination）B186報文鑒別碼的用法發(fā)送者（Source）A接收者（Destination）B

(b)保密性和報文鑒別的第1和2項服務(wù)明文加報文鑒別碼187報文鑒別碼的用法發(fā)送者（Source）A接收者（Destination）B

(b)保密性和報文鑒別的第1和2項服務(wù)密文加報文鑒別碼內(nèi)容提要4、報文鑒別碼4.3報文鑒別碼的性質(zhì)188189MAC的性質(zhì)MAC是密碼性質(zhì)校驗和

MAC=CK(M)壓縮可變長度的報文M使用秘鑰K輸出固定長度的報文鑒別碼是一個多對一的函數(shù)可能許多報文有相同的MAC但是找到這些MAC值相同的報文是非常困難的190MAC的要求攻擊：能夠找到M’≠M,但CK(M’)＝CK(M)需要MAC滿足以下要求:不能通過一個報文和它的MAC，找到另一條有相同MAC的報文MAC應(yīng)該是均勻分布的MAC應(yīng)該取決于報文的每一位191可以使用分組密碼的CBC（CipherBlockChaining）模式將最后一個密文塊作為MACDataAuthenticationAlgorithm(DAA)

報文鑒別碼算法就是基于DES-CBC，是一個早期的MAC生成算法令I(lǐng)V=0并用比特0填充最后一個明文塊在CBC模式下使用DES加密報文將最后一個密文塊作為MAC值或者最后一個塊的最左邊的M位(16≤M≤64)這個算法最終得到的MAC太短，不夠安全簡單的構(gòu)造MAC算法的方法192DAA算法內(nèi)容提要5、哈希函數(shù)5.1哈希函數(shù)的定義與性質(zhì)193194哈希函數(shù)（Hash）將任意長度的報文壓縮到固定長度的二進(jìn)制串：