# RSA and How It Works

In the last post we discussed Euler’s theorem:

If $a$ and $n$ are relatively prime, then $$a^{\phi(n)} \equiv 1 \pmod{n}$$ where $\phi(n)$ is the number of integers in $[1,n]$ that are relatively prime to $n$.

For any positive integer $n = p_1^{k_1}p_2^{k_2}p_3^{k_3}…p_r^{k_r}$, where $p$ and $k$ are from the factored form under the fundamental theorem of arithmetic. We have $$\phi(n) = n\prod_{p|n}(1 – \frac{1}{p})$$

Let’s consider a simpler case, $n = pq$, where $p$ and $q$ are two distinct primes. For this special case, $\phi(n) = (p-1)(q-1)$. We simply verify it as follows:

Because $p$ and $q$ are primes, integers in $[1,pq]$ that are relatively prime to $pq$ must be multiple of $p$ or multiple of $q$. There are $q$ multiples of $p$ and $p$ multiples of $q$, and $pq$ is counted twice. Therefore $$\phi(n) = pq -p – q + 1 = (p-1)(q-1)$$

RSA works as follows:

• Two large different primes $p$ and $q$, and their product $n = pq$. When they are large, the factoring can be extremely hard.
• An integer $e$ that satisfies $\gcd(e, \phi(n)) = 1$ is chosen. The pair $(e, n)$ are used as the public key and serve the purpose of encryption. $$m’ = \mathrm{rem}(m^e, n)$$
• An integer $d$ that satisfies $de \equiv 1 \pmod{\phi(n)}$ is chosen. The pair $(d, n)$ are used as the private key and serve the purpose of decryption. $$m = \mathrm{rem}((m’)^d, n)$$

Let’s understand why the decryption works?

\begin{align} m’ & = \mathrm{rem}(m^e, n) \\ m’ & \equiv m^e \pmod{n} \\ (m’)^d & \equiv m^{ed} \pmod{n} \end{align}

We know $de \equiv 1 \pmod{\phi(n)}$, so $\exists~r \in \mathbb{Z}$, such that $r\phi(n) + 1 = de$. We substitute it back to the one above,

\begin{align} (m’)^d & \equiv m^{r\phi(n) + 1} \pmod{n}\\ & \equiv (m^{\phi(n)})^rm \pmod{n} \\ & \equiv m \pmod{n} \end{align}

Now we can see that $$m = \mathrm{rem}((m’)^d, n)$$

Implementation wise, there are are few things to note:

• We know $n = pq$, so as long as both $p$ and $q$ don’t divide $m$, we have $\gcd(m,n) = 1$. When $p$ and $q$ are large, this is usually the case. However, if $\gcd(m,n) \neq 1$, the whole system will break.

## Author: Chaoping Guo

Learning is a privilege that I am grateful for.