The RSA cipher

RSA is the most famous asymmetric-key cipher. It is based on a few technical results from number theory that we recall below.

Background

The Euler function. The Euler function \Phi(n) returns the number of numbers less than or equal to n that are coprime to n. Recall that i and n are coprime iff gcd(i,n) = 1, i.e., if the only common divisor is 1. So, for example, we have that \Phi(3) = 2 since 1 and 2 are coprime to 3, \Phi(4) = 2 since only 1 and 3 are coprime to 4 and so on. We report some values below:

\begin{array}{c|c}n & \Phi(n) \\ \hline 1 & 1\\2 & 1\\3 & 2\\4 & 2\\ 5&4\\ 6&2 \\ 7&6 \\ \end{array}

We immediately notice that if n is prime then \Phi(n) = n-1. In fact, by definition, a prime number n is coprime to all the numbers smaller than n. There is another situation where \Phi(n) is easy to compute: when n=p_1 \ldots p_k with p_1 \neq p_2 \neq \ldots \neq p_k prime numbers, we have that \Phi(n) = \Phi(p_1) \ldots \Phi(p_k) = (p_1-1) \ldots (p_k-1).

We prove this result for n = pq with p\neq q primes. The numbers less than n that are not coprime to n is exactly the multiples of p and q, i.e., p,2p,\ldots,(q-1)p,q,2q,\ldots,(p-1)q that are (q-1)+(p-1). Now we have that \Phi(n) = pq-1 - (q-1)-(p-1) = pq  -q -p +1 = (p-1)(q-1).

The Euler Theorem. Let a and n be coprime, i.e., gcd(a,n)=1. Then a^{\Phi(n)} \mod n = 1.
Proof. Let S = (s_1, \ldots, s_{\Phi(n)}) be the \Phi(n) numbers less than n and coprime with n. We consider R = (a s_1 \mod n, \ldots, a s_{\Phi(n)} \mod n) and we show that S = R. We need a few lemmas:

Lemma 1. Let x,y be coprime to n. Then xy is coprime to n.
Proof. This can be easily proved by considering that all divisors of xy are products of divisors of x or y. Thus a common divisor of xy and n must also divide x and/or y. Thus, gcd(xy,n)>1 would imply that gcd(x,n)>1 or gcd(y,n)>1 giving a contradiction.

Lemma 2. Let x be coprime to n. Then x \mod n is coprime to n.
Proof. Since x \mod n = x - kn we have that any common divisor d of x \mod n and n must divide x. In fact, \frac{x \mod n}{d} = t = \frac{x - kn}{d} = \frac{x}{d} - kr that implies \frac{x}{d} is an integer value.

Lemma 3. Let ax \mod n = ay \mod n with gcd(a,n)=1. Then x \mod n = y \mod n.
Proof. We have ax - kn =  ax \mod n = ay \mod n = ay - jn. Thus ax - ay = wn that implies \frac{ax - ay}{a} = \frac{wn}{a} and so x-y = \frac{wn}{a} . Since gcd(a,n)=1 we have that a must divide w and so x-y = tn, i.e., x \mod n = y \mod n.

Now, by Lemma 1 and 2 we have that all numbers in set R are coprime to n and smaller than n. Since S is the set of all numbers coprime to n and smaller than n we obtain that R \subseteq S. Now, consider a s_i \mod n and a s_j \mod n in R. Since a is coprime to n, by Lemma 3 we obtain that a s_i \mod n = a s_j \mod n implies  s_i \mod n =  s_j \mod n, which give a contradiction. Thus we have that a s_i \mod n \neq a s_j \mod n for all i and j. This proves that R = S.

To conclude the proof it is enough to observe that \prod_{i=1}^{\Phi(n)}{s_i} = \prod_{i=1}^{\Phi(n)}{a s_i \mod n} = a^{\Phi(n)}\prod_{i=1}^{\Phi(n)}{s_i \mod n}. Since all s_i are coprime to n, by applying many times Lemma 3 we obtain 1 = a^{\Phi(n)} \mod n, which is what we wanted to prove.

The RSA cipher

RSA stands for Rivest-Shamir-Adleman, the authors of the cipher in 1978. We let n = pq with p,q big prime numbers. We also let a and b be such that ab \mod \Phi(n) = 1. The public key is (b,n) while the private key (secret trapdoor) is (a,n). We let {\cal P}={\cal C} = \mathbb{Z}_n. Encryption is defined as E_{PK}(x) = x^{b} \mod n while decryption is D_{SK}(y) = y^{a} \mod n.

