The Number Theory Behind RSA

NumberTheory

• One of my favorite symbiotic relationships between Number Theory and Cryptography is the intricate. Number Theory provides the reliability that an algorithm works and Cryptography shows us the how secure it is when attacked. RSA incorporates of my favorite theorem in Number Theory and its elegance has allowed us to provably send secure messeges in the modern age.

The Number Theoretic History of RSA

• It all starts with Fermat, and his discovers of the peropeties in numbers. We start our journey with Fermats Little Theorem : \

Fermats Little Theorem

• If p is a prime, then

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

Proof!

• Fermats little theorem lets us examine polynomials of the following form:

$$\begin{array}{r}{x}^n-1=0\end{array}$$

• Using Fermats little theorem, we apply a small restriction, only allowing numbers n = p-1. However, when we send messages to one another, its translated to binary and binary can be interpreted as any integer$\ge 1$. This is when Eulers theorem comes in handy in allowing us to use any positive integrer!

Eulers Theorem

• 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 beign 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}$$

The Cryptographic part of RSA

In most Cryptographic Algorithms, we need to use very large primes(click here to find out why). Lets denote these two large primes p and q. When we multiply p and q, we create a composite number $n=p\times q$ which, using the technology of 2025 is really hard to predict. Using the euler-totient function $\varphi$, we can now generate an encrypted message in the following way. Let C be our encrypted message, then Here is a chart of all the variables to keep track of:

Variable	Reference
p, q	Large Primes Numbers
$n$	modulus ($n=p\times q$)
$e$	Public Key ($e\in [\varphi (n)]$)
$M$	Message that we want to send
$d$	Private Key ($d\in [\varphi (n)],d\ne e$)

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

To generate the private key, you must use the euclidean algorithm.