Background knowledge

The reader is assumed to know some basic mathematics, but nothing too complicated. These assumed concepts include the knowledge of what a prime number is, what taking the modulus of a number means and the ability to read basic mathematical notation.

Co-primes

The next important concept is that of “co-primes”. Two integers, \(a\) and \(b\), are co-prime if the only number that divides them without remainder is 1. In other words their greatest common denominator (from herein "gcd") is 1, which we can write as \(gcd(a,b)=1\). As an example, 14 and 9 are co-prime; there is no number other than 1 that divides both 14 and 9 (note that neither 14 or 9 is a prime however).

Euler’s totient

This is a scary name for a quite simple concept. It’s normally written as \(\phi(n)\), which makes it look even scarier, however don’t be put off as what it represents is quite simple. So what is it? Well the totient is a count: it is the number of integers less than \(n\) that are co-prime to \(n\).

Let’s take an example \(n=6\). Well, taking all the numbers less than 6 we have \({1, 2, 3, 4, 5}\). The number 1 is obviously co-prime. The number 2 is not co-prime to 6 since 2 itself a common factor (\(gcd(2, 6) =2\)), equally 3 and 4 are not co-prime. The number 5 is co-prime to 6 as only number that divides 5 and 6 is 1. Putting all this together we see that the co-primes to 6 are 1 and 5. Thus the number of numbers that are co-prime in the range \(1\leq m \leq 6\) is 2, which means \(\phi(6)=2\).

One more example. What’s the totient of 14. Again we write out all the potential numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 in the range. The numbers which are co-prime to 14 (remember this means there are no factors that divide both the number in question and 14) are 1, 3, 5, 9, 11, 13, which means the number of numbers co-prime to 14 is 6, and hence \(\phi(14)=6\).

Hopefully this shows that despite the scary sounding name the actual thing the totient represents is in itself quite easy to get your head around.

Some interesting properties of the totient.

I’m not going to prove any of these properties, but it’s interesting to note they are true:

  1. The totient is “multiplicative”: \(\phi(mn)=\phi(m)\phi(n)\)

  2. The totient can be computed by using Euler’s product formula. In the simplified case when \(n\) only has 2 prime factors, \(n=qp\), then this product formula looks like \(\phi(n)=n(1-1/q)(1-1/p)=pq(1-1/q)(1-1/p)=(p-1)(q-1)\). Notice that because of multiplicative law, this also implies that for prime numbers \(\phi(p)=p-1\) . This is obvious when you think about it: for any prime number \(p\), all the numbers from 1 to \(p-1\) must be co-prime to \(p\), since \(p\) is prime and therefore by definition has no factors except 1. Hence all the integers below \(p\) share no common factors with it and can be counted in the totient. For our example of \(n=14\), 14=7*2, so that q=7 and p=2, and plugging into the formula does ,reassuringly, give 6.

  3. Euler’s Theorem: \(a^{\phi(n)} \equiv 1 \mod n\), where \(a\) and \(n\) are co-prime positive integers. I’ll say more on this notation in the next segment.

  4. Fermat’s Little Theorem: a special case of Euler’s theorem and says \(a^p \equiv a \mod p\) when \(p\) is prime. In words, it says that any integer when raised to a prime will yield another number that will give remainder one when divided by that prime. Example: \(3^5=243\) and \(243 \bmod 5 = 3\). The modified form of this of interest to us comes by "diving through" by \(a\) and is \(a^{p-1} \equiv 1 \mod p\).

Modular arithmetic and congruence

Hopefully the reader knows what a modulus is, for example \(10 \bmod 3 = 1\) and \(8 \bmod 3 = 2\)….It’s simply the remainder after division. Let’s see what this looks like for a range of numbers if we fix the modulus to 3:

1 mod 3 = 1
2 mod 3 = 2
3 mod 3 = 0 
4 mod 3 = 1
5 mod 3 = 2
6 mod 3 = 0
7 mod 3 = 1
8 mod 3 = 2
9 mod 3 = 0

Do you see the pattern here? It’s a cycle: 1, 2, 0, 1, 2, 0, 1, 2, 0….. that just repeats on and on for however far we would care to go. In effect, we’ve mapped all the integers just one of three numbers, 0, 1 or 2. The set \({1, 4, 7, 10, …..}\) can be grouped together because “under mod 3” they all have remainder 1. They are said to be "congruent" if we wish to use the lingo. We could write this group like \(3k+1\), where \(k\) is an integer.

This leads us to be able to write strange, at first, looking relations like \(1 \equiv 4 \mod 3\), which in words is read as “1 is equivalent to 4 under mod 3”. Really all it means is that 1 and 4 are both members of the set \({1, 4, 7, 10, …..}\) that we mapped out explicitly above. They are both members of the group of numbers that under mod 3 have remainder 1.

A more familiar example is that of time on a 12 hour clock. Here we are working in mod 12. Every 12 hours, time cycles. If it’s 4 now, then in 12 hours it won’t be 4+12=16, it will be 16 mod 12 = 4. In 24 hours it won’t be 24+4=28 it will be 28 mod 12 = 4.

