Using RSA \302\2512007 by Mike May, S.J., Saint Louis University - maymk@slu.edu An introduction to the RSA cryptographic system restart:

The first thing to do to use RSA is to find two large primes. For this worksheet we will be looking for primes that are about 80 digits long. (I chose 80 digits because that is what easily fits on one line.) We do this with the rand and nextprime functions in Maple. M1 := rand(10^80)(); M2 := rand(10^80)(); P1 := nextprime(M1); P2 := nextprime(M2); The use of a random number function in the selection of the primes is intended to make them hard to guess. The output has been converted to Maple input so that we can work with repeatable computations. M1 := 99596883909465520335617712166467577059926068276305009675299763431340064249105338; M2 := 34633129088861013688643347733731974176548310874222673528866121995231476726634212; P1 := 99596883909465520335617712166467577059926068276305009675299763431340064249105379; P2 := 34633129088861013688643347733731974176548310874222673528866121995231476726634233; I need to compute n, the product of the two primes, and the number of elements of Z_n relatively prime to n, or the product of one less than each of the primes. n := P1*P2; n2 := (P1-1)*(P2-1); I now need to decide on a value for e, the encrypting number. Since e will be public, I don't need to worry about random generation. I can consider numbers that will be easy to work with mathematically. Since I will want e to be relatively prime to n2, it is best if I choose e to be prime. For computational reasons it is nicer if e represented base 2 should be almost all zeroes. Thus we choose a Fermat prime, that is a number of the form 2^k+1, where k is a power of 2. Following a number of sources we use 2^16+1. e:= 2^16+1; isprime(e); gcd(e,n2); Recall that we had to make sure that e is relatively prime to n2. That is easier because we have chosen e to be prime. Now we need to compute d, the multiplicative inverse of e mod n2. We could do that directly with the extended Euclidean algorithm, but we will just use the modular arithmetic of Maple. d := eval(1/e mod n2); We are ready to define encoding and decoding procedures. encoder := (a,e,n) -> Power(a,e) mod n: decoder := (a,d,n) -> Power(a,d) mod n: A quick note on programming is in order here. The use of the Power (a, d) mod n construction here than a^d mod n is important. The second construction would try to compute a^d as an intermediate step and if a=2, then a^d has more digits than there are atoms in the universe. We obviously want to check that the procedures reverse each other, at least for a small sample of messages. LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYxLUkjbWlHRiQ2KFEjbTFGJy8lJ2ZhbWlseUdRK01vbm9zcGFjZWRGJy8lJ2l0YWxpY0dRJmZhbHNlRicvJStmb3JlZ3JvdW5kR1EqWzI1NSwwLDBdRicvJTBmb250X3N0eWxlX25hbWVHUSxNYXBsZX5JbnB1dEYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy1JI21vR0YkNjBRIn5GJ0YvRjVGOEY7LyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGUi1GPzYwUSomY29sb25lcTtGJ0YvRjVGOEY7RkJGREZGRkhGSkZMRk4vRlFRLDAuMjc3Nzc3OGVtRicvRlRGWUY+LUYsNihRKGVuY29kZXJGJ0YvRjJGNUY4RjstSShtZmVuY2VkR0YkNiktRiM2KS1JI21uR0YkNidRIjVGJ0YvRjVGOEY7LUY/NjBRIixGJ0YvRjVGOEY7RkIvRkVRJXRydWVGJ0ZGRkhGSkZMRk5GUC9GVFEsMC4zMzMzMzMzZW1GJy1GLDYoUSJlRidGL0YyRjVGOEY7RmFvLUYsNihRIm5GJ0YvRjJGNUY4RjsvJStleGVjdXRhYmxlR0Y0RjtGLy8lJWJvbGRHRmVvRjVGOC9GPFElYm9sZEYnLyUrZm9udHdlaWdodEdGY3AtRj82MFEiO0YnRi9GNUY4RjtGQkZkb0ZGRkhGSkZMRk5GUEZaLUYsNihRI3AxRidGL0YyRjVGOEY7Rj5GVS1GLDYoUShkZWNvZGVyRidGL0YyRjVGOEY7LUZpbjYpLUYjNilGK0Zhby1GLDYoUSJkRidGL0YyRjVGOEY7RmFvRltwRl5wRjtGL0ZgcEY1RjhGYnBGZHBGZnBGXnBGOw==

