Using RSA
Mike May, S. J., 1998
Setting up the algorith and choosing big primes.
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 bacause 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. (To convert to Maple input I had to copy the output to a simpletext document than copy fromthere back into Maple.)
>
M1 := 19669081321110693270343633073697474256143563558458718976746753\
830538032062222085;
M2 := 74121768604305613921745580037409259811952655310075487163797179\
490457039169594160;
P1 := 19669081321110693270343633073697474256143563558458718976746753\
830538032062222257;
P2 := 74121768604305613921745580037409259811952655310075487163797179\
490457039169594213;
I need to compute the product of the two primes and 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. It seems that the best criterion for mathematical ease is that e represented base 2 should be almost all zeroes.
>
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 proceedures.
>
encoder := (a,e,n) -> Power(a,e) mod n:
decoder := (a,d,n) -> Power(a,d) mod n:
We obviously want to check that the procedures reverse each other, at least for a small sample of messages.
>
m1 := encoder(5,e,n);p1 :=decoder(m1,d,n);
Exercises:
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.)
>
Encoding messages rather than numbers
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 charachter 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 -> if a < 16 then cat(`0`,convert(a,hex))
else convert(a,hex) fi:
We are ready to start with a small message.
>
### WARNING: incomplete quoted name; use ` to end the name
mess1 := `Good morning Mr. Phelps,
### WARNING: incomplete quoted name; use ` to end the name
This morning we look at RSA.
3rd line`;
Error, reserved word `to` unexpected
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)):
lengthofmess := nops(stringofhex):
#Now we concatenate the hex numbers
hexstring := cat(seq(stringofhex[i],i=1..lengthofmess)):
#Finally we convert the big number back to decimal
convert(hexstring,decimal,hex):
end:
>
messnum1 := shortconverter(mess1);
Next we want to encode our number and convert it to hex for easy handling.
>
sechex1 := convert(encoder(messnum1,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 ant 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.
>
length(sechex1);
>
sechex2 := cat(seq(`0`,counter = 1..(140-length(sechex1))),sechex1);
>
secmess := linalg[vector](14, i-> substring(sechex2,10*i-9..10*i));
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 messnum1 above.
>
newnum1 := decoder(hexvectodec(secmess,14),d,n);
>
convert(newnum1,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(declist,list),bytes);
end:
>
numtostring(newnum1);
Exercises
5) For the procedures above to work, we have to restrict ourselves to messages that encode as numbers less than n. What is the maximum length of a message that we can encode?
>
6) Enter a message of about 50 characters and encode it Using the nande 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\
752298049755073623061549604680218687683561183675344052519958\
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 othe 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.
>
