Recently, I took the course of Applied Cryptography and learned more details about RSA. The math behind the scene is complicated and attractive for me, so I decided to figure it out.

There are lots of correctness proofs for RSA on the internet, and the most elegant one comes from original paper. This article serves as a note or index about the algorithm, and related math theorems.

First look

RSA uses exponent calculation based on modular arithmetic. A message $M$ is encrypted by raising it with some number $e$, eg, the cipher $C = M ^ e$; and decryption by raising the cipher to another number $d$, eg, $M = C ^ d = (M ^ e) ^ d = M ^ {ed}$.

The original paper has an example, $e = 17$, $d = 157$, modular $n = 2773$, and the message $M = 920$. Using python, we can easily check that $C \equiv M ^ e \equiv 920 ^ {17} \equiv 948 \mod 2773$, and for decryption, $M \equiv C ^ d \equiv 948 ^ {157} \equiv 920 \mod 2773$. it works.

>>> 920 ** 17
242322122805021463846350650290995200000000000000000
>>> _ % 2773
948
>>> 948 ** 157
228511974050288606356776902344003250786765339280429567483703996687679918754310808116762581946500309044935063895813994903862607889435410969372665687695332125577189642781886048649411339280291847319790295052238061530036066382680768550813673301548951552880234295829603371076580111293376807996489026124001520858798504685685090226812534126526485193603752385784652819655258004954411544721976443792145433128756776848416542537051430937496263760556207832371853899712995186966528
>>> _ % 2773
920

How $e$ and $d$ are chosen?

Let’s first walk through the process generating $e$ and $d$.

RSA firstly chooses two prime numbers $p$ and $q$, making the modular $n = pq$. Then $e$ and $d$ are generated with the constraint that $ed - 1$ is a multiple of $\varphi(n)$. Note that $\varphi()$ is Euler’s totient function, in our case, $\varphi(n) = \varphi(pq) = (p - 1)(q - 1)$.

Why does it work?

In the above example, we see that $M \equiv M ^ {ed} \mod n$. If both sides can be divided by $M$, we have:

\(M ^ {ed - 1} \equiv 1 \mod n \tag{1}\).

This looks quite like Euler’s Theorem, which states:

\[M ^ {\varphi(n)} \equiv 1 \mod n\]

As $ed - 1$ is a multiple of $\varphi(n)$, we have $ed - 1 = k \varphi(n)$ for some k. By using Euler’s Theorem, we can conduct that:

\[\begin{align} M ^ {ed} &\equiv M ^ {ed - 1 + 1} \\ &\equiv M ^ {k \varphi(n)} \times M \\ &\equiv M ^ {\varphi(n)} \times M ^ {\varphi(n)} \times … M ^ {\varphi(n)} \times M \\ &\equiv （M ^ {\varphi(n)} \mod n) \times (M ^ {\varphi(n)} \mod n) \times … (M ^ {\varphi(n)} \mod n) \times M \\ &\equiv 1 \times 1 \times … \times 1 \times M \\ &\equiv M \mod n \tag{2} \end{align}\]

The plain text $M$ and modular $n$ should be coprime by the precondition of Euler’s Theorem. However, this precondition is not necessary if conducted by Fermat’s Little Theorem.

By Fermat’s Little Theorem, if $M$ and $p$ are coprime, we have $M ^ {p - 1} \equiv 1 \mod p$, which leads to:

\[\begin{align} M ^ {ed} &= M ^ {k \varphi(n)} \times M \\ &= M ^ {k(p -1)(q - 1)} \times M \\ &= (M ^ {p - 1}) ^ {k(q - 1)} \times M \\ &= (M ^ {p - 1} \mod p) ^ {k(q - 1)} \times M \\ &= 1 ^ {k(q - 1)} \times M \\ &= 1 \times M \\ &= M \mod p \tag{3} \end{align}\]

And the same applies for $q$: $M ^ {ed} \equiv M \mod q$.

Since $M ^ {ed}$ has the same remainder when divided by $p$ and $q$, we have $M ^ {ed} = M \mod pq = M \mod n$ by Chinese Remainder Theorem.

Since $p$ and $q$ are prime numbers, any other number is naturally coprime to both of them. We don’t need coprime precondition any more.

Modular Arithmetic

Equation (1) is derived by division, which we take for granted in real number arithmetic; and equation (2)(3) utilized a multiplication property: $ a \times b \mod n \equiv (a \mod n) \times (b \mod n) \mod n $. Things become different as we are not doing usual arithmetic. We need to prove those properties before taking advantages of them. Let’s begin with intuition.

Intuition

Old textbook told me that math is abstract. Indeed modular arithmetic is the abstract of periodic things in the real world. Clock is one of the periodic things. When the clock handle goes past number 12 in the plate, it’s round back to number 1. The addition and subtraction on the clock is abstract from moving the clock handle clockwise or counter clockwise.

For example:

\[9 + 5 \equiv 2 \mod 12\]