1) The chosen primes let us encode and decode messages that are numbers approximately in the range of 0 to 10^159. Randomly pick 5 numbers in that range and verify that encoding and decoding act as inverse operations on these numbers. 2) Of the numbers found so far, explain which numbers I want to publish, which ones I want to save but keep secret, and which ones I want to destroy and forget if I am using RSA as a public key system. 3) Randomly pick two primes of your own in the 1-10^80 range and prepare your own keys. Test that your keys encrypt and decrypt on two numbers of your choice. (You probably don't want to reuse the names n, e, or d, since we will continue to use these numbers in later exercises. 4) Post your public key and modulus to the bulletin board so that others in the class can send you messages. (Do not post your secret key.)

Now we want to turn our attention to encoding messages. Following the pattern from earlier work, if we want to turn our message into into a single number, the trick is to use convert to change a message from ASCII to a string of decimal equivalents, then convert each of the decimal numbers into a two digit hex number, concatenate (string together) the hex numbers into one big number, then convert it back to a decimal number. We can then encode our message number, convert it to a hex number and store it in some reasonable form. Recall that we had a problem with hex conversion before. If the decimal equivalent of the ASCII character is less than 16, the hex number is only one digit long, and we want to assume characters contribute 2 hex digits to keep placement straight. (In particular the "return" character is equivalent to 13.) The procedure twodigithex converts with a two digit output. twodigithex := a -> substring(convert(a+256,hex),2..3): We are ready to start with a small message. Message1 := "Good morning Mr. Phelps, This morning we look at RSA. 3rd line"; We want a procedure to convert this to a number. shortconverter := proc(messagestring) local stringofhex, lengthofmess, hexstring, i: #First we convert the ASCII string to a list of decimal equivalents #Then we convert thedecimal numbers to hex equivalents stringofhex := map(twodigithex, convert(messagestring,bytes)): print(stringofhex); lengthofmess := nops(stringofhex): print(lengthofmess); #Now we concatenate the hex numbers hexstring := cat(seq(stringofhex[i],i=1..lengthofmess)): print(hexstring); #Finally we convert the big number back to decimal convert(hexstring,decimal,hex): end: MessageAsNumber1 := shortconverter(Message1); Next we want to encode our number and convert it to hex for easy handling. SecretHex1 := convert(encoder(MessageAsNumber1,e,n),hex); This does not look very easy to copy back and forth. (I am sure I would make a mistake if I tried to type a copy of a string that long.) To give a nice form to the output, I want to pad the message out with leading zeroes, then break it into blocks of a nice size. For today, I think 10 characters forms a nice block size. MessageLength := length(SecretHex1);SecretHex2 := cat(seq("0",counter = 1..(MessageLength-(floor(MessageLength/10)*10))),SecretHex1);SecretMessage := [seq(substring(SecretHex2,10*i-9..10*i),i=1..ceil(MessageLength/10))]; Now we want to verify that we can put the message back together and decode it. We define a procedure for converting the vector of hexblock into a single number. hexvectodec := (hexvec,size) -> convert(cat(seq(hexvec[i],i=1..size)),decimal,hex): Now we can convert our message back to a decoded number. We should get an answer equal to MessageNumber1 above. NewNumber1 := decoder(hexvectodec(SecretMessage,14),d,n);convert(NewNumber1,hex); We also want a procedure for turning the decoded number back into a message. numtostring := proc(bignum) local hexstr1, listlength, declist, i: #convert to a hex string hexstr1 := convert(bignum,hex): #make sure the hex string has even length if (length(hexstr1) mod 2) = 1 then hexstr1 := cat(`0`,hexstr1) fi; #compute the number of characters listlength := length(hexstr1)/2: #convert to a vector of decimal numbers declist := linalg[vector](listlength); for i from 1 to listlength do declist[i] := convert(substring(hexstr1,2*i-1..2*i),decimal,hex); od; #convert the vector to a list, then to an ASCII string convert(convert(convert(declist,list),bytes),name); end: numtostring(NewNumber1); There is one more issue to deal with. For the procedures above to work, we have to restrict ourselves to messages that encode as numbers less than n. A message of length t encodes as a number less than 256^t.

5) What is the maximum length of a message that we can encode with n chosen as above? 6) Enter a message of about 50 characters and encode it Using the n and e defined above. 7) Verify that you can decrypt the message with the secret key. 8) For the rest of this worksheet, Fr. May's modulus is 145790709434263657193410815968586298032651591491182486164339\134 752298049755073623061549604680218687683561183675344052519958\134 7698019954839165932427842278373706998741 and his encrypting key is 65537. Encrypt your short message and send it to him through the bulletin board. 9) Obtain the public keys of two other people in the class and send them a short encrypted message via the bulletin board. 10) Respond to the messages you get with encrypted messages. 11) Make a shorter RSA worksheet that you can use as an application for encrypting and decrypting.

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities. LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=