《信息安全導論（以問題為導向）》全套教學課件

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

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

1.古典密碼

1.1對稱密鑰密碼模型

SymmetricCipherModel3本課件是可編輯的正常PPT課件要解決的問題：通信保密安全需求SecurityRequirements安全服務SecurityServices保密性Confidentiality完整性Integrity可用性Availability4本課件是可編輯的正常PPT課件三個古典密碼系統(tǒng)羊皮傳書藏頭詩Caesar5本課件是可編輯的正常PPT課件羊皮傳書古希臘的斯巴達人將一條1厘米寬、20厘米左右長的羊皮帶，以螺旋狀繞在一根特定粗細的木棍上…...6本課件是可編輯的正常PPT課件藏頭詩明才子唐伯虎：我愛蘭江水悠悠，愛晚亭上楓葉稠。秋月溶溶照佛寺，香煙裊裊繞經樓。明朝解縉祝某宰相壽辰進詩：真真宰相,老老元臣,烏紗戴頂,龜鶴遐林.粗看"密文”,渾然詩句,頌揚兼祝愿,福祿壽全有;細究則密語藏頭,挖苦帶諷刺,詛咒"真老烏龜”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密碼學的基礎假設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，隱寫術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模型合理嗎？什么當保密；什么當公開？19世紀荷蘭人A.Kerckhoffs就提出了一個在密碼學界被公認為基礎的假設，也就是著名的“Kerckhoffs假設”：秘密必須全寓于密鑰。

OtherModels?2122Discussion“誰是我們的敵人，誰是我們的朋友，這個問題是革命的首要問題”——毛選易用性秘密全部寓于密鑰≠算法當公開，要看應用環(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.如何設計好的密碼算法？

攻擊->防御->改進->更好的密碼算法->攻擊…螺旋式上升過程中領會密碼設計的關鍵問題262.如何設計好的密碼算法？

2.1

Caesar密碼與單字母表密碼

攻擊->防御->改進->更好的密碼算法->攻擊…螺旋式上升過程中領會密碼設計的關鍵問題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.如何設計好的密碼算法？

2.2

Playfair密碼

攻擊->防御->改進->更好的密碼算法->攻擊…螺旋式上升過程中領會密碼設計的關鍵問題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.如何設計好的密碼算法？

2.3

Vigenère密碼

攻擊->防御->改進->更好的密碼算法->攻擊…螺旋式上升過程中領會密碼設計的關鍵問題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.對稱密鑰密碼的理論標桿

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

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

61置換密碼重新排列明文字母，達到信息加密的目的與替代密碼不同的是，原來明文中的字母同樣出現在密文中，順序打亂。古典的置換密碼例子：62RailFence密碼明文：meetmeafterthetogaparty順序打亂（本來應該從左向右橫向寫，現在是先縱向寫兩個字母，再橫向寫）:mematrhtgpryetefeteoaat密文：MEMATRHTGPRYETEFETEOAAT63行置換密碼略復雜的例子Key:4312567Plaintext:attackpostponeduntiltwoamxyzCiphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZ

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

兩次替代構成一個更復雜的替代密碼兩次置換構成一個更復雜的置換密碼替代與置換的疊加同樣……通向現代密碼技術的基本道路655.轉子機（RotorMachines）

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

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

Block

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

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

4084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917572598每一輪做什么99F函數詳解100子密鑰Ki的生成假設密鑰為K，長度為64位，但是其中第8、16、24、32、40、48、64用作奇偶校驗位，實際上密鑰長度為56位。K的下標i的取值范圍是1到16，用16輪來構造101子密鑰Ki的生成102DES算法的安全性1993年R.Session和M.Wiener給出了一個非常詳細的密鑰搜索機器的設計方案它基于并行的密鑰搜索芯片每個芯片每秒測試5×107個密鑰當時這種芯片的造價是10.5美元5760個這樣的芯片組成的系統(tǒng)需要10萬美元系統(tǒng)平均1.5天即可找到密鑰，如果利用10個這樣的系統(tǒng)，費用是100萬美元，但搜索時間可以降到2.5小時103DES算法的安全性1997年1月28日，RSA公司在互聯(lián)網上開展了一項名為“密鑰挑戰(zhàn)”的競賽，懸賞一萬美元，破解一段用56比特密鑰加密的DES密文一位名叫RockeVerser的程序員設計了一個可以通過互聯(lián)網分段運行的密鑰窮舉搜索程序，組織實施了一個稱為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標準

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

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

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

，私有密鑰KRb

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

，要確定私有密鑰KRb

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

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

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

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

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

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

≡1modφ(n)擴展的歐幾里德算法（輾轉相除法）134當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本講內容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例子–密鑰挑選質數:p=17&q=11計算

n=?138RSA例子–密鑰挑選質數: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

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

RSA安全性討論144RSA算法的安全性在理論上,RSA的安全性取決于模n分解的困難性。若n被分解成功,則RSA被攻破。目前最快的分解因子算法其時間復雜性為并沒有證明分解大整數就是NP問題,并不能排除存在尚未發(fā)現的多項式時間算法。也沒有證明對RSA的攻擊的難度與分解n等價因此對RSA的攻擊的困難程度不比大數分解難目前，RSA的一些變種算法已被證明等價于大數分解。不管怎樣，分解n是最顯然的攻擊方法?，F在人們已能分解多個十進制位的大素數，因此，模數n必須選大一些。145RSA因數分解挑戰(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算法的速度由于都是大數計算，RSA最快的情況也比DES慢許多倍，無論是軟件還是硬件實現。速度一直是RSA的缺陷。一般來說只用于少量數據加密。RSA是被研究得最廣泛的公鑰算法，提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一148本講內容6、公鑰密碼的特征總結公開密鑰算法設計需要有以下基本要求：加密與解密由不同的密鑰完成；知道加密算法，從加密密鑰得到解密密鑰在計算上是不可行的；兩個密鑰中任何一個都可以作為加密而另一個用作解密。公鑰密碼的特征公鑰密碼算法基礎單向函數

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

y

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

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

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

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

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

通信保密

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

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

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

報文vs.

明文

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

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

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

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

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

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

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

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

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

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

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

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

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