# Finding the decryption exponent

For RSA to work, we need to be able to calculate the decryption exponent, given knowledge of the two secret primes. Let's see how this can be done.

In order for the RSA algorithm to be useful, Alice must be able to decrypt any message received. We shall now see how she can calculate the decryption exponent making use of her secret knowledge of the two primes (p) and (q).

Before we show how to do that calculation, let’s introduce one new piece of notation, which makes the calculations slightly simpler.

## Euler’s totient function

If we look at the numbers from 1 to (n) (for any given integer (n)) some of them will be coprime to (n) (which means they share no factor in common with (n)) and some of them will share a common factor with (n). We define (phi(n)), known as Euler’s totient function, to be the number of numbers between (1) and (n) that are coprime to (n).

For example, the numbers 1, 5, 7 and 11 are coprime to 12, so (phi(12) = 4).

If (p) is a prime, it is easy to see that (phi(p) = p-1). This is because every number between (1) and (p) is coprime to (p) other than (p) itself, by definition of (p) being a prime.

If (N=p times q) is the product of two distinct primes, then a number not coprime to (N) must be either divisible by (p) or by (q), and no number other than (N) itself is divisible by both (p) and (q), which again follows from the fact they are primes. That is, the number of numbers not coprime to (N) is equal to (q) (the number of numbers from (1) to (pq) that are divisible by (p)) plus (p-1) (the number of numbers from (1) to (pq) that are divisible by (q), but excluding (pq) since that’s already been counted). Therefore (phi(N),) which is the number of numbers which are coprime to (N), equals (N-(q+p-1)).

Since (N=pq), we see that factors nicely as (phi(N) = (p-1)(q-1).)

For example, take (N=15 = 3times 5). The numbers between 1 and 15 which are coprime to 15 are 1, 2, 4, 7, 8, 11, 13, 14, so (phi(15) = 8). We know that (phi(3) = 3-1) and (phi(5) = 5-1) (since 3 and 5 are prime), and we see that (phi(15) = (3-1)(5-1)), as expected.

So what’s really going on with RSA is that we are finding a (d) such that (ed equiv 1 text{ (mod }phi(N)text{)}).

Remark 1: With a little bit more thought, an argument similar to the one given shows that if (a) and (b) are two coprime integers, then (phi(ab) = phi(a) phi(b)). It is crucial that (a) and (b) are coprime for this to hold true. This means that if you know the factorisation of (n) it is simple to evaluate (phi(n)).

Remark 2: The astute among you will notice that finding (d) such that (ed equiv 1 text{ (mod }p-1text{)}) and also (ed equiv 1 text{ (mod }q-1text{)}) is not equivalent to finding (d) such that (ed equiv 1 text{ (mod }(p-1)(q-1)text{)}) (that is, modulo (phi(N))), but rather it is equivalent to finding (d) such that (ed equiv 1 text{ (mod lcm}(p-1, q-1)text{)}), where lcm stands for the least common multiple. This is true, but most books use (phi(N)) and we shall follow them here.

## Calculating (d) using Euclid’s Algorithm

Remember the RSA algorithm told us to pick (e) coprime to (p-1) and (q-1). This means that (e) is coprime to (phi(N)). And this means the greatest common divisor of (e) and (phi(N)) is (1).

Recall in Week 1, when we looked at the Vigenère cipher we introduced Euclid’s algorithm for finding greatest common divisors. That same algorithm will help us find (d), an integer such that (ed equiv 1 text{ (mod }phi(N)text{)}).

We will show this with an illustrative example using very small primes:

Let’s say Alice chooses (p=11) and (q=17). This means (N=187) but also she can easily calculate (phi(N) = 10 times 16 = 160). Let’s say Alice picks (e=27).

We use Euclid’s algorithm to check that the greatest common divisor of (e) and (phi(N)) is 1, as follows.

First we write (phi(N)) as a multiple of (e) plus a remainder

[160 = 5 times 27 + 25.]

Next we write (27) as a multiple of (25) plus a remainder, as

[27 = 1 times 25 + 2.]

Doing the same thing again shows the gcd is 1:

[25 = 12 times 2 + 1.]

Now we go back up that chain of equalities, in order to write 1 as an integer linear combination of (phi(N)) and (e). The last equation can be rearranged to show

[1 = 25 – 12 times 2.]

But from the second line we know that (2 = 27 – 1 times 25) so we substitute that in to get

[begin{split} 1 &= 25 – 12 times (27 – 1 times 25) \ &= 13 times 25 – 12 times 27. end{split}]

Again, from the first line we know that (25 = 160 – 5 times 27), so substituting that in we see that

[begin{split} 1 &= 13 times (160 – 5 times 27) – 12 times 27 \ &=13 times 160 – 77 times 27. end{split}]

Since (phi(N) = 160) and (e=27), we see that this last equation can be written as (1 equiv -77 times e text{ (mod }phi(N)text{)}).

This suggests that we could take (d = -77).

However, we don’t really want to take negative powers, so note that we can cleverly add and subtract (27times 160) to the equation (1 = 13 times 160 – 77 times 27) to get (1 = (13-27) times 160 + (-77 + 160)times 27), and thus we can take (d=-77+160 = 83).

That is, Alice’s decryption key can be taken to be (d=83).

Remark: The method already hints that the decryption key is not unique.