信息安全導論（以問題為導向） 課件 01 古典密碼-第一部分

古典密碼（1）-ClassicalEncryptionTechniques1教學視頻、國家級一流在線課程鏈接：/course/FUDAN-12063578111.古典密碼

1.1對稱密鑰密碼模型

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

firstattesteduseinmilitaryaffairsexample:meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWB7Terminologiesplaintext-theoriginalmessageciphertext-thecodedmessagekey-infousedincipherknownonlytosender/receiverencipher(encrypt)-convertingplaintexttociphertextdecipher(decrypt)-recoveringplaintextfromciphertextcipher-algorithmfortransformingplaintexttociphertext8SymmetricCipherModel9DefinitionAcryptosystemisa5-tuple

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

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

nothing

aboutthemsg)eavesdropperbla-blacmb-cmbbla-blaSharedKeyNeed

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

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

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

encryption:BothsenderandreceiverusethesamekeyAsymmetric,two-key,orpublic-key

encryption:thesenderandreceiveeachusesadifferentkey23CryptographyCatalogThewayinwhichtheplaintextisprocessedBlock:processestheinputoneblockofelementsatatime,producinganoutput

block

foreachinputblockStream:processestheinputelementscontinuously,producingoutputoneelementatatime,asitgoesalong.242.如何設計好的密碼算法？

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

2.1

Caesar密碼與單字母表密碼

攻擊->防御->改進->更好的密碼算法->攻擊…螺旋式上升過程中領會密碼設計的關鍵問題26SubstitutionTechniquesCaesarcipherEasytobreak!27CryptanalysisofCaesarCipherThereareonly25keystotryAmapstoA,B,..Zcouldsimplytryeachinturnabruteforcesearch

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

hencekeyis26letterslong30MonoalphabeticCipherSecuritynowhaveatotalof26!=4x1026keyswithsomanykeys,mightthinkissecure

butwouldbe!!!WRONG!!!

problemislanguagecharacteristics31LanguageRedundancyandCryptanalysishumanlanguagesareredundant

lettersarenotequally

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

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

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

try

everykey

mostbasic

attack,proportionaltokeysizeassumeeitherknoworrecogniseplaintext36MoreDefinitionsunconditionalsecurity

nomatterhowmuch

computerpowerisavailable,theciphercannotbebrokensincetheciphertextprovidesinsufficientinformationtouniquelydeterminethecorrespondingplaintextcomputationalsecurity

givenlimited

computingresources(eg.timeneededforcalculationsisgreaterthanageofuniverse),theciphercannotbebroken

Unconditionalsecuritywouldbenice,buttheonlyknownsuchcipheristheone-timepad(later).Forallreasonable

encryptionalgorithms,havetoassumecomputationalsecuritywhereiteithertakestoolong,oristooexpensive,tobother

breakingthecipher.372.如何設計好的密碼算法？

2.2

Playfair密碼

攻擊->防御->改進->更好的密碼算法->攻擊…螺旋式上升過程中領會密碼設計的關鍵問題38MonoalphabeticCipherSecuritynowhaveatotalof26!=4x1026keyswithsomanykeys,mightthinkissecure

butwouldbe!!!WRONG!!!

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

Playfair“一”對“多”

Vigenère40PlayfairCiphernoteventhelargenumberofkeysinamonoalphabeticcipherprovidessecurity

oneapproachtoimprovingsecuritywastoencryptmultiplelettersthePlayfairCipherisanexampleinventedbyCharlesWheatstonein1854,butnamedafterhisfriendBaronPlayfair

4142PlayfairKeyMatrixa5X5matrixoflettersbasedonakeywordfillinlettersofkeyword(sansduplicates)fillrestofmatrixwithotherletterseg.usingthekeywordMONARCHYMONARCHYBDEFGIKLPQSTUVWXZ43EncryptingandDecryptingplaintextencryptedtwolettersatatime: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)44SecurityofthePlayfairCiphersecuritymuchimproved

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

2.3

Vigenère密碼

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

calledpolyalphabetic

substitution

ciphers

makescryptanalysisharderwithmorealphabetstoguessandflatterfrequencydistributionuseakeytoselectwhichalphabetisusedforeachletterofthemessageuseeachalphabetinturnrepeatfromstartafterendofkeyisreached47VigenèreCiphersimplestpolyalphabeticsubstitutioncipheristheVigenèreCipher

effectivelymultiplecaesarcipherskeyismultipleletterslongK=k1k2...kdithletterspecifiesithalphabettouseuseeachalphabetinturnrepeatfromstartafterdlettersinmessagedecryptionsimplyworksinreverse48VigenèreCipher49PlaintextKeyExamplewritetheplaintextoutwritethekeywordrepeatedaboveituseeachkeyletterasacaesarcipherkeyencryptthecorrespondingplaintextletteregusingkeyworddeceptiveKey:deceptivedeceptivedeceptivePlaintext:wearediscoveredsaveyourselfCiphertext:ZICVTWQNGRZGVTWAVZHCQYGLM