密码学-关键词加密法.ppt

经典单码加密法经典单码加密法KeywordCipherv1.selectakeyword-ifanylettersarerepeateddropthesecondandallotheroccurrencesfromthekeywordv1.选择一个关键词，如果这个关键词中有重复的字母，则去除第一次出现之外的所有相同字母。v2.writethekeywordbelowthealphabet,fillintherestofthespacewiththeremaininglettersinthealphabetintheirstandardorderv2.将关键词写在字母表的下方，并用字母表中除了关键词之外的其他字母按标准的顺序填写余下的空间。ExamplevThekeywordisMAGICNETABCDEFGHIJKLMNOPQRSTUVWXYZplaintextplaintextciphertextciphertextCNETBFDJHLKPORQUSWVXZYIMAG这样的话这样的话,明文字母明文字母A就由密文字母就由密文字母M来替换来替换，B则由则由A来替换，来替换，.明文：明文：HELPIAMLOST密文：密文：TCHOBMJHLRSExercisevThekeywordisCOUNTABCDEFGHIJKLMNOPQRSTUVWXYZplaintextplaintextciphertextciphertextTABDEGFIHKJMLQPSRWVXZYNCOUStartingPositionvThekeyworddoesnothavetostartatthebeginningoftheplaintextalphabet（关键词不从第一字母开始）itcouldstartatanyletterforexample,“count”couldstartat“k”ciphertextciphertextTABDEGFIHKJLMQPSRWVXZYNCOUABCDEFGHIJKLMNOPQRSTUVWXYZplaintextplaintextExamplevIfthekeywordis“visit”(note,thesecond“i”invisitisdroppedbelow)startingat“a”andtheplaintextis“next”,theapplicationis:ABCDEFGHIJKLMNOPQRSTUVWXYZplaintextplaintextciphertextciphertextLMNOPRQWUYXZVSIATCBDFEKGHJN E X TN E X TK K A A X XQ QKeywordinCAPv运行CAP软件，输入一些明文，然后从Cipher菜单选取Keyword菜单项，将弹出一个KeywordCipher窗口。关键词加密法的分析法关键词加密法的分析法v关键词加密法当然比简单移位加密法功能更强，因为要尝试所有的关键词及其位置，显然比所有25种移位加密密钥要困难得多。v这种攻击法的原理就是计算机用字典中的每个词进行尝试，直至找到一个能破解该加密法的为止。v用穷举查找攻击法（即尝试所有可能的关键词）在今天也是可行的，但不是可取的。BreakingaKeywordvThekeywordcipherisnotsecure,infactitiseasytobreakvOnereasonwhyitisusefultostudysuchacipheristhatinordertobreakthiscipheryoumustusesomeofthemostfundamentaltoolsofcryptanalysis（破译关键词密码需要一些密码分析基本工具）ChallengevConsiderasimplemonoalphabetickeywordsubstitutionciphersuchasthefollowing:GJXXNGGOTZNUCOTWMOHYJTKTAMTXOBYNFGOGINUGJFNZVQHYNGNEAJFHYOTWGOTHYNAFZNFTUINZBNFGNLNFUTXNXUFNEJCINHYAZGAEUTUCQGOGOTHJOHOATCJXKHYNUVOCOHQUHCNUGHHAFNUZHYNCUTWJUWNAEHYNAFOWOTUCHNPHOGLNFQZNGOFUVCNZJHTAHNGGNTHOUCGJXYOGHYNABNTOTWGNTHNTXNAEBUFKNFYOHHGIUTJUCEAFHYNGACJHOATAEIOCOHUFQXOBYNFGBasicCryptanalysisvThemostbasicobservationofcryptanalysisisthateveryletterofalanguagehasapersonalityofitsownifeveryplaintexttischangedtoaciphertextm,thenintheciphertext,massumesthepersonalityofttothetrainedobserver,thepersonalityofalettergivesawayitsidentity对训练有素的观察者来说，字母的特性揭示了其真实面目。vSomeofthesepersonalitycharacteristicsare:frequencyofoccurrencecontactwithotherletterspositionwithinwords字母的特性主要有：出现的频率、与其他字母的联系、在单词中的位置。LetterFrequencyvWhatisthemostfrequentletterinEnglish?vActuallythefrequencydependsonthetypeoftext.Awidelyusedfrequencytableof400lettersofstandardEnglish（英文字母的频率）Letter:A B C D E F G H I J K L M N O P Q Count:32 6 12 16 42 8 6 24 26 2 2 14 12 28 32 8 1 Letter:R S T U V W X Y Z Count:26 24 36 12 4 6 2 8 1 In Order:ETAONIRSH DLUCMPFYWGB VJKQXZLetterFrequencyvThefrequencycountforthechallengetextis:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z17 4 13 0 7 17 23 26 5 12 3 2 2 36 25 1 5 0 0 23 20 3 6 9 13 8 We could compare this with the expected frequency:Standard:ETAONIRSHDLUCMPFYWGBVJKQXZ Cipher:NHOGTUAFCYJXZEWIQBKVLMPDRS（密文）（密文）Result:OLUUE OOANC EIHAN PJATD.However,while relative frequencies may shift slightly,(i may be more frequent than a),they do not stray far from their area in the frequency tableLetterFrequencyv当然，这只是个概数，不会与每篇文章的字母出现频率完全一样，通常越短的信息的字母频率与上面的相比就越不相符，越短的信息也就越难破解了。如：John,ajazzist,willgotoJapaninJunetojoinajazzparty.其中，J的百分比是12.8，出现6次，而E的百分比是0，对其进行频率分析就毫无意义。又如：UOCTXH.若明码表ABCDEFGHIJKLMNOPQRSTUVWXYZ密码表QWERTYUIOPASDFGHJKLZXCVBNM则它被翻译为GIVEUP.但若明码表ABCDEFGHIJKLMNOPQRSTUVWXYZ密码表QWUETRYIXPASCHOMDFGJKLZVBN则它被翻译为COMEIN.究竟哪个是真的，不得而知。但当它放进一篇文章里，就可从前后推知它应怎样翻译了。FrequencyGroupsvHighFrequencyGroupETAONIRSHvMediumFrequencyGroupDLUCMvLowFrequencyGroupPFYWGBVvRareGroupJKQXZ字母在分组中的位置可能会字母在分组中的位置可能会字母在分组中的位置可能会字母在分组中的位置可能会发生变化，但很少会出现在发生变化，但很少会出现在发生变化，但很少会出现在发生变化，但很少会出现在其他的分组中去。其他的分组中去。其他的分组中去。其他的分组中去。SingleFrequencyReasoningvThingstolookforinafrequencyreportIftherearehillsandvalleyssimilartostandardEnglishthenthecipherismostlikelyasubstitution,so（密文字母频率的高峰低谷部分）Findthebreakbetweenhighfrequencyandmediumfrequency(lookfora2%dropbetweentwoletters)Themostfrequentletterisprobably“e”oratleast“t”or“a”WARNING:this is only useful if you have enough text to maintain the“average”picture of frequency distributionsFrequencyReportvAgainconsiderthefrequencycountforthechallenge:N H O G T U A F C Y J X Z E W I Q B K V L M P D R S36 26 25 23 23 20 17 17 13 13 12 9 8 7 6 5 5 4 3 3 2 2 1 0 0 0Where is the break-that is,which set of characters are in the Where is the break-that is,which set of characters are in the high frequency group?high frequency group?Out of the possible high frequency group which is e?Out of the possible high frequency group which is e?ChallengeDigramsvThischartliststhedigramsformedbythemostfrequentlettersintheciphertext:First task-identify(or confirm)eFirst task-identify(or confirm)eN is a good possibility by frequency countsN also contacts more characters than any other(17-look at the full digram table)N H O G T U A FN 0 3 0 4 1 0 1 3H 1 2 4 2 4 1 1 2O 0 4 0 6 1 0 0 1G 5 1 4 2 0 2 0 3T 4 2 7 0 0 4 2 1U 5 1 1 0 3 0 0 2A 5 1 2 2 3 0 0 0F 7 0 1 0 0 3 4 0确定字母EConsonants（辅音）（辅音）vTheeasiesttospotisNbecause80%ofthelettersthatprecedenarevowels（字母N前的字母80%为元音字母）lookforahighfrequencyletterwhichmostoftenfollowsavowelforthechallengetext,Tfollowsoneofthevowels(N,O,U,A)17outof23timesvhfrequentlyappearsbeforeeandalmostneverafterit（h通常在e前）inthechallenge,thepairYNoccursfrequentlybutNYneveroccursvthiscommonifYisreallyh,thenHmustbetbecausethiscommon有用的经验有用的经验ththhehe组合非常常见组合非常常见组合非常常见组合非常常见CurrentStatus（当前状态）（当前状态）vUsingourbestguess,thekeylookslike plain:A B C D E F G H I J K L M N O P Q R S T U V W X Y Zcipher:UNY OT AH1.ht,yh,ne二连三连2.Tn（ot，nt较多）3.otin还是oton?4.Ua,A-oChallengeTextG J X X N G G O T Z N U C O T W M O H Y J T K T A M T X O B Y N F G O G I N U G E I N E A I N I T H N N O N I H E I E AJ F N Z V Q H Y N G N E A J F H Y O T W G O T H Y N A F Z N F T U I N Z A N F G E T H E E O T H I N I N T H E O E N A E O EN L N F U T X N X U F N E J C I N H Y A Z G A E U T U C Q G O G O T H J O H O AE E A E A E E T H O O A N A I I N T I T I OT C J X K H Y N U V O C O H Q U H C N U G H H A F N U Z H YN T H E A I I T A T E A T T O E A T HWheel of Fortune Time-are there any words?Update plain:A B C D E F G H I J K L M N O P Q R S T U V W X Y Zcipher:U N Y O T A HG J X X N G G O T Z N U C O T W M O H Y J T K T A M T X O B Y N F G O G I N U G E I N E A I N I T H N N O N I H E I E AJ F N Z V Q H Y N G N E A J F H Y O T W G O T H Y N A F Z N F T U I N Z A N F G E T H E E O T H I N I N T H E O E N A E O EN L N F U T X N X U F N E J C I N H Y A Z G A E U T U C Q G O G O T H J O H O AE E A E A E E T H O O A N A I I N T I T I OT C J X K H Y N U V O C O H Q U H C N U G H H A F N U Z H Y.N T H E A I I T A T E A T T O E A T HMJWUWUUUUUUKKKLVWGGGSSSSSSSSSSSSSXCCCCCCCQLYYLLLLLYorderVZD BDDDDDBKeyword?ERIB D FPSPRMRFRRRMRRMRFNFR练习练习分组练习分组练习Examplev阿拉伯人的破译方法是阿拉伯人的破译方法是频率分析法频率分析法，下面先说说各字母在英语文章，下面先说说各字母在英语文章中出现的频率中出现的频率（百分比）（百分比）A:8.2N:6.7B:1.5O:7.5C:2.8P:1.9D:4.3Q:0.1E:12.7R:6.0vF:2.2S:6.3G:2.0T:9.1H:6.1U:2.8I:7.0V:1.0J:0.2W:2.4K:0.8X:0.2L:4.0Y:2.0M:2.4Z:0.1顺序是顺序是ETAOINSHRDLUCMWFGYPBVKJXQZExamplev.YSZXENATRXZRGZEXMEDYLT1640CNZNZERYBCNZKEMOZXSLUUZBEHLUGFEMMLXNADYKEMOZXSLUUZNZFEMEFLURETRZSLUHETNZFEMPXAZUETRZTVYGZRNATCLTDWZYWUZMLXNADYBZUULTUYSZFLCNCNZREADNCZXYBEBEXHZXFNYFEMETZLDNKYAXYBNLMCNZGYATDFYHETFEMEBXELRYBCNZZSLUNADYETRESYLRZRNLHYTZREGNADYNZEXRCNECNZXBECNZXETRKXYCNZXMFZXZEFEGNZOTZFCNECMNZFYAURKZEUYTZMYNZXYRZCYCNZBEXHFLCNBLSZYXMLIYBNLMZSLUBXLZTRMCNZGHERZCNZDLXUDYKEPOCYKEMOZXSLUUZNEUUFLCNCNZHETRUYPOZRNZXLTEXYYHAWMCELXMCNZTCNZGMECRYFTLTCNZDXZECRLTLTDNEUUCYRXLTOEMAMAEUCNZGRXETOKYCCUZEBCZXKYCCUZETRMYYTCNZGKZDETCYMLTDETRUEADNETRMNYACZSLUFYXRM.（约550个字母）Examplev先对它进行频率分析（出现次数先对它进行频率分析（出现次数/百分比）百分比）A:16/2.9N:46/8.4B:14/2.5O:8/1.5C:38/6.9P:3/0.5D:16/2.9Q:0/0.0E:54/9.8R:29/5.3F:17/3.1S:11/2.0G:10/1.8T:35/6.4H:9/1.6U:29/5.3I:1/0.2V:1/0.2J:0/0.0W:3/0.5K:10/1.8X:34/6.2L:34/6.2Y:41/7.5M:27/4.9Z:65/11.8v标准顺序：ETAOINSHRDLUCMWFGYPBVKJXQZv本样本：ZENYCTXLRUMFADBSKGHPWIVQJOExamplev可发现E，Z出现的频率很高，那么我们可假设ZE，EA或ZA，EE。看看原来的文章，其中E以单字母单词出现，那么基本上ZE，EA。（还有些辨别E和A的方法，如一般文章中EE出现的频率比AA高）再来看看，CNZ，ETR作为三字母单词出现多次，那么他们有可能分别是THE和AND那么CT，NH，TN，RD。再说，文章中C，N，T，R出现的频率分别是：6.9，8.4，6.4，5.3，除了C有一点偏差以外，其余的和标准频率都差不多，不妨继续下去。又看看，文章中出现过LT1640。若TN的话，L就应该是I了，原文中LTCNZ就是INTHE了，上面的推理应该无误。Examplev又看文中，出现了又看文中，出现了CNZNZERYBCNZKEMOZXSLUUZ，YB也出也出现过几次，而我们知道现过几次，而我们知道CNZTHE，那么这是不是，那么这是不是THEXXXXOFTHEXXXXXXXXXXX呢，呢，YBOF？Y，B出现的频出现的频率是率是7.5，2.5，标准频率中，标准频率中O，F出现的频率是出现的频率是7.5，2.2，好像是吧？，好像是吧？而后面出现过几个而后面出现过几个CY，就是，就是TO了，英文中了，英文中TO出现的频率也颇高，就出现的频率也颇高，就又证实了自己的推理。又证实了自己的推理。当我们解密的时候，除了大胆假设，还要不时运用其他证据来证实自当我们解密的时候，除了大胆假设，还要不时运用其他证据来证实自己的推理，否则很容易到了最后才发现自己的错误，那又要花大量时己的推理，否则很容易到了最后才发现自己的错误，那又要花大量时间重头做起了。间重头做起了。现在找找和现在找找和Y有关的单词，可发现文中有一个有关的单词，可发现文中有一个MY，有可能是，有可能是NO和和SO，假设是，假设是NO，那与后面的，那与后面的NZ（HE）就组成）就组成NOHE，好像不大通顺，好像不大通顺，如果是如果是SOHE就比较通顺了，就比较通顺了，M应该就是应该就是S了。接着，由了。接着，由NLH和和HET推出推出HM，又推出，又推出FYHET和和FNY中中FW，从，从1640知道文章使用过知道文章使用过去时态，那么去时态，那么FEM代表代表WAS应是正确的。应是正确的。Examplev明码表ABCDEFGHIJKLMNOPQRSTUVWXYZ密码表ERZBNLHTYMCFtobecontinued.将其代入原文，得：.oSeXahAndXedGeaXsaDoin1640theheadoftheKasOeXSiUUefamiUGwassiXhADoKasOeXSiUUehewasawiUdandeSiUmanhewasPXAeUandenVoGedhAntinDWeoWUesiXhADofeUUinUoSewiththedaADhteXofafaXmeXwhowasaneiDhKoAXofhistheGoAnDwomanwasafXaidoftheeSiUhADoandaSoidedhimonedaGhADoheaXdthatheXfatheXandKXotheXsweXeawaGheOnewthatshewoAUdKeaUonesoheXodetothefaXmwithfiSeoXsiIofhiseSiUfXiendstheGmadetheDiXUDoKaPOtoKasOeXSiUUehaUUwiththemandUoPOedheXinaXoomAWstaiXsthentheGsatdownintheDXeatdininDhaUUtodXinOasAsAaUtheGdXanOKottUeafteXKottUeandsoontheGKeDantosinDandUaADhandshoAteSiUwoXds.（小写的是替换后的）Examplev文中有句文中有句.thatheXBatheXandKXotheXsweXe.，可推出可推出XR，又由，又由oSeXahAndXedGeaXsaDo等提示可推出等提示可推出AU，SV，GY，DG。注意到文中有单词。注意到文中有单词haUU，查字典易知符，查字典易知符合条件的只有合条件的只有HALL，所以，所以UL。又有又有fiSeoXsiI，即，即fiveorsiI，那么，那么IX。由。由.theDiXUDoKaPOto.推出推出KB。由。由.heOnewthat.推出推出OK。由。由.enVoGedhAntinDWeoWUe.推出推出VJ，WP。由。由.hewasPXAeU.和结合上下文可知和结合上下文可知PC。那么就有：。那么就有：明码表明码表ABCDEFGHIJKLMNOPRSTUVWXY密码表密码表EKPRZBDNLVOUHTYWXMCASFIGExamplev最后整篇文章就出来了：.Overahundredyearsago,in1640,theheadoftheBaskervillefamilywasSirHugoBaskerville.Hewasawildandevilmanhewascruelandenjoyedhuntingpeople.SirHugofellinlovewiththedaughterofafarmerwhowasaneighbourofhis.TheyoungwomanwasafraidoftheevilHugo,andavoidedhim.Oneday,Hugoheardthatherfatherandbrotherswereaway.Heknewthatshewouldbealone.Soherodetothefarmwithfiveorsixofhisevilfriends.TheymadethegirlgobacktoBaskervilleHallwiththemandlockedherinaroomupstairs.Thentheysatdowninthegreatdininghalltodrink.Asusualtheydrankbottleafterbottleandsoontheybegantosingandlaughandshoutevilwords.v参考：http:/ provides all the tools you need to CAP provides all the tools you need to break a keyword cipherbreak a keyword ciphervThese includeThese includeFrequency AnalysisFrequency AnalysisLetter AnalysisLetter AnalysisA special worksheetA special worksheetCAPFrequencyAnalysisvSinceitisoneofthemostusefultoolsincryptanalysis,CAPprovidesafrequencyanalysiswindowFrequencyGraphvCAPwilldisplaythefrequencyinagraphSelecttheGraphmenuandclickonshowCAPVowelIDvCAPprovidesawindowtoaidintheidentificationofvowelsCAPConsonantIDvCAPalsoprovidesaconsonantIDwindowCAPWordIDvCAPwillsearchtheciphertextforpossiblewordpatternsCAPKeywordWorksheetvFinally,whenyouarecloseusethekeywordworksheettomanuallylookforwordsCAPRecordKeepingvCAPwillmonitoryoureffortAffineCiphervTheaffinecipherisanotherversionofasubstitutioncipherEachletterisassignedanumberA=0,B=1,.,Z=25Twonumbersareselected(a,b)between0and25suchthatthegcd(a,26)=1Letpandcrepresentletters(p,carenumbersbetween0and26)wherepisaplaintextletterandcisaciphertextletterthen:c=ap+bmod26p=a-1(c-b)mod26AffineCipherinCAPvSelectAffineundertheciphermenu.AffineExamplevSelectthekey(a,b)=(7,3)gcd(7,26)=17-1mod26=15(since7x15=105and105mod26=1)Thegeneralencipher/decipherequationsare:c=7p+3mod26“hot”is71419c(h)=7*7+3mod26=52mod26=0=ac(o)=7*14+3mod26=98mod26=23=xc(t)=7*19+3mod26=133mod26=6=gp=15(c-3)mod26BreakinganAffineCiphervHow would you break the affine cipher?The same way as a keyword cipheror,take advantage of the mathematical relationshipvGiven this ciphertext from an affine cipher find the key and plaintext:FMXVE DKAPH FERBN DKRXR SREFM ORUDS DKDVS HVUFE DKAPR KDLYE VLRHH RHAnalysis1vStartwithafrequencyanalysisoftheciphertextthemostfrequentlettersinorderare:RDEHKFSVAssumethatRis“e”andDis“t”thatimplies:c(4)=17c(19)=34a+b=1719a+b=3a=6,b=19WRONG,sincegcd(6,26)=2sotryanothercombinationAnalysis2vTryotherpossiblecombinations:R D E H K F S VetR=e,E=ta=13gcd(13,26)=13R=e,H=ta=8gcd(8,26)=2R=e,K=ta=3gcd(3,26)=1b=5Algorithms are quite general definitions of arithmetic processesTryontheciphertext:UsingCAPtobreakanaffineciphervCAPprovidesasimpleaffineanalysistoolMultiliteralCiphervAnothertypeofmonoalphabeticcipheriscalledamultiliteralcipherThisisanotherweakmonoalphabeticcipherthatisworthexaminingbecauseittriestodosomethingunique-itreplaceseachplaintextletterwithapairofletters.Theresultingciphertextistwiceaslargeastheplaintextandlooksverystrange.MultiliteralKeyvTheMultiliterialCipherkeyisa5x5matrix.Thefivecolumnsandthefiverowsareeachlabeledbythesame5letterkeyword.Thiskeywordcannothaveanyrepeatingletters.Thealphabetiswritteninthematrix.Sincethematrixhasonly25slotsbutthealphabethas26letters,sotheletters“i”and“j”occupythesamecell.Forexample,ifthekeywordis“codes”thenthekeymatrixbecomes:a b c d ea b c d ef g h i kf g h i kl m n o pl m n o pq r s t uq r s t uv w x y zv w x y zc o d e sc o d e sc co od de es s H e l pH e l podod cscs dc dc dsdsSummaryvMonoalphabetic CiphersKeywordAffineMultiliteral