The RSA Public key cryptosystem

In 1978, R. Rivest, A. Shamir, and L. Adelman published the description of the
RSA public key system[RSA], which we will describe here.
As discussed in §9.3, a public key system
allows anyone to encode messages that only the intended recipient may
decode. This algorithm relies
on the fact that unless one knows some special facts about *n*, calculating
the Euler -function
(*n*) is as hard as factoring *n*, which,
for very large *n* (say, 200 digits), is very hard indeed.

Details of the RSA algorithm

To set up the system, we pick at random two large primes *p* and *q*, of about
100 digits each. We then compute the base *n* as the product of *p*
and *q*. Note that
(*n*) = (*p* - 1)(*q* - 1). We also pick some other
number *e*, called the exponent, which is relatively
prime to
(*n*). We make the numbers (*n*, *e*) public-- these form
the key needed for encoding. We also use the Euclidean algorithm to compute *x*
which satisfies
*ex* - *y*(*n*) = 1; that is, so that
*ex*(*n*) = 1. The number *x* is the part of the key we keep
private; our decrypting key is the pair (*n*, *x*).

This relies on Euler's theorem (Thm. 10.11), so that
*n* = 1.
Euler's theorem only guarantees that this will work for
gcd(, *n*) = 1.
However, we can easily see that decryption works for all < *n*,
whether or not it is relatively prime to *n*.

If
gcd(, *n*) = 1, the result follows from Euler's theorem.

Otherwise, since

**Remarks.**

- The symmetry between
*e*and*x*means that we can encrypt with either the public or the private key, using the other for decryption. To use RSA works for authentication, the private key (*n*,*x*) is used encrypt a message which can be decrypted with the public key (*n*,*e*). Only one who possesses the private key could have encrypted such a message, which serves as a proof of identity. - If
*e*is small, there is a possibility of having some message elements for which <*n*; for such a , decrypting without knowledge of (*n*) is easy: just compute the*e*-th root of , since*n*is not a consideration. With care, one can either ensure that such do not occur, or one can encrypt such messages in a slightly different manner. - For efficiency reasons, many implementations always use 3 for
the encoding exponent
*e*. In general, computing*n*when*e*is of the form 2^{k}+ 1 is quite efficient. Other common choices for*e*are 17 and 65537 (2^{16}+ 1), which are only slightly less efficient than 3. - Instead of using the Euler -function, one can use
Carmichael's -function, which is the largest order
of any element of . In the case where
*n*is a product of two primes*p*and*q*, we have (*n*) =*lcm*(*p*- 1,*q*- 1). Since*p*- 1 and*q*- 1 are always even, the resulting private exponent*x*will be smaller. - There are a number of considerations in the choice of primes
*p*and*q*that we will mostly ignore. For example,*p*and*q*should not be too close together, and both*p*- 1 and*q*- 1 should both have at least one large prime factor.

Implementing RSA in Maple

Now that we have covered how the RSA system works in theory, it is fairly straightforward to implement it.

Implementing the basics of RSA

First, we write a Maple procedure which, given a size for *n* (our
public base), will choose *n* as the product of two large primes *p*
and *q*, as well as an exponent *e* which is relatively prime to
(*n*), and compute the decrypting exponent *x*.

For real security, *n* should be at least 200 decimal digits, meaning
that the primes *p* and *q* will be about 100 digits each. Such large
numbers are not easily factored (which is how we get our security), so
how do we expect to be able to find 100-digit prime numbers? It turns
out that there are a number of very efficient ways to test whether a
number is prime without actually factoring it. Maple's
isprime function uses such methods. So all we really
need to do is generate a random number of around 100 digits, then use
nextprime to get the next prime bigger than that number. We
should use randomize() to ensure that we get different numbers
each time (See the discussion of pseudo-random numbers in
§5.2, page ).

In RSAsetup below, the approximate number of digits for *n* is
given, and *p* is chosen as a prime with one less than half that many
digits, while *q* has one more than half the number of digits of *n*.
This means *n* must have at least 5 digits (or else *p* would have to be 2,
3, 5 or 7). After calculating *n* and
(*n*), a random number
is chosen for the public exponent *e*. If this number is not
relatively prime to
(*n*), another random choice is taken until
such a number is found. Finally, *x* is computed as the inverse of
*e* modulo
(*n*). The result of the function is the public key
(*n*, *e*) and the private key (*n*, *x*).

