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 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.
Lemma 3
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:
and
.
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.
Pingback: Notes on Cryptology | Kıvanç's Pancake House
Great! Here is another article-explanation of RSA: http://yurichev.com/blog/RSA/
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.