We now show the correctness of the cipher, i.e., that decrypting under the private key a plaintext x encrypted under the public key gives x. Notice that ab \mod \Phi(n) = 1 implies ab = k\Phi(n) +1 for some k. What we need to prove is that x^{ab} \mod n = x. In fact, if this holds we have

\begin{array}{rcl}D_{SK}(E_{PK}(x))  =  (x^b)^a \mod n  =  x^{ab} \mod n = x \end{array}

Notice now that  x^{ab} \mod n = x^{k\Phi(n) + 1} \mod n = (x^{\Phi(n)})^k x \mod n. Thus, in order to prove x^{ab} \mod n = x it is enough to show that (x^\Phi(n))^k x \mod n = x. This proof is split into two cases:

  • gcd(x,n)=1. In this case we know that Euler theorem holds, and we directly have that x^{\Phi(n)} \mod n = 1 which implies (x^{\Phi(n)})^k \mod n = 1, giving the thesis;
  • gcd(x,n)>1. In this case, since x<n we have that either gcd(x,n)=p or gcd(x,n)=q. Without loss of generality we assume gcd(x,n)=p (the proof for the other case is identical). We now have x = jp for some j and gdc(x,q)=1. Euler theorem gives x^{\Phi(q)} \mod q = 1, which implies x^{\Phi(q)\Phi(p)} \mod q = x^{\Phi(n)} \mod q = 1. This implies (x^{\Phi(n)})^k \mod q = 1 giving (x^{\Phi(n)})^k = wq + 1 for some w. We obtain

    \begin{array}{rcl} (x^{\Phi(n)})^k x \mod n &=& (wq + 1) x \mod n\\& =& (wq + 1) jp \mod n\\ &=& wqjp + x \mod n = x\end{array}.

Implementation

As we will discuss, RSA requires a big modulus n of at least 1024 bits. With these sizes, implementation becomes an issue. For example a linear complexity O(n), that is typically considered very good, is prohibitive as it would require at 2^{1024} steps. Every operation should in fact be polynomial with respect to the bit-size k.

Basic operations

We first observe that basic operations such as sum, multiplication and division can be performed in O(k), O(k^2), O(k^2), respectively, by using simple standard algorithms (the one we use when we compute operations by hand). Reduction modulo n amounts to compute a division which is, again, O(k^2).

Exponentiation

This operation is used both for encryption and decryption. First notice that we cannot implement exponentiation to the power of b as b multiplications. In fact, public and private exponents can be the same size as n. Performing b multiplications would then require k^2 2^k operation, i.e., O(2^k) which is like brute-forcing the secret trapdoor and infeasible for k \geq 1024. We thus need to find some smarter, more efficient way to compute this operation.

There exists a much faster algorithm, known as Square-and-Multiply, that is based on the following observation: when we rise a number x to a power of 2 such as 8, instead of performing 7 multiplications we can simply compute ((x^2)^2)^2 = xxxxxxxx which is just 3 multiplications. In general, if the exponent is not a power of 2, we can exploit a similar trick by performing some additional multiplications when needed. For example x^{10} can be done as ((x^2)^2 x )^2 = xx \ xx \ x \ \ xx \ xx \ x: after squaring twice we multiply the result by x so that we have x^5. With a final square we obtain the result.

In particular x^{10} can be written as (x^{5})^2 which is (x^{4}x)^2 and finally ((x^2)^2) x)^2. Intuitively, if the exponent is even we divide it by 2 and we square, if it is odd we get one x out (which is an additional multiplication) and we proceed as above. Dividing the exponent by 2 amounts to follow its binary representation. For example, 10 is 1010.
We start from the most significant bit. At each step we square and, only when we have a 1 we multiply by x. A python implementation follows:

The number of steps in the worst case is O(k^2) for the two multiplications, iterated k times, giving O(k^3). Thus for 1024 bits we can expect about 1 billion steps, which is still efficient on modern machines.

A few examples follow:

Inverse modulo \Phi(n)

This operation is necessary to compute the private exponent from the public one. Recall that RSA requires ab \mod \Phi(n) = 1. To find these two numbers, one technique is to choose b and to compute its multiplicative inverse modulo \Phi(n). This is guaranteed to exist, by the Euler theorem, when gcd(b,\Phi(n))=1. In this particular case, there is also an efficient algorithm to compute the inverse based on the Euclidean algorithm for computing gcd.

We recall the Euclidean algorithm, written in iterative style:

