信息安全导论（以问题为导向） 课件 01 古典密码-第一部分

古典密码（1）-ClassicalEncryptionTechniques1教学视频、国家级一流在线课程链接：/course/FUDAN-12063578111.古典密码

1.1对称密钥密码模型

SymmetricCipherModel2要解决的问题：通信保密安全需求SecurityRequirements安全服务SecurityServices保密性Confidentiality完整性Integrity可用性Availability3三个古典密码系统羊皮传书藏头诗Caesar4羊皮传书古希腊的斯巴达人将一条1厘米宽、20厘米左右长的羊皮带，以螺旋状绕在一根特定粗细的木棍上…...5藏头诗明才子唐伯虎：我爱兰江水悠悠，爱晚亭上枫叶稠。秋月溶溶照佛寺，香烟袅袅绕经楼。明朝解缙祝某宰相寿辰进诗：真真宰相,老老元臣,乌纱戴顶,龟鹤遐林.粗看"密文”,浑然诗句,颂扬兼祝愿,福禄寿全有;细究则密语藏头,挖苦带讽刺,诅咒"真老乌龟”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三个古典系统的再讨论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“谁是我们的敌人，谁是我们的朋友，这个问题是革命的首要问题”——毛选易用性秘密全部寓于密钥≠算法当公开，要看应用环境(商用，军用，……)开放的系统更安全，??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