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.
We first briefly describe the algorithm and then present the mathematical statement to validate.
Let where and are two prime numbers. Let . Choose an integer with such that and are relatively prime.
The public key consists of and where 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:
where is a positive integer and is the original message.
The private key is a positive integer that satisfies:
In other words, is the multiplicative inverse of in the modular arithmetic of modulo . The above condition is equivalent to: for some integer .
The number 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 , he or she uses the following decryption function to obtain the original message .
The Mathematical Statement to Validate
What we prove is that the decryption function is to undo the encryption function. Specifically, we prove the following:
In other words, applying the decryption function to the encryption function 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 is a prime number and is an integer such that and are relatively prime, then
is an integer multiple of
or equivalently .
For a proof of Fermat’s little theorem, see this post.
Lemma 2 (Euclid’s Lemma)
Let , and be integers where . Then if divides (symbolically ), then either or .
Euclid’s Lemma is needed to prove the following Lemma.
Let be an integer. Let and be prime numbers with .
Then if and , then .
Proof of Lemma 3
Suppose we have and . Then for some integers and , we have:
Then . This implies that divides (). By Euclid’s lemma, we have either or . Since and are distinct prime numbers, we cannot have . So we have and that for some integer .
Now, , implying that .
The Proof of (1)
We now prove the property described above. We show that
We first show that and . Then the desired result follows from Lemma 3.
To show , we consider two cases: or .
Case 1. . Then is an integer multiple of , say where is an integer. Then . So both and are integer multiples of . Thus .
Case 2. . This means that and are relatively prime (having no common divisor other than 1). Thus we can use Fermat’s Little Theorem. We have .
From the way the decryption key is defined above, we have for some integer . We then have:
At the step with *, we apply Fermat’s Little Theorem. So we have .
The same reason reasoning can show that .
By Lemma 3, it follows that .
Revised August 9, 2014.