{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2 " -1 4 1 {CSTYLE "" -1 -1 "Geneva" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 } 1 1 0 0 4 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 1 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Geneva" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 } {PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 256 1 {CSTYLE "" -1 -1 "Geneva" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 4 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 3" -1 257 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 17 "Frequency Attacks" }} {PARA 256 "" 0 "" {TEXT -1 57 "Using letter frequencies to attack mono alphabetic ciphers" }}{PARA 19 "" 0 "" {TEXT -1 37 "\251Mike May, S. J ., 2002, maymk@slu.edu" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "re start:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 251 "We have seen that one \+ of the major weaknesses of a monoalphabetic substitution cipher stems \+ from the fact that the distribution of letters is not random in Englis h, or in any natural language. We would like to use that fact to help us attack ciphers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 256 38 "Constructing a fr equency counting tool" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 251 "To mecha nize this kind of attack, we want a tool that does frequency counts fo r us. The first step is to use a procedure that strips out the specia l characters and converts lower case to upper case. (We will leave th e message as a string of numbers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 480 "specialCharacterStrip := proc(message)\n local mes sList, letter, messlength, messList2, i;\n messList := convert(messa ge, bytes):\n messlength := linalg[vectdim](messList);\n messList2 := [];\n for i from 1 to messlength do\n letter := messList[i]: \n if (letter > 64) and (letter < 91) then\n messList2 := [op(messList2), letter] fi:\n if (letter > 96) and (letter < 123 ) then\n messList2 := [op(messList2), letter-32] fi:\n od: \n messList2:\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "The nex t step is to count the number of occurrences of each character as well as the total number of characters producing a frequency vector." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 367 "shortCounter := proc(messag eList)\n local message2, letter, messlength, freqVector, i;\n mess length := linalg[vectdim](messageList);\n freqVector := linalg[vecto r](27, i->0):\n for i from 1 to messlength do\n letter:= messag eList[i] - 64:\n freqVector[letter] := freqVector[letter]+1:\n \+ freqVector[27] := freqVector[27]+1:\n od:\n freqVector:\n end: " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 164 "Finally we put these two pro cedures together into a single procedure for convenience. For conveni ence we would like a procedure to print the output in a nice form." }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 677 "freqCounter := message -> \+ shortCounter(specialCharacterStrip(message)):\nfreqPrinter := proc(fre qVector)\n local message2, letter, messlength, freqcount, i, count era, \n temp0, temp1, temp2;\n temp1 := convert(freqVector[27 ],string):\n print(`The string had `||temp1||\n ` characters fr om the Latin alphabet.`);\n for countera from 1 to 26 do\n temp0 := convert(convert([64 + countera], bytes),string):\n temp1 := co nvert(freqVector[countera],string):\n temp2 := convert(evalf(\n \+ freqVector[countera]/freqVector[27]*100.0,4),string):\n print (`The letter `|| temp0 || ` appears `||temp1||` times,`||\n tem p2||`% of the time.`);\n od;\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 330 "Next we want to check out this routine with a reasonable strin g. Since we want to look at frequency counts as a way to attack codes , we want to look at a longer passage. The following is a paragraph f rom \"Pi in the Sky.\" (Note that double double quotation marks are u sed to put a double quotation marks symbol inside a string.)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1845 "message1 := \"Numbers domi nate much of our everyday lives in diverse and \nbarely perceptible wa ys. Parents are anious to see their children attain\ngood grades in m athematics, assured that this is a passport to success \nand security. The government stipulates that mathematical studies are\ncompulsory \+ for most of a child's time at school. Intelligence tests \ncontain pa rticular ingredients to test the candidates' ability to reason \nmathe matically. Advertisements promising challenging and well-paid \nemplo yment invite us to seek further details if we can successfully spot\nt he next number in puzzling sequences. Students change subjects when\n they discover the mathematical content of their course is too difficul t \nto master. Young children turn out to be extraordinarily talented \nin mathematics with abilities outstripping children twice their age, \nyet their performance in other subjects is unremarkable. Only\nin ar t and music is such precociousness so impressive. Looking out into \n the wider world, we see the cogs of the Western world turned by the\ne ngines of mathematical understanding. Computers programmed with \nine xorable logic control our economies and money markets, our aeroplanes \nand trains. Our own minds are seen as a fallible \"\"natural\"\" fo rm\nof intelligence that these computers will ultimately perfect in an \nembodiment of \"\"artificial\"\" intelligence that is nothing more t han a\ncomplicated mathematical algorithm that can be implemented\nele ctronically far faster and less fallibly than by our own feeble brains .\nIn our universities there is an unspoken suspicion that the further \na discipline lies from mathematics and the smaller the body of\nmath ematical statements at its core the less rigorous and intellectually\n respectible it is.\":\nfreqVector1 := freqCounter(message1):\nprint(fr eqVector1);\nfreqPrinter(freqVector1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'vectorG6#7=\"$8\"\"#@\"#i\"#W\"$x\"\"#D\"#C\"#a\"$@\"\"\"#\" \"&\"#x\"#b\"$-\"\"#()\"#H\"\"\"\"#*)\"$1\"\"$\\\"\"#\\\"\"*\"#:\"\"$ \"#BF0\"%W9" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%XThe~string~had~1444~c haracters~from~the~Latin~alphabet.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #%SThe~letter~A~appears~113~times,7.826%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~B~appears~21~times,1.454%~of~the~time .G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~C~appears~62~times, 4.294%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~D ~appears~44~times,3.047%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%SThe~letter~E~appears~177~times,12.26%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~F~appears~25~times,1.731%~of~th e~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~G~appears~24~ times,1.662%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~le tter~H~appears~54~times,3.740%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%SThe~letter~I~appears~121~times,8.380%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~J~appears~2~times,.1385 %~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~K~appe ars~5~times,.3463%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%R The~letter~L~appears~77~times,5.332%~of~the~time.G" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%RThe~letter~M~appears~55~times,3.809%~of~the~time.G " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%SThe~letter~N~appears~102~times,7 .064%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~O~ appears~87~times,6.025%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~P~appears~29~times,2.008%~of~the~time.G" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#%TThe~letter~Q~appears~1~times,.6925e-1%~of~the~ time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~R~appears~89~ti mes,6.163%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%SThe~lett er~S~appears~106~times,7.341%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%SThe~letter~T~appears~149~times,10.32%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~U~appears~49~times,3.39 3%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~V~app ears~9~times,.6233%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#% RThe~letter~W~appears~15~times,1.039%~of~the~time.G" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%QThe~letter~X~appears~3~times,.2078%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~Y~appears~23~times,1.59 3%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~Z~app ears~2~times,.1385%~of~the~time.G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 167 "In this pass age, the most common letters in order of frequency are e, t, i, a, s, n, r, o, and l, while we expect them to be e, t, a, o, i, n, s, h, an d r in general." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 125 "Since we want to work with monoalphabetic ciphers, we recall the procedures needed \+ to encode with these substitution ciphers." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 781 "monoalph := proc(letter, rule, key)\n#This procedu re changes one letter with a monoalphabetic cipher named rule\n lo cal temp, temp2;\n temp := letter:\n if letter > 64 then\n \+ if letter < 91 then\n temp := 65 + rule(temp - 65, key):\n \+ fi:fi:\n if letter > 96 then\n if letter < 123 then\n \+ temp := 97 + rule(temp - 97, key):\n fi:fi:\n temp:\n end:\nenc odemonoalph := proc(message, rule, key)\n#This procedure uses monoalph to uncode a string\n local temp:\n #first convert the messag e to numerical equivalents\n temp[1] := convert(message, bytes):\n \+ #then uses monalph to scrable the letters\n temp[2] := map(mon oalph, temp[1], rule, key):\n #then convert back to the ASCII cod e\n convert(convert(temp[2], bytes), name):\n end:" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 26 "Attacking additive ciphers" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 104 "caesarrule := (letter, key) -> ((l etter + key) mod 26):\n#This procedure is the rule used for the Caesar " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 248 "The method of an additive c ipher is to translate x -> x + key for some key. A ciphertext created with an additive cipher is decrypted by using another additive cipher . To obtain the key it is enough to find a key that works for a singl e letter. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 34 "Consider the following ciphertext." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 292 "secret1 := `Dolu fvb dlyl h ahkwvsl huk P dhz h mp zo\nPu aol Whslvgvpj aptl,\nHuk zpkl if zpkl vu aol liipun apkl\nDl zw yhdslk aoyvbno aol vvgl huk zsptl,\nVy zrpaalylk dpao thuf h jhbkhs ms pw\naoyvbno aol klwaoz vm Jhtiyphu mlu\nTf olhya dhz ypml dpao aol qvf vm spml,\nMvy P svclk fvb lclu aolu.`;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(secret1G%a\\lDolu~fvb~dlyl~h~ahkwvsl~huk~P~dhz~h~mpzo|+Pu~aol ~Whslvgvpj~aptl,|+Huk~zpkl~if~zpkl~vu~aol~liipun~apkl|+Dl~zwyhdslk~aoy vbno~aol~vvgl~huk~zsptl,|+Vy~zrpaalylk~dpao~thuf~h~jhbkhs~mspw|+aoyvbn o~aol~klwaoz~vm~Jhtiyphu~mlu|+Tf~olhya~dhz~ypml~dpao~aol~qvf~vm~spml,| +Mvy~P~svclk~fvb~lclu~aolu.G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "W e start by doing a frequency count on the ciphertext" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "freqVector1 := freqCounter(secret1):\npri nt(freqVector1);\nfreqPrinter(freqVector1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'vectorG6#7=\"#<\"\"&\"\"#\"\")\"\"!\"\"'F)F'\"\"%\" \"$\"#7\"#IF*F.\"#;\"#=\"\"\"F3F*F(F/F1F(F+\"#5\"\"*\"$=#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%WThe~string~had~218~characters~from~the~Latin~ alphabet.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~A~appears~1 7~times,7.798%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~ letter~B~appears~5~times,2.294%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~C~appears~2~times,.9174%~of~the~time.G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~D~appears~8~times,3.670%~ of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%NThe~letter~E~appear s~0~times,0.%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~l etter~F~appears~6~times,2.752%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~G~appears~2~times,.9174%~of~the~time.G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~H~appears~17~times,7.798% ~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~I~appea rs~4~times,1.835%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QT he~letter~J~appears~3~times,1.376%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~K~appears~12~times,5.505%~of~the~time.G" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~L~appears~30~times,13.76 %~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~M~appe ars~8~times,3.670%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%Q The~letter~N~appears~3~times,1.376%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~O~appears~16~times,7.339%~of~the~time.G" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~P~appears~18~times,8.257 %~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~Q~appe ars~1~times,.4587%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%Q The~letter~R~appears~1~times,.4587%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~S~appears~8~times,3.670%~of~the~time.G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~T~appears~5~times,2.294%~ of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~U~appear s~12~times,5.505%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RT he~letter~V~appears~16~times,7.339%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~letter~W~appears~5~times,2.294%~of~the~time.G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%NThe~letter~X~appears~0~times,0.%~of~ the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%RThe~letter~Y~appears~1 0~times,4.587%~of~the~time.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~ letter~Z~appears~9~times,4.128%~of~the~time.G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 235 "From the frequency count, we see that L is the most c ommon letter in the ciphertext. We will guess that the decryption sho uld take L to E. Since L is the 12th letter and E is the 5th letter, \+ we want -7 as the first guess for our key." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 40 "encodemonoalph(secret1, caesarrule, -7);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#%a\\lWhen~you~were~a~tadpole~and~I~was~a~fis h|+In~the~Paleozoic~time,|+And~side~by~side~on~the~ebbing~tide|+We~spr awled~through~the~ooze~and~slime,|+Or~skittered~with~many~a~caudal~fli p|+through~the~depths~of~Cambrian~fen|+My~heart~was~rife~with~the~joy~ of~life,|+For~I~loved~you~even~then.G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 73 "This gives an English plaintext from the poem Evolution b y Langdon Smith." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 123 "A minor impr ovement we can make is to produce a procedure that calculates the key \+ knowing an initial letter and its target." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 116 "caesarkeyfinder := proc(twoletters)\nlocal nums:\n nums := convert(twoletters, bytes):\n(nums[2] - nums[1]) mod 26:\nend: " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "In our case we wanted to take L to E." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "caesarkeyfinder (`le`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#>" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 59 "encodemonoalph(secret1, caesarrule, caesarkeyf inder(`le`));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#%a\\lWhen~you~were~a~ tadpole~and~I~was~a~fish|+In~the~Paleozoic~time,|+And~side~by~side~on~ the~ebbing~tide|+We~sprawled~through~the~ooze~and~slime,|+Or~skittered ~with~many~a~caudal~flip|+through~the~depths~of~Cambrian~fen|+My~heart ~was~rife~with~the~joy~of~life,|+For~I~loved~you~even~then.G" }}} {SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 257 10 "Exercises:" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 171 "1) Enter a passage of at least 1 000 characters from any page of any book you own. Do a frequency coun t on the letters in the passage. Does the count give any surprises?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 28 "2) Consider the ciphertext," }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 25 "Vhfinmxkl ikhzktffxw pbma" }} {PARA 0 "" 0 "" {TEXT -1 72 "bgxqhktuex ehzbv vhgmkhe hnk xvhghfbxl tg w fhgxr ftkdxml, hnk txkhietgxl" }}{PARA 0 "" 0 "" {TEXT -1 64 "tgw mk tbgl. Hnk hpg fbgwl tkx lxxg tl t yteebuex \"gtmnkte\" yhkf" }}{PARA 0 "" 0 "" {TEXT -1 66 "hy bgmxeebzxgvx matm maxlx vhfinmxkl pbee nembf tmxer ixkyxvm bg tg" }}{PARA 0 "" 0 "" {TEXT -1 67 "xfuhwbfxgm hy \"tk mbybvbte\" bgmxeebzxgvx matm bl ghmabgz fhkx matg t" }}{PARA 0 "" 0 " " {TEXT -1 58 "vhfiebvtmxw ftmaxftmbvte tezhkbmaf matm vtg ux bfiexfxg mxw" }}{PARA 0 "" 0 "" {TEXT -1 74 "xexvmkhgbvteer ytk ytlmxk tgw exll yteebuer matg ur hnk hpg yxxuex uktbgl." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 98 "Use frequency counts to find the k ey to the additive cipher needed to decode. Give the plaintext." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 410 "We would like to automate the attack and also reduce err ors in guessing the key by noting that rather than just looking for th e most frequent letter we can look for the pattern of frequent letters in the alphabet. We do this by taking a dot product of the frequency vector with the vector giving the frequencies of letter usage in typi cal English text. For technical reasons we will repeat that vector tw ice." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 210 "engFreq := [.082, \+ .015, .028, .043, .127, .022, .020, .061, .070, .002,\n .008, .040, .0 24, .067, .075, .019, .001, .060, .063, .091, .028,\n .010, .023, .001 , .020, .001]:\nengFreq2 := [op(engFreq), op(engFreq)];" }}{PARA 12 " " 1 "" {XPPMATH 20 "6#>%)engFreq2G7V$\"##)!\"$$\"#:F($\"#GF($\"#VF($\" $F\"F($\"#AF($\"#?F($\"#hF($\"#qF($\"\"#F($\"\")F($\"#SF($\"#CF($\"#nF ($\"#vF($\"#>F($\"\"\"F($\"#gF($\"#jF($\"#\"*F(F+$\"#5F($\"#BF(FGF3FGF &F)F+F-F/F1F3F5F7F9F;F=F?FAFCFEFGFIFKFMF+FOFQFGF3FG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "Now we take a dot product with all possible shi fts." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 114 "for i from 0 to 25 do\n print(sum(engFreq2[i+j]*freqVector1[j]/freqVector1[27], j=1..26) ,\n \"with key of\", i) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+ cgEpQ!#6Q,with~key~of6\"\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+) zd$HM!#6Q,with~key~of6\"\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+ W%GT]$!#6Q,with~key~of6\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+ pD3**R!#6Q,with~key~of6\"\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+ d\\%RV%!#6Q,with~key~of6\"\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\" +dreaP!#6Q,with~key~of6\"\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+ 1xCZS!#6Q,with~key~of6\"\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+, Ak?S!#6Q,with~key~of6\"\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+2) oD`%!#6Q,with~key~of6\"\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+II jfO!#6Q,with~key~of6\"\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+R^; )>$!#6Q,with~key~of6\"\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+&=?U Y$!#6Q,with~key~of6\"\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+mf:() Q!#6Q,with~key~of6\"\"#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+.Ak?L! #6Q,with~key~of6\"\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+d#3*RL!# 6Q,with~key~of6\"\"#9" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+'e/b]%!#6 Q,with~key~of6\"\"#:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+$3**)yO!#6 Q,with~key~of6\"\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+zYh()H!#6Q ,with~key~of6\"\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+]%Rt0%!#6Q, with~key~of6\"\"#=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+k[$=X'!#6Q,w ith~key~of6\"\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+)pOSu$!#6Q,wi th~key~of6\"\"#?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+$)zdVH!#6Q,wit h~key~of6\"\"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+'Rt!)e$!#6Q,wit h~key~of6\"\"#A" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+St!)=Y!#6Q,with ~key~of6\"\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+9w8:M!#6Q,with~k ey~of6\"\"#C" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+_Qi[O!#6Q,with~key ~of6\"\"#D" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 222 "Note that the dot \+ product shifted by the decryption key is almost .065, while the other \+ shifts are all less than .048. We can automate this a bit more by onl y printing out the result when the dot product is at least .055." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 168 "for i from 0 to 25 do\n dot Prod := sum(engFreq2[i+j]*freqVector1[j]/freqVector1[27], j=1..26):\n \+ if (dotProd > .06) then print(dotProd, ` with decrypt key of`, i) fi: \+ od:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+k[$=X'!#6%5~with~decrypt~ke y~ofG\"#>" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "For convenience we r educe this to a single procedure." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 595 "keyFinder := proc(freqVect)\n local engFreqVect, i, dotProd:\n engFreqVect := [.082, .015, .028, .043, .127, .022, .020, .061, .070, .002,\n .008, .040, .024, .067, .075, .019, .001, .06 0, .063, .091, .028,\n .010, .023, .001, .020, .001, .082, .015, . 028, .043, .127, .022, \n .020, .061, .070, .002, .008, .040, .024 , .067, .075, .019, .001, \n .060, .063, .091, .028, .010, .023, . 001, .020, .001]:\n for i from 0 to 25 do\n dotProd := sum(engFreq Vect[i+j]*freqVect[j]/freqVect[27], j=1..26):\n if (dotProd > .06) \+ then print(dotProd, ` with decrypt key of`, i) fi: \n od:\nend:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "keyFinder(freqCounter(secret 1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"+k[$=X'!#6%5~with~decrypt~k ey~ofG\"#>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 257 "" 0 "" {TEXT -1 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "2A) repeat exercise 2 with an automated attack." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 32 "Attacking multiplicative ciphers" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "Multipl icative ciphers are much like additive ciphers with a differing encryp tion rule" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 114 "multrule := ( letter, key) -> ((letter * key) mod 26):\n#This procedure is the rule \+ used for multiplicative ciphers " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 369 "The attack in the multiplicative case is much like the attack in \+ the additive case. We start the attack by using a frequency count to \+ identify a common letter, X, in ciphertext and what we think it should be, Y, in plaintext. We then reason that we want to find the key suc h that Y = key*X. The obvious thing to try is to let the key be Y/X. \+ The problem is that in " }{XPPEDIT 18 0 "Z[26]" "6#&%\"ZG6#\"#E" } {TEXT -1 140 ", X need not be invertible, so we may not be able to do \+ the division. The solution is to simply check all the keys to see whi ch one works. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 402 "multkeyf inder := proc(twoletters)\n# The input is assumed to be a sequence of \+ two lower case letters.\nlocal counta, nums, key:\nkey := 1:\nfor coun ta from 1 to 25 do\nif igcd(counta, 26) = 1 then\nnums := convert(twol etters, bytes):\nif (counta*(nums[1] - 97) - (nums[2] - 97)) mod 26 = \+ 0 then\nkey := counta:\nbreak:\nfi; fi; od;\nif key = 1 and (nums[1] < > nums[2])then\nprint(`No key will work`): fi:\nkey:\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "multkeyfinder(\"mm\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "multkeyfinder(`mz`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%1No~key ~will~workG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "multkeyfinder(`bf`);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"\"&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Th ere are a few technical details of this procedure worth commenting on. " }}{PARA 0 "" 0 "" {TEXT -1 179 "1) The procedure considers a multip licative cipher with the understanding that A is treated as 0, B treat ed as 1 and so forth. Recall that convert takes `a` to 97 and `A` to \+ 65." }}{PARA 0 "" 0 "" {TEXT -1 90 "2) The procedure assume then that the two letter sequence it uses as input is lower case." }}{PARA 0 " " 0 "" {TEXT -1 285 "3) Since we are planning to use the procedure to produce a key when we think we know a letter and its target. Thus we not only need to understand that we may have guessed wrong. We also \+ need to consider that there may be no key that takes our favorite lett er to its intended target." }}{PARA 0 "" 0 "" {TEXT -1 70 "4) The pro cedure will only give answers that are invertible in Z[26]." }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 258 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "3) Consider the ciphertext" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 225 "`Kn ymf mnkxsfqkb ksq bzsfs kq an mnqjygsn qmqjkwkyn bzab bzs dmfbzsf\na hkqwkjrkns rksq dfyc cabzscabkwq anh bzs qcarrsf bzs lyhe yd\ncabzscabkwar qbabscsnbq ab kbq wyfs bzs rsqq fkoyfymq anh knbsrrswbmarre\\nfsqjswbklrs kb kq. `" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 96 "It w as produced with a multiplicative cipher. Find the decryption key and decipher the message." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 24 "Attacking affine ciphers" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "affinerule := (letter, key) \+ -> ((letter*key[1] + key[2]) mod 26):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 437 "Affine ciphers are a combination of additive and multipl icative ciphers. Our key becomes an ordered pair [A,B] with the lette r X being taken to AX + B. Once again we decrypt by using the affine \+ cipher with the appropriate key. A difference from the earlier rules \+ is that an affine cipher is a linear function, and it is not determine d by a single point. Instead we need two pairs of letters to determin e the key for an affine cipher." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 86 "Thus the process of finding the key reduc es to the following college algebra question:" }}{PARA 0 "" 0 "" {TEXT -1 101 "If you are told that Y1 = A*X1 +B and Y2 = A*X2 + B, can you recover A and B from X1, X2, Y1, and Y2?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 266 "To solve the problem we \+ note that (Y1 - Y2) = A*(X1 - X2) and that once we have A, that B = Y1 - A*X1. We should note that if X1 - X2 divides 26, we may have more \+ than one possible key. Since A must be invertible, we only have to be concerned when (X1 - X2) is 13." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 695 "affinekeyfinder := proc(fourletters)\n# Input `abcd` designates we want a -> b, c -> d.\n# inputs all assumed lower case. \nlocal counta, nums, key, multanswers:\nkey := [1,0]:\nnums := conver t(fourletters, bytes):\nif igcd(nums[1] - nums[3], 26) = 13 then\n m ultanswers := 1:\n print(`warning, multiple answers are possible`): \n else\n multanswers := 0 fi:\nfor counta from 1 to 25 do\n if i gcd(counta, 26) = 1 then\n if (counta*(nums[1]-nums[3]) - (nums[2 ]-nums[4])) mod 26 = 0 then\n key := [counta, nums[2]-96 - cou nta*(nums[1]-96) mod 26]:\n if multanswers = 1 then print(k ey) fi;\n# break;\nfi; fi; od;\nif key = [1,0] then\n pri nt(`No key works`): fi:\nkey;\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "Check the code on some simple cases." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "affinekeyfinder(`abno`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%Gwarning,~multiple~answers~are~possibleG" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7$\"\"\"F$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$ \"\"$\"#D" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"&\"#B" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7$\"\"(\"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7 $\"\"*\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"#6\"#<" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7$\"#:\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$ \"#<\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"#>\"\"*" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7$\"#@\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7 $\"#B\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"#D\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"#D\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "affinekeyfinder(`abce`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%-No~key~worksG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\" \"\"\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "affinekeyfinde r(`accg`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"#:\"#9" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 82 "It is also useful to have a procedure tha t finds inverse keys for the affine rule." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 82 "invertaffinekey := proc(key)\nprint([1/key[1] mod 2 6, -key[2]/key[1] mod 26]):\nend:" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 259 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 264 "4) It was noted above that (Y1 - Y2) = A*(X1 - X2) can have multi ple keys when (X1 - X2) divides 26. Explain how many keys we can get \+ when this difference is even and when the difference is 13. Explain w hy we can still only get one key if the difference is even." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "5) Consider the following ciphertext encrypted with an a ffine cipher:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 68 "\"Zc nbu bczmhufzqzhf qohuh zf pc bcfynvhc fbfyzlznc qopq qoh sbuqohu" }}{PARA 0 "" 0 "" {TEXT -1 62 "p wzflzygzch gzhf sunr rp qohrpqzlf pcw qoh frpgghu qoh anwt ns" }}{PARA 0 "" 0 "" {TEXT -1 72 " rpqohrpqzlpg fqpqhrhcqf pq zqf lnuh qoh ghff uzdnunbf pcw zcqhgghlqbpg gt" }}{PARA 0 "" 0 "" {TEXT -1 21 "uhfyhlqzagh zq zf.\" " }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "Find the key and g ive the plaintext" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 168 "6) Enter a message of approximat ely 10 lines. Use one of the ciphers above to encrypt it. Post the c iphertext and the method, but not the key, to the bulletin board." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 297 "7) Crack someone else's post. Come up with an appropri ate reply. Post your reply as a response to the message. Your messag e should be encrypted by the same method as the original. Give the ke y to your response in your posting. (Be careful to keep the encryptin g and decrypting keys distinct." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }