Public-Key Cryptography for Dummies (RSA Version)

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 $y=f(x)$ is easy to compute and its inverse transformation $x=f^-1(y)$ 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?

Integer Factorization is the integer factorization you learned in primary school. Could you factor out number 12 (1 is not included)?

Easy! $12 = 2 *2*3$.

This may sound incredible at first, but what if factor out number 273,390,491,469,749,653?

The answer is $512,927,377 *533,000,389$.

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 $O(2^{1025})$ 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  $r_0$ and $r_1$ $\rightarrow gcd(r_0,r_1)$

\begin{aligned} & r_0 = q_1 * r_1 + r_2 && \rightarrow gcd(r_0,r_1)= gcd(r_0,r_1) \\ & r_1 = q_2 * r_2 + r_3 && \rightarrow gcd(r_1,r_2)= gcd(r_2,r_3) \\ & . \\ & . \\ & . \\ & r_{m-2} = q_{m-1} * r_{m-1} + r_m && \rightarrow gcd(r_{m-2},r_{m-1})= gcd(r_{m-1},r_m) \\ & r_{m-1} = q_m * r_m + 0 && \rightarrow gcd(r_{m-1},r_m) = r_m = gcd(r_0,r_1) \end{aligned}

Example: Compute the gcd(42,18) by using Euclidean Algorithm.

\begin{aligned} 42 = 2 * 18 + 6 \\ 18 = 3 * 6 + 0 \\ Thus \; gcd(42,18) = 6 \end{aligned}

• The Extended Euclidean Algorithm

It helps us quickly calculate the modular inverse of a number.

\begin{aligned} & r_0 = q_1 * r_1 + r_2 && \rightarrow r_2 = 1*r_0 - q_1*r_1 \\ &&& = s_2 * r_0 + t_2 * r_1 \\ & r_1 = q_2 * r_2 + r_3 && \rightarrow r_3 = 1*r_1 - q_2*r_2 \\ &&& = r_1 - q_2 * r_2 \\ &&& = r_1 - q_2(r_0 - q_1 * r_1) \\ &&& = -q_2 * r_0 + (1+q_1 * q_2)*r_1 \\ &&& = s_3 * r_0 + t_3 * r_1 \\ & . \\ & . \\ & . \\ & r_{i-4} = q_{i-3} * r_{i-3} + r_{i-2} && \rightarrow r_{i-2} = s_{i-2}*r_0 + t_{i-2} * r_1 & \raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {1}}}\\ & r_{i-3} = q_{i-2} * r_{i-2} + r_{i-1} && \rightarrow r_{i-1} = s_{i-1}*r_0 + t_{i-1} * r_1 & \raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {2}}}\\ & r_{i-2} = q_{i-1} * r_{i-1} + r_{i} ; \raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {3}}} && \rightarrow r_{i} = s_{i-1}*r_0 + t_{i-1} * r_1 & \raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {4}}}\\ & . \\ & . \\ & . \\ & r_{m-2} = q_{m-1} * r_{m-1} + r_m && \rightarrow r_m = s_m*r_0 + t_m * r_1 \raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {5}}}\\ & r_{m-1} = q_m * r_m + 0 && \rightarrow s = s_m, t = t_m \\ \end{aligned}

Notice the implication in equation $\raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {5}}}$. It tell us that there exist integer m and t such that:

$gcd(r_0,r_1) = r_m = s * r_0 + t * r_1$

What is the usage of this lemma? Assume two integers m and a have the gcd(m,a) = 1. Then we can write:

\begin{aligned} s*m + t*a = 1 \\ t*a = (-s)*m + 1 \end{aligned}

According to the definition of modular inverse, we can get that $t = a^{-1}$. Compared with the brute force algorithm, which list all possible values to do the modular inverse operation with running-time $O(2^n)$, 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 $\raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {3}}}$, we can get:

$r_{i} = r_{i-2} - q_{i-1} * r_{i-1}$

Then plugin equation $\raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {1}}}\:\raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {2}}}$ into it, we get:

$r_{i+2} = (s_i - q_{i+1}*s_{i+1} ) * r_0 + ( t_i - q_{i+1}*t_{i+1}) * r_1 ; \raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {5}}}$

Compare equation $\raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {4}}}$ and $\raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {5}}}$, we can conclude that:

$s_{i} = (s_{i-2} - q_{i-1}*s_{i-1} ) * r_0 \\ t_{i} = (t_{i-2} - t_{i-1}*t_{i-1} ) * r_0 \\ With \; initial \; value: \; s_0 = 1, t_0 = 0, s_1 = 0, t_1 = 1$

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.

\begin{aligned} & 587 = 4 * 127 + 81 && t_2 = t_0 - q_1*t_1 = 0 - 4 * 1 = -4\\ & 127 = 1 * 81 + 46 && t_3 = t_1 - q_2*t_2 = 1 - 1 * -4 = 5\\ & 81 = 1 * 46 + 35 && t_4 = t_2 - q_3*t_3 = -4 - 1 * 5 = -9\\ & 46 = 1 * 35 + 11 && t_5 = t_3 - q_4*t_4 = 5 - 1 * -9 = 14\\ & 35 = 3 * 11 + 2 && t_6 = t_4 - q_5*t_5 = -9 - 3 * 14 = -51\\ & 11 = 5 * 2 + 1 && t_7 = t_5 - q_6*t_6 = 14 - 5 * -51 = 269\\ & 2 = 2 * 1 + 0 &&\ \end{aligned} \\ The\;modular\;inverse\;of\;127\;mod\;589\;is\;269\;mod\;589.

