Supplementary material for the
lecture of Wednesday, July 14

How to make RSA data using Maple

The following routine has Maple compute primes P and Q, and a pair of encryption/decryption exponents e and d, given an integer n. P and Q will be n decimal digits long. 

RSA:=proc(n)
local P,Q,frog,T,R,S,toad,zebra;
P:=3;Q:=5;
while(type(2*n-length(P*Q),positive) and P<>Q) do
frog:=rand(10^(n-1)..10^n-1);
P:=nextprime(frog());
Q:=nextprime(frog())
od;
T:=(P-1)*(Q-1);
toad:=rand(10^iquo(2*n,4)..10^(3*iquo(2*n,4)));
R:=T;
while(igcd(T,R)>1) do
R:=toad();
zebra:=msolve(R*S=1,T)
od;assign(zebra);
RETURN(P,Q,P*Q,R,S);
end;
You can copy this and try it yourself. Here is one use of this routine: 
>RSA(15);
  481321110693277, 397474256143567, 191312750439005747675813699059,
        305613921751630036805, 163151755562420097036265148189
The first two numbers are fifteen decimal digit primes, and the third number is the product of the primes. The last two numbers are the encryption and decryption exponents. Alice in this case would publish the encryption exponent, 305613921751630036805, and also the product (which I called N in class), 191312750439005747675813699059.

There's one more computational wrinkle. How "hard" (in turns of time or number of operations) is exponentiation? Direct computation takes a long time. For example, the command
2^1234567 mod 10000000000000000039;
on my PC took over one and a half seconds. The numbers actually used in "real" RSA are much bigger. There is a shortcut, though, which I will explain in class (or see section 5.7 in the notes, beginning on p. 24). Maple uses this shortcut if you write exponentiation slightly differently. The command
2&^7654321 mod 10000000000000000039;
which also exponentiates took less than one-hundredth of a second to compute! The ampersand (&) before the caret (^) uses the faster exponentiation method.

How long does this program take? Please note that Maple generally doesn't run fast, and this code is not optimized. Here is how long RSA(n) for various n's on my desktop PC:

# of decimal
places (n)		Time in
seconds
10.01
20.02
50.059
100.066
1508.48

So even for a terrible implementation on a not-so-fast computer, creating two 100-decimal digit primes, etc., takes less than a second.

Maintained by greenfie@math.rutgers.edu and last modified 7/13/2004.