Perhaps now, we can better understand the Euler formula, \(a^{\phi(n)} \equiv 1 \mod n\). It says that when we are working under mod n, then if \(a\) and \(n\) are co-prime (remember this simply means that \(a\) and \(n\) share no common factors other than 1), then \(a\) raised to the power of \(\phi(n)\) (the count of the number of numbers co-prime to n) will be equivalent unity under mod n. This means the that the result will be a member of the group of numbers that under mod n has remainder 1.

Let’s try this. So we need two numbers co-prime to each other, so let’s choose \(a=3\) and \(n=14\). We already know \(\phi(14) = 6\) from earlier. Thus \(3^6=729\). If we compute \(729 \bmod n = 729 \bmod 14 = 1\). It works!

Similarly for Fermat's Little Theorem, \(a^p \equiv a \mod p\) when \(p\) is prime. This says that when we are working under mod p, then any integer raised to the power of \(p\) will yield a result that is in the group of numbers with remainder \(a\).

I’m certainly not going to attempt a proof of Euler’s theorem here, but keeping in mind what is and means will be essential.

Modular multiplication follows the law:

$$(A * B) \bmod C = (A \bmod C * B \bmod C) \bmod C$$

and modular exponentiation follows the law:

$$ A^B \bmod C = ( (A \bmod C)^B ) \bmod C $$

Modular Multiplicative Inverses

If two numbers \(x\) and \(y\) yield unity when multiplied together under mod n, then they are said to be modular inverses, i.e. \(x\times y \equiv 1 \mod n\) then \(y=x^{-1}\). For example \(4\times7 = 1 \bmod 9\), so 4 and 7 are inverse under mod 9.

Modular inverses don’t always exist, for example if we continue to work under mod 9, then choose \(x=3\), what is the modular inverse? In other words for what \(y\) could you solve \(3\times y = 1 (\bmod 9)\). There is no such \(y\).

It turns out that if \(x\) is co-prime to \(p\) (the mod group we have chosen to work under), then it will have a multiplicative inverse in somewhere between \(1\) and \(p-1\). Existence is guaranteed.

For any prime number \(p\), then every number from 1 to \(p-1\) is co-prime to \(p\) (has a gcd of 1 with \(p\)), remember this is why \(\phi(p)=p-1\) when \(p\) is prime. This means that every number from 1 to \(1-p\) has a multiplicative inverse somewhere in the range 1 and \(p-1\) when we are working under mod p. We could take \(p=7\), then choose \(x=4\) and we are guaranteed to find it’s modular inverse (mod 7) in between 1 and 7 . It turns out this inverse is 2, since \(4\times2 \bmod 7 = 1\), hence in mod 7 the numbers 4 and 2 are inverse to one another.

Euclid's lemma

This one of the last building blocks before we go on to RSA proper.

Euclid's lemma says that if a prime \(p\) divides the product \(ab\) of two integers \(a\) and \(b\), then \(p\) must divide at least one of those integers \(a\) and \(b\).

Extra lemma

We can use Euclid's lemma to prove that if \(M\) is an integer and \(p\) and \(q\) are primes with \(p \ne q\) then if \(a\equiv M \mod p\) and \(a \equiv M \mod q\) then it also true that \(a \equiv M \mod p.q\).

Optional aside (proof this):

Suppose we have \(a \equiv M \mod p\) and \(a \equiv M \mod q\). Then for some integers \(i\)  and \(j\), we have:

$$a= M+p.i$$

and

$$a=M+q.j$$

Then necessarily \(p.i=q.j\). This implies that \(p\) divides \(q.j\). By Euclid’s lemma, we have either \(p\) divides \(q\) or \(p\) divides \(j\). Since \(p\) and \(q\) are distinct prime numbers \(q\) cannot be divisible by \(p\) . So we must have that \(p\) divides \(j\), and therefore \(j=p.w\) for some integer \(w\)

With that fact, we can write

$$a= M+q.j = M+q.p.w$$

which implies that

$$a \equiv M \mod p.q $$

Onward to RSA

What we want to first do is find two numbers, \(e\) and \(d\) such that \(ed \equiv 1 \mod \phi(n)\). In words, two numbers that when multiplied together and after division by \(\phi(n)\) give remainder 1. Working in mod n, these numbers \(e\) and \(d\) are inverses. You may have guessed that "e" stands for encryption and "d" for decryption.

If we pick 2 prime numbers \(p\) and \(q\), and we multiply them together to get another number \(n=pq\), then we can calculate the totient of this product by remembering from Euler’s product formula that \(\phi(n)=(p-1)(q-1)\). It’s essential to note, that for us, who know the prime factors of \(n\), \(p\) and \(q\), it was very easy to compute \(\phi(n)\), BUT if \(n\) was really really really large and we didn’t know \(p\) and \(q\) then it would be very computationally difficult to compute \(\phi(n)\). The truth of this statement is key to the security of RSA.