• Euler's Phi Function

Before I explain the definition, I will introduce the concept of $Ring\;Z_m$

1.The set $Z_m = {0,1,2...m-1}$

2.Two operations:

a. Addition such that $a + b \equiv c\;mode\;m$ for all elements $a,b,c in Z_m$

b. Multiplication such that $a \times b \equiv c\;mode\;m$ for all elements $a,b,c \in Z_m$

So, what the Euler's Phi Function does is to determine the number of integers in the $Ring\;Z_m$ that are relatively prime to m and is denoted as $\phi(m)$.

If we factor out the integer m and represented it as the product of prime numbers in the form $m = P^{e_1}_1*P^{e_2}_2*P^{e_3}_3...P^{e_n}_n$. Then

$\phi(m) = \prod_{i=1}^{n}(P^{e_i}_i - P^{e_{i}-1}_i)$

Proof:

Since $P^{e_i}$ is a prime number and a factor of m. The number that is not relative prime to $P^{e_1}_1$ is $P_i, 2P_i, 3P_i, 4P_i ... P^{e_1}_1$, which contains $\frac{P^{e_i}_i}{P_i}=P^{e_i-1}$ numbers. The amount of numbers that is relative prime to $P^{e_1}_1$ is $P^{e_i}-P^{e_i-1}$. Then the amount of numbers that is relative to m is $\phi(m) = \phi(P^{e_1}_1)*\phi(P^{e_2}_2)...\phi(P^{e_n}_n) = \prod_{i=1}^{n}(P^{e_i}_i - P^{e_{i}-1}_i)$

• Euler's Theorem

Euler's Theorem states that if the $gcd(a,m) = 1$, then $a^{\phi(m)} \equiv 1\;mod\;m$

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 $Ring\;Z_p$.

From the Euler's Theorem, we have

$a^{\phi(m)} \equiv 1\;mod\;m$

Multiply both side with $a^{-1}$

$a^{-1}*a^{\phi(m)} \equiv a^{-1}\;mod\;m \\ a^{\phi(m)-1} \equiv a^{-1} \;mod\;m \rightarrow modular\;inverse\;of\;a$

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. Comput $n = p * q$

2. Compute the Euler's Phi function $\phi(n) = (p^1-p^0)(q^1-q^0) = (p-1)(q-1)$

3. Find a number $b$, such that $0 < b < \phi(n)$ and $gcd(\phi(n),b) = 1$

4. Compute the modular inverse of  b: $a = b^{-1} \;mod\;\phi(n)$

5. The public key will be $(n,b)$ and the private key will be $(p,q,a)$.

The encryption/decryption process:

$x\;is\;the\;plaintext,\;y\;is\;the\;ciphertext. \\ Encryption:\; y = x^b\;mod\;n \\ Decryption:\; x = y^a\;mode\;n \\$

Proof:

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 $y=x^b\;mod\;n$ into $x = y^a\;mode\;n$, we can get:

\begin{aligned} Right\;Hand\;Side &= (x^b\;mod\;n)^a\;mod\; \\ &= (x^b)^a\;mod\;n \\ &= x^{ab}\;mod\;n \end{aligned}

Since a is the modular inverse of b, then $a*b=1\;mod\;n$

\begin{aligned} Right\;Hand\;Side &= x^{ab}\;mod\;n \\ &= x^{1\;mod\;\phi(n)}\;mod\;n \\ &= x^{w\phi(n)+1}\;mod\;n \\ &= (x^{\phi(n)})^w*x\;mod\;n \\ \end{aligned}

Now, we need split the situation into two cases: $gcd(x,n)=1\;and\;gcd(x,n)\neq1$

For $gcd(x,n)=1$, Euler's Theorem states that $x^{\phi(n)}=1\;mod\;n$

Then,

\begin{aligned} Right\;Hand\;Side &= (1\;mod\;n)^w*x\;mod\;n &= (1*x)\;mod\;n &= x \end{aligned}

For $gcd(x,n)\neq1$. 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 $gcd(x,n)=p$, then $x = a * p$ and $gcd(x,q)=1$.

Again, Euler's Theorem states that $x^{\phi(q)}=1\;mod\;n$.Thus,

\begin{aligned} Right\;Hand\;Side &= (x^{\phi(n)})^w*x\;mod\;n \\ &= (x^{(p-1)(q-1)})^w*x\;mod\;n \\ &= (x^{\phi(q)(p-1)})^w*x\;mod\;n \\ &= (x^{\phi(q)})^{(p-1)*w}*x\;mod\;n \\ &= (1\;mod\;n)^{(p-1)*w}*x\;mod\;n \\ &= (1 + s*q)*x\;mod\;n \\ &= (x + s*q*x)\;mod\;n \\ &= (x + s*q*a*p)\;mod\;n\;\;(x = a * p)\\ &= (x + s*a*n)\;mod\;n \\ &= x\;mod\;n \\ &= x \\ \end{aligned}