It means to move 5 units clockwise to the clock handle pointed at number 9, as the result, the handler now points to number 2. For normal arithmetic, $ 5 * 3 = 5 + 5 + 5 = 15 $, the same applies to modular arithmetic:

\[5 * 3 \equiv 5 + 5 + 5 \equiv 15 \equiv 3 \mod 12\]

And, division is the inverse of multiplication. For normal arithmetic, divisor zero is meaningless. Because division is a one to one map, all numbers map to zero when multiplied by zero, so the inverse is all numbers when divided by zero. For modular arithmetic, we have $ 4 \times 5 \equiv 8 \mod 12 $, so $ 8 \div 5 \equiv 4 \mod 12 $. However, $ 8 \div 4 \mod 12 $ is meaningless, as $ 4 \times 2 \equiv 8 \mod 12 $, $ 4 \times 5 \equiv 8 \mod 12 $, $ 4 \times 8 \equiv 8 \mod 12 $ and $ 4 \times 11 \equiv 8 \mod 12 $, so when divided by $4$, we get four results $2$, $5$, $8$ and $11$ which is not a one to one map.

Properties

After the abstraction, it’s time to find the properties of modular arithmetic.

The first comes to the addition:

If $A \equiv a \mod n$, and $B \equiv b \mod n$, then $A + B \equiv a + b \mod n$.

We can prove it by visualizing $A$ and $B$ to two lines. As the figure below shows, $A$ and $B$ both can be broken down into divisible parts and remainders, the remainders are $a$ and $b$. When $A$ and $B$ are concatenated together, the divisible parts are still divisible, so the result depends on the remainders of $A$ and $B$, which is $a + b$.

image/svg+xml a b A B a+b

Then is the multiplication:

If $ A \equiv a \mod n $, and $ B \equiv b \mod n $, then $ AB \equiv (A \mod n)(B \mod n) \equiv ab \mod n $.

This time we can use a rectangle to visualize the proof, of which the width and length is $A$ and $B$. The area of the rectangle can be broken down into four parts by the divisible parts and remainder parts of $A$ and $B$. Three of them are divisible, and the non-divisible part is equal to ab, which proves the property.

image/svg+xml a b ab A B

Thanks for this multiplication property, the transformations are valid in equations (2)(3).

And by these properties, we can conclude that modular arithmetic only cares about the remainder part.

Then is the division:

For real number, divided by some number is equivalent to multiply with its inverse. The same applies for modular division, so it is valid if and only if the inverse is unique. It turns out that the unique divisor exists if and only if divisor and modular are coprime. The sufficient and necessary conditions are proved in here and here. Now we understand why the original paper requires message and modular are coprime and the precondition of equation (1).

Theorems leveraged by RSA

Now we start proving theorems leveraged by RSA.

Fermat’ Little Theorem

This theorem states that $ a ^ {p - 1} \equiv 1 \mod p $ if $a$ and $p$ are coprime. Wikipedia uses an intuitive way to prove it by counting necklaces. Section Fermat/Euler Theorem in another paper proves it by congruent and permutation, which defines two sets $P$ and $Q$ under prime modular $p$. Elements in $P$ are from $1$ to $p - 1$, which are all coprime to $p$. And $Q$ is made by multiplying each element in $P$ with some number. The theorem is proved by observing that $Q$ and $P$ are the same since the result of multiplications of elements in $P$ is a permutation of $P$ as elements in $Q$ are distinct to each other and the size/range of $P$ and $Q$ are the same. However, it’s insufficient to support the Euler’s Theorem using this approach provided by the paper. By the way, Fermat’s Little Theorem is a special case in Eulur’s Theorem.

Euler’s Theorem:

Now the modular is not required to be prime, so it’s a general case of Fermat’s little theorem. The theorem is also proved by congruent and permutation. An Indian brother explained the proof with his heavy accent. The set $P$ still contains all the numbers coprime to modular and $Q$ is still made by multiplying all the numbers in $P$. Note that as the modular is not prime, some numbers from $1$ to the $modular - 1$ may not belong to set $P$, which distincts it from Fermat’s Little Theorem. After multiplying, numbers in $Q$ have the possibility of not coprime with modular any more. So extra steps are taken to show that elements in $Q$ are still coprime, by which we get a precondition of permutation. Other processes are the same as Fermat’s Little Theorem.

Euler’s totient function is proved in a series of posts beginning at here by leveraging the multiplicative property of it and factorization.

Chinese Remainder Theorem

RSA uses the corollary or special case of Chinese Remainder Theorem. Let’s walk through the general case first. This theorem says if $ x \equiv a \mod p $ and $ x \equiv b \mod q $, then we have a unique solution for $ x \mod pq $. Here the theorem is proved by constructing $x$ via modular inverse mentioned before.

The corollary says that if $a$ and $b$ are the same, we have $ x \equiv a \mod pq $. Here is the proof of the corollary by letting $ x = a = b $. The corollary is also proved directly by the paper used before to prove Fermat’s Little Theorem.