The Number Theory Behind RSA

The RSA algorithm is one of the most used asymmetric encryption algorithm. Ever since its public release in 1977, its become the one of the most prominent systems for encryption and digital signature. But it’s creation is the byproduct of centuries of mathematical discoveries in Number Theory whose mathematical foundations continue to influence modern cryptography. Let me guide you through its rich history and make you excited about it!

This article will contain math notation. If you get lost, you can reference this list of notation towards the end of the article.

The Number Theoretic History of RSA

When it comes to discoveries or patterns in number theory, more likely then not, Fermat noticed it first. He noticed the following phenomenon back in 1640:

Fermat's Little Theorem (1640)

• Let p be a prime and a be an integer such that $p\nmid a$, then

$$\begin{array}{r}{a}^{p-1}\equiv 1(\mathrm{mod}p)\end{array}$$

Proof

• To prove fermats Theorem, we will first show $a^p\equiv a(\mathrm{mod}p)$. Primes and the Binomial Theorem will be helpful for lying this out: Base Case:

$$\begin{array}{rl}{0}^p& \equiv 0(\mathrm{mod}p)\\ 1^p& \equiv 1(\mathrm{mod}p)\\ 2^p=(1+1{)}^p& \equiv 1^p+1^p\equiv 1+1=2(\mathrm{mod}p)\\ 3^p=(2+1{)}^p& \equiv 2^p+1^p\equiv 2+1=3(\mathrm{mod}p)\\ & ⋮\end{array}$$

Inductive Step: Suppose that $a^p\equiv a(\mathrm{mod}p)$, then $(a+1{)}^p\equiv a^p+1^p\equiv a+1(\mathrm{mod}p)$ And since p is prime, a has an inverse, giving us: $a^{p-1}=a^{-1}\cdot a^p\equiv a^{-1}\cdot a\equiv 1(\mathrm{mod}p)$

One powerful consequence of Fermat’s little theorem is it’s ability to examine polynomials form $x^n-1=0$. These polynomials are extremely important for cryptography. It’s the basis of many encryption and decryption schemes. We can actually build a simple one using Fermat’s Little Theorem in the following way:

Suppose we choose a prime $p$, and our message $M<p$. We can generate public key $e$ and private key $d$ if we satisfy the following equation:

$de\equiv 1(\mathrm{mod}p-1)$

• We want to solve this particular equation as finding the keys would be non-trivial! It simply requires to first choose any number $e$ that is co-prime to p-1, and then running the Euclidean algorithm to solve for $d$!

To get our encrypted message $C$ we will just do the following:

$$\begin{array}{r}\text{Encryption: }C\equiv M^e(\mathrm{mod}p)\\ \text{Decryption: }M\equiv C^d(\mathrm{mod}p)\end{array}$$

And why does this work? Well its just simple modular arithmetic! $M^{ed}\equiv M^{1+pk-k}\equiv M(M^{p-1}{)}^k\equiv M\cdot 1^k\equiv M(\mathrm{mod}p)$

The problem

If two parties wanted to send encrypted messages to each other, they would need to send over the public key and the prime number used in order to decrypt it. Using both the public and the prime number, an adversary could easily find compute private key by running the extended Euclidean Algorithm!

You could even decrypt it without the public key! Given the prime, there are p-1 options you could test to try to brute force the message. In order to get a better system to encrypt and decrypt messages, we need an algorithm that is harder to generate the private key and brute force.

Adding a new level of complexity, Integer Factorization

Since part of the process is to first, find an agreed upon pair of keys, why not make the modulos the harder part to break? There lies the Integer factorization problem! When given an integer, we already have quick methods of multiplying two integers, but we currently do not have an easy way to find the prime factors given any integer. So instead of making out modulus a single prime, we can make it the product of two very large primes! (I won’t go into detail as to why, but just know that its important. The larger the primes are, the longer it takes for a computer to figure out its prime factors)

Euler to the rescue

The problem with Fermat’s Little Theorem is its reliance of a prime number. Luckily, Euler noticed the following phenomenon!

Eulers Theorem (1760)

• If $n\ge 1$ and $\gcd (a,n)=1$, then $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

Proof!

Lemma) Reordering a set of co-prime numbers

• Let $S=\{a_1,...,a_{\varphi (n)}\}$, where $\gcd (a_i,n)=1$ We construct another set, call it $T=\{a\cdot a_1,...,a\cdot a_{\varphi (n)}\},a\in S$. We claim that $S=T$.

Proof

In multiplying by an arbitrary element in S, we transposed the elements in the set. Hence a transposition of elements in the set results in two equal sets

• Using the above lemma, we can do the following: (note: $\sigma$ is being used as a group action to denote the transposition of the index)

$$\begin{array}{rl}(a\cdot a_1)\cdot ...\cdot (a\cdot a_{\varphi (n)})& \equiv a_{\sigma (1)}\cdot ...\cdot a_{\sigma (\varphi (n))}(\mathrm{mod}n)\\ (a^{\varphi (n)})(a_1\cdot ...\cdot a_{\varphi (n)})& \equiv a_1\cdot ...\cdot a_{\varphi (n)}(\mathrm{mod}n)\\ a^{\varphi (n)}& \equiv 1(\mathrm{mod}n)\end{array}$$

Now we can reconstruct our encryption and decryption primitives in the following way:

