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.