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.

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:

def squareAndMultiply(x,e):
    r=1
    b = bin(e)[2:]		# binary representation of e, removes the 0b
    for bit in b:		# for all bits of exponent
        r = (r*r)             	# we always square
        if bit=='1':
            r = (r*x)		# we multiply only if bit is 1
    return r

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:

>>> squareAndMultiply(2,8)
256
>>> squareAndMultiply(2,10)
1024
>>> squareAndMultiply(2,20)
1048576
>>> squareAndMultiply(2,1024)
17976931348623159077293051907890247336179769789423065727343008115773267580550096313270847732240753
60211201138798713933576587897688144166224928474306394741243777678934248654852763022196012460941194
53082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356
329624224137216L
>>> squareAndMultiply(2,2048)
32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913
46368871796092189801949411955915049092109508815238644828312063087736730099609175019775038965210679
60576383840675682767922186426197561618380943384761704705816458520363050428875758915410658086075523
99123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150
25859286417711672594360371846185735759835115230164590440369761323328723122712568471082020972515710
17269313234696785425806566979350459972683529986382155251663894373355436021354332296046453184786049
52148193555853611059596230656L
>>>

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:

def Euclid(c,d):
    while d != 0:
        tmp = c % d
        c = d
        d = tmp
    return c

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

q = c//d		# integer division
tmp = c - q*d	# this is c % d

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

def EuclidExt(c,d):
    d0 = d
    e = 1
    f = 0
    while d != 0:
        q = c//d	# integer division
        tmp = c - q*d	# this is c % d
        c = d
        d = tmp
        tmp = e - q*f	# new computation for the inverse
        e = f
        f = tmp
    if c == 1:
	return e % d0	# if gcd is 1 we have that e is the inverse

For example

>>> EuclidExt(5,17)
7
>>> 7*5 % 17
1
>>> EuclidExt(14,17)
11
>>> 14*11 % 17
1
>>>

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

        tmp = g - q*h	# new computation for the inverse
        g = h
        h = tmp

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:

import sys, math

def Sieve(N):
    Ns = int(math.sqrt(N))              # square root of N
    sieve = set(range(2,N+1))           # sets are good to model the 'sieve'
    for p in range(2,Ns+1): 
        if p in sieve:                  # for all survived numbers
            for q in range(p*p,N+1,p):  # we remove multiples bigger that p*p
                sieve.discard(q)
    print sieve                         # sieve have only primes

For example

>>> Sieve(22)
set([2, 3, 5, 7, 11, 13, 17, 19])
>>>

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:

Prime(n):
    write n-1 = 2^k * m
    pick a random a such that 1 < a < n
    b = a^m mod n
    if b == 1:
        return True
    for i in range(0,k):
        if b == n-1:
            return True
        b = b*b mod n
    return False

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)

def Prime(n):
    m = n-1
    k = 0
    while (m&1 == 0):       # while m is even
        m = m>>1
        k += 1
    a = random.randrange(2,n)
    b = squareAndMultiply(a,m,n)
    if b == 1:
        return True
    for i in range(k):
        if b == n-1:
            return True
        b = b*b % n
    return False

For example:

>>> from primality import *
>>> Prime(3)
True
>>> Prime(5)
True
>>> Prime(8)
False
>>> Prime(11522209602914035334582776765168233041221730674213419598532382197901576899621082
564579279226654163047918553777391630395657069138498001131991904807951650901)
True
>>>

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:

$ openssl genrsa 1024
Generating RSA private key, 1024 bit long modulus
.............................++++++
..........++++++
e is 65537 (0x10001)
-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgQCgEsd7T2jArgJsusd2bXXR0D5JjUnvccwiDuEJXtk6AhZcOHSX
kWxPWvgskXMDXxgNZtyYr3aC8VYEP83yVj6qH/T5fueWH0O0reygy1LTLfvbp56F
g/52ssCwQCLtFjIEPu93Sa5MR5d2iJ9LKamE22qGbiSmQvfOJLMAtarkcQIDAQAB
AoGAEbpCsVtYBI7A4f3FfU4eEEB5xXeKSqRVsSfosDr637u/cjMmZmrKjfdLKNRq
4mKzrThJEffMri/AEPRoAICgq9XJn3AlW1CC9F7ISs2K/BUKYkvHHHQsqQsyR+Y+
EISmtVtYGUW0ShKfqtO61DmDbrtWlCn4BZRFUfyTzIPyTckCQQDOR7DLWBlRl6tI
ldTTUnytnxHvbsQuZIMBMdDhYRDOjBPjHAT2h0gMRbstp4fqJguT8+7jKeHZ29yE
LZDlbf9DAkEAxqfzNi2FxFnSvANJ5MAoOXNQhWqme5WtJ+Hc4ffelSGrt/lgfAMe
OtWqlmCFOpZw7YuhnHe27TRFpa2tnjGwOwJAXi8HfuC7trBcaWjX4qDgAloF01+s
vU3xLsNzDuTFyrjUf7aUYYeFEu1nuEGs4fD7ClOvOBMwZstnFQbFCKw/hwJAD0MZ
+WCX9VTdTtqF09A7huZoGkfuUHJYYkcE/EtZy2VR1wmOsxheOzDtMS5rLewe8vEW
UnoUELdCXo8wVoYEvwJAWhpesKH6cA7+sYZk2PK6edEPHnRCP6eewnG5M14CTin9
DR0N0kkoOdybAY/V8CbhqTMlrE3g7+pchbAe83OmuA==
-----END RSA PRIVATE KEY-----

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.