The idea is that, to compute gcd(c,d), when d \neq 0, we can compute gcd(d, c \mod d) since it can be easily seen that they are the same. This algorithm terminates in O(k^3), given that the number of iterations is O(k). This latter fact can be proved by observing that every 2 steps we at least halve the value d. Assume that after one step this is not true, i.e., c \mod d > \frac{d}{2}. Next step will compute d \mod (c \mod d) = d - (c \mod d) < \frac{d}{2} giving the thesis. We know that halving leads to a logarithmic complexity, i.e., linear with respect to the number of bits k.

We now extend the algorithm so to compute the inverse modulo d whenever gcd(c,d)=1. We substitute the computation of c\mod d with

We add two extra variables e and f and we save the initial value of d in d0, as follows:

For example

To see the correctness of the algorithm, we need two auxiliary variables g and h, initialized with 0 and 1, and updated as e and f, i.e.,

Let c0 and d0 note the initial values of c and d, at each iteration it holds e * c0 + g * d0 = c and f * c0 + h * d0 = d. This can be proved by induction:

  • Base case: at the beginning we have c0 = c, d0 = d, e = 1, f = 0 and g = 0, h = 1. Thus e * c0 + g * d0 = c0 = c and f * c0 + h * d0 = d0 = d.
  • Inductive case: we assume e * c0 + g * d0 = c and f * c0 + h * d0 = d hold and we prove they hold after c, d, e, f, g and h are updated. Since c, e and g are updated with the values of d, f and h, respectively, we have that e * c0 + g * d0 = c holds because of f * c0 + h * d0 = d. Variables d, f and h are updated as c – q*d, e – q*f and g – q*h. Thus, f * c0 + h * d0 = (e – q*f) * c0 + (g – q*h) * d0 = e * c0 + g * d0 – q*( f*c0 + h * d0) = c – q*d = d, which gives the thesis.

Thus, when we return e % d0 we have that c is 1 and the invariant e * c0 + g * d0 = c = 1 implies that ( e * c0 + g * d0 ) % d0 = 1, i.e., (e * c0) mod d0 = 1, which by definition means that e mod d0 is the inverse of c0 modulo d0.

Generating RSA exponents

We can thus pick a random public exponent b and compute its inverse modulo \Phi(n). This works if we are lucky and b is coprime to \Phi(n). This happens quite frequently. It can be proved that two random numbers are coprime with probability ~0.6. Thus iterating this 2-3 times should give a suitable pair of public, private exponents.

In practice, however, it is often the case that the public exponent is a fixed constant, typically the prime number 2^{16} +1 = 65537. Using a low exponent improves the performance of encryption (recall that each 1 in the exponent requires an extra multiplication). In this case, of course, we have to choose n so that \Phi(n) = (p-1)(q-1) is not a multiple of 65537.

RSA and factorization: Notice that knowing \Phi(n) makes it very simple to compute the private exponent. Factoring n into pq allows for computing \Phi(n) = (p-1)(q-1). Thus we now understand that RSA security is based on the infeasibility of factoring the modulus n. For this reason we require n to be at least 1024 bits. Numbers of this size are still considered impossible to factor in a reasonable time. A size of 2048 is however already suggested for critical applications. Moreover, if we compute \Phi(n) we can easily factor n since we have a system of 2 equations with two variables p,q:

\left[ \begin{array}{l}n  =  pq\\ \Phi(n) = (p-1)(q-1)\end{array} \right.

By solving it we can find p and q. We thus have that finding \Phi(n) is at least as difficult as factoring. This gives high confidence of the difficulty of breaking the private exponent by simply computing the inverse modulo \Phi(n). However, there could be other ways to break the cipher. We will discuss this more in detail in the next lessons.

Primality test

We finally see how to generate two big prime numbers. The oldest algorithm for finding prime numbers is due to Eratosthenes and is known as the “Sieve of Eratosthenes”. In order to discover all prime numbers less than or equal N we write all numbers from 2 to N. We then start from the smallest (2, initially) that we call p and we remove from the list all of its multiples 2p, 3p, … We iterate the procedure by picking the smallest p survived from previous steps.

At the end, the remaining numbers are guaranteed to be prime since they are not multiples of any smaller number. The algorithm can be optimized by removing multiples starting from p^2. In fact, any smaller np with n < p would have been removed at a previous step when checking the multiples of n. This also implies that we can stop when p is the square root of N. A simple python implementation follows:

For example

Unfortunately this algorithm takes at least N steps meaning 2^{1024} for the smallest RSA modulus.

Instead of generating all the primes we pick them at random and test their primality. There are many probabilistic efficient algorithms for primality test. In 2002, Agrawal, Kayal and Saxena proposed the first deterministic algorithm for primality test in the paper “PRIMES is in P” published on Annals of Mathematics. This is a very important result but the proposed algorithm is much slower with respect to existing probabilistic ones, as it costs O(k^6) which makes it rather slow for k > 1024.

Miller-Rabin test: Here we illustrate one of the most famous probabilistic primality tests due to Miller and Rabin. The algorithm is a NO-biased Montecarlo, meaning that it is always correct for the NO answer (the number is not prime) but can be wrong for the YES case (the number is prime). The probability of being wrong, however, is less than a constant  \epsilon = \frac{1}{4}. This allows for iterating the test until the error is small enough: by running the test r times, the probability that it says YES and the number is not prime is less than \epsilon^r = \frac{1}{4^r}, i.e., it decreases exponentially with respect to the number of iterations. For example if we pick r = 128 we have an error with probability less than \frac{1}{4^{128}} which is less than brute-forcing a typical symmetric key, and so small to be negligible.

Let us now illustrate the algorithm:

Theorem. the above algorithm is always correct on False answers (NO-biased).

Proof. Assume, by contradiction, that the algorithm returns False but the number n is prime. False is only returned at the last step which means the algorithm ‘survived’ all the if branches. In particular we have that a^m \mod n \neq 1. Moreover a^{2^i m} \mod n \neq n-1, for i=0\ldots k-1. By the assumption that n is prime and by Euler theorem we know that a^{\Phi(n)} \mod n = a^{n-1} \mod n = a^{2^k m} \mod n = 1. In summary we have:

\begin{array}{c@{~~~~~}c@{~~~~~}c@{~~~~~}c@{~~~~~}c@{~~~~~}c}a^m \mod n & a^{2^1m} \mod n & a^{2^2m} \mod n & \ldots & a^{2^{k-1}m} \mod n & a^{2^k m} \mod n \\ \not\,\parallel &\not\,\parallel &\not\,\parallel & & \not\,\parallel &\parallel \\ 1,n-1 & n-1 & n-1 & & n-1 & 1\end{array}

It is easy to show that, if n is prime then the only square roots of 1 modulo n are n-1 and 1. In fact, r is a square root of 1 iff r^2 \mod n = 1, i.e., r^2 = 1 + zn for some z, meaning that  r^2 - 1 = (r-1)(r+1) = zn which implies \frac{(r-1)(r+1)}{n} = z. Since n is prime we have that n must divide either r-1 or r+1 and so r = -1,1 \mod n. Notice that if n is not prime there might be square roots of 1 different from 1 and n-1. For example for n=8 we have that 5^2 \mod 8 = 1 meaning that 5 is a square root of 1 modulo 8.

It is now sufficient to notice that each of the above values is the square of the preceding one. Since the last one (a^{2^{k}m}) is equal to 1 we have the the previous (a^{2^{k-1}m}) is a square root of 1 modulo n, i.e., it is 1 or n-1. Now we know that it is different from n-1 which implies it is 1. We iterate (backward) this on all the values until we get a^m \mod n = 1 which gives a contradiction. This proves that the algorithm can never return False if n is prime.

A working python implementation follows. Notice the use of squareAndMultiply for exponentiation (this is necessary if we want to test large primes)

For example:

Generating RSA primes

How can we finally generate big primes? We simply generate them at random and we test their primality. This takes about ln~n steps, where n is the upper bound of the interval we choose from. It can be proved, in fact, that about 1 out of ln~n numbers less than n are prime. For example, if we want 512 bits of size (for a modulus of 1024) we have that ln~n = log_2 n \times ln 2 \approx 512 \times 0.7 \approx 358. Thus, on average, after 358 attempt we should find a prime number of size 512 bits.

Notice that the Miller-Rabin algorithm should be iterated to lower as needed the probability of error in case of successful answer. Even if the original paper proved that such a probability is bounded by \frac{1}{4}, in a subsequent paper [1] it has been shown that the algorithm is much more precise that that. In practice this is the suggested number of iterations from NIST (Appendix C.3): 7,4 and 3 for 512, 1024 and 1536 bits, with an error probability of 2^{-100}, meaning that the test requires very few iterations to give a prime with high probability.

Case study

openSSL uses a number of iterations slightly bigger than the one suggested above. For a 1024 key we have:

The six occurrences of ‘+’ represent six iterations of the Miller-Rabin test.

References

[1] I. Damgard, P. Landrock, and C. Pomerance, C. “Average Case Error Estimates for the Strong Probable Prime Test” Mathematics of Computation, v. 61, No, 203, pp. 177-194, 1993.

Leave a Reply

Your email address will not be published. Required fields are marked *