{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 "" -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 Outpu t" 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 2005 - RSA" }}{PARA 257 "" 0 "" {TEXT -1 0 "" }{TEXT 258 0 "" }{TEXT 259 16 "Thursday June 16" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 260 15 "Our Plan Today:" }{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 Dav is \"Cryptography\" notes, page 13-14. These are great notes - you ca n think of them as the Cliff Notes for \"The Code Book.\" Davis' examp le uses small numbers and a one-letter message, and Maple will do all \+ of our computations. I believe this will make the algorithm more clea r to you. The explanation of the Algorithm on page 6-7 of the Rivest- Shamir-Adleman paper is also a very concise outline which will make mo re and more sense as you play with examples." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 589 "After we digest Davis' example we will try somewhat larger prime numbers, to help prepare you for t he part of your group project in which you send yourselves (and me) en coded messages . In your actual project, which will be posted later \+ today, you will impliment a medium-sized version of an RSA cipher syst em (big enough to send short messages, but not really big enough to be secure). You will also incorporate the \"secure signature\" feature, which we will discuss today. You can read about this in section 8.2 \+ of Davis' notes, or in section IV of the Rivest-Shamir-Adleman paper. \+ " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 349 "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 of tomorrow morning at 9:10 (after your session with the Women's Resource Center) 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 numb er theory we've talked about, and the relation to RSA cryptography, i s usually taught in our number theory course, Math 4400. This is a se nior level course, so I would expect that some of what we've talked ab out has been challenging. Still, students can take Math 4400 fairly e arly in their undergraduate careers since it does not have very many p rerequisites beyond algebra and the ability to reason mathematically. \+ As far as ACCESS goes, we hope that you're enjoying the magic hidde n in modular arithmetic, and that you are pleasantly surprised that th is \"abstract\" mathematics turns out to be so practical." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 238 "I will make you d o a lot of your own typing in Part I below, so that you can begin lear ning MAPLE and common errors which users make. Therefore, in the file you download, many of the Maple commands which you see in the hardcop y 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 pag es 13-14. We are also going to use his table on page 9 to convert let ters 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 whe n he encripts his message to her. So she picks two prime numbers, see page 13: (p=23 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 5 "3a) " }{TEXT 269 5 "Al ice" }{TEXT -1 1 " " }{TEXT 271 9 "privately" }{TEXT -1 459 " computes the auxillary modulus N2:=(p-1)*(q-1), which is related to Euler's th eorem, with which Alice will pick her encoding and decoding powers. N o one else will ever see or use this number. First 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 (p-1)*(q-1), so that Alice will be able to find a decoding po wer d. So we check the gcd: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 5 "7 ) " }{TEXT 270 5 "Alice" }{TEXT -1 1 " \+ " }{TEXT 280 10 "privately " }{TEXT -1 702 "finds her \"secret\" decod ing power. Since she does this step sooner than Davis says, we will t oo. Since e is relatively prime to (p-1)*(q-1) it has a multiplicativ e inverse d, mod (p-1)*(q-1). (We talked about how to find the multip licative inverse using the Euclidean algorithm. Luckily for us, Maple has a subroutine which does this step for us.) By Euler's Theorem, w hich Jim mentioned but didn't prove, this d will be the decoding 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 is the fi rst step to understanding. I'll be happy to talk with anyone who want s to understand this part of the math better...." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "3b) Now " }{TEXT 272 5 "A lice" }{TEXT -1 171 " is ready to receive messages. She yells from th e rooftops: My modulus is N=943. My encryption power is e=7. If you want to send me a message use the encrypt function:" }}{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 f or 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' tab le on page 9. The number that corresponds to Y is 35. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "5) " }{TEXT 274 3 "Bo b" }{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 263 6 "Alice " }{TEXT 277 97 "consults the table, sees that 35 c orresponds to Y, and understands what Bob has sent. WE DID IT!" } {TEXT 278 2 " " }{TEXT 279 146 "Except with Alice's puny primes our m essage 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 than 10^50, so that your moduli will be bigger than 10^ (100). This is still not big enough to be secure, but you will be abl e 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 messag e packets of 6 characters. This means our message packets will have u p to 12 digits per packet, which will be less than our modulus N, sinc e N will be greater than 10^12. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 271 "restart: #this will clear all old definitions.\n #It's a good idea to restart when yo u begin\n #new work - of course you might need to \n \+ #go back and re-enter some old commands that\n #you need \+ again. (Repetition is good pedagogy.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 395 "randomize();#this will tell the \"random\" number ge nerator \n #where to start. the \"seed\" it generates is bas ed\n #on the system clock, so if you all enter this command \+ at\n #the same time you might get the same \"random\" number s.\n #That would be bad. See help windows to see how to\n \+ #make your random numbers unlike your classmates'.\n \+ " }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "ran d(); #random number generator,\n #default range is betwee n 0 and 12 digits " }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "bigger:=rand(1..10^51): #much bigger\nbi gger();" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{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 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 213 "for i from 1 to 100 do\n x1:=good():\n i f (x1>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 0 "" 0 "" {TEXT -1 272 "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.) You may chose your 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 223 "p:= ; #I got these with my mouse, by \n #highlighting with left mouse,\n \+ #clicking cursor, and pasting with\n #middle mouse (at least on our system) \nq:= ;\nN:= ; #our modulus" }}} {PARA 0 "" 0 "" {TEXT -1 227 "To see that a system of this size is not secure, try the following command. This is the command that would fa il 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 "" {TEXT -1 0 "" }}}{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 "" {TEXT -1 0 "" }}}{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:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "e:=1683301;\ngcd(e,N2); #check re lative prime" }}}{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 "" {TEXT -1 0 "" }}}{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 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT 264 16 "Technical Point:" }{TEXT -1 644 " When we get to step 6, or certainly step 8 Maple will complain when we try to compute large powers of large numbers, so we have to lead i t through this modular computation in smaller steps. The procedure bel ow does an analgous computation to what Jim did yesterday, and what Da vis also outlines, except using powers of 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 encryption algorithm makes use of the \+ digit procedure which picks off the coefficients of powers of 10 in th e decimal expansion of a number. So make sure to load digit before yo u load encrypt." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "digit:=(x ,n)->trunc(x/10^n)-10*trunc(x/10^(n+1));" }}}{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 powe rs of 10" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 454 "encrypt:= proc (M1,E,N3) #message, encipher power,modulus\n #we assum e 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; #an swer\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\nRETU RN(ans);\nend:\n \n " }}}{PARA 0 "" 0 "" {TEXT -1 14 "Let's check!!!" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "M:=123456 78910;" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "secret:=encrypt(M,e,N);" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "encrypt(secret,d,N); \n #decryption is just encryption with a different power" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{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;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "C1:=encrypt(M1,e,N);\nC2:=encrypt(M2,e,N) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "encrypt(C1,d,N);\nencr ypt(C2,d,N);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "50 0" 272 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }