Setting up RSA to encode numbers

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);

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 -> substring(convert(a+256,hex),2..3):

We are ready to start with a small message.

>	mess1 := "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)):     #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 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.

>	length(sechex1);

>	sechex2 := cat(seq("0",counter = 1..(140-length(sechex1))),sechex1);

>	secmess := [seq(substring(sechex2,10*i-9..10*i),i=1..14)];

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(convert(declist,list),bytes),name); end:

>	numtostring(newnum1);

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 numebr less than 256^t.