{VERSION 5 0 "SUN SPARC SOLARIS" "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 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 2 0 0 0 0 0 0 0 1 }{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 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }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 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 260 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE " " 0 261 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 262 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 263 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {PARA 256 "" 0 "" {TEXT -1 0 "" }{TEXT 256 0 "" }{TEXT 257 17 "ACCESS 2003 - RSA" }}{PARA 257 "" 0 "" {TEXT -1 0 "" }{TEXT 258 0 "" }{TEXT 259 16 "Thursday June 19" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 260 15 "Our Plan Today:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 592 "To help clarify the RSA \+ public-key encryption method that Jim introduced yesterday, we will do the example worked out in the Tom Davis \"Cryptography\" notes, page \+ 13-14. These are great notes - you can think of them as the Cliff Not es for \"The Code Book.\" Davis' example uses small numbers and a one- letter message, and Maple will do all of our computations. I believe \+ this will make the algorithm more clear to you. The explanation of th e Algorithm on page 6-7 of the Rivest-Shamir-Adleman paper is also a v ery concise outline which will make more and more sense as you play wi th examples." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 589 "After we digest Davis' example we will try somewhat larger pr ime numbers, to help prepare you for the part of your group project in which you send yourselves (and me) encoded messages . In your actua l project, which will be posted later today, you will impliment a medi um-sized version of an RSA cipher system (big enough to send short mes sages, but not really big enough to be secure). You will also incorpo rate the \"secure signature\" feature, which we will discuss today. Y ou can read about this in section 8.2 of Davis' notes, or in section I V of the Rivest-Shamir-Adleman paper. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 287 "We will stop our lab work by 10:10 today so that we have plenty of time to make our way over to JTB 120 \+ for the lecture by Professor Seger at 10:30; we will back here all o f tomorrow morning to tie up loose ends we don't finish today, and to \+ get a good start on your week 1 projects. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 626 "The number theory we've talked about, and the relation to RSA cryptography, is usually taught in ou r number theory course, Math 4400. This is a senior level course, so \+ I would expect that some of what we've talked about has been challengi ng. Still, math majors can take Math 4400 fairly early in their under graduate careers since it does not have very many prerequisites beyond algebra and the ability to reason mathematically. As far as ACCESS g oes, we hope that you're enjoying the magic hidden in modular arithm etic, and that you are pleasantly surprised that this \"abstract\" mat hematics turns out to be so practical." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 238 "I will make you do a lot of your own typing in Part I below, so that you can begin learning MAPLE and comm on errors which users make. Therefore, in the file you download, many of the Maple commands which you see in the hardcopy are gone." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 267 7 "Part I " }}{PARA 258 "" 0 "" {TEXT -1 18 "The Davis Example:" }}{PARA 0 "" 0 " " {TEXT -1 196 "In this example Bob is going to send a message to Alic e. I will follow Davis' numbering of the steps on pages 13-14. We a re also going to use his table on page 9 to convert letters to numbers .\n" }}{PARA 0 "" 0 "" {TEXT -1 5 "1) " }{TEXT 261 5 "Alice" }{TEXT -1 173 " must create her public key, for Bob to use when he encripts h is message to her. So she picks two prime numbers, see page 13: (p=2 3 and q=41). Define p and q using Maple." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 278 "restart: #Just as every time you reopen a file you m ust \n # re-execute its commands into Maple's memory, you will of ten\n #want to redo a process in a given file using different\n \+ #data variables. The restart command clears all of \n #the c urrent memory\n " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 217 "p:=23;\nq:=41;\n #Insert prompts with the [> button on the menu bar.\n #use shift-return for multi-l ine commands.\n #make definitions with the symbols :=, NOT with =\n \+ #comment lines have # as their first character" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"# T" }}}{PARA 0 "" 0 "" {TEXT -1 4 "2) " }{TEXT 268 5 "Alice" }{TEXT -1 100 " defines her modulus to be the product of p and q. This will \+ be the first piece of her public key. " }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "N:=p*q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"$V*" }}}{PARA 0 "" 0 "" {TEXT -1 5 "3a) " } {TEXT 269 5 "Alice" }{TEXT -1 1 " " }{TEXT 271 9 "privately" }{TEXT -1 459 " computes the auxillary modulus N2:=(p-1)*(q-1), which is rela ted to Euler's theorem, with which Alice will pick her encoding and de coding powers. No one else will ever see or use this number. First s he 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 mu st be relatively prime to (p-1)*(q-1), so that Alice will be able to f ind a decoding power d. So we check the gcd: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "N2:=(p-1)*(q -1);\ne:=7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#N2G\"$!))" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"eG\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "gcd(e,880); #greatest common denominator \n \+ #-we want it to be 1\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\" " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 361 "ifactor(N2); ifactor(e );\n #for small numbers (only) we can also\n \+ #compare factors to deduce the gcd.\n #How would you fin d out about these commands if you\n #weren't sure how to \+ use them, or even if they existed?\n #Answer: you would u se the Help button at the \n #top right of the menu." }} {PARA 11 "" 1 "" {XPPMATH 20 "6#*()-%!G6#\"\"#\"\"%\"\"\"-F&6#\"\"&F*- F&6#\"#6F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%!G6#\"\"(" }}}{PARA 0 "" 0 "" {TEXT -1 5 "7 ) " }{TEXT 270 5 "Alice" }{TEXT -1 1 " " } {TEXT 280 10 "privately " }{TEXT -1 540 "finds her \"secret\" decoding power. Since she does this step sooner than Davis says, we will too. Since e is relatively prime to (p-1)*(q-1) it has a multiplicative i nverse d, mod (p-1)*(q-1). By Euler's Theorem, which Jim talked about yesterday, this d will be the decoding power. I wouldn't be surprise d if you're still amazed and confused by this fact, but like I tell my students in every class, confusion is the first step to understanding . I'll be happy to talk with anyone who wants to understand this part of the math better...." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 361 " isolve(e*z+y*N2=1); #isolve stands for \"integer solve\", \n #i.e . find integer solutions. Here the unknowns \n #are z and y, sinc e we already set e=7 \n #and N2=880 We don't really care about th e y-value, \n #we just want z. this is because when we interpret \+ \n #e*z+y*N2=1 in N2 clock arithmetic, N2 is congruent to 0, so\n \+ #so ez=1 mod N2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$/%\"yG,&\"\"$ \"\"\"*&\"\"(F(%$_Z1GF(F(/%\"zG,&\"$x$!\"\"*&\"$!))F(F+F(F0" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 197 "d:=-377 mod N2;\n #usin g mod N2 will get d back in usual residue range.\n #We get DAvis' \+ solution from step 7! For \"fun\" you could\n #try getting this n umber from the Euclidean algorithm." }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%\"dG\"$.&" }}}{PARA 0 "" 0 "" {TEXT -1 9 "3b) Now " }{TEXT 272 5 " Alice" }{TEXT -1 171 " is ready to receive messages. She yells from t he rooftops: My modulus is N=943. My encryption power is e=7. If yo u want to send me a message use the encrypt function:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 232 "encrypt:=x->x^e mod N;\n #if you define d e and N above, \n #then their values will be used for the encrypt f unction\n #this command is Maplese for encrypt(x)=x^e mod N.\n #So t his is the syntax for defining \n #elementary functions." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(encryptGf*6#%\"xG6\"6$%)operatorG%&arrowGF(- %$modG6$)9$%\"eG%\"NGF(F(F(" }}}{PARA 0 "" 0 "" {TEXT 262 5 "Note:" } {TEXT -1 97 " In class and in the picture notes I made for you we use the letter E for the encrypt function. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "4) The message which " }{TEXT 273 3 "Bob" }{TEXT -1 117 " wishes to send Alice is the letter Y. He \+ consults Davis' table on page 9. The number that corresponds to Y is \+ 35. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "M:=35;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"MG\"#N" }}}{PARA 0 "" 0 "" {TEXT -1 3 "5) " }{TEXT 274 3 "Bob" }{TEXT -1 48 " \+ encrypts the message using Alice's public key: " }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 59 "C:=encrypt(M); #either of these should work\n C:=M^e mod N;\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"CG\"$X&" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"CG\"$X&" }}}{PARA 0 "" 0 "" {TEXT -1 2 "6)" }{TEXT 276 5 " Bob" }{TEXT -1 31 " sends the number 545 to \+ Alice." }}{PARA 0 "" 0 "" {TEXT -1 4 "8) " }{TEXT 275 5 "Alice" } {TEXT -1 88 " decodes the message using her decoding power d, which sh e found in step 7, a while ago." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "decrypt:=y->y^d mod N;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%(decryptGf*6#%\"yG6\"6$%)operatorG%& arrowGF(-%$modG6$)9$%\"dG%\"NGF(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "decrypt(C); #both of these should work\nC^d mod N;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#N" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#N" }}}{PARA 0 "" 0 "" {TEXT 263 6 "Alice " }{TEXT 277 97 "con sults the table, sees that 35 corresponds to Y, and understands what B ob has sent. WE DID IT!" }{TEXT 278 2 " " }{TEXT 279 146 "Except wit h Alice's puny primes our message pieces can only be one letter long, \+ so what we've got is really no better than a substitution cipher. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 259 "" 0 "" {TEXT -1 9 "Part II: " }}{PARA 260 "" 0 "" {TEXT -1 22 "A more practical size." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 359 " In your pro ject everyone will pick primes bigger than 10^50, so that your moduli \+ will be bigger than 10^(100). This is still not big enough to be secu re, but you will be able to send messages with up to 50 characters per packet. (And so that decoding doesn't get too tedious for all groups , you will be limited to a total message at most 2 packets.) " }} {PARA 0 "" 0 "" {TEXT -1 239 " For now we will pick primes bigger \+ than 10^6, and use message packets of 6 characters. This means our me ssage packets will have up to 12 digits per packet, which will be less than our modulus N, since N will be greater than 10^12. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 271 "r estart: #this will clear all old definitions.\n #It's a go od idea to restart when you begin\n #new work - of course yo u might need to \n #go back and re-enter some old commands t hat\n #you need again. (Repetition is good pedagogy.)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 385 "randomize();#this will tell the \"random\" number generator \n #where to start. the \"s eed\" it generates is based\n #on the system clock, so if yo u all hit this at\n #the same time you might get the same \" random\" numbers.\n #That would be bad. See help windows to see how to\n #make your random numbers unlike your classmat es'.\n " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+^\\*f0\"" } }}{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#\"-jJp\"f7&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "bigger:=rand(1..10^51): #much bigger\nbigger();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"T`Y'=r'pLc\"42(eOM3o()3Pl_MY#3u" } }}{PARA 0 "" 0 "" {TEXT -1 8 "For now," }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "good:=rand(1..10^7):\ngood();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"(?e7$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 213 " for i from 1 to 100 do\n x1:=good():\n if (x1>10^6 #check n umber is big enough\n and\n isprime(x1)=true) #and check if n umber is prime\n then print(x1); #if it is, let's see it\n fi; \nod: \n " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"(*)fv'" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"(T4f%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"($o ^L" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"(4MO(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"(VGL&" }}}{PARA 0 "" 0 "" {TEXT -1 259 "It's unlikely your numbers agree with mine. (Well, in truth if you all start the g enerator at the same place, you'll all get the same so-called random n umbers.) But let's all use two of mine. We are repeating the process we worked out in the tiny example.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 233 "p:=6755989; #I got these with my mouse, by \n #highlighting with left mouse,\n \+ #clicking cursor, and pasting with\n #middle mous e (at least on our system) \nq:=4590941;\nN:=p*q; #our modu lus" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"(*)fv'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"(T4f%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %\"NG\"/\\c*oM;5$" }}}{PARA 0 "" 0 "" {TEXT -1 227 "To see that a syst em of this size is not secure, try the following command. This is the command that would fail if we had chosen primes of length 200 instead of 12, and that's the reason RSA is secure when you use huge primes. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(N);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%!G6#\"(T4f%\"\"\"-F%6#\"(*)fv'F(" }}}{PARA 0 "" 0 "" {TEXT -1 28 "3) Find an encoding power e" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "N2:=(p-1)*(q-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#N2G\"/?([bL;5$" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "for i from 1 to 10 do\n x2 :=good();\n if gcd(x2,N2)=1\n then print(x2);\n fi\nod:" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"(,Lo\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"(,.w#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "e:=1683301 ;\ngcd(e,N2); #check relative prime" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"eG\"(,Lo\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{PARA 0 "" 0 "" {TEXT -1 21 "7) Get decoding power" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "isolve(e*z + y*N2 =1);\n #find decryption power " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$/%\"zG,&\"-ztALkY!\"\"*&\"/?([bL ;5$\"\"\"%$_Z1GF+F(/%\"yG,&\"&9`#F+*&\"(,Lo\"F+F,F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "d:= -466433227379 mod N2;\n #use \+ the mouse to copy and paste big numbers" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"/T8K-*\\0$" }}}{PARA 0 "" 0 "" {TEXT 264 16 "Technical P oint:" }{TEXT -1 644 " When we get to step 6, or certainly step 8 Map le will complain when we try to compute large powers of large numbers, so we have to lead it through this modular computation in smaller ste ps. The procedure below does an analgous computation to what Jim did y esterday, and what Davis also outlines, except using powers of 10 rath er than powers of 2. It's fine with me if you just use this procedure , but it's even finer if you can understand it. The encryption algori thm makes use of the digit procedure which picks off the coefficients \+ of powers of 10 in the decimal expansion of a number. So make sure to load digit before you load encrypt." }}{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$%)operator G%&arrowGF),&-%&truncG6#*&9$\"\"\")\"#59%!\"\"F3*&F5F3-F/6#*&F2F3)F5,& F3F3F6F3F7F3F7F)F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 126 "di git(123.56,-1);\ndigit(123.56,2);\ndigit(123.56,0);\n #check how dig it picks off the digits corresponding\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 "" {MPLTEXT 1 0 454 "encrypt:= proc(M1,E,N3) #message, encipher pow er,modulus\n #we assume all M1's, E's have at most 105 \+ digits\n local i,j, #indices\n L1, #list of succesive 1 0th powers of M1\n ans; #answer\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 ans:=1: \+ #initialize answer\n for j from 1 to 105 do\n ans:=ans*(L1[j]^ digit(E,j-1)) mod N3;\n od:\n\nRETURN(ans);\nend:\n \n \+ " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 14 "Let's check!!!" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "M:= 12345678910;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"MG\",5*ycM7" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "secret:=encrypt(M,e,N);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%'secretG\"/m_@3[xI" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "encrypt(secret,d,N);\n #decryption is ju st encryption 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 261 "" 0 "" {TEXT -1 26 "Part III\nAn Actual Message" }}{PARA 263 "" 0 "" {TEXT -1 0 "" }}{PARA 262 "" 0 "" {TEXT -1 0 "" }{TEXT 265 44 "We Use Davis' Table on page 9 to encrypt \" " }{TEXT -1 9 "I'm Dizzy" }{TEXT 266 27 "\". We will need two chunks" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "M1:=196749101445;\nM2:=62626163;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M1G\"-X95\\n>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M2G\")jhi i" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "C1:=encrypt(M1,e,N);\n C2:=encrypt(M2,e,N);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#C1G\"/z6a,! *oF" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#C2G\"/8&44bY*G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "encrypt(C1,d,N);\nencrypt(C2,d,N); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"-X95\\n>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\")jhii" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "47 1" 49 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }