{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 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 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 }{PSTYLE "" 0 264 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 265 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 266 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 {PARA 256 "" 0 "" {TEXT -1 0 "" }{TEXT 256 0 "" }{TEXT 257 17 "ACCESS 2009 - RSA" }}{PARA 257 "" 0 "" {TEXT -1 0 "" }{TEXT 258 0 "" }{TEXT 259 14 "Friday June 19" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 260 15 "Our Plan Today:" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 675 "We'll finish yesterday's number theory notes, which explain how t o find decryption powers from encryption powers, in modular arithmetic . Then to help explain the RSA public-key encryption method we will do the example worked out in the Tom Davis \"Cryptography\" notes, page \+ 13-14, also using the hand-drawn Alice and Bob diagram. Davis' exampl e uses small numbers and a one-letter message, and Maple will do all o f our computations. I believe this will make the algorithm more clear to you. The explanation of the Algorithm on page 6-7 of the Rivest-S hamir-Adleman paper is also a very concise outline, as is appendix J o f \"The Code Book.\" You could also consult Wikipedia." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 458 "After we digest Dav is' example we will try somewhat larger prime numbers, to help prepar e you for the part of your group project in which you send yourselves \+ (and me) encoded messages . In your actual project you will implemen t a medium-sized version of an RSA cipher system (big enough to send s hort messages, but not really big enough to be secure). You will also incorporate the \"secure signature\" feature, which we will discuss u sing Alice and Bob. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 745 "The number theory we've talked about, and the relatio n to RSA cryptography, is usually taught in our number theory course, Math 4400. This is a senior level course, so I would expect that som e of what we've talked about has been challenging. Still, some studen ts take Math 4400 fairly early in their undergraduate careers since it does not have very many prerequisites beyond algebra and the ability \+ to reason mathematically. As far as ACCESS goes, we hope that you're enjoying the magic hidden in modular arithmetic, that you are pleasa ntly surprised that this \"abstract\" mathematics turns out to be so p ractical, and that you are appreciating that discovery, experiment and deduction have roles in mathematics just as they do in science." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 253 "I will m ake you do a lot of your own typing in Part I below, so that you can b egin learning MAPLE and how to fix the common errors which users make. Therefore, in the file you download, many of the Maple commands whic h you see in the hardcopy are gone." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 588 "We will use Maple 8, and I recommend yo u avoid Maple 10 or higher in this project. In Maple 8, once commands from one Maple worksheet are entered into memory they are known in al l the other Maple worksheets you open in your Maple desktop. This let s you organize different pieces of your computation in different windo ws. Maple 10 keeps different memory for each opened worksheet so you \+ must put everything into a single worksheet. Also, if you're working on Maple 10 and plan to return to Maple 8 you must save your file spe cially in \"classic\" mode, so that Maple 8 can recognize it." }} {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." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{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 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{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 i s related to Euler's theorem, with which Alice will pick her encoding \+ and decoding powers. No one else will ever see or use this number. F irst 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 goo d e must be relatively prime to (p-1)*(q-1), so that Alice will be abl e to find a decoding power d. So we check the gcd: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 5 "7 ) " }{TEXT 270 5 "Al ice" }{TEXT -1 1 " " }{TEXT 280 10 "privately " }{TEXT -1 766 "finds h er \"secret\" decoding power. Since she does this step sooner than Da vis says, we will too. Since e is relatively prime to N2=(p-1)*(q-1) \+ it has a multiplicative inverse d, mod (p-1)*(q-1). (We talked about \+ how to find the multiplicative inverse using the Euclidean algorithm. \+ Luckily for us, Maple has a subroutine which does this step for us.) \+ By the Euler-FermatTheorem, which was the page of our notes we didn't quite get to go through carefully yesterday, :(, this d will be the d ecoding power. I wouldn't be surprised if you're still amazed and con fused by this fact, but like I tell my students in every class, confus ion is the first step to understanding. I'll be happy to talk with an yone who wants to understand this part of the math better...." }} {PARA 0 "" 0 "" {TEXT -1 148 " The first command is having Maple do the Euclidean algorithm method of finding multiplicative inverses, so you won't have to do this by hand!!!!" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 9 "3b) Now " }{TEXT 272 5 "Alice" } {TEXT -1 171 " is ready to receive messages. She yells from the rooft ops: My modulus is N=943. My encryption power is e=7. If you want t o send me a message use the encrypt function:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "encrypt:=x->x^e mod N;\n " }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{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 m essage 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 tha t corresponds to Y is 35. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "5) " }{TEXT 274 3 "Bob" }{TEXT -1 48 " encrypts the message using Alice's public key: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{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 she found in ste p 7, a while ago." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 263 6 "Alice " }{TEXT 277 97 "co nsults the table, sees that 35 corresponds to Y, and understands what \+ Bob has sent. WE DID IT!" }{TEXT 278 2 " " }{TEXT 279 146 "Except wi th 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 p roject everyone will pick primes bigger than 10^50, so that your modul i will be bigger than 10^(100). This is still not big enough to be se cure, but you will be able to send messages with up to 50 characters p er packet. (And so that decoding doesn't get too tedious for all grou ps, 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 395 "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 enter this command at\n #the same time you might get t he same \"random\" numbers.\n #That would be bad. See help \+ windows to see how to\n #make your random numbers unlike you r classmates'.\n " }{TEXT -1 0 "" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "rand(); \+ #random number generator,\n #default range is between 0 and \+ 12 digits " }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "bigger:=rand(10^50..10^51): #much bigger\nbigger( );" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 24 "F or now, (but not later)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "g ood:=rand(10^6..10^7):\ngood();" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 154 "for i from 1 to 100 do\n x 1:=good():\n if isprime(x1)=true) #check if number is prime\n th en print(x1); #if it is, let's see it\n end if;\nod: \n " }}} {PARA 0 "" 0 "" {TEXT -1 272 "It's unlikely your numbers agree with mi ne. (Well, in truth if you all start the generator at the same place, you'll all get the same so-called random numbers.) You may chose you r p and q using your list! We are repeating the process we worked out in the tiny example.)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 225 "p := ; #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:= ;\nN:= p*q ; \+ #our modulus" }}}{PARA 0 "" 0 "" {TEXT -1 227 "To see that a sy stem of this size is not secure, try the following command. This is t he command that would fail if we had chosen primes of length 200 inste ad 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 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 28 "3) Find an e ncoding power e" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "N2:=(p-1) *(q-1);" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 153 "#find encryption pow er which has a multiplicative inverse\n#mod N2:\nfor i from 1 to 10 do \n x2:=good();\n if gcd(x2,N2)=1\n then print(x2);\n fi\nod: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "e:=;\ngcd(e,N2); #che ck relative prime\n" }}}{PARA 0 "" 0 "" {TEXT -1 21 "7) Get decoding p ower" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "isolve(e*z + y*N2 =1 );\n #find decryption power, which is \"z\" above" }}{PARA 11 "" 1 " " {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 133 "d:= mod N2; #need a positive power-\n #this will put it into the N2 residu e range\n #use the mouse to copy and paste big numbers" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "d:= e^(-1) mod N2; #I only recent discovered this shortcut!" }}}{PARA 0 " " 0 "" {TEXT 264 16 "Technical Point:" }{TEXT -1 422 " When we get to step 6, or certainly step 8 Maple will complain when we try to comput e large powers of large numbers, so we have to lead it through this mo dular computation in smaller steps. The procedure below does the trick . It's analagous to method Davis outlines in his notes, except using p owers of 10 rather than powers of 2. We've been using similar tricker y in class. Here's the idea: Suppose we want to compute" }}{PARA 264 "" 0 "" {XPPEDIT 18 0 "[783]^565;" "6#*$7#\"$$y\"$l&" }{TEXT -1 7 " m od N" }}{PARA 0 "" 0 "" {TEXT -1 25 "in small steps. We write" }} {PARA 265 "" 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 266 "" 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,&F3F3F6F3F7F3F7F)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 "" {MPLTEXT 1 0 611 "en crypt:= proc(M1,E,N3) #message, encipher power,modulus\n \+ #we assume all M1's, E's have at most 105 digits\n local i,j, # indices\n L1, #list of succesive 10th powers of M1\n \+ ans; #answer\n #this do loop makes the list of powers of M1 descr ibed 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 table entries to get th e residue value of the\n #encryption power function:\n ans:=1: #i nitialize 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 "" {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 "se cret:=encrypt(M,e,N);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'secretG\"/ 5t#pXC4\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 107 "encrypt(secre t,d,N);\n #decryption is just \n #encryption in modular arithmetic, \+ with a different power.\n " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\",5*yc M7" }}}{PARA 0 "" 0 "" {TEXT -1 6 "YES!!!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 111 "What would happen above if you st arted with an M which was larger than your modulus N? (It would not b e good.)" }}{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 o n 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 "M 1:=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:=en crypt(M2,e,N);" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 86 "encrypt(C1,d,N); #decryption is encryption wi th\nencrypt(C2,d,N); #a different power!" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}}{MARK "67 0 0" 1 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }