信息安全基础2(密码编码学与网络安全).ppt

Chapter2Cryptography 2012 FoundationofInformationSecurity 1 2 3 4 Overview OverviewofCryptography ClassicalCiphers BlockCiphers 5 6 1OverviewofCryptography 1 1HistoryofCryptography 1 2Cryptosystem 1 3Cryptanalysis 1 4Cryptography Before1949 ClassicalEncryption古典加密Beforecomputerwasinvented cryptographywasartmorethanscience Thereweresomecipheralgorithms encryptionmachines simplecryptanalysis密码分析ways Themainencryptionobjectsarealphabetcharacter Thesecurityofdataisbasedonthesecrecyofalgorithms 1 1HistoryofCryptography密码学历史 ThePhaistos 1700BC EncryptionMachinesinEarly20thCentury 1949 1976 Shannonpublished TheCommunicationTheoryofSecretSystems in1949 whichindicatedcryptographybecameaformalsubject Thedevelopmentofcomputerenabledciphersoncomplexcomputing Thesecurityofdataisbasedonthesecrecyofsecretkeyinsteadofcipheralgorithm HistoryofCryptography cont d After1976 Diffie Hellmanpublished NewDirectionsinCryptography in1976 inwhichputforwardasymmetriccryptography不对称密码体制 Rivest Shamir AdlemanbringforwardRSApublickeyalgorithm Publickeycryptographyenablessecretcommunicationwithoutkeytransmissionbetweensender receiverwhichiswellfitfordigitalsignature数字签名 HistoryofCryptography cont d Diffie Hellmanpublished NewDirectionsinCryptography in1976GovernmentoftheUnitedStatesenacted颁布 DataEncryptionStandard DESin1977GovernmentoftheUnitedStatesenactednewencryptionstandard EESin1993DoctorfromtheBellLabbrokeEESin1995DESwasbrokenin1997GovernmentoftheUnitedStatesrecruited征集newstandardforcomputerencryption AESallovertheworldin1997AESwasenactedin2001afterstrictselection Memorabilia大事记ofModernCryptography HypothesizethatattackerknowsthecipheralgorithmusedSecurityofacryptosystemshouldrelyonthesecrecyofthekeyinsteadofthecipheralgorithmAsaresult thedesignofcryptosystemshouldfollowthepublicprinciple Kerckhoffs Principle 1883 Definition Cryptography密码编制学studyofencryptionprinciples methods Cryptanalysis密码分析学studyofprinciples methodsofdecipheringciphertext密文withoutknowingkey Cryptology密码学thefieldofbothcryptographyandcryptanalysisPrincipleCamouflaging伪装message preventingunauthorizeduserfromknowingwhatitmeans 1 2Cryptosystem密码体制 Plaintext Message 明文 theoriginalmessageCiphertext密文 thecodedmessageKey密钥 infousedinencryption decryption knownonlytosender receiver whichshouldbekeptsecretK Encipher加密算法 encrypt convertingplaintexttociphertextC E M Ke Decipher解密算法 decrypt recoveringplaintextfromciphertextM D C Kd ComponentofCryptosystem Tworequirementsforsecureuseofsymmetricencryption对称加密 astrongencryptionalgorithm asecretkeyknownonlytosender receiverAssumeencryptionalgorithmisknownExistasecurechanneltodistributekey Requirements CiphertextCxlcm CiphertextCxlcm cryptanalyst Source Destination encryptionkey decryptionkey PlaintextMlove securechannel Ke Kd Key Encryption PlaintextMlove channel Decryption Contentsofkeepsecret Restrictedalgorithm secrecyofalgorithm ClassicalCipher Key basedalgorithm secrecyofkey ModernCipherNumberofkeysused Hashfunctions nokey Secretkeycryptography onekey SymmetricCipher对称密码 ConventionalCipher传统密码 Single KeyCipher单钥密码 Publickeycryptography twokeys public private AsymmetricCipher非对称密码 Public KeyCipher公钥密码 Two KeyCipher双钥密码 Wayinwhichplaintextisprocessed Block分组密码 processinput outputasblock Stream流密码 序列密码 processinput outputasbitorcharacter ClassificationofCryptography SymmetricCipherKe KdAsymmetricCipherKe KdKeKdSo makeKepublic keepKdsecret SymmetricCipher AsymmetricCipher ConventionalCipher BlockCipherDESIDEAEESAES StreamCipherRC4PublicKeyCipher RSAElGamalECC ExamplesofModernCipherType AdvantagesofConventionalCipher speedyforencryption decryptionDisadvantagesofConventionalCipher hardtodistribute managekey realizedigitalsignatureAdvantagesofPublicKeyCipher easytodistribute managekey realizedigitalsignatureDisadvantagesofPublicKeyCipher hardtogeneratekey slowforencryption decryption Advantages Disadvantages Definition TheprocessofattemptingtodiscoverMorKorbothisknownascryptanalysis BruteForceAttack暴力破解攻击 穷举攻击 StatisticsAnalyseAttack统计分析攻击MathematicsAnalyseAttack数学分析攻击 1 3Cryptanalysis Decryptciphertextbytryingeverypossiblekeyaccordingtothelengthofkeyspace untilgettingpossiblerightplaintextCanbreakanycryptosystembytheoryOnaverage halfofallpossiblekeysmustbetriedtoachievesuccess BruteForceAttack BruteForceAttack cont d Mostbasicattack proportionaltokeynumber timeofonedecryptionAssumeeitherknow recogniseplaintextAverageTimeRequiredforExhaustive无遗漏的KeySearch Compare analyzethestatisticalcharacterofplaintext ciphertextCanbreakalmostallclassicalciphers StatisticsAnalyseAttack AnalyzeaccordingtothemathematicaltheoryMainwaytobreakpublickeycipher MathematicsAnalyseAttack Ciphertextonly惟密文 onlyknowalgorithm ciphertext statistical canidentifyplaintextKnownplaintext已知明文 know suspectcorrespondingpairsofplaintext ciphertexttoattackcipherChosenplaintext选择明文 selectplaintextandobtainciphertexttoattackcipherChosenciphertext选择密文 selectciphertextandobtainplaintexttoattackcipherChosentext选择文本 selecteitherplaintextorciphertexttoen decrypttoattackcipher ClassifybyResourcesCryptanalystGets Unconditionalsecurity绝对安全 Nomatterhowmuchcomputerpowerisavailable theciphercannotbebroken Onlyone timepadscheme Shannon qualifies合格One timepad一次一密 absolutelyunbreakable永不可破 Usearandomkeywhichisaslongasthemessage withnorepetitions Plaintextandciphertextarestatisticallyindependent Keygeneration distributionisofdifficulty Unconditionalvs ComputationalSecurity Computationalsecurity计算上的安全 Thecostofbreakingthecipherexceedsthevalueoftheencryptedinfo代价 Thetimerequiredtobreakthecipherexceedstheusefullifetimeoftheinfo MorK 时间 Unconditionalvs ComputationalSecurity cont d Diffusion扩散 dissipatesstatisticalstructureofplaintext keyoverbulkofciphertextConfusion混淆 makesrelationshipbetweenciphertextandkeyascomplexaspossibleIterationofproduct乘积迭代 Usesdiffusion confusioninsuccession连续 1 4Cryptography密码编制学 2ClassicalCiphers 20 8 1 14 11 25 15 21 9 12 15 22 5 25 15 21 trytodecipherit Cryptography theWorldWarII ThePearlHarborIncidentwasonDecember7 1941 CounterminingofUSA美国将计就计 JapanesePurple紫密AmericanMagic魔码 MidwayNavalBattles中途岛战役 theTurningPointofWWII JapaneseNavy sJN25werebrokenbyAmericanMilitaryin1942IsorokuYamamoto山本五十六diedofinformationdecodingin1943Thesuccessofdeciphercutthewarlengthas8yearsatleast Substitution Permutation Transposition代换和置换 Substitution Lettersofplaintextarereplacedbyotherlettersorbynumbersorsymbols Plaintextisviewedasasequenceofbits thensubstitutionreplacesplaintextbitpatternswithciphertextbitpatterns ModifiedHieroglyphics象形文字1900B C Egypt Substitution Permutation Transposition cont d Permutation Transposition Hidethemessagebyrearrangingtheletterorderwithoutalteringtheactuallettersused SpartanScytale斯巴达棍500B C ClassificationofClassicalCipher SubstitutionCipher代换密码 Single lettersubstitution单字母代换Monoalphabeticsubstitution单表ShiftCipher移位密码 加法密码 MultiplicativeCipher乘法密码AffineCipher仿射密码Homophone同音字Polyalphabeticsubstitution多表VigenereCipher维吉尼亚密码VernamCipher弗纳姆密码RotorMachine转轮机 Multiple lettersubstitution多字母代换PlayfairHillPermutation TranspositionCipher置换密码RailFencecipher栅栏密码ColumnarTranspositionCipher列置换密码 2 1SubstitutionCipher 2 2PermutationCipher 2 1SubstitutionCipher 2 1 1Definition 2 1 2ShiftCipher 2 1 3Homophone 2 1 4VigenereCipher 2 1 5VernamCipher 2 1 6Playfair 2 1 7RotorMachine 2 1 1Definition Single lettersubstitution单字母代换Mappingofaplaintextlettertoacorrespondingciphertextletterindependently Monoalphabeticsubstitution单表代换Uniquemappingofaplaintextalphabettoaciphertextalphabet Polyalphabeticsubstitution多表代换MappingofaplaintextalphabettoseveralciphertextalphabetsMultiple lettersubstitution多字母代换Lettermappingisdependentonitspositiononthecontext whichmaybemanagedingroups 2 1 2ShiftCipher移位密码 CaesarCipher凯撒密码2000yearsago earliestknownmonoalphabeticsubstitutioncipher byJuliusCaesarReplaceeachletterbythefollowing3rdletterExamplemeetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWB CaesarCipher cont d DefinetransformationasabcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCC LQIRUPDWLRQVHFXULWBP Mathematicallygiveeachletterasequencenumberabcdefghijklmnopqrstuvwxyz012345678910111213141516171819202122232425DefineUniversalCaesarCipherasC E m m k mod26p D C C k mod26K 1 25 CaesarCipher cont d Onlyhave26possibleciphers 25useful AmapstoB Z keyspace 25 Givenciphertext justtryallshiftsoflettersAbruteforcesearchof25possibilitiestoattackuniversalCaesarcipher Brute ForceCryptanalysis CiphertextonlyattackCharacteristicsforsuccess Theencryptionanddecryptionalgorithmsareknown Thereareonly25keystotry Thelanguageoftheplaintextisknownoreasilyrecognizable ShufflingCipher置乱密码 Ratherthanshiftingthealphabet shuffle打乱thelettersarbitrarily eachplaintextlettermapstoadifferentrandomciphertextletterMessage ciphertext EnglishalphabetA ZKey therelevantrelationshipbetweenthemessagealphabet theciphertextalphabetExample Message DANGERHELPME Ciphertext ZBWUOEAOCQRO Keysize 26Keyspace 26 4x1026Foralongtimethoughtsecure buteasilybreakablebyfrequencyanalysisattack频率分析攻击 Arabianscientistsin9thcentury Why Languagecharacteristics Lettersofhumanlanguagearenotequallycommonlyused StatisticsAnalyseCryptanalysisonShufflingCipher RelativeFrequencyofLettersinEnglishText FrequencyStatisticsofLanguage Inadditiontothefrequencyinfoofsingleletters thefrequencyinfooftwo letter digram双字母 orthree letter trigram三字母 combinationscanbeusedforthecryptanalysisMostfrequentdigrams TH HE IN ER AN RE ED ON ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET IT AR TE SE HI OFMostfrequenttrigrams THE ING AND HER ERE ENT THA NTH WAS ETH FOR DTH Example P25 26 GivenciphertextUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQCountrelativeletterfrequencies THE TH T E A O IT Example P25 26 Proceedingwithtryanderrorfinallyget UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ HA E EEN B T O ITI A VF BA PY UI LX CH V B U PLCL Example P25 26 CiphertextUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQMessageitwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietcong越共inmoscow情报内容据悉昨天在莫斯科有一些非正式但是直接与越南共产党的政治代表的接触 2 1 3Homophone同音词 InventedbyMathematicianGaussAtypeofmonoalphabeticsubstitutionMappingofaplaintextlettertoseveralcorrespondingciphertextletters theamountofcipherlettersforoneplaintextletterisproportionaltothefrequencyoftheplaintextletterusedIftheamountofcorrespondingciphertextletterismorethanone differentlettershouldbechosenforeveryencryption Example A316299431476852B8771C80267D11406293E2152837544160738990215776F970G3482H99435124017I4192781334666J100K39L1451496M1088N1352036695049O618957459482330P9153Q101R927942581238S354461568577T82563557264869798U326583V78W6775X102Y2284Z103P informationsecurityC ShortcomingofHomophone AplaintextletteronlyaffectsoneorseveralciphertextlettersfixedlyDigram trigramfrequenciesstillsurviveintheciphertextTwoapproachesforthisproblem UsemultiplealphabetsPolyalphabeticsubstitution EncryptmultiplelettersMultiple lettersubstitution 2 1 4Vig nereCipher 1553 Best knownpolyalphabeticsubstitutionciphersEachkeyletterdeterminesoneof26Caesar shift ciphersRepeatfromstartafterendofkeyisreachedMakescryptanalysisharderwithmorealphabetstoguessandflatfrequencydistribution Vig nereCipher cont d Multiple 26 CaesarciphersKeywordisrepeatedtomakeakeyaslongastheplaintextCi pi ki mod26ki a zExample Thelengthofkeyism keyspaceis26m Key deceptivedeceptivedeceptivePlaintext wearediscoveredsaveyourselfCipheretxt ZICVTWQNGRZGVTWAVZHCQYGLMGJ Vig nereCipher cont d KasiskiTest synchronization同步 Have26possibleciphertextlettersforeachplaintextletterHenceletterfrequenciesareobscured不明显Butnottotallylostfortheshortlength repeatingusingofkeyGivenasufficientamountofciphertext commonsequencesarerepeated exposingtheperiod keywordlength Onetargetofthecryptanalysis Key deceptivedeceptivedeceptivePlaintext wearediscoveredsaveyourselfCipheretxt ZICVTWQNGRZGVTWAVZHCQYGLMGJ KasiskiTest cont d RepetitionsinciphertextgivecluestokeyperiodIfthedistanceoftwosameplaintextsequencesisthemultiplesofkeylength we llgettwosameciphertextsequencesegrepeated VTW inpreviousexampleSuggestskeysizeof3or9 KasiskiTest cont d KeysizeisshortBruteforceattack keyspace 26nKeysizeislongAssumethatkeywordlengthisn thenVigen recipher ineffect consistsofnmonoalphabeticsubstitutionciphers Analyzeeachoftheciphersseparatelybysingle letterfrequencyanalysisattackforntimestogetnkeys1 2 n 1 n1 n 2 n 2n 1 2n1 2n 2 2n 3n 1 3n1 3n 2 3n 4n 1 4n k1k2kn 1kn AutokeyCipher密钥自动生成系统 Vigen reautokeysystem afterkeyisexhausted useplaintextforrunningkey toeliminatetheperiodic周期性nature Aminorerrorcausedbydecryptionmayleadtoconsequentialdecryptionerrorsatfix lengthintervals间隔overawidearea Key deceptivewearediscoveredsavPlaintext wearediscoveredsaveyourselfCipheretxt ZICVTWQNGKZEIIGASXSTSLVVWLA AutokeyCipher cont d Keyandplaintextsharethesamefrequencydistributionofletters sostatisticaltechniquecanbeusedforthecryptanalysise g eencipheredwithewouldoccurwithafrequencyof 0 1275 2 0 0163 tencipheredwithtwouldoccurwithafrequencyof 0 0925 2 0 0086Takethecommonlyusedtrigram the asapartofplaintext key shiftingittogetmorecluesforcryptanalysis ref en wikipedia orgforautokeycipher 2 1 5VernamCipher InventedbyGilbertVernamin1918StreamCipher onbit notonletterCi pi kipi Ci kiSecurityresidesontherandomicity随机性ofkey Commoncryptanalysisisbasedonthefactthatthesameshortkeyisusedrepeatedly easyforthestorage distribution BruteForceAttackonVigenereCipher Cipheretxt TryingKey Message WhyDoWeNeedOne timePad Keylength 3 abd abd eam heq NO Commoncryptanalysisisbasedonthefactthatthesameshortkeyisusedrepeatedly easyforthestorage distribution BruteForceAttackonVigenereCipher Cipheretxt TryingKey Message WhyDoWeNeedone timePad The4 groupmessage ciphertextshowthecommonrelevance Keylength 3 bbc bbc dan ger bbc bbc hel pme YES Keyspace 263 17576 HowCanKeyBeSafer AssumethatKeyisaslongasthemessageCipheretxt ZICVTWQNZICVTWQNPossibleKey RXOAPYCTRBCCPYCTMessage ILOVEYOUIHATEYOUWhichoneistruekey AnalysisHardtojudgebecauseM CarenotrelevantGivenanymeaningfulmessageofequallengthtotheciphertext theremustexistakeytoproducethatmessage IsaveyouIkillyouCalmdownSpiritup One timePad JosephMauborgneintroducedtheideaandShannonprovedthecorrectnessKeyisaslongasthemessage withnorepetitionsPlaintextandciphertextarestatisticallyindependentUnconditionallysecure Unbreakable Onlyusedinmilitaryuseforthedifficultyofkeygeneration distribution 2 1 6Playfair InventedbyCharlesWheatstonein1854 butnamedafterhisfriendBaronPlayfairBest knownmultiple lettersubstitution encryptmultiplelettersatonetime Digramcipher digramtodigram i e E pipi 1 cici 1throughkeyword based5x5transformationtable PlayfairMatrix A5X5matrixoflettersbasedonakeywordFillinlettersofkeywordFillrestofmatrixwithotherletterseg usingthekeywordMONARCHY Keyword monarchyPlaintext HSEAARMUCiphertext BPIMRMCMJM Encrypting Encrypttwolettersatatime 1 Ifapairisarepeatedletter insertafillerlike X Z eg balloon encryptsas balxloon 2 Ifbothlettersfallinthesamerow replaceeachwithlettertoright wrappingbacktostartfromend eg ar encryptsas RM 3 Ifbothlettersfallinthesamecolumn replaceeachwiththeletterbelowit againwrappingtotopfrombottom eg mu encryptsto CM 4 Otherwiseeachletterisreplacedbytheoneinitsrow inthecolumnoftheotherletterofthepaireg hs encryptsto BP and ea to IM or JM SecurityofthePlayfairCipher Stillhasmuchofplaintextstructure digram eg th he canbebroken givenafewhundredlettersSincehave26x25 650digrams needa650entryfrequencytabletoanalyse verses26forsingle letter Widelyusedformanyyears eg British USmilitaryinWW1 2 RelativeFrequencyofOccurrenceofLetters 2 2Permutation TranspositionCipher RailFencecipher栅栏密码Writemessagelettersoutdiagonally对角线overanumberofrowsThenreadoffcipherrowbyrowe g writemessageoutasmematrhtgpryetefeteoaatGetciphertextMEMATRHTGPRYETEFETEOAAT ColumnarTranspositionCipher列置换密码 AmorecomplexschemeMessageiswritteninrectangle矩形 rowbyrow butreadoffcolumnbycolumnThelengthofrectangle theorderofcolumnsreadoffisthekeyKey 4312567Plaintext attackpostponeduntiltwoamxyzCiphertext TTNAAPTMTSUOAODWCOIXKNLYPETZ Multiple stepTransposition多步置换 Multiple steptranspositionishardtoreconstructedKey 4312567Input ttnaaptmtsuoaodwcoIxknlypetzOutput NSCYAUOPTTWLTMDNAOIEPAXTTOKZTheoriginalsequenceofletters 01020304050607080910111213141516171819202122232425262728Afterthefirsttransposition 03101724041118250209162301081522051219260613202707142128Afterthesecondtransposition 17090527241612071002222003251513042319141101262118080628 ProductCiphers乘积密码 CiphersusingsubstitutionortranspositiononlyarenotsecurebecauseoflanguagecharacteristicsConsiderusingseveralciphersinsuccession连续tomakeharder twosubstitutionsmakeamorecomplexsubstitution twotranspositionsmakeamorecomplextransposition butasubstitutionfollowedbyatranspositionmakesanewmuchhardercipherAbridgefromclassicaltomodernciphers 2 1 7RotorMachine转轮机 Beforemodernciphers rotormachinesweremostcommonproductcipherwithmultiplesubstitutionsMechanicalciphermachines机械密码装置 extensivelyusedinWWII Germany Enigma Japan Purple Sweden Hagelin RotorMachine cont d EachrotorcorrespondstoasubstitutioncipherAone rotormachineproducesapolyalphabeticsubstitutioncipherwith26alphabetsAftereachpress therotorisrotated旋转byonescaleOutputofeachrotorisinputtonextrotorAfterafull roundrotation theadjacentrotorisrotated likeodometer里程表 byonescale An3 rotormachineproduces263 17576alphabets Three RotorMachines 3Steganography隐写术 HidemessagesinothermessagesAnalternativetoencryption encryption makeinformationunreadable steganography hidemessagetoconcealitsexistenceSimmons PrisonerProblem 1983 囚犯问题Artofcoveredwriting Charactermarking Invisibleink Pinpunctures Firstletterofeachword藏头诗 Letterpositiononpage Typewritercorrectionribbon Microdots微缩胶片Drawbacks highoverheadtohiderelativelyfewinfobitsbyusingredundancyofmedia Example NewsEightWeather Tonightincreasingsnow UnexpectedprecipitationSmothersEasterntowns Beextremelycautiousanduse