RSA is still the most common public key algorithm in cryptography world. Even though, applying the algorithm is very easy, it lies behind powerful math theorems. We’ve already proven the Fermat’s Little Theorem and Fermat-Euler Theorem. Now, we’ll extend Fermat’s one to prove Euler’s theorem. In this way, we can show correctness proof of RSA algorithm.
Vlog
You can either continue to read this tutorial or watch the following video. They both cover the math behind RSA encryption algorithm.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Proof of Fermat’s Little Theorem with necklace method and Euler’s Generalization.
Proof of Fermat’s Little Theorem by Induction
Fermat’s Little Theorem
an = a (mod n)
Notice that Fermat’s little theorem states if n is a prime, and a is any integer coprime to n, then an – a is divisible by n without remainder.
Remember that n is a prime number in that expression. Herein, we can divide both side of the term to number a because a and n must be co-primes.
an-1 = 1 (mod n)
Euler’s Theorem
RSA encryption algorithm uses the Euler’s generalization of Fermat’s little theorem.
aϕ(n) = 1 (mod n)
Actually, totient function ϕ(n) is number of integers less than or equal to n that are relatively prime to n. Notice that n is a prime number in Fermat’s Little Theorem. In this case, totient must be n-1.
In Euler’s statement, n does not have to be prime. It says any module n, and any integer a coprime to n. Totient function still means number of integers between 1 and n that are coprime to n. However, we will define n as multiplication of two primes.
We’ll turn back to Fermat-Euler generalization.
RSA Algorithm
We should pick the global module n as multiplication of two primes and named them as p and q.
n = p . q
Notice that ϕ(p) and ϕ(q) are (p-1) and (q-1) respectively because they both are prime numbers. The question is that what is ϕ(n) or ϕ(pq) because it is not prime.
Herein, totient function is a multiplicative function.
ϕ(n) = ϕ(p.q) = ϕ(p).ϕ(q) = (p-1).(q-1)
That is why, we can produce a generalized demonstration.
aϕ(n) = 1 (mod n)
aϕ(p)ϕ(q) = 1 (mod pq)
a(p-1)(q-1) = 1 (mod pq)
Finding the totient function with this formula will be performed very fast because its time complexity is O(1). On the other hand, if you want to find the positive integer number that co-prime to n with a for loop, it would be O(n). Notice that we must work with very large primes and multiplication of those large primes will be very large number. We do not want to spend O(n) for that large number!
Then, the algorithm instructs to pick a random number e that co-prime to ϕ(n). Then, we’ll find its multiplicative inverse for module ϕ(n) and named it d.
e.d = 1 mod ϕ(n)
We can express this term as e.d = k . ϕ(n) + 1
Suppose that m is the message. Let’s calculate m to e to d.
(me)d mod n = med mod n = mk . ϕ(n) + 1 mod n = (mk . ϕ(n) . m) mod n = (mϕ(n))k . m mod n
Now, please focus on the term in the parenthesis. Is it familiar?
mϕ(n) mod n
Yes, it is Fermat-Euler generalization. It must be equal to 1.
mϕ(n) mod n = 1 mod n
Let’s replace it.
(mϕ(n))k . m mod n = (1)k . m mod n = 1 . m mod n = m mod n
As seen, we can restore the message again. Herein, e and d are correlate numbers. We can use one for encryption and the other one for decryption. In other words, let’s say c is the ciphertext. Then, message can be encrypted as illustrated below.
c = me mod n
Message can be restored as demonstrated below.
m = cd mod n
This is the proof of RSA algorithm.
Conclusion
So, RSA algorithm is based on Fermat – Euler generalization. Today, most of digital signatures and certificates are launched on this algorithm. Interestingly, Fermat lived in 17th century and Euler lived in 18th century. However, we’ve just put these genius mathematicians’ discoveries in backbones of security world in 21th century. This is the satisfactory part of math, it does not change. On the other hand, all other sciences would change. Even the physics could change, consider Galileo’s physics and Einstein’s physics.
Bonus
Homomorphic encryption is letting us to make calculations on the encrypted data directly. RSA is partially homomorphic because we will be able to make calculations on its encrypted data if the operation is multiplication.
Like this blog? Support me on Patreon
