Why RSA Decrypts Correctly: Euler's Theorem and the Chinese Remainder Theorem

This article has three layers:

1. The intuition: public keys, private keys and the "one-way door"
2. Real-world use: HTTPS certificates, signatures and some classic failures
3. The mathematics: Euler's theorem, why $ed \equiv 1$, CRT speedups and a worked example

Layer 1: The Intuition

1.1 A padlock anyone can close but only you can open

An RSA public key is like an open padlock: you can make thousands of copies and send them around the world, and anyone can use one to lock a box. But only you hold the key, so only you can open a locked box.

1.2 A one-way door: easy to multiply, hard to take apart

RSA's security comes from a very plain fact:

• A computer multiplies two 300-digit primes $p, q$ in the blink of an eye;
• But given the product $n = pq$, recovering $p$ and $q$ would take the fastest known classical algorithms practically forever.

The private key $d$ is computed from $p$ and $q$. An outsider only knows $n$, and without factoring $n$ cannot compute $d$. A structure that is "easy in one direction, hard in the other, but easy again if you know a secret ($p, q$)" is called a trapdoor one-way function.

1.3 Why "a power of a power" returns to the start

Picture a clock face, not with 12 positions but with very many. Start from $m$ and step forward by multiplying by $m$ each time. After exactly $\varphi(n)$ steps you always land on $1$; one more step brings you back to $m$ itself.

RSA chooses $e$ and $d$ so that $e \cdot d = 1 + k\varphi(n)$, so "going $e$ times, then $d$ times" means circling $k$ full laps plus one more step, landing exactly on $m$. Outsiders don't know how long a lap is ($\varphi(n)$), so they don't know how many steps lead back.

Layer 2: Real-World Use

2.1 Encryption and signatures

• Encryption: lock with someone else's public key, and only they can open it. In practice RSA only encrypts a random AES key (a "digital envelope"), and AES handles the bulk data.
• Signatures: the reverse. "Lock" a document's hash with your own private key, and anyone can open it with your public key to verify. If it opens, the private-key holder must have signed it.

HTTPS certificates, software-update signatures, PGP email and SSH logins relied mostly on RSA for decades. New systems increasingly use elliptic curves (see "Elliptic Curves"), because the keys are far shorter for the same security:

2.2 Some classic failures

Layer 3: The Mathematics

3.1 Key generation

1. Choose two large primes $p, q$ and let $n = pq$;
2. Compute $\varphi(n) = (p-1)(q-1)$, the number of integers in $\{1, \dots, n\}$ coprime to $n$;
3. Choose $e$ with $\gcd(e, \varphi(n)) = 1$ (commonly $e = 65537$);
4. Use the extended Euclidean algorithm to find $d \equiv e^{-1} \pmod{\varphi(n)}$.

The public key is $(n, e)$ and the private key is $d$.

3.2 Euler's theorem: a corollary of Lagrange's theorem

$\mathbb{Z}_n^\times$ (the invertible elements modulo $n$) is a finite group under multiplication, of order $\varphi(n)$. By Lagrange's theorem, the order of every element divides the order of the group, so

$$a^{\varphi(n)} \equiv 1 \pmod n,\qquad \gcd(a, n) = 1.$$

This is Euler's theorem; when $n = p$ is prime it is Fermat's little theorem, $a^{p-1} \equiv 1$.

3.3 Why decryption is correct

From $ed = 1 + k\varphi(n)$,

$$c^d = (m^e)^d = m^{1 + k\varphi(n)} = m \cdot \big(m^{\varphi(n)}\big)^k \equiv m \cdot 1^k = m \pmod n.$$

3.4 The CRT speedup

By the Chinese Remainder Theorem, $\mathbb{Z}_n \cong \mathbb{Z}_p \times \mathbb{Z}_q$ is a ring isomorphism. So $c^d \bmod n$ can be split into two halves:

$$m_p = c^{\,d \bmod (p-1)} \bmod p,\qquad m_q = c^{\,d \bmod (q-1)} \bmod q,$$

and $(m_p, m_q)$ is then combined into the unique solution modulo $n$. Reducing the exponents modulo $p-1$ first is also thanks to Fermat's little theorem. The modulus has half as many bits, making multiplication about 4 times cheaper, and the exponent has half as many bits too; overall it is 3 to 4 times faster.

3.5 A worked example

Summary