{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 2004 - RSA" }}{PARA 257 "" 0 "" {TEXT -1 0 "" }{TEXT 258 0 "" }{TEXT 259 16 "Thursday June 17" }}{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 623 "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, students can take Math 4400 fairly early in their undergra duate careers since it does not have very many prerequisites beyond al gebra and the ability to reason mathematically. As far as ACCESS goes , we hope that you're enjoying the magic hidden in modular arithmeti c, and that you are pleasantly surprised that this \"abstract\" mathem atics 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 ty ping in Part I below, so that you can begin learning MAPLE and common \+ 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 Alice. I will follow Davis' numbering of the steps on pages 13-14. We are 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 279 "restart: #Just as every time you reopen a file you m ust \n #re-execute its commands into Maple's memory, you will\n \+ #often want to redo a process in a given file using \n #diffe rent data variables. The restart command clears \n #all of 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 713 "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). (We talked about how to find the multiplic ative inverse using the Euclidean algorithm. Luckily for us, Maple ha s a subroutine which does this step for us.) By Euler's Theorem, whic h Jim talked about yesterday (very briefly), this d will be the decodi ng power. I wouldn't be surprised if you're still amazed and confused by this fact, but like I tell my students in every class, confusion i s 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 stand s for \"integer solve\", \n #i.e. find integer solutions. Here th e unknowns \n #are z and y, since we already set e=7 \n #and N 2=880 We don't really care about the y-value, \n #we just want z. this is because when we interpret \n #e*z+y*N2=1 in N2 clock ari thmetic, 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 #using mod N2 will get d back in usual resi due range.\n #We get DAvis' solution from step 7! For \"fun\" you could\n #try getting this number 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 t o receive messages. She yells from the rooftops: My modulus is N=943 . My encryption power is e=7. If you want to send me a message use t he encrypt function:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 232 "enc rypt:=x->x^e mod N;\n #if you defined e and N above, \n #then their \+ values will be used for the encrypt function\n #this command is Maple se for encrypt(x)=x^e mod N.\n #So this is the syntax for defining \n #elementary functions." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(encrypt Gf*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 th e picture notes I made for you we use the letter E for the encrypt fun ction. " }}{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. T he 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 pu blic key: " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "C:=encrypt(M); #either of these should work\nC:=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 he r decoding power d, which she found in step 7, a while ago." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "de crypt:=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 "consults the table, sees that 35 corresponds to Y, and understands what Bob has sent. WE DID IT!" }{TEXT 278 2 " " }{TEXT 279 146 "Except with 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 project everyone will pick primes bigger th an 10^50, so that your moduli will be bigger than 10^(100). This is s till not big enough to be secure, but you will be able to send message s 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 messag e 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 cha racters. This means our message packets will have up to 12 digits per packet, which will be less than our modulus N, since N will be greate r than 10^12. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 271 "restart: #this will clear all old definitio ns.\n #It's a good idea to restart when you begin\n \+ #new work - of course you might need to \n #go back and re -enter some old commands that\n #you need again. (Repetitio n is good pedagogy.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 385 "ra ndomize();#this will tell the \"random\" number generator \n \+ #where to start. the \"seed\" it generates is based\n #on t he system clock, so if you 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 num bers unlike your classmates'.\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\"f 7&" }}}{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 (x 1>10^6 #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# \"(*)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 y ou all start the generator at the same place, you'll all get the same \+ so-called random numbers.) But let's all use two of mine. We are rep eating the process we worked out in the tiny example.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 233 "p:=675 5989; #I got these with my mouse, by \n #highlighting wit h left mouse,\n #clicking cursor, and pasting with\n \+ #middle mouse (at least on our system) \nq:=4590941;\nN:=p*q; \+ #our modulus" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"(*)f v'" }}{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 system of this size is not secure, try the following com mand. 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\n od:" }}{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 de cryption 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 "Te chnical Point:" }{TEXT -1 644 " When we get to step 6, or certainly s tep 8 Maple will complain when we try to compute large powers of large numbers, so we have to lead it through this modular computation in sm aller steps. The procedure below does an analgous computation to what \+ Jim did yesterday, and what Davis also outlines, except using powers o f 10 rather 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 encrypti on algorithm makes use of the digit procedure which picks off the coef ficients of powers of 10 in the decimal expansion of a number. So mak e 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$%)ope ratorG%&arrowGF),&-%&truncG6#*&9$\"\"\")\"#59%!\"\"F3*&F5F3-F/6#*&F2F3 )F5,&F3F3F6F3F7F3F7F)F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 126 "digit(123.56,-1);\ndigit(123.56,2);\ndigit(123.56,0);\n #check \+ how digit 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, enciphe r power,modulus\n #we assume all M1's, E's have at most 105 digits\n local i,j, #indices\n L1, #list of succes ive 10th 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*(L 1[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 just 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\")jhii" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "C1:=encrypt (M1,e,N);\nC2:=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 "19 0 0" 272 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }