{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "2D Input" 2 19 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 }{PSTYLE "N ormal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 " " 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 } {PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }} {SECT 0 {PARA 18 "" 0 "" {TEXT -1 23 "MAT312: Applied Algebra" }} {PARA 18 "" 0 "" {TEXT -1 19 "Computer project #2" }}{PARA 19 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 191 "This project is similar \+ to project #1, except that in this case the message was encoded with a poor choice of primes. Your job is to crack the code, decipher the m essage, and save the world." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 18 11 "As before, " }{TEXT 19 8 "Message " }{TEXT 18 234 " is a message which has been encrypted using the RSA public key a lgorithm. In its encrypted form, it consists of 30 numbers of about 70 decimal digits each. To get Maple to read it, you must hit the \+ enter key for each statement." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2190 "Message :=[\n1353835550982 5098433817370926846543919557618499237576192098246352249328, 4288631183 008148222245169930544201064436274587412275369523418748801451, 13111522 597076326283731781125350440020750846270752206992134849857445558, 23445 040905763019929260502479371806274153356976083214903855583773649152, 24 981107695348169489280262930682208281602995470706428076926633376896388, 181012299469589147939669682802419936082843128285096586760258104033812 9, 3389685337087291163539414778743932432569058954615477557380889911423 09, 102460611415200563571105017081859463249041541645883223559793527418 92110, 267719248599189604044945095147316776981270364773823759772583762 65281282, 260866832095576752908392968714355922871151372434151118409424 41232109781, 120307438286073623576890242353633261995361619128058622861 18765328506247, 671135308621709039254469854693418379800582114657092370 8450384727375787, 9404427465295141226096007183116150199481189289774968 168740119794246714, 27140404046308762893094890395854086938657754547516 000267249338941002102, 22824400246154264316495348301599100259922768735 450011009742545640398770, 12844753218630148577500389061739741237346858 698121676853383367963356972, 12656900291905081666057697726323575464153 031698602409768725750790221081, 91283994455647849354683255469549459033 90175564677010550827489350481665, 146247768264442929607014117270046223 0079039137822876836723042099168994, 2676793024650673944656328446863312 4742267462780690963089990837504602166, 2664968728637273234137896989884 4355219329717392638840243671854721928643, 2714922439311715499484960384 3271853891347718002688277820144076575398054, 1637760541444209211187762 7185463674674910220425473664503730976288670026, 2601684555379140161007 0492488218139106368886689332861371007833241250517, 2056433485069218658 1317145377273150911004397404537868685196624575449462, 2141460791274714 3936886577387304522692506496345672951724577839345356072, 7999184836524 6740193983934361605494240006768820454709360009627229985, 7281267267054 040587811908517170389134748042772257000377189509121332945, 10038099270 738439341621472388355782696615407460357145991750833581958941, 19312121 694824256292880058640333274620788725194560429244270423719031594]:" }}} {PARA 0 "" 0 "" {TEXT -1 24 "As before, the notation " }{TEXT 19 10 "M essage[n]" }{TEXT -1 28 " allows you to refer to the " }{XPPEDIT 18 0 "n^th;" "6#)%\"nG%#thG" }{TEXT -1 20 " number in the list." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "The message was e ncoded using the following " }{TEXT 19 4 "base" }{TEXT -1 50 ", which \+ is, as usual, the product of two primes. " }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 80 "base := 2760698538716225514973902344910793166845871 6142620601169954803000803329;" }}}{PARA 0 "" 0 "" {TEXT -1 50 "The mes sage was encoded using the public exponent " }{TEXT 19 2 "a " }{TEXT -1 6 "below." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "a:=955414075 64551142884433930859007846184688349517132011538195190379009;" }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 253 "Unfortun ately for the sender (but fortunately for you), the sender of the mess age wasn't paying attention in class and chose a base which is not suf ficiently large to provide cryptographic security. In order to crack \+ the code, you need only factor the " }{TEXT 19 4 "base" }{TEXT -1 44 " and determine the mutiplicative inverse of " }{TEXT 19 1 "a" }{TEXT -1 84 ", then proceed as in project 1. There are a few words on how t o do this at the end." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 510 "As in the first project, after cracking the code, yo u have a pile of 30 numbers, and you need to convert these numbers bac k to readable text. In this case, the message was read 32 characters \+ at a time (instead of 47 as before), so the each chunk of the message \+ can be viewed as a 32-digit number in base 128 (such numbers are abou t 70 digits long when written in base 10). As before, spaces, punctua tion, line breaks, and so on were treated as part of the message, and \+ also encoded. Below is a version of " }{TEXT 19 18 "PrintNumberAsText " }{TEXT 18 100 "which translates such numbers back to text. It is e ssentially the same as the version in project 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 165 "PrintNumber AsText:= proc(num)\n local i,p,k;\n p:=128;\n k:=32;\n printf(\"%s \",\n convert([seq( iquo(modp(num,p^(k-i+1)), p^(k-i)), i=1.. k)],'bytes'));\n end;" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 144 "Now we return to th e mechanics of cracking the code. One thing we need to know is how to factor the base. Maple will factor integers using the " }{TEXT 19 8 " ifactor " }{TEXT -1 86 "command. For example, to factor the number 12 34567890123456789, we do the following:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "ifactor(123456789012345678901);" }}}{PARA 0 "" 0 "" {TEXT -1 106 "WARNING: big numbers take a long time to factor. Maple \+ may take a few minutes to factor the number called" }{TEXT 19 5 " base " }{TEXT -1 176 " above. Factoring another number only slightly large r may take an hour or two, and, of course, factoring a 100-digit numbe r should not be doable at all with today's computers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 149 "In order to avoid ret yping the factors, we have to do a little trickiness. If this confuse s you, just ignore this part, or cut and paste the answer." }}{PARA 0 "" 0 "" {TEXT -1 24 "One way would be to use " }{TEXT 19 8 "ifactors" }{TEXT -1 61 " instead, but here's another. First, factor the number \+ with " }{TEXT 19 7 "ifactor" }{TEXT -1 78 ", and give the result a nam e. Then each factor can be accessed using Maple's " }{TEXT 19 3 "op \+ " }{TEXT -1 18 "command, as below:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "facts:=ifactor(123456789012345678901);\nf1:=op([1,1], facts);\nf2:=op([2,1],facts);" }}}{PARA 0 "" 0 "" {TEXT -1 155 "Now we can use f1 and f2 for the factors instead of trying to retype them. \+ That is, of course, less important in this example where the factors a re short." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 216 "The other mechanical piece needed is how to compute the multiplic ative inverse. Maple does this easily. for example, to compute the i nverse of 9 modulo 17 (the answer should be 2, since 2*9=18=1 mod 17), we just do" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "1/9 mod 17;" }{TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 108 "Or, to compute the inverse of 123456789012345678901 mod \+ 510422739085023549128244953257600876799 and call it " }{TEXT 19 3 "inv " }{TEXT -1 39 ", the command is essentially the same:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "inv := 1/23456789012345678901 mod 5 10422739085023549128244953257600876799;" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 219 "Armed with those two bits of info rmation, your deep understanding of the RSA algorithm, and your exper ience with project 1, you should now be able to figure out the decrypt ion key and decipher the message. Good Luck." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK " 40" 0 }{VIEWOPTS 1 1 0 3 2 1804 }