Fermat’s Little Theorem and RSA Algorithm

RSA is a cryptographic algorithm that is used to send and receive messages. We use the Fermat’s Little Theorem to prove that RSA works correctly and accurately. In other words, the decrypted message is indeed the original message from the sender. Mathematically we show that applying the encryption function and the decryption function successively produces the identity function.

To see how RSA works, see the previous post An Illustration of the RSA Algorithm.

___________________________________________________________________________________________________________________

RSA Algorithm

We first briefly describe the algorithm and then present the mathematical statement to validate.

Let $N=p \cdot q$ where $p$ and $q$ are two prime numbers. Let $\phi=(p-1) \cdot (q-1)$ . Choose an integer $e$ with $1<e<N$ such that $e$ and $\phi$ are relatively prime.

The public key consists of $N$ and $e$ where $e$ is the encryption key. Once it is published, anyone can use it to encrypt messages to send to the creator of the public key. The following is the encryption function:

$f(M) \equiv M^e \ (\text{mod} \ N)$

where $M$ is a positive integer and is the original message.

The private key is a positive integer $d$ that satisfies:

$d \cdot e \equiv 1 \ (\text{mod} \ \phi=(p-1) \cdot (q-1))$

In other words, $d$ is the multiplicative inverse of $e$ in the modular arithmetic of modulo $\phi$ . The above condition is equivalent to: $de-1=(p-1) \cdot (q-1) \cdot k$ for some integer $k$ .

The number $d$ is the decryption key that will be used to decode messages. So it should remain private.

Once the creator of the public key receives an encrypted message $C=f(M)$ , he or she uses the following decryption function to obtain the original message $M$ .

$g(C) \equiv C^d \ (\text{mod} \ N)$

___________________________________________________________________________________________________________________

The Mathematical Statement to Validate

What we prove is that the decryption function is to undo the encryption function. Specifically, we prove the following:

$g(C)=g(f(M))=(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

In other words, applying the decryption function $g$ to the encryption function $f$ produces the original message.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

In this section, we list out the tools we need to prove the correctness of RSA.

Theorem 1 (Fermat’s Little Theorem)
If $p$ is a prime number and $a$ is an integer such that $a$ and $p$ are relatively prime, then

$a^{p-1}-1$ is an integer multiple of $p$

or equivalently $a^{p-1} \equiv 1 \ (\text{mod} \ p)$ .

For a proof of Fermat’s little theorem, see this post.

Lemma 2 (Euclid’s Lemma)
Let $a$ , $b$ and $d$ be integers where $d \ne 0$ . Then if $d$ divides $a \cdot b$ (symbolically $d \lvert a \cdot b$ ), then either $d \lvert a$ or $d \lvert b$ .

Euclid’s Lemma is needed to prove the following Lemma.

Lemma 3
Let $M$ be an integer. Let $p$ and $q$ be prime numbers with $p \ne q$ .

Then if $a \equiv M \ (\text{mod} \ p)$ and $a \equiv M \ (\text{mod} \ q)$ , then $a \equiv M \ (\text{mod} \ p \cdot q)$ .

Proof of Lemma 3
Suppose we have $a \equiv M \ (\text{mod} \ p)$ and $a \equiv M \ (\text{mod} \ q)$ . Then for some integers $i$ and $j$ , we have:

$a=M+p \cdot i$ and $a=M+q \cdot j$ .

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

Now, $a=M+q \cdot j=M+q \cdot p \cdot w$ , implying that $a \equiv M \ (\text{mod} \ p \cdot q)$ . $\blacksquare$

___________________________________________________________________________________________________________________

The Proof of (1)

We now prove the property $(1)$ described above. We show that

$(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)$

We first show that $M^{ed} \equiv M \ (\text{Mod} \ p)$ and $M^{ed} \equiv M \ (\text{Mod} \ q)$ . Then the desired result follows from Lemma 3.

To show $M^{ed} \equiv M \ (\text{Mod} \ p)$ , we consider two cases: $M \equiv 0 \ (\text{Mod} \ p)$ or $M \not \equiv 0 \ (\text{Mod} \ p)$ .

Case 1. $M \equiv 0 \ (\text{Mod} \ p)$ . Then $M$ is an integer multiple of $p$ , say $M=p \cdot w$ where $w$ is an integer. Then $M^{ed}=(p \cdot w)^{ed}=p \cdot p^{ed-1} \cdot w^{ed}$ . So both $M$ and $M^{ed}$ are integer multiples of $p$ . Thus $M^{ed} \equiv M \ (\text{Mod} \ p)$ .

Case 2. $M \not \equiv 0 \ (\text{Mod} \ p)$ . This means that $p$ and $M$ are relatively prime (having no common divisor other than 1). Thus we can use Fermat’s Little Theorem. We have $M^{p-1} \equiv 1 \ (\text{mod} \ p)$ .

From the way the decryption key $d$ is defined above, we have $ed-1=(p-1) \cdot (q-1) \cdot k$ for some integer $k$ . We then have:

$\displaystyle \begin{aligned} M^{ed}&=M^{ed-1} \cdot M \\&=M^{(p-1) \cdot (q-1) \cdot k} \cdot M \\&=(M^{p-1})^{(q-1) \cdot k} \cdot M \\&\equiv (1)^{(q-1) \cdot k} \cdot M \ (\text{Mod} \ p) \ * \\&\equiv M \ (\text{Mod} \ p) \end{aligned}$

At the step with *, we apply Fermat’s Little Theorem. So we have $M^{ed} \equiv M \ (\text{Mod} \ p)$ .

The same reason reasoning can show that $M^{ed} \equiv M \ (\text{Mod} \ q)$ .

By Lemma 3, it follows that $M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)$ . $\blacksquare$

___________________________________________________________________________________________________________________

Revised August 9, 2014.

3 thoughts on “Fermat’s Little Theorem and RSA Algorithm”

Pingback: Notes on Cryptology | Kıvanç's Pancake House
timclimber on July 25, 2015 at 12:04 am said:

Great! Here is another article-explanation of RSA: http://yurichev.com/blog/RSA/

Reply ↓
andrzej on May 10, 2017 at 3:04 am said:

a=4, b=15, d=6; so d |a*b but neither d | a nor d | b;
In Lemma 2 the missing assumption is that d is a prime.

Reply ↓

Exploring Number Theory

A blog on elementary number theory

Fermat’s Little Theorem and RSA Algorithm

3 thoughts on “Fermat’s Little Theorem and RSA Algorithm”

Leave a Reply Cancel reply

Share this:

Like this:

Related

3 thoughts on “Fermat’s Little Theorem and RSA Algorithm”

Leave a Reply Cancel reply