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 $\varphi$-function $\varphi$(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 $\varphi$(n) = (p - 1)(q - 1). We also pick some other number e, called the exponent, which is relatively prime to $\varphi$(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$\varphi$(n) = 1; that is, so that $\modn$ex$\varphi$(n) = 1. The number x is the part of the key we keep private; our decrypting key is the pair (n, x).

To encode a message: The sender divides his message up into blocks of length k, and to each block assigns an integer $\beta$ (for example, by treating the characters of the message as a k-graph, as in §5.3, with 0$\le$$\beta$ < n. For each block of plaintext, the sender transmits $\modn$$\beta^{e}_{}$n = $\mu$.

To decode the message: For each unit $\mu$ of the crypttext received, the recipient computes $\modn$$\mu^{x}_{}$n, which is the integer representing of a k-graph of the original plaintext message. We can see that this is so, because

$$\modn$$$$\mu^{x}_{}$$n = $$\modn$$$$\beta^{ex}_{}$$n = $$\modn$$$$\beta^{1+\varphi(n)y}_{}$$n = $$\modn$$$$\beta$$n$$\modn$$$$\beta^{y\varphi(n)}_{}$$n = $$\modn$$$$\beta$$n$$\left(\vphantom{ \modn{ \beta^{\varphi(n)}}{n} }\right.$$$$\modn$$$$\beta^{\varphi(n)}_{}$$n$$\left.\vphantom{ \modn{ \beta^{\varphi(n)}}{n} }\right)^{y}_{}$$ = $$\modn$$$$\beta$$n ^. 1^y = $$\beta$$.

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

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

Otherwise, since p and q are prime, we have $\beta$ a multiple of either p or q, but not both (since $\beta$ < pq by assumption). Suppose $\beta$ $\equiv$ 0 (mod p), and so

$$\modn$$$$\beta^{1+y\varphi(n)}_{}$$p = 0 = $$\modn$$$$\beta$$p.

Since $\beta$ is a multiple of p less than pq, and both p and q are prime, we must have gcd($\beta$, q) = 1. We can apply Euler's theorem using modulus q to conclude $\modn$$\beta^{\varphi(q)}_{}$q = 1, so

$$\modn$$$$\beta^{1+y\varphi(n)}_{}$$q = $$\modn$$$$\beta$$q$$\modn$$$$\beta^{\varphi(q)}_{}$$q^{y(p - 1)} = $$\modn$$$$\beta$$q.

We have two equations modulo p and modulo q, and can apply the Chinese Remainder Theorem (Thm. 10.5) to obtain one modulo pq. Hence

$$\modn$$$$\beta^{1+y\varphi(n)}_{}$$n = $$\modn$$$$\beta$$n = $$\beta$$

as desired. In the case where $\modn$$\beta$q = 0, the argument is the same after exchanging p and q.

Remarks.

1. 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.

2. If e is small, there is a possibility of having some message elements $\beta$ for which $\beta^{e}_{}$ < n; for such a $\beta$, decrypting without knowledge of $\varphi$(n) is easy: just compute the e-th root of $\beta$, since n is not a consideration. With care, one can either ensure that such $\beta$ do not occur, or one can encrypt such messages in a slightly different manner.

3. For efficiency reasons, many implementations always use 3 for the encoding exponent e. In general, computing $\modn$$\beta^{e}_{}$n when e is of the form 2^k + 1 is quite efficient. Other common choices for e are 17 and 65537 (2¹⁶ + 1), which are only slightly less efficient than 3.

4. Instead of using the Euler $\varphi$-function, one can use Carmichael's $\lambda$-function, which is the largest order of any element of $\Z_{n}^{*}$. In the case where n is a product of two primes p and q, we have $\lambda$(n) = lcm(p - 1, q - 1). Since p - 1 and q - 1 are always even, the resulting private exponent x will be smaller.

5. 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 $\varphi$(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 $\varphi$(n), a random number is chosen for the public exponent e. If this number is not relatively prime to $\varphi$(n), another random choice is taken until such a number is found. Finally, x is computed as the inverse of e modulo $\varphi$(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 $\beta$ and a key (n, e), and computes $\modn$$\beta^{e}_{}$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.

Making it Useful

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

$$\mverb$$Alen^k < n

where Alen is the length of our alphabet.

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 $\mverb$Alen^k < n, so there will often be $\beta$ so that $\modn$$\beta^{e}_{}$n > $\mverb$Alen^k. In the example above, note that 97² = 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⁷⁵ < 10¹⁵⁰ < 97⁷⁶.

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

> 
  crypt:=RSAEncodeString(text,public);

> 
  RSADecodeString(crypt,private);