$$\begin{array}{rl}\text{Encryption: }C& \equiv M^e(\mathrm{mod}n)\\ \text{Decryption: }M& \equiv C^d(\mathrm{mod}n)\\ \text{Key Generation: }de& \equiv 1(\mathrm{mod}\varphi (n))\end{array}$$

Now you may be wondering: Wouldn’t the attacker be able to easily find the private key? NO! You have to remember, $\varphi (n)$ is locked behind the difficulty of finding the primes of $n$! Current integers used for modern day RSA are about 308 decimal digits long. This computation using modern computers would require computational time that far exceeds the age of the universe!

The Chinese Remainder Theorem!

The most beautiful part of RSA is seeing the Chinese Remainder Theorem working behind the scenes for the public and private key generation. It all starts with out ability to break apart the modulus.

Modulo Factorization

Let $N=n_1\cdot \dots \cdot n_k$ be the factorization of N into pair-wise co-prime factors. Then the congruence $x\equiv a(\mathrm{mod}N)$ is equivalent to

$$\begin{array}{rl}x& \equiv a(\mathrm{mod}{n}_1)\\ x& \equiv a(\mathrm{mod}{n}_2)\\ & ⋮\\ x& \equiv a(\mathrm{mod}{n}_k)\end{array}$$

Proof $n_i\mid N$ for $i\in [k]$ and $x\equiv a(\mathrm{mod}N)⟺N\mid (x-a)$, by transitivity, $n_i\mid (x-a)⟺x\equiv a(\mathrm{mod}{d}_i)$ giving us our system of equations:

$$\begin{array}{rl}x& \equiv a(\mathrm{mod}{n}_1)\\ x& \equiv a(\mathrm{mod}{n}_2)\\ & ⋮\\ x& \equiv a(\mathrm{mod}{n}_k)\end{array}$$

We break apart $\varphi (n)=n_1\cdot \dots \cdot n_k$ such that $gcd(n_i,n_j)=1$ we can rewrite $de\equiv 1(\mathrm{mod}\varphi (n))$ into the following system of equations:

$$\begin{array}{rl}de& \equiv 1(\mathrm{mod}{n}_1)\\ de& \equiv 1(\mathrm{mod}{n}_2)\\ & ⋮\\ de& \equiv 1(\mathrm{mod}{n}_k)\end{array}$$

And when we have a system as such, we can now use the Chinese remainder theorem!

Chinese Remainder Theorem (3rd-5th C.E., proved by Gauss 1801)

Let $n_1,n_2,\dots ,n_r$ be positive integers such that $gcd(n_i,n_j)=1$ for $i\ne j$. Then the linear congruence’s:

$$\begin{array}{rl}x& \equiv a_1(\mathrm{mod}{n}_1)\\ x& \equiv a_2(\mathrm{mod}{n}_2)\\ & ⋮\\ x& \equiv a_r(\mathrm{mod}{n}_r)\end{array}$$

has a simultaneous solution, which is unique modulo the integer $n_1{n}_2\cdots n_r$.

Proof

• Existence of a solution:

Let $n=n_1\cdots n_r$ For each $k\in [r]$, let $N_k=\frac{n}{n_k}$. Since $gcd(n_i,n_j)=1$, then $gcd(N_k,n_k)=1$. Using this, we know that there exists a solution to $N_{k}x\equiv 1(\mathrm{mod}{n}_k)$ We will denote the unique solution of this equation as $x_k$. Our goal is to prove that the integer: $\bar{x}=a_1{N}_1{x}_1+\dots +a_r{N}_r{x}_r$ is a simultaneous solution of the given system.

1. $N_i\equiv 0(\mathrm{mod}{n}_k)$ when $i\ne k$, because $n_k\mid N_i$. We get the following congruence: $\bar{x}\equiv a_k{N}_k{x}_k(\mathrm{mod}{n}_k)$
2. Since $N_k{x}_k\equiv 1(\mathrm{mod}{n}_k)$, we now get $\bar{x}\equiv a_k(\mathrm{mod}{n}_k)$ Giving us the existence of a solution to the system of congruences.

• Uniqueness of the Solution

Suppose $x^{\prime }$ is another integer that satisfies these congruences. Then, $\bar{x}\equiv a_k\equiv x^{\prime }(\mathrm{mod}{n}_k)k\in [r]$ Then $n_k\mid \bar{x}-x^{\prime }$ for every $k$. Since $gcd(n_i,n_j)=1$, then we can easily obtain $n_1{n}_2\dots n_r\mid \bar{x}-x^{\prime }⟺\bar{x}\equiv x^{\prime }(\mathrm{mod}{n}_1{n}_2\cdots n_r)$. Hence proving that our solution is unique modulo the integer $n_1{n}_2\cdots n_r$

Can you make your own primitive?

As you can see, RSA is the final product of interlocking many different mechanisms in number theory. From the Chinese remainder to Euler to even Gauss, it is one of the most beautiful examples of how centuries of mathematical curiosity lead to one of the most used algorithms in our modern age.

Quick Notation Reference

Variable	Reference
$p,q$	Large Primes Numbers
$M$	Message we want to encrypt
$C$	Encrypted message we will send or decrypt
$e$	Public Key
$d$	Private Key
$n$	modulus ($n=p\times q$)
$\varphi (n)$	Euler-Totient Function

Back Links

Fermat’s Little Theorem Euler’s Theorem Chinese Remainder Theorem Modulo Factorization Theorem