> randomize():RSAsetup:=proc(numdigits::posint) local p,q,phi,e,n, x, pm, qm;

if (numdigits <= 4) then error("Too few digits for this to work"); fi;

pm:=floor((numdigits-1)/2); qm:=numdigits-pm; p:=nextprime(rand(10^(pm-1)..10^(pm))()); q:=nextprime(rand(10^(qm-1)..10^(qm))());

n:=p*q; phi:=(p-1)*(q-1);

e:=rand(3..phi/2)(); while(gcd(e,phi) <> 1) do e:=rand(3..phi/2)(); od; x := modp(1/e, phi); return([[n,e],[n,x]]); end:

We should remark that in certain cases, both *p* and *q* might be
chosen at the extreme ends of their ranges, giving *n* with one fewer
or one more digit than requested. If this were important, it could be
repaired with a slightly more complicated program.

Once the keys are chosen, writing the heart of the RSA encoding is
quite easy. We just need a function that eats a number and a
key (*n*, *e*), and computes
*n*.

> RSAEncodeNum := proc(num::nonnegint, key::list(posint)) return( modp( num &^ key[2], key[1] )); end:

As a brief example, we'll generate a random pair of keys with a 5-digit modulus, and then encrypt and decrypt the number 47.

> keys:=RSAsetup(5): public := keys[1]; private:= keys[2];

> RSAEncodeNum(47,public); RSAEncodeNum(

Of course, we want to encrypt more than a single number, but this is the heart of the whole thing.

In order to encrypt a string of text, we have to convert our text to
a list of numbers. It is probably best to use *k*-graphs to represent
our text, as in §5.3, where *k* is the largest
integer power of the size of our alphabet that is smaller than
*n*. While it will work to use a single character alphabet, this can
compromise security significantly-- see the remarks at the end of
§11.1.

We can use StringToKgraph and KgraphToString from
§5.3 to represent our strings as *k*-graphs. In
order to determine the appropriate choice of *k*, we find the largest
integer *k* so that

Once we have our plaintext represented as a list of integers, we merely map the function RSAEncodeNum onto that list.

> Alphabet := cat("",Select(IsPrintable,convert([seq(i,i=1..255)],bytes))): Alen := length(Alphabet); k:=floor(log[Alen](public[1]));

> text := "Once upon a midnight dreary, while I pondered, weak and weary":

> StringToKgraph(text,k);

> crypt:=map(RSAEncodeNum,

We can reverse the process, using the private key, to decrypt.

> KgraphToString( map(RSAEncodeNum,crypt,private), k);

It is important to note that if we want to represent the result of the
encryption as a string instead of a list of numbers, we must use
(*k* + 1)-graphs rather than *k*-graphs. This is because
*Alen*^{k} < *n*, so there will often be so that
*n* > *Alen*^{k}. In the example above, note that
97^{2} = 9409, and there are several elements of the list
crypt larger than 9409.

We can put it all together in two simple procedures.

> RSAEncodeString := proc(text::string, key::list(posint)) local Alen, k; global Alphabet;Alen := length(Alphabet); k:=floor(log[Alen](key[1])); KgraphToString( map(RSAEncodeNum, StringToKgraph(text, k), key), k+1); end:

RSADecodeString := proc(text::string, key::list(posint)) local Alen, k; global Alphabet;

Alen := length(Alphabet); k:=floor(log[Alen](key[1])); KgraphToString( map(RSAEncodeNum, StringToKgraph(text, k+1), key), k); end:

Now we try it out, with a 150-digit choice of *n*. Note that this means
we'll be using 75-graphs, since
97^{75} < 10^{150} < 97^{76}.

> keys:=RSAsetup(150): public:=keys[1]; private:=keys[2];

> crypt:=RSAEncodeString(text,public);

> RSADecodeString(crypt,private);

2002-08-29