{VERSION 6 0 "IBM INTEL NT" "6.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 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 } {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 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {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 "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 257 1 {CSTYLE "" -1 -1 "Times" 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 {PARA 256 "" 0 "" {TEXT 256 0 "" }{TEXT 257 10 " Math Club" }} {PARA 256 "" 0 "" {TEXT 280 3 "RSA" }}{PARA 256 "" 0 "" {TEXT -1 0 "" }{TEXT 258 0 "" }{TEXT 259 16 "Wednesday Dec. 3" }{TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 260 15 "Our Plan Today:" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 241 "We want to mak e a public key and send secret messages to each other using Maple. No te: Maple commands are in red, and the output from the command is in \+ blue. To execute the command, press enter when the cursor is anywhere in the red text." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "restart: #It's a good idea to restart when \+ you begin new work" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }{TEXT 266 7 "Part I " }}{PARA 257 "" 0 "" {TEXT -1 16 "A Small Example:" }}{PARA 0 "" 0 "" {TEXT -1 135 "In this example \+ Bob is going to send a message to Alice. We will use the table on pa ge 4 of our notes to convert letters to numbers.\n" }}{PARA 0 "" 0 "" {TEXT -1 5 "1) " }{TEXT 261 5 "Alice" }{TEXT -1 167 " must create he r public key for Bob to use when he encripts his message to her. So s he picks two prime numbers: (p=71 and q=41). We will define p and q \+ using Maple." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "p:=71;\nq:=4 1;\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#r" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"qG\"#T" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "It is a good idea to make sure our numbers are prime, and Maple has a wa y of checking that." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "isprime(p);\nisprime(q);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "2) \+ " }{TEXT 267 5 "Alice" }{TEXT -1 103 " defines her modulus N to be the product of p and q. This will be the first piece of her public key. \+ " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "N:=p*q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"%6H" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 5 "2a) " }{TEXT 268 5 "Alice" }{TEXT -1 1 " \+ " }{TEXT 270 9 "privately" }{TEXT -1 97 " computes the auxillary modul us N2:=(p-1)*(q-1). No one else will ever see or use this number. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "N2:=(p-1)*(q-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#N2G\"%+G" }}}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 269 "3) Now she finds a number e which \+ is relatively prime to N2; this will be the public encoding power and \+ she will tell it to the world. A good e must be relatively prime to N 2=(p-1)*(q-1), so that Alice will be able to find a decoding power d. \+ So we check the gcd: " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "e := 13;\ngcd(e,N2); #check relative prime" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"eG\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" } }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 6 "3a ) " }{TEXT 269 5 "Alice" }{TEXT -1 1 " " }{TEXT 279 10 "privately " } {TEXT -1 372 "finds her \"secret\" decoding power. Since e is relativ ely prime to N2=(p-1)*(q-1) it has a multiplicative inverse d, mod (p- 1)*(q-1). (We can find the multiplicative inverse using the Euclidean algorithm. It can be rather tedious, but luckily for us, Maple has a subroutine which does this step for us.) By the Euler-Fermat Theorem , this d will be the decoding power. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "isolve(e*z + y*N2 =1);\n #find decryption power, wh ich is \"z\" above" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$/%\"yG,&\"\") \"\"\"*&\"#8F(%$_Z1GF(F(/%\"zG,&\"%B " 0 "" {MPLTEXT 1 0 21 "d:= -1723 mod N2;\n " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"%x5" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 8 "4) Now " }{TEXT 271 5 "Alice" }{TEXT -1 173 " is ready to receive messages. She yells from the rooftops: My \+ modulus is N=2911. My encryption power is e=13. If you want to send \+ me a message use the encrypt function:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "encrypt:=x->x^e mod N;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(encryptGf*6#%\"xG6\"6$%)operatorG%&arrowGF(-%$modG6$)9$%\"eG% \"NGF(F(F(" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 262 5 "Note:" }{TEXT -1 61 " In the notes we use the letter E for the encrypt function. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 22 "5) The message which " }{TEXT 272 3 "Bob" }{TEXT -1 239 " wishes to send Alice is \"Hi\". He consults Davis' table on pag e 4. The number message is 1819. Then he checks to make sure that nu mber is less than Alice's N. It is, so we don't need to worry about b reaking the message up into packets." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "M:=1819;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"MG\"%> =" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "5a) \+ " }{TEXT 273 3 "Bob" }{TEXT -1 48 " encrypts the message using Alice's public key: " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "encrypt(M); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$;%" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 275 1 " " }{TEXT -1 39 "and then sends the number 416 to Alice." }}{PARA 0 "" 0 "" {TEXT -1 4 "6) " }{TEXT 274 8 "Mr. Evil" }{TEXT -1 94 " intercepts the message, but he can't d ecode it since he doesn't know what Alice's d value is." }}{PARA 0 "" 0 "" {TEXT -1 102 "7) Alice now decodes the message using her decodin g power d, which she found in step 3a, a while ago." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "decrypt:=x->x^d mod N;\ndecrypt(416);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%(decryptGf*6#%\"xG6\"6$%)operatorG%& arrowGF(-%$modG6$)9$%\"dG%\"NGF(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#\"%>=" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 263 6 "Alice " }{TEXT 276 100 "consults t he table, sees that 1819 corresponds to Hi, and understands what Bob h as sent. WE DID IT!" }{TEXT 277 2 " " }{TEXT 278 65 "Except with Ali ce's puny primes our code could easily be broken. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT -1 9 "Part II: " }}{PARA 257 " " 0 "" {TEXT -1 22 "A more practical size." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 308 " In a good code, the prime s will be BIG. For this example, we will use somewhat small primes ag ain, but they will be bigger than 10^50, so that our moduli will be bi gger than 10^(100). This is still not big enough to be secure, but we will be able to send messages with up to 50 characters per packet. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 271 "restart: #this will clear all old definitions.\n #I t's a good idea to restart when you begin\n #new work - of c ourse you might need to \n #go back and re-enter some old co mmands that\n #you need again. (Repetition is good pedagogy .)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 395 "randomize();#this wi ll tell the \"random\" number generator \n #where to start. \+ the \"seed\" it generates is based\n #on the system clock, s o if you all enter this command at\n #the same time you migh t get the same \"random\" numbers.\n #That would be bad. Se e help windows to see how to\n #make your random numbers unl ike your classmates'.\n " }{TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+RUFG7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "rand(); #random number generator,\n #default range is between 0 and 12 digits " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"-%=4\\j g#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "bigger:=rand(1..10^51 ): #much bigger\nbigger();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"T`t() >vC.ozo\"z=m*HltS9S7w$4!=$" }}}{PARA 0 "" 0 "" {TEXT -1 8 "For now," } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "good:=rand(1..10^51):\ngood ();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"TK\\;#oxPAT+d/*=YIz$RfN*oQ3;$ y" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 214 "for i from 1 to 100 d o\n x1:=good():\n if (x1>10^50 #check number is big enough \n and\n isprime(x1)=true) #and check if number is prime\n \+ then print(x1); #if it is, let's see it\n fi;\nod: \n " }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"Tf[+P0#[))ePAnL?RP!*eXPR0([L,\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"T*3Pm-)*>!\\ID3#*>&4[%Gr#o[z#eoo&" } }}{PARA 0 "" 0 "" {TEXT -1 382 "It's unlikely your numbers agree with \+ mine. (Well, in truth if you all start the generator at the same plac e, you'll all get the same so-called random numbers.) You may chose y our p and q using your list! We are repeating the process we worked o ut in the tiny example.) If there aren't two options listed above, re peat the above commands until there are two options for p and q." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 42 "1) Choos e two primes from the list above." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 216 "p:= 101334870539374558903739203367223758884820537004 859; #Just copy and paste the numbers from your list above using \nq: = 568685827948682712844809519920825304901998026637089; #the shortcut \+ keys (ctrl c and ctrl v)." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"T f[+P0#[))ePAnL?RP!*eXPR0([L,\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" qG\"T*3Pm-)*>!\\ID3#*>&4[%Gr#o[z#eoo&" }}}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 58 "2) Compute our modulus N which is pa rt of our public key." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "N:=p*q;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6 #>%\"NG\"`q^ahA#3:?]*=7%G>uL*[h!zK4^TwwF%\\9HHl8()=U:\\c/?)pzcFv/xid" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 393 "To se e that a system of this size is not secure, we could try the following command. This is the command that would fail if we had chosen primes of length 200 instead of 50, and that's the reason RSA is secure when you use huge primes. Note: It might take too long for the computer \+ to do this, so you can skip this command if you want. It is very effe ctive if we chose primes of length 12." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(N);" }}}{PARA 0 "" 0 "" {TEXT -1 46 "2a) Fin d our auxillary modulus N2=(p-1)*(q-1)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "N2:=(p-1)*(q-1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#> %#N2G\"`q/N(*e'*o9k))pJbpa#[9VLtWC\"3i(4F%\\9HHl8()=U:\\c/?)pzcFv/xid " }}}{PARA 0 "" 0 "" {TEXT -1 72 "3) Find our encryption power which \+ has a multiplicative inverse mod N2." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "for i from 1 to 10 do\n x2:=good();\n if gcd(x2,N 2)=1\n then print(x2);\n fi\nod:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"T`=,O$=YjYa959,!H@Ti*zA_gX?!*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"T*>\\a!of>0h9'3VcL;cDEeTumStq" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \"Tb,MUcPnw+P@0&oz.u$*elXs$zc>$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"T Nl$[NU\\N#fuC\">E]Zr*QHE)Hevij" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 91 "e:= 902045605222799624121290011410145446634618336011853;\ngcd( e,N2); #check relative prime" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" eG\"T`=,O$=YjYa959,!H@Ti*zA_gX?!*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \"\"\"" }}}{PARA 0 "" 0 "" {TEXT -1 22 "3a) Get decoding power" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "isolve(e*z + y*N2 =1);\n # find decryption power, which is \"z\" above" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#<$/%\"yG,&\"T@`<&os(QcD(>$HB%[\">*o!3knHy4K#\"\"\"*&\"T `=,O$=YjYa959,!H@Ti*zA_gX?!*F(%$_Z1GF(F(/%\"zG,&\"`q6[R'GI;'[#e4p[%3mJ wZh4s6q7;uP*>&zO$ynJzE4#)QW!G\"oO2(RqF[\"!\"\"*&\"`q/N(*e'*o9k))pJbpa# [9VLtWC\"3i(4F%\\9HHl8()=U:\\c/?)pzcFv/xidF(F+F(F0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 161 "d:=-14827703970736681280443882092679316778 336795199377416127011720961477631660844869095824861630286394811 mod N2 ;\n #use the mouse to copy and paste big numbers" }}{PARA 12 "" 1 " " {XPPMATH 20 "6#>%\"dG\"`q$pyDPfIbhS2%oCY;8b'=xB2!Q\\\"o\\+D'\\#>e.dU F#Gog:q:,-#y++!G%" }}}{PARA 0 "" 0 "" {TEXT 264 16 "Technical Point:" }{TEXT -1 459 " To speed up the computation for the computer, or so M aple will not complain too much, we need to tweek things a bit. We wi ll run into problems when we try to take large powers of large numbers , so we have to lead it through this modular computation in smaller st eps. The procedure below does the trick. It's analagous to the method \+ Davis outlines in his notes, except using powers of 10 rather than pow ers of 2. Here's the idea: Suppose we want to compute" }}{PARA 256 " " 0 "" {XPPEDIT 18 0 "[783]^565;" "6#*$7#\"$$y\"$l&" }{TEXT -1 7 " mo d N" }}{PARA 0 "" 0 "" {TEXT -1 25 "in small steps. We write" }} {PARA 256 "" 0 "" {XPPEDIT 18 0 "[783]^565 = [[783]^500]*[[783]^60]*[[ 783]^5];" "6#/*$7#\"$$y\"$l&*(7#*$7#F&\"$+&\"\"\"7#*$7#F&\"#gF-7#*$7#F &\"\"&F-" }{TEXT -1 7 " mod N" }}{PARA 256 "" 0 "" {XPPEDIT 18 0 "` ` = [[783]^100]^5*[[783]^10]^6*[[783]]^5;" "6#/%\"~G*(7#*$7#\"$$y\"$+\" \"\"&7#*$7#F)\"#5\"\"'7#7#F)F+" }{TEXT -1 8 " mod N." }}{PARA 0 "" 0 "" {TEXT -1 112 "By successive multiplication and reduction to the res idue value, we then make a table of the residue values of " } {XPPEDIT 18 0 "783;" "6#\"$$y" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "[783]^ 10;" "6#*$7#\"$$y\"#5" }{TEXT -1 3 " , " }{XPPEDIT 18 0 "[783]^100;" " 6#*$7#\"$$y\"$+\"" }{TEXT -1 3 " , " }{XPPEDIT 18 0 "[783]^1000;" "6#* $7#\"$$y\"%+5" }{TEXT -1 268 ", etc., i.e of residue values for the po wers of 783, where the power is itself a power of 10. We then multiply these table residue values and reduce mod N, the appropriate number o f times, as indicated in the decomposition above. Thus we recover the residue value of " }{XPPEDIT 18 0 "[783]^565" "6#*$7#\"$$y\"$l&" } {TEXT -1 69 " without every having to deal with integers which are gr eater than " }{XPPEDIT 18 0 "N^2;" "6#*$%\"NG\"\"#" }{TEXT -1 77 ". \+ (Actually I was sloppy, and my intermediate numbers could get as large as " }{XPPEDIT 18 0 "N^10;" "6#*$%\"NG\"#5" }{TEXT -1 48 ", but for o ur N-values this won't be a problem.)" }}{PARA 0 "" 0 "" {TEXT -1 85 " Here is the procedure, which uses a subprocedure to pick off digit s from numbers:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "digit:=(x ,n)->trunc(x/10^n)-10*trunc(x/10^(n+1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&digitGf*6$%\"xG%\"nG6\"6$%)operatorG%&arrowGF),&-%&truncG6#*& 9$\"\"\")\"#59%!\"\"F3*&F5F3-F/6#*&F2F3)F5,&F6F3F3F3F7F3F7F)F)F)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 126 "digit(123.56,-1);\ndigit(12 3.56,2);\ndigit(123.56,0);\n #check how digit picks off the digits c orresponding\n #to powers of 10" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 183 "4) Now \+ Alice tells everyone her values for e and N and says to send her a mes sage, put your message broken into packets of no more then 50 digits i nto the following encrypt function." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 611 "encrypt:= proc(M1,E,N3) #message, encipher power,mo dulus\n #we assume all M1's, E's have at most 105 digit s\n local i,j, #indices\n L1, #list of succesive 10th p owers of M1\n ans; #answer\n #this do loop makes the list o f powers of M1 described above:\n L1[1]:=M1 mod N3;\n for i from 2 \+ to 105 do\n L1[i]:=L1[i-1]^10 mod N3;\n od: \n #now multiply tab le entries to get the residue value of the\n #encryption power functi on:\n ans:=1: #initialize answer\n for j from 1 to 105 do\n a ns:=ans*(L1[j]^digit(E,j-1)) mod N3;\n od:\n\nRETURN(ans);\nend:\n \+ \n " }}}{PARA 0 "" 0 "" {TEXT -1 54 "5) Let's check!! ! Bob sends the message 12345678910." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "M:=12345678910;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"MG\",5*ycM7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "5a) Bob encrypt s his secret message. He calls it \"secret,\" and he sends it to Alic e." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "secret:=encrypt(M,e,N );" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'secretG\"`qQUm[\"\\M;%y]W>q^^ t2s]Xrf#[A*yv:dhPS_4m$ey@/:8hF(o&\\-J$y#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "6) Mr. Evil can't decode the message." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "7) Alice now decodes t he message with her secret d value." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "encrypt(secret,d,N);\n #decryption is just encryptio n with a different power" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\",5*ycM7 " }}}{PARA 0 "" 0 "" {TEXT -1 6 "YES!!!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT -1 26 "Pa rt III\nAn Actual Message" }}{PARA 257 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT -1 0 "" }{TEXT 265 64 "We Use Davis' Table on page 4 to encrypt the following message." }}{PARA 0 "" 0 "" {TEXT -1 210 "3 0444110535737484556611051421049415439611045551050515610555654374550414 0631010195610405451525241564410375510564441104341505648411054374550104 254514910444137584150105752414010564441105248373941103841504137564463 " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 105 "Our \+ message is too long, so we need to break it up into packets, each of w hich is no more then 50 digits." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 239 "M1:=30444110535737484556611 051421049415439611045551050;\nM2:=515610555654374550414063101019561040 54515252415644;\nM3:=1037551056444110434150564841105437455010425451491 0;\nM4:=44413758415010575241401056444110524837394110384150;\nM5:=41375 64463;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M1G\"S]5bX5hRaT\\5U^5hcX[ Pd`5TWI" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M2G\"SWcT__^aS5c>55jST]X Pacb5c^" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M3G\"S5\\^aU5]XPa5T[c]TV 5TWc5bP5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M4G\"S]TQ5TRP[_5TWc5ST_ d5]TePTW" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M5G\"+jWcPT" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 104 "C1:=encrypt(M1,e,N);\nC2:=encrypt( M2,e,N);\nC3:=encrypt(M3,e,N);\nC4:=encrypt(M4,e,N);\nC5:=encrypt(M5,e ,N);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#C1G\"`q<)pg#fns%*)*f5))QT#f *=MCx\\I(HA!)*\\/B6Ke0F5+YVG.N&>LK&[/`nc&" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#C2G\"`q3(*>iO!yuy,`g^,cnOh6Nnsq!Gc/:!)e%y;%\\>1lg!o5 $y*[;q2L'HTt%" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#C3G\"`q_s6lZmBj19# \\12Z\"zZ$H0(RYQ]#ohB*H<8iLvzh&Q6oSuk5xLo;t'>#" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#C4G\"`q#)*e.#*oYi[w1L$H\"QsA>YA2-cY))f3&owm&GX%RR=&G %#C5G\"`q0\\t.Pb# 3Wj1Hub.\\=e)HDu\\So9`v#HDY\"zXM\")oy>!34V$4lC8;mGS&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 152 "encrypt(C1,d,N); #decryption is encrypti on with a\n #different power.\nencrypt(C2,d,N);\nencry pt(C3,d,N);\nencrypt(C4,d,N);\nencrypt(C5,d,N);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"S]5bX5hRaT\\5U^5hcX[Pd`5TWI" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"SWcT__^aS5c>55jST]XPacb5c^" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"S5\\^aU5]XPa5T[c]TV5TWc5bP5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"S]TQ5TRP[_5TWc5ST_d5]TePTW" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+jWcPT" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}}{MARK "0 1" 4 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }