{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 "" -1 256 "" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 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 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 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 "Title" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 256 19 "Maple Worksheet #4 " }} {PARA 18 "" 0 "" {TEXT 284 39 "The RSA Public Key Cryptographic Scheme " }{TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 24 "How the RSA s cheme works" }}{PARA 0 "" 0 "" {TEXT -1 96 "Suppose Alice wants Bob to send her a secret message using the RSA scheme. Here's what she does. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "1. Sh e finds two large primes p and q." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 33 "2. She forms the product m = pq.\n" }} {PARA 0 "" 0 "" {TEXT -1 16 "3. She computes " }{XPPEDIT 18 0 "phi(m) \+ = (p-1)*(q-1);" "6#/-%$phiG6#%\"mG*&,&%\"pG\"\"\"F+!\"\"F+,&%\"qGF+F+F ,F+" }{TEXT -1 25 ". [This is the so-called " }{TEXT 263 18 "Euler phi function" }{TEXT -1 28 " applied to the modulus m. ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "4. She chooses a posit ive integer e such that igcd(e," }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6# %\"mG" }{TEXT -1 6 ") = 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "5. She computes the inverse, call it d, of e modu lo " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 2 ".\n" }} {PARA 0 "" 0 "" {TEXT -1 92 "6. She sends the pair of numbers [m,e] to Bob. This pair of numbers may be made public, but " }{TEXT 257 11 "th e numbers" }{TEXT -1 8 " p,q, d " }{TEXT 259 3 "and" }{TEXT -1 1 " " } {XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 1 " " }{TEXT 258 23 "should be kept secret! " }{TEXT -1 19 " We call [m,e] the " } {TEXT 261 10 "public key" }{TEXT -1 12 " and d, the " }{TEXT 262 11 "p rivate key" }{TEXT -1 2 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 106 "7. She tells Bob how to use Maple to convert t he text of his message into a sequence of positive integers " } {XPPEDIT 18 0 "a[1];" "6#&%\"aG6#\"\"\"" }{TEXT -1 3 " , " }{XPPEDIT 18 0 "a[2];" "6#&%\"aG6#\"\"#" }{TEXT -1 10 ", . . . , " }{XPPEDIT 18 0 "a[k];" "6#&%\"aG6#%\"kG" }{TEXT -1 51 " each less than m. One such \+ method is shown below. " }{TEXT 260 31 "This method can be made public ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "8. S he tells Bob to compute for each i the number " }{XPPEDIT 18 0 "b[i] = `mod`(a[i]^e,m);" "6#/&%\"bG6#%\"iG-%$modG6$)&%\"aG6#F'%\"eG%\"mG" } {TEXT -1 51 " and tells him to send her the sequence of numbers " } {XPPEDIT 18 0 "b[1];" "6#&%\"bG6#\"\"\"" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "b[2];" "6#&%\"bG6#\"\"#" }{TEXT -1 9 ", . . ., " }{XPPEDIT 18 0 "b[k];" "6#&%\"bG6#%\"kG" }{TEXT -1 23 ". He need not keep the " } {XPPEDIT 18 0 "b[i];" "6#&%\"bG6#%\"iG" }{TEXT -1 64 " 's secret after he has computed them. But, he should keep the " }{XPPEDIT 18 0 "a[i] ;" "6#&%\"aG6#%\"iG" }{TEXT -1 10 "'s secret." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "9. Now when Alice gets th e " }{XPPEDIT 18 0 "b[i];" "6#&%\"bG6#%\"iG" }{TEXT -1 28 " 's from Bo b, she computes " }{XPPEDIT 18 0 "`mod`(b[i]^d,m);" "6#-%$modG6$)&%\" bG6#%\"iG%\"dG%\"mG" }{TEXT -1 34 " and this will turn out to be the \+ " }{XPPEDIT 18 0 "a[i];" "6#&%\"aG6#%\"iG" }{TEXT -1 82 "'s. Then she \+ can use Maple to convert these back into text as we illustrate below. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 21 "The Maple map command" }}{PARA 0 "" 0 "" {TEXT -1 212 " Let f deno te any function. We let L1 denote the list [1,2,3,4,5] . We can use ma p to apply f to each element of this list and obtain a new list [f(1), f(2),f(3),f(4),f(5)] which we call L2. f may be any function." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 30 "L1:=[1,2,3,4,5,6,7,8,9,10,11];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L2:=map(f,L1);" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 61 "We can then apply a function g to L2 to obtain a n ew list L3." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L3:=map(g,L2 );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 62 "To be more specific define \+ f, for example, to be the function " }{XPPEDIT 18 0 "f(x) = x^2;" "6#/ -%\"fG6#%\"xG*$F'\"\"#" }{TEXT -1 67 " and g to be the inverse g(x) =s qrt(x). And let's see what happens:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "f:=x->x^2;\ng:=x->sqrt(x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "L1:=[1,2,3,4,5];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L2: =map(f,L1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L3:=map(g,L2 );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 18 "A detailed examp le" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 168 "We illustrate the RSA scheme using two randomly chosen primes wit h 20 decimal digits each. We first generate two 20 digit random number s and then use the Maple command " }{TEXT 271 9 "nextprime" }{TEXT -1 56 " to obtain the smallest primes greater than each number:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "N:=rand(10^19..10^20 -1)(); \nM:=rand(10^19..10^20 -1)();" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "p:=nextprime(N);\nq:=nextprime(M);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "m:=p*q;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 " length(m);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "PHI:=(p-1)*(q -1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "e:=rand(10^19..10^2 0-1)();" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 200 "If by chance the modu lar inverse doesn't exists you may go back, put the cursor back on the line where e is computed and hit return. After, possibly, a few tries you will obtain a suitable value of e." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "d:=1/e mod PHI;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "Check that ed mod " }{XPPEDIT 18 0 "phi(m)" "6#-%$phiG6#%\"mG" } {TEXT -1 5 " = 1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "e*d mo d PHI;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 7 "So the " }{TEXT 264 10 " public key" }{TEXT -1 32 " sent to Bob and made public is " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "Public_Key:=[m,e];" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "The private key in this case is:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Private_key:=[p,q,d,PHI];" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 " In cryptography, " }{TEXT 267 10 "plain text" }{TEXT -1 78 " refers to any message that is not enciphered. After enciphered it is called " }{TEXT 268 13 "cipher text. " }{TEXT -1 76 "\n\nNow we assign Bob's me ssage to the variable named plain_text, as follows:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 374 "plain_text:=\"Neil Johnson has a j ob that's nothing if not unusual: He investigates how to uncover conce aled messages embedded in sound and video files. \n\nA researcher at V irginia's George Mason University, Johnson is one of a small but growi ng number of digital detectives working in the field of computer stega nalysis -- the science of detecting hidden communications. \"; \n" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 297 "Note that the text includes new l ine symbols, \\n, as well as numerous blanks.The \\ at the end of each line is just Maple's way of saying that this should all be on one lin e, but I am forced to break it at this point. The number List1 may be \+ thought of as a base 256 representation of some number. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "List1:=convert(plain_text,bytes);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "We now convert the base 256 re presentation to base m with the following command. We call the result \+ List2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "List2:=convert(Li st1,base, 256,m);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "Next we appl y the mapping which send x to " }{XPPEDIT 18 0 "`mod`(x^e,m);" "6#-%$m odG6$)%\"xG%\"eG%\"mG" }{TEXT -1 67 " to each number in List2. This ca n be done using the Maple command " }{TEXT 265 5 "map. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "To make this easier we define a decipheri ng function E so that " }{XPPEDIT 18 0 "E(x) = `mod`(x^3,m);" "6#/-% \"EG6#%\"xG-%$modG6$*$F'\"\"$%\"mG" }{TEXT -1 67 ". We use the binary exponentiation method implemented by Maple as " }{TEXT 266 17 "Power( x,e) mod m." }{TEXT -1 343 " This allows us to implement in Maple the two functions E and D described in the corollary on page 149. (Note \+ that we cannot use D since it is protected by Maple to use for the dif ferentiation operator. We get around this by use of the command unprot ect(D). This is okay for us since we won't be doing any differentiatio n in this worksheet.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "un protect(D);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "E:=x->Power( x,e) mod m;\nD:=x->Power(x,d) mod m;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "We illustrate that the functions given by " }{TEXT 269 3 "e,m " }{TEXT -1 19 " and that given by " }{TEXT 270 3 "d,m" }{TEXT -1 50 " are inverses of each other. Starting with x = 58:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "58,E(58), D(E(58));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "This shows that D(E(58)) = 58 as we desire.\n" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "Now we can apply this to List2 to \+ obtain the enciphered list of numbers we will send to Alice:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "cipher_text:=map(E, List2); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 253 "Bob sends this to Alice and \+ the whole world for that matter. But since only Alice has the secret \+ private key, only she will be able to decipher the message. We show no w how she deciphers the message. First she applies her secret decipher ing function D:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "decipher 1:=map(D,cipher_text);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "She nex t converts back to base 256:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "decipher2:=convert(decipher1,base,m,256);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "Finally she converts the numbers back to text and se es what message Bob sent her:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "decipher3:=convert(decipher2,bytes);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 23 "Breaking the RSA scheme" }}{PARA 0 "" 0 "" {TEXT -1 157 "To decipher a message sent with this scheme i t is believed that one must be able to find the private key d given on ly the public keys m and e. If one knows " }{XPPEDIT 18 0 "phi(m);" "6 #-%$phiG6#%\"mG" }{TEXT -1 54 " then Maple quickly computes d by the c ommand 1/e mod " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 3 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "It is known that computing " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6# %\"mG" }{TEXT -1 497 " is the same order of difficulty as factoring m. If m is the product of two 100 digit primes, say, then m is about 200 digits long and current factoring algorithms are unable to factor suc h numbers within a reasonable time. Don't ask Maple to factor such a \+ number for you unless you want to wait a long time -- years or centuri es, depending on the size of the number and luck. Factoring algorithms sometimes depend on luck. After all one might guess the factors. But \+ this would be very unlikely. " }}{PARA 0 "" 0 "" {TEXT -1 5 " " }} {PARA 0 "" 0 "" {TEXT -1 6 "It is " }{TEXT 274 8 "believed" }{TEXT -1 178 " but not proved that breaking the RSA scheme is equivalent to fa ctoring the modulus m. The best algorithm known at present for factori ng large, difficult numbers, is called the " }{TEXT 275 38 "Number Fie ld Sieve Factoring Algorithm" }{TEXT -1 342 ". There is always the po ssibility that someone will find a new faster factoring algorithm or t hat scientists will be able to build superfast computers based on some new technology such as quantum mechanics or DNA. Very crude quantum \+ computers and DNA computers have been implemented. But at present they are able to solve only toy problems." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 33 "A group of mathematicians called " } {TEXT 272 9 "The Cabal" }{TEXT -1 79 " announced the completion, on No vember 14, 2000, of the factorization with the " }{TEXT 273 33 "Specia l Number Field Sieve (SNFS)" }{TEXT -1 36 " of the 233-digit Cunningha m number " }{XPPEDIT 18 0 "2^773+1;" "6#,&*$\"\"#\"$t(\"\"\"F'F'" } {TEXT -1 77 ". The sieving was done on about 250 computers working on ly on this problem. " }{TEXT 282 43 "The sieving took about five calen dar months" }{TEXT -1 45 ". Factorization details are available from: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT 279 48 "f tp://ftp.cwi.nl/pub/herman/SNFSrecords/SNFS-233" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 361 "Numbers as large as 200 \+ decimal digits which are a product of two 100 digit primes which are c hosen with care now seems to be out of reach of current theory and tec hnology. For even better security one may of course increase the size \+ of the initial primes and hence the size of m. However, if a poor ch oice of primes is made the number still may be factored. " }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 249 "There are many so urces of information on the RSA scheme. It is important not only for s ending data securely but also can be used to \"sign\" electronically s ubmitted documents. For more information see, for example, any of the \+ many books available on " }{TEXT 276 14 "cryptography. " }{TEXT -1 149 "Just search on this key word using Web Luis or on your favorite s earch engine. There is now a company that controls the use of the RSA \+ scheme called " }{TEXT 277 21 "RSA Data Security Inc" }{TEXT -1 25 " w hose website's URL is " }{TEXT 278 1 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT 285 30 "http://www.rsasecurity.com/. \+ " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 89 "Both \+ Netscape and Internet Explorer contain security software from RSA Data Security Inc." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 22 "Homework Assignment #4" }}{PARA 0 "" 0 "" {TEXT 280 11 "Exercise 1." }{TEXT -1 98 " Alice sent a message to Bob using the RSA scheme. The public key used to encode the message was " }}{PARA 0 "" 0 "" {TEXT -1 22 " " }}{PARA 0 "" 0 "" {TEXT -1 44 " [m,e] = [2885500349, 37813]. " }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "The enciphered mes sage was" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 164 " [563138230, 1266232333, 8056785, 2212264067, 2797153 755].\n\nDecipher this message. [In this case it is possible since m i s easy to factor using Maple's " }{TEXT 283 7 "ifactor" }{TEXT -1 14 " procedure.]\n\n" }{TEXT 281 11 "Exercise 2." }{TEXT -1 170 " Find, u sing Maple, a triple [m,e,d] where m is the product of two 100 decimal digit primes, e is a random number of 100 decimal digits and d is the inverse of e modulo " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" } {TEXT -1 0 "" }{TEXT -1 169 ". Use this to encipher some message of yo ur choice of at least three lines length using the RSA scheme. Then de cipher the enciphered text to obtain the original message." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{MARK "5 7 6" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }