{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 1 12 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 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Gen eva" 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 "List Item" -1 14 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 3 3 1 0 1 0 2 2 14 5 }{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 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 15 "The Hill Cipher" }}{PARA 19 "" 0 "" {TEXT -1 37 "\251Mike May, S. J., 2002, maymk@slu.edu" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 164 "The worksheets we have done so far look at techni ques that encrypt a message one character at a time. These encryption method are insecure for a variety of reason:" }}{PARA 14 "" 0 "" {TEXT -1 195 "The frequency with which the 26 letters are used in Engl ish is far from random. Even a relatively short message can be analyz ed statistically by looking at which letters show up most frequently. " }}{PARA 14 "" 0 "" {TEXT -1 168 "We can also do frequency counts on \+ the beginning letters, ending letters, and double letters of words. T hese counts will give different sets of most common characters." }} {PARA 14 "" 0 "" {TEXT -1 135 "We can also do frequency counts on two \+ letter and three letter combinations. This would help us check letter s that are less common. " }}{PARA 14 "" 0 "" {TEXT -1 88 "If the mes sage is an English text, there are a small number of 1, 2, and 3 lette r words." }}{PARA 0 "" 0 "" {TEXT -1 169 "This makes the initial monoa lphabetic ciphers we used very weak. Recall that an affine cipher is \+ completely cracked if we know how almost any two letters are replaced. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 368 "One solution to developing a stronger system is to \+ encode blocks of characters at a time. This effectively increases the size of our alphabet and reduces the usefulness of much of the data o n the structure of English. The easiest way to encode blocks of chara cters is to convert blocks to vectors of numbers and then to multiply \+ the vector by an invertible matrix. " }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 31 "Technical details I - Alphabets" }}{EXCHG {PARA 0 "" 0 " " {TEXT -1 932 "One of our objectives is to mask the beginning and end ing of words to keep an attacker from using that information for an at tack on our code. This could be done by removing spaces and punctuati on before we encode, but that also confuses the message after it has b een decoded by the person we are sending it to. The other strategy is to consider special characters as part of a larger alphabet. Since M aple has a command to convert characters in a string to ASCII equivale nts, it is easiest to simply use the normal ASCII character set for ou r alphabet. That means that our alphabet has 127 letters in it. In k eeping with the numbering conventions of ASCII, we will also be using \+ clock arithmetic rather than modular arithmetic. (Our numbers will go from 1 to 127 rather than from 0 to 126.) We notice as a bonus that \+ 127 is prime. We start by defining a command that adjust numbers from modular notation to clock arithmetic." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "clock127 := x -> ((x-1) mod 127) + 1:" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 256 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 132 "1) With an aphine cipher acting on an al phabet of 26 characters, some encryption keys cannot be decrypted. Ch aracterize those keys." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 338 "2) For cracking an affine cip her, it was noted that it sufficed to find the substitution rule for a lmost any two letters. Explain what pairs of characters don't give en ough information and why. (Notice for example, that the keys (1,0), ( 3, 24), and (5, 22) both fix the letters represented by 1 and 14 in an alphabet of 26 characters.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 206 "3) I mentioned that it was a bonus that we would be using an alphabet whose size is prime. \+ If we are to work over mod n, where n is the size of our alphabet, why is it a bonus to have n be a prime number?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 36 "Initial Variables and Message Length" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 " We next need a message and an encrypting key. Our initial key will be a 3 by 3 invertible matrix over " }{XPPEDIT 18 0 "Z[127]" "6#&%\"ZG6# \"$F\"" }{TEXT -1 146 ". For the next several worksheets, our message s will begin and end with know strings. Our beginning string is \"az \+ AZ - Good morning, Mr. Phelps." }}{PARA 0 "" 0 "" {TEXT -1 33 "The sec ret message for today is:\"" }}{PARA 0 "" 0 "" {TEXT -1 108 "The endin g string is \"az AZ\". Notice that the beginning string has a newline character in the middle of it." }}{PARA 0 "" 0 "" {TEXT -1 53 "Our se cret message for today is a poem by Ogden Nash." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 346 "mess1 := `az AZ - Good morning, Mr. Phelps. \+ \nThe secret message for today is:\nI objurgate the centipede,\nA bug \+ we realy do not need.\nAt sleepy time he beats a path\nStraight to bed room or the bath.\nYou always wollop where he's not,\nOr if he is, he \+ leaves a spot.\naz AZ`:\nnums1 := convert(mess1, bytes);\nmykey := mat rix([[1,2,3],[0,5,7],[0,0,11]]);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>% &nums1G7][l\"#(*\"$A\"\"#K\"#l\"#!*F(\"#XF(\"#r\"$6\"F-\"$+\"F(\"$4\"F -\"$9\"\"$5\"\"$0\"F1\"$.\"\"#WF(\"#xF0\"#YF(\"#!)\"$/\"\"$,\"\"$3\"\" $7\"\"$:\"F6F(\"#5\"#%)F8F9F(F\"F9F(F0F9F&F:FBF(F.F-F (F1F-F@F(F1F9F9F.F6F=F)F@F(F%&mykeyG-% 'matrixG6#7%7%\"\"\"\"\"#\"\"$7%\"\"!\"\"&\"\"(7%F.F.\"#6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 76 "We want to check the determinant of mykey and that mykey is invertible over " }{XPPEDIT 18 0 "Z[127]" "6#&%\"ZG 6#\"$F\"" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "Det(mykey) mod 127;\nunkey := Inverse(mykey) mod 127;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#b" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&unkeyG- %'matrixG6#7%7%\"\"\"\"#D\"#I7%\"\"!\"#^\"#$)7%F.F.\"$/\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 384 "Since we are encrypting the message in b locks of three characters, the next detail is to make sure that the me ssage has a length divisible by three (the size of the encrypting mat rix). Evensize is a procedure that takes a list of decimal numbers an d pads it out with 32's to make the message a length divisible by the \+ size of the key. (the ASCII equivalent of 32 is a blank space.)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "linalg[vectdim](nums1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"$d#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 248 "evensize := proc(decvec,bsize)\nlocal charLength, pa ddingLength, j, temp;\ntemp := decvec;\ncharLength :=linalg[vectdim](d ecvec);\npaddingLength := (bsize - irem(charLength, bsize)) mod bsize; \ntemp := [op(temp),seq(32, j=1..paddingLength)]:\n#temp;\nend:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "nums2 := evensize(nums1,3); " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&nums2G7^[l\"#(*\"$A\"\"#K\"#l\" #!*F(\"#XF(\"#r\"$6\"F-\"$+\"F(\"$4\"F-\"$9\"\"$5\"\"$0\"F1\"$.\"\"#WF (\"#xF0\"#YF(\"#!)\"$/\"\"$,\"\"$3\"\"$7\"\"$:\"F6F(\"#5\"#%)F8F9F(F\"F9F(F0F9F&F:FBF(F.F-F(F1F-F@F(F1F9F9F.F6F=F)F@F(F " 0 "" {MPLTEXT 1 0 456 "matmult := p roc(decvec, key, keysize)\nlocal l1, l3, i, j, k, temp, temp2, temp3; \ntemp2 := linalg[vector](keysize);\ntemp := convert(decvec,array);\nl 1 :=linalg[vectdim](temp);\nl3 := l1/keysize;\nfor j from 0 to (l3 -1) do\n for i from 1 to keysize do\n temp2[i] := temp[j*keysize+i] :\n od;\n temp2 := map(clock127,linalg[multiply](key,temp2)):\n \+ for i from 1 to keysize do\n temp[j*keysize + i] := temp2[i]: \+ \n od:\nod;\nconvert(temp,list);\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 82 "Now we apply the transformation, then convert back to ASC II and print the message." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "nums3 := matmult(nums2,mykey,3);\nmess2 := convert(nums3,bytes);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&nums3G7^[l\"#c\"#s\"#)*\"#()\"#RF (\"#o\"#A\"#>\"$D\"\"$7\"\"#%)\"#v\"#_\"#y\"#9\"#:\"#7\"#n\"#h\"$.\"\" #?\"#S\"$6\"\"#'*\"#&)\"$=\"\"$A\"F?\"#X\"#**\"\")F.\"#]\"\"$\"#N\"#@ \"#%*F(\"$1\"\"#b\"#t\"#H\"#Z\"\"'FA\"$4\"\"#&*\"\"\"F<\"#^F:FHF(\"#J \"#$)F<\"#*)F)F3F,\"#iF8\"#z\"#gF@\"#V\"#`\"#TF;F(FVFM\"$8\"F<\"#5\"#F FN\"\"&FTFNFGFHF(\"$B\"FinF7FhnF*FUF=\"#kFPFin\"$C\"\"#!)\"#rF*\"#<\"# ;\"$/\"F*\"$E\"\"#pF\"F0FP\"#6FioFR\"#\")F]oF.\"#8FWF3\"#\"*F^pFR\"\"#\" \"%FR\"#mFjoF(\"#IFenFAFSFcoFU\"#uFZFQF\\oFcpFPFFF0FPF%&mess2GQ][l 8HbW'bD|7|4|hrpTK4N|/|0|-C=g|5(o`Uvzv-c|)|hr2|$#|6^bj7I|>/|'-m_|\"o3|5 ^b|@SoYWN|7>=O/qo|+|<|'|&S|'|6^b|fr|&C|<'Y`@_|&|grPG'|2|1h'|ir Eoob-hbT|gr)C:*bkE__.n|-*b|irh_5|+=G-|-|;^b|6^bS)3=%bt7Y|'&|\"|1T|'sM| -|9>|'YWN|86_|;MN,|(b6~bwT_|,|;3QP|hr|.ON[M3|#|%3B%b|?)-|@EYJ5|\"|gr|( _#T_o%b-a|'/_kp|'|-a|ir|\"c|'|--?b|6^b])3|?(zDJb%CNo.n8HbW'b6\"" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 463 "The printed ciphertext is not ver y manageable. By using the larger alphabet, we now have special chara cters sprinkled throughout the ciphertext. It makes retyping the ciph ertext impossible, and we also could not include the ciphertext in a m ail message. Before we look at that problem, let us make sure that we can decipher the message. Decryption should be done by the same proc ess of matrix multiplication with a key that is the inverse of the ori ginal key." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "unkey := Inve rse(mykey) mod 127;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&unkeyG-%'mat rixG6#7%7%\"\"\"\"#D\"#I7%\"\"!\"#^\"#$)7%F.F.\"$/\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 87 "nums4 := matmult(nums3, unkey, 3);\nmess3 := convert(nums4, bytes);\nconvert(mess3,name);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&nums4G7^[l\"#(*\"$A\"\"#K\"#l\"#!*F(\"#XF(\"#r\"$6\" F-\"$+\"F(\"$4\"F-\"$9\"\"$5\"\"$0\"F1\"$.\"\"#WF(\"#xF0\"#YF(\"#!)\"$ /\"\"$,\"\"$3\"\"$7\"\"$:\"F6F(\"#5\"#%)F8F9F(F\"F9F( F0F9F&F:FBF(F.F-F(F1F-F@F(F1F9F9F.F6F=F)F@F(F%&mess3GQ][laz~AZ~-~Good~morning,~Mr.~Phelps.~|+The~se cret~message~for~today~is:|+I~objurgate~the~centipede,|+A~bug~we~realy ~do~not~need.|+At~sleepy~time~he~beats~a~path|+Straight~to~bedroom~or~ the~bath.|+You~always~wollop~where~he's~not,|+Or~if~he~is,~he~leaves~a ~spot.|+az~AZ~6\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#%][laz~AZ~-~Good~ morning,~Mr.~Phelps.~|+The~secret~message~for~today~is:|+I~objurgate~t he~centipede,|+A~bug~we~realy~do~not~need.|+At~sleepy~time~he~beats~a~ path|+Straight~to~bedroom~or~the~bath.|+You~always~wollop~where~he's~n ot,|+Or~if~he~is,~he~leaves~a~spot.|+az~AZ~G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 26 "Cleaning up the Ciphertext" }}{EXCHG {PARA 0 "" 0 " " {TEXT -1 325 "Now we get to worry about presenting the encoded messa ge. The easiest solution seems to be to go back to hex representation , then store the code in blocks corresponding to 3 (the size of the ke y) characters. We need to recall the procedures defined in the Type C onversions worksheet for blocking and unblocking hex vectors." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 488 "blocker := proc(hexvec,bsiz e)\nlocal numCharacters, paddingNum, numWords, i, j, temp, hexblock;\n temp := hexvec;\nnumCharacters :=linalg[vectdim](hexvec);\nnumWords := ceil(numCharacters/bsize);\npaddingNum := numWords*bsize - numCharact ers;\ntemp := [op(temp),seq(`00`,j = 1..paddingNum)];\nhexblock := \n [seq( cat(seq(temp[bsize*i + j], j = 1..bsize)), i=0..numWords-1)]: \nend:\nunblocker := (hexblock,bsize) ->\n map(hexString -> seq(subst ring(hexString,2*j-1..2*j), j = 1..bsize),hexblock):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 618 "We have one more problem to be aware of. Our \+ use of the procedure blocker assumes that every ASCII character has a \+ two digit hex representation. However Maple's conversion to hex follo ws the usual math convention and leaves off leading zeroes. With norm al ASCII text, this only give us problems if a newline (ASCII equivale nt of 13) is included, since that would be represented by a single hex character. After we have used the Hill cipher, the characters are di stributed, so it should give us a problem for 1 character out of 8. W e solve this problem by recalling a procedure converts to 2 character \+ hex strings." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "intTo2dHex \+ := intValue -> substring(convert(intValue+256,hex), 2..3):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "Now we can convert our output to hex bloc ked words." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "nums5 := map( intTo2dHex, nums3);\nnums6 := blocker(nums5,3);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&nums5G7^[l%#38G%#48G%#62G%#57G%#27GF(%#44G%#16G%#13G %#7DG%#70G%#54G%#4BG%#34G%#4EG%#0EG%#0FG%#0CG%#43G%#3DG%#67G%#14G%#28G %#6FG%#60G%#55G%#76G%#7AGF?%#2DG%#63G%#08GF.%#32G%#03G%#23G%#15G%#5EGF (%#6AG%#37G%#49G%#1DG%#2FG%#06GFA%#6DG%#5FG%#01GF<%#33GF:FHF(%#1FG%#53 GF<%#59GF)F3F,%#3EGF8%#4FG%#3CGF@%#2BG%#35G%#29GF;F(FVFM%#71GF<%#0AG%# 1BGFN%#05GFTFNFGFHF(%#7BGFinF7FhnF*FUF=%#40GFPFin%#7CG%#50G%#47GF*%#11 G%#10G%#68GF*%#7EG%#45GF%&nums6G7bp%'384862G%'572762G%'441613G%'7D7054G%'4B344EG%'0E0F0CG%'4 33D67G%'14286FG%'605576G%'7A762DG%'63087DG%'320323G%'155E62G%'6A3749G% '1D2F06G%'2D6D5FG%'016F33G%'145E62G%'1F536FG%'59574EG%'163E3DG%'4F3C7A G%'2B3529G%'28623EG%'2F716FG%'0A1B06G%'055306GF2%'7B0543G%'1B2759G%'60 405FG%'057C50G%'472711G%'106827G%'7E456FG%'6F622DG%'686254G%'7C2943G%' 3A2A62G%'6B455FG%'5F2E6EG%'0C2A62G%'7E685FG%'350A3DG%'472D0CG%'1A5E62G F2%'532933G%'3D2562G%'743759G%'062601G%'105406G%'734D0CG%'183E06GF9%'1 7365FG%'1A4D4EG%'2C0762G%'362062G%'77545FG%'0B1A33G%'51507DG%'0D4F4EG% '5B4D33G%'020433G%'422562G%'1E292DG%'1F4559G%'4A3501G%'7C075FG%'23545F G%'6F2562G%'2D6106G%'2F5F6BG%'70060CG%'617E01G%'63060CG%'2D3F62GF2%'5D 2933G%'1E287AG%'444A62G%'25434EG%'6F2E6EGF&F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "As always, we want to test that this final encoded mes sage can be decoded." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 155 "nu ms7 := unblocker(nums6,3);\nnums8 := map(convert,nums7,decimal,hex);\n nums9 := matmult(nums8,unkey,3);\nmess4 := convert(nums9,bytes);\nconv ert(mess4, name);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&nums7G7^[l%#38 G%#48G%#62G%#57G%#27GF(%#44G%#16G%#13G%#7DG%#70G%#54G%#4BG%#34G%#4EG%# 0EG%#0FG%#0CG%#43G%#3DG%#67G%#14G%#28G%#6FG%#60G%#55G%#76G%#7AGF?%#2DG %#63G%#08GF.%#32G%#03G%#23G%#15G%#5EGF(%#6AG%#37G%#49G%#1DG%#2FG%#06GF A%#6DG%#5FG%#01GF<%#33GF:FHF(%#1FG%#53GF<%#59GF)F3F,%#3EGF8%#4FG%#3CGF @%#2BG%#35G%#29GF;F(FVFM%#71GF<%#0AG%#1BGFN%#05GFTFNFGFHF(%#7BGFinF7Fh nF*FUF=%#40GFPFin%#7CG%#50G%#47GF*%#11G%#10G%#68GF*%#7EG%#45GF%&nums8G7^[l\"#c\"#s\"#)*\"#() \"#RF(\"#o\"#A\"#>\"$D\"\"$7\"\"#%)\"#v\"#_\"#y\"#9\"#:\"#7\"#n\"#h\"$ .\"\"#?\"#S\"$6\"\"#'*\"#&)\"$=\"\"$A\"F?\"#X\"#**\"\")F.\"#]\"\"$\"#N \"#@\"#%*F(\"$1\"\"#b\"#t\"#H\"#Z\"\"'FA\"$4\"\"#&*\"\"\"F<\"#^F:FHF( \"#J\"#$)F<\"#*)F)F3F,\"#iF8\"#z\"#gF@\"#V\"#`\"#TF;F(FVFM\"$8\"F<\"#5 \"#FFN\"\"&FTFNFGFHF(\"$B\"FinF7FhnF*FUF=\"#kFPFin\"$C\"\"#!)\"#rF*\"# <\"#;\"$/\"F*\"$E\"\"#pF\"F0FP\"#6FioFR\"#\")F]oF.\"#8FWF3\"#\"*F^pFR\"\" #\"\"%FR\"#mFjoF(\"#IFenFAFSFcoFU\"#uFZFQF\\oFcpFPFFF0FPF%&nums9G7 ^[l\"#(*\"$A\"\"#K\"#l\"#!*F(\"#XF(\"#r\"$6\"F-\"$+\"F(\"$4\"F-\"$9\" \"$5\"\"$0\"F1\"$.\"\"#WF(\"#xF0\"#YF(\"#!)\"$/\"\"$,\"\"$3\"\"$7\"\"$ :\"F6F(\"#5\"#%)F8F9F(F\"F9F(F0F9F&F:FBF(F.F-F(F1F-F@ F(F1F9F9F.F6F=F)F@F(F%&mess4GQ][laz~ AZ~-~Good~morning,~Mr.~Phelps.~|+The~secret~message~for~today~is:|+I~o bjurgate~the~centipede,|+A~bug~we~realy~do~not~need.|+At~sleepy~time~h e~beats~a~path|+Straight~to~bedroom~or~the~bath.|+You~always~wollop~wh ere~he's~not,|+Or~if~he~is,~he~leaves~a~spot.|+az~AZ~6\"" }}{PARA 12 " " 1 "" {XPPMATH 20 "6#%][laz~AZ~-~Good~morning,~Mr.~Phelps.~|+The~secr et~message~for~today~is:|+I~objurgate~the~centipede,|+A~bug~we~realy~d o~not~need.|+At~sleepy~time~he~beats~a~path|+Straight~to~bedroom~or~th e~bath.|+You~always~wollop~where~he's~not,|+Or~if~he~is,~he~leaves~a~s pot.|+az~AZ~G" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 257 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "4) Find the key t hat scrambles 5 letter blocks, taking \"abcde\" to \"ecadb\". Use tha t key to encrypt message1 above." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 161 "5) Enter a \+ 10 line message of your choice with the name prob1. Produce a nontriv ial key of size 4. Use your key to encrypt prob1, saving the result \+ as prob2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "6) Find the inverse to your key above an d use it to decrypt prob 2. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 26 "Cleaning up our proce dures" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 225 "Since we will be storing our cyphertext in hex blocks we can rewrite our procedures to make th em a bit more compact and portable. This will also make them easier t o copy and paste if we want to use them on another worksheet." }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 216 "Our first two procedures are for \+ housekeeping. The next two are procedures to convert a string into a \+ list of blocked hex words and back again. We give these procedures t he names stringtoblocks and blockstostring." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1079 "cl ock127 := x -> ((x-1) mod 127) + 1:\nintTo2dHex := intValue -> substri ng(convert(intValue+256,hex), 2..3):\nstringtoblocks := proc(charstrin g,bsize)\n local declist, hexlist, hexblock, i, j, numChars, numBloc ks, paddingLength:\n #First we convert string to decimals and padd ou t with spaces\n declist := convert(charstring,bytes):\n numChars : =linalg[vectdim](declist);\n numBlocks := ceil(numChars/bsize):\n \+ paddingLength := numBlocks*bsize - numChars:\n declist := [op(declis t),seq(32, j=1..paddingLength)];\n #Now we convert to hex and block i nto words\n hexlist := map(intTo2dHex,declist):\n hexblock := [seq (cat(seq(hexlist[bsize*i + j], j = 1-bsize..0)),i=1..numBlocks)];\nend :\nblockstostring := proc(hexblock,bsize)\n local declist, hexlist, \+ charstring, i, j, l1:\n #First we back to a list of hex characters\n \+ hexlist := map(hexString -> \n seq(substring(hexString,2*j-1..2 *j), j = 1..bsize), hexblock);\n #Then we convert back to a decimal l ist, then to a string.\n declist := map(convert,hexlist,decimal,hex) :\n charstring := convert(declist,bytes):\nend:" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 67 "We also need a procedure for multiplying a matrix \+ times a hex word." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 336 "matmu ltbloc := proc(word,key,bsize)\n local i, j, decvect, hexvect, hexwo rd: \n decvect := linalg[vector]([seq(\n convert(substring(word, (2*i-1)..(2*i)),decimal,hex),i=1..bsize)]):\n decvect := map(clock12 7, linalg[multiply](key,decvect)):\n hexvect := map(intTo2dHex,decve ct):\n hexword := cat(seq(hexvect[j],j=1..bsize)):\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "We want to define a key and use these pr ocedures to uncrypt a message, then decrypt it to check our work." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 277 "key5 := matrix(5,5,[[1,2,3, 4,5],[7,0,0,0,0],[0,0,0,12,0],[0,0,13,0,0], [0,11,0,0,0]]);\na:= strin gtoblocks(mess1,5);\nsecret1 := map(matmultbloc,a,key5,5);\nunkey5 := \+ Inverse(key5) mod 127;\nb := map(matmultbloc,secret1,unkey5,5);\ntest1 := blockstostring(b,5);\nconvert(test1,name);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%key5G-%'matrixG6#7'7'\"\"\"\"\"#\"\"$\"\"%\"\"&7'\" \"(\"\"!F1F1F17'F1F1F1\"#7F17'F1F1\"#8F1F17'F1\"#6F1F1F1" }}{PARA 12 " " 1 "" {XPPMATH 20 "6#>%\"aG7V%+617A20415AG%+202D20476FG%+6F64206D6FG% +726E696E67G%+2C204D722EG%+205068656CG%+70732E200AG%+5468652073G%+6563 726574G%+206D657373G%+6167652066G%+6F7220746FG%+6461792069G%+733A0A492 0G%+6F626A7572G%+6761746520G%+7468652063G%+656E746970G%+6564652C0AG%+4 120627567G%+2077652072G%+65616C7920G%+646F206E6FG%+74206E6565G%+642E0A 4174G%+20736C6565G%+7079207469G%+6D65206865G%+2062656174G%+7320612070G %+6174680A53G%+7472616967G%+687420746FG%+2062656472G%+6F6F6D206FG%+722 0746865G%+2062617468G%+2E0A596F75G%+20616C7761G%+797320776FG%+6C6C6F70 20G%+7768657265G%+2068652773G%+206E6F742CG%+0A4F722069G%+6620686520G%+ 69732C2068G%+65206C6561G%+7665732061G%+2073706F74G%+2E0A617A20G%+415A2 02020G" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(secret1G7V%+042C122348G%+ 29615A2372G%+010F262354G%+5024325F43G%+0936627062G%+3361455276G%+17160 35A7AG%+1C50032B01G%+6548455549G%+40616E2B38G%+652C032B75G%+390F7A236F G%+2841033133G%+4E2B720303G%+0C0F076C3EG%+4256456F33G%+6B32032B01G%+7D 48756F43G%+4448142B54G%+094A070462G%+0161032B27G%+7848370733G%+1041322 34EG%+1632452162G%+2E4112037DG%+626145077AG%+2A167A233DG%+3A0169235FG% +6661152B3EG%+0F2B037662G%+502C785206G%+2E3275766FG%+365D7A2306G%+6861 392B3EG%+490F03144EG%+3224696F62G%+6A617A763EG%+5C443E0E6EG%+72611F073 3G%+51551F237AG%+7A794A2E2DG%+4347622B01G%+0461572B01G%+7E617A2E43G%+1 44603556BG%+1A4F455262G%+636403407AG%+6C48450762G%+084003625FG%+62613E 3B7AG%+744443766EG%+794A032365G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%' unkey5G-%'matrixG6#7'7'\"\"!\"$4\"F*F*F*7'F*F*F*F*\"$/\"7'F*F*F*\"#))F *7'F*F*\"#`F*F*7'\"#^\"#H\"$5\"\"$D\"\"#g" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"bG7V%+617A20415AG%+202D20476FG%+6F64206D6FG%+726E69 6E67G%+2C204D722EG%+205068656CG%+70732E200AG%+5468652073G%+6563726574G %+206D657373G%+6167652066G%+6F7220746FG%+6461792069G%+733A0A4920G%+6F6 26A7572G%+6761746520G%+7468652063G%+656E746970G%+6564652C0AG%+41206275 67G%+2077652072G%+65616C7920G%+646F206E6FG%+74206E6565G%+642E0A4174G%+ 20736C6565G%+7079207469G%+6D65206865G%+2062656174G%+7320612070G%+61746 80A53G%+7472616967G%+687420746FG%+2062656472G%+6F6F6D206FG%+7220746865 G%+2062617468G%+2E0A596F75G%+20616C7761G%+797320776FG%+6C6C6F7020G%+77 68657265G%+2068652773G%+206E6F742CG%+0A4F722069G%+6620686520G%+69732C2 068G%+65206C6561G%+7665732061G%+2073706F74G%+2E0A617A20G%+415A202020G " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&test1GQ_[laz~AZ~-~Good~morning, ~Mr.~Phelps.~|+The~secret~message~for~today~is:|+I~objurgate~the~centi pede,|+A~bug~we~realy~do~not~need.|+At~sleepy~time~he~beats~a~path|+St raight~to~bedroom~or~the~bath.|+You~always~wollop~where~he's~not,|+Or~ if~he~is,~he~leaves~a~spot.|+az~AZ~~~6\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#%_[laz~AZ~-~Good~morning,~Mr.~Phelps.~|+The~secret~message~for~t oday~is:|+I~objurgate~the~centipede,|+A~bug~we~realy~do~not~need.|+At~ sleepy~time~he~beats~a~path|+Straight~to~bedroom~or~the~bath.|+You~alw ays~wollop~where~he's~not,|+Or~if~he~is,~he~leaves~a~spot.|+az~AZ~~~G " }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 258 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 15 "7) The message" }}{PARA 0 "" 0 "" {TEXT -1 882 "[`4273713B7C`, `1B5E151D5A`, `2A665C2B7F`, `733867127 7`, `38637C2704`, `04751D4D73`, `4653531D1D`, `752B7B2A5F`, `742B3D524 7`, `743C231736`, `751D5E3E5F`, `6C047A3E31`, `4444232B5F`, `320B71132 8`, `5E59091622`, `686D434407`, `5476586A65`, `250D0C337D`, `525525305 9`, `2557295949`, `7852387820`, `6E40285C58`, `234A2E1C70`, `4A5320524 D`, `5105215901`, `7B395F6F1B`, `3607053D0F`, `5A60412E2F`, `441B7E3F3 B`, `2E7F1F1564`, `7A35576A73`, `0A47385F62`, `7648485C0F`, `7065726D3 5`, `7A42560E7C`, `7663753770`, `2F712F6744`, `2B2F18287E`, `54407A715 A`, `2C29343F0D`, `3F254E2056`, `242348373C`, `4243073F70`, `2B7E560C7 5`, `29590B7460`, `707E1D5136`, `282E5E3E5F`, `3E71756A5F`, `18460D120 F`, `02266E1976`, `71557C6D79`, `7C6D625C21`, `5E51185230`, `500942200 5`, `5639053D0F`, `01436B503B`, `4D42673844`, `6A554C2B45`, `7F3372286 7`, `5340726A6C`, `03770B7534`, `5D284C3367`, `1332434407`]" }}{PARA 0 "" 0 "" {TEXT -1 22 "was uncrypted with key" }}{PARA 0 "" 0 "" {TEXT -1 119 "seckey := MATRIX([[2, 3, 5, 11, 17], [19, 23, 29, 31, 37 ], [0, 0, 41, 43, 47], [0, 0, 0, 7, 11], [0, 0, 101, 0, 113]])." }} {PARA 0 "" 0 "" {TEXT -1 18 "Decode the message" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 124 "8) P roduce a key of size 5 to encrypt a message of 10 lines. Post the key and the encrypted message to the bulletin board." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "9) \+ Decrypt somone else's posted message." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 208 "10) Create \+ a shorter worksheet to use to do matrix encryption and decryption. (T he shorter worksheet would be a collection of just the procedures need ed. It could more easily be used for other assignments." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{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 }