Next we choose another prime number \(e\) from the range \(3 \leq e < \phi(n)\). The hope in choosing \(e\) like this is that because it is prime it has a high chance of having a gcd with \(\phi(n)\) equal 1. In other words, a high chance \(e\) and \(\phi(n)\) (the count of co-primes of n) having a highest common denominator of 1. In other words \(e\) and \(\phi(n)\) being themselves co-prime. If it’s not the case, we must choose \(e\) again.

The reason we need them to be co-prime, is that we are eventually going to seek another prime \(d\), such that \(e.d \equiv 1 \mod \phi(n)\), i.e. \(e\) and \(d\) are modular inverses under \(\phi(n)\), and as we stated above such a modular inverse , \(d\), is only guaranteed if \(e\) and \(\phi(n)\) are co-prime.

The reason why we need them to be modular inverses should become clear later when we examine the ciphering/deciphering.

Our public key becomes \((e, n)\) and our private key will be \((d, n)\).

Cipher

Now if we have a message, \(m\), we generate a cipher, \(c\) with the following

$$ c= m^e \bmod n $$

and to decipher we'd do

$$ c^d \bmod n $$

we need to prove that this results in \(m\) again.

Now the fact that \(ed\equiv 1 \mod \phi(n)\) means that we can write

$$ed=k\phi(n)+1$$

where \(k\) is some integer.

Then

$$ c^d \bmod n =[m^e \bmod n]^d \bmod n $$

Using \(A^B \bmod C = ( (A \bmod C)^B ) \bmod C\), we can write the above as

$$ m^{ed} \bmod n $$

However we start by consider \( m^{ed} \bmod p \).

and substituting in \(ed=k\phi(n)+1\) we have

$$ m^{k\phi(n)+1} \bmod p$$ $$ = (m. m^{k\phi(n)}) \bmod p$$ $$ = (m. (m^{\phi(n)})^k) \bmod p $$

Now using \((A * B) \bmod C = (A \bmod C * B \bmod C) \bmod C\), we can write this as

$$ = ((m \bmod p) ((m^{\phi(n)})^k \bmod p)) \bmod p $$

Using \(\phi(n)=(p-1)(q-1)\):

$$ = ((m \bmod p) ((m^{(p-1)(q-1)})^k \bmod p)) \bmod p $$ $$ = ((m \bmod p) ((m^{(p-1)})^{k(q-1)} \bmod p)) \bmod p $$ $$ = ((m \bmod p) ((m^{(p-1)} \bmod p)^{k(q-1)} \bmod p)) \bmod p $$

Now we can use the modified form of Fermat's Little Theorem, which says that \( m^{(p-1)} \equiv 1 \mod p\) to yield

$$ = ((m \bmod p) (1^{k(q-1)} \bmod p)) \bmod p $$ $$ = ((m \bmod p) (1 \bmod p)) \bmod p $$ $$ = (m \times 1) \bmod p $$ $$ = m \bmod p $$

so we showed that

$$ m^{ed} \bmod p = m \bmod p $$

Assuming our message \(m<p\) (this is why in RSA message size is bounded) then \(m \bmod p = m\) and we can write:

$$ m^{ed} \bmod p = m $$

As an equivalence we can thus now write

$$ m^{ed} \equiv m \mod p $$

Similarly, if we examine \(m^{ed} \bmod q\), we can follow the exact same steps almost to show that

$$ m^{ed} \equiv m \mod q $$

Now, earlier we showed with Euclid's lemma that if \(p\ne q\) then these 2 conditions mean that

$$ m^{ed} \equiv m \mod n $$

This was the desired result. It shows correctness. We get our original message back after decryption.

Testing this by plugging in some numbers

Let's choose our primes \(p=11\) and \(q=13\). This means \(n=11\times13=143\), and \(\phi(n)=(p-1)(q-1)=120\). We need to pick another prime number \(e\) for the public encryption key. It should be co-prime with the totient. We choose \(e=7\) to satisfy those conditions.

Now we need to find our decryption key \(d\) such that \(e.d=1 \mod \phi(n)\) is satisfied, i.e. it's the inverse in this mod world. We can use the Extended Euclidean Algorithm in practice to work out that number quickly, but here I will just state that \(d=103\) and you can test it works because \(7\times103 \bmod 120=1\).

So we have our public key \((7, 143)\) and our secret key \((103, 143)\).

Let's try to encrypt a message \(m=8\).

The cipher

$$ c=m^e \bmod n = 8^7 \bmod 143 = 57 $$

and decryption looks like

$$ c^d \bmod n = 57^103 \bmod 143 = 8 $$

so we encrypted and decrypted our message successfully.

Currently unrated

About Lee

I am a Theoretical Physics PhD graduate now working in the technology sector. I have strong mathematical skills and originally started in heavy-duty scientific computing, but now I work mostly with Python and the Django framework. I am available for hire now, so check out my resume and get in touch.

Comments