Recently, I was studying the public key cryptography and found some related textbooks. But it seems to me that the mathematical principle behind the encryption does not be explained very clearly. Most books just pass through the proof part and leave me scratching my head.
I am writing this post to explain the mathematical principle in details and may help you get a better understanding of the public-key cryptography. This post is a little lengthy, please be patient and bring up a pen and some scratch papers to finish the examples by yourself.
Reference book: Understanding and Applying Cryptography and Data Security
First of all, what is public-key cryptography?
As the name suggested, the "public-key" means everyone can see the key.But this key can only be used as encryption. Only the person who has another unique key, also called private key, can decrypt the message.
Why it works?
The way it works is based on one-way functions, which its forward transformation is easy to compute and its inverse transformation is very difficult to compute. But if we provide an additional parameter, which is the private-key in our case, the inverse transformation becomes significantly easier to compute.
The most common one-way function for public-key crypto system is the Integer Factorization. And we will discuss the Integer Factorization in this post.
The other popular one-way functions for public-key crypto are: Discrete Logarithms and Elliptic Curves.
Wait! Did you just say Integer Factorization?
Answer is: Yes and.... no.
Integer Factorization is the integer factorization you learned in primary school. Could you factor out number 12 (1 is not included)?
This may sound incredible at first, but what if factor out number 273,390,491,469,749,653?
The answer is .
Recent public-key crypto commonly use 1024 bits to represent the number to be factor out. Just imagine that if we use a brute force algorithm to let the computer list all the possible values to find the answer, the worst running time would be and we can not find the answer during our life time. [Calculation] This makes the Exhaustive Key Search Attack impossible.
But how we decrypt it (factor out the huge number)? Then, it is time for private-key to flex its muscles.
Before we dive into the topic, let us learn some math.
- Euclidean Algorithm:
Compute the Greatest Common Divisor and
Example: Compute the gcd(42,18) by using Euclidean Algorithm.
- The Extended Euclidean Algorithm
It helps us quickly calculate the modular inverse of a number.
Notice the implication in equation . It tell us that there exist integer m and t such that:
What is the usage of this lemma? Assume two integers m and a have the gcd(m,a) = 1. Then we can write:
According to the definition of modular inverse, we can get that . Compared with the brute force algorithm, which list all possible values to do the modular inverse operation with running-time , the running-time of this algorithm is O(log(n)) under binary implementation.
The following steps will show you how to solve the parameter t (modular inverse of a) .
From equation , we can get:
Then plugin equation into it, we get:
Compare equation and , we can conclude that:
Let us do an example to help you get a better understanding of the process. Compute the inverse of 127 mod 589 using the Extended Euclidean Algorithm.
- Euler's Phi Function
Before I explain the definition, I will introduce the concept of
a. Addition such that for all elements
b. Multiplication such that for all elements
So, what the Euler's Phi Function does is to determine the number of integers in the that are relatively prime to m and is denoted as .
If we factor out the integer m and represented it as the product of prime numbers in the form . Then
Since is a prime number and a factor of m. The number that is not relative prime to is , which contains numbers. The amount of numbers that is relative prime to is . Then the amount of numbers that is relative to m is
- Euler's Theorem
Euler's Theorem states that if the , then
For the proof part you can check this link: Euler's Theorem Proof
- Fermat's Little Theorem
Fermat extends the Euler's Theorem and is used to determine the inverse of an element a in the .
From the Euler's Theorem, we have
Multiply both side with
Public Key Cryptography in real world --- RSA
The main encryption process behind the RSA will be quiet simple to understand if you read the math theorems in the previous section.
The set-up stage:
1. Choose two large prime numbers p and q
2. Compute the Euler's Phi function
3. Find a number , such that and
4. Compute the modular inverse of b:
5. The public key will be and the private key will be .
The encryption/decryption process:
Did you still remember the Integer Factorization problem? For hackers, the first step to find the private key is to factor out the huge number n (commonly 1024 bits), which is impossible by using brute force algorithm.
The following steps shows you why can we decrypt the cipher text by using private key.
Plugin into , we can get:
Since a is the modular inverse of b, then
Now, we need split the situation into two cases:
For , Euler's Theorem states that
For . Since n is consist of two large prime numbers, namely p and q, and gcd(x,n) does not equal 1, then p or q must be the greatest common divisor of x and n. Assume , then and .
Again, Euler's Theorem states that .Thus,