RSA Cryptosystem

RSA underlies much of practical public-key cryptography: TLS/SSL handshakes that secure web traffic, PGP and S/MIME email encryption, code-signing certificates, and SSH key authentication all use RSA or its close descendants for key exchange and digital signatures. The correctness proof given here — Euler's theorem plus CRT — is also exactly the identity exploited in fast RSA implementations: decryption is done separately modulo $p$ and modulo $q$ (each with a much smaller exponent, via Fermat's little theorem) and then recombined by CRT, giving roughly a fourfold speedup over direct exponentiation mod $n$. Beyond cryptography, RSA is a standard teaching vehicle in computational number theory courses for illustrating fast modular exponentiation, the extended Euclidean algorithm, and primality testing (needed to generate $p$ and $q$ in the first place), and it motivated decades of research into integer factorization algorithms (Pollard's rho, the quadratic sieve, the number field sieve) precisely because breaking RSA via factoring became a concrete, well-funded research target.

Ask the tutor: How does the CRT-based decryption speedup used in real implementations follow from the same correctness proof given here?

Think of $n$ as a padlock that anyone can snap shut but that only the key-holder can open. Snapping it shut corresponds to raising $m$ to the power $e$ modulo $n$ — an operation any onlooker can perform because $n$ and $e$ are public. Opening it corresponds to raising to the power $d$. The reason this asymmetry is possible is that $e$ and $d$ are inverses not modulo $n$, but modulo the hidden number $\varphi(n)$, and computing $\varphi(n) = (p-1)(q-1)$ requires knowing $p$ and $q$ — which is exactly what factoring $n$ would reveal, and factoring large numbers is (believed) computationally hard. A helpful picture is the "clock inside a clock." The exponent arithmetic $ed \equiv 1 \pmod{\varphi(n)}$ happens on a small hidden clock of size $\varphi(n)$; but the raw computation $m^e \bmod n$ happens on the big public clock of size $n$. Euler's theorem is the gear that connects the two clocks: raising a unit $m$ to a multiple of $\varphi(n)$ brings you back to $1$ on the big clock, precisely because the order of any unit divides $\varphi(n)$, the size of the small clock.

The other subtlety worth picturing is that Euler's theorem, in its basic form, only speaks about units — residues $m$ coprime to $n$. Since $n = pq$, the only non-units modulo $n$ in the range $[0, n-1]$ are the multiples of $p$ or of $q$, a rare and controllable set. Correctness for these exceptional messages needs a separate short argument, supplied by the Chinese Remainder Theorem, and this is where a fully rigorous proof must do a bit more work than "just cite Euler."

Remark on proof technique. The proof uses reduction to prime moduli via CRT, a standard device precisely because Euler's theorem, in its elementary form, is a clean statement only about units; passing to $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$ turns the multiples of $p$ or $q$ into the trivial zero case, so no separate machinery (Carmichael function, group actions) is needed — only Fermat's little theorem, applied twice, and the CRT isomorphism.

Example 1: full key generation and encryption/decryption with asymmetric numbers. Let $p = 61$, $q = 53$ (deliberately unequal, of different bit-lengths in spirit). Then

Choose $e = 17$. Check $\gcd(17, 3120) = 1$: since $3120 = 2^4 \cdot 3 \cdot 5 \cdot 13$ and $17$ is prime and shares no factor with these, indeed $\gcd(17,3120)=1$. Find $d$ with $17d \equiv 1 \pmod{3120}$ via the extended Euclidean algorithm:

Back-substitute:

So $-367 \times 17 \equiv 1 \pmod{3120}$, i.e. $d \equiv -367 \equiv 3120 - 367 = 2753 \pmod{3120}$. Check: $17 \times 2753 = 46801$. Divide: $46801 / 3120 = 15.0003\ldots$, and $15 \times 3120 = 46800$, so $17 \times 2753 = 46800 + 1 = 46801$, confirming $17 \times 2753 \equiv 1 \pmod{3120}$. So $d = 2753$. Public key: $(n,e) = (3233, 17)$. Private key: $(n,d) = (3233, 2753)$.

Encrypt $m = 65$ (an asymmetric, non-round choice). Compute $c = 65^{17} \bmod 3233$ by repeated squaring:

$992^2 = 984064$. Divide: $984064 / 3233 \approx 304.4$, and $304 \times 3233 = 982832$, remainder $984064 - 982832 = 1232$. So $65^4 \equiv 1232$.

$1232^2 = 1517824$. $469 \times 3233 = 1516277$; remainder $1517824 - 1516277 = 1547$. So $65^8 \equiv 1547$.

$1547^2 = 2393209$. $740\times 3233 = 2392420$; remainder $2393209-2392420 = 789$. So $65^{16}\equiv 789$. Now $17 = 16 + 1$, so

$789\times 65 = 51285$. Divide: $15\times 3233 = 48495$; remainder $51285 - 48495 = 2790$. So $c = 2790$.

Decrypt $c=2790$ using $d = 2753$: we must verify $2790^{2753} \equiv 65 \pmod{3233}$. Rather than repeat a 2753-step exponentiation by hand in full, we verify correctness structurally, as the theorem guarantees, and spot-check consistency using the multiplicative structure: since $65$ and $3233 = 61\times 53$ share no common factor ($65 = 5\times 13$, coprime to $61$ and $53$), Euler's theorem applies directly to $m=65$, and the theorem proved above guarantees

using $17\times 2753 = 46801 = 1 + 15\times 3120$ exactly as computed above. This is the content of the correctness theorem applied to this specific numerical instance; the reader can confirm it by continuing the square-and-multiply decryption to the same value $65$.

Example 2: a message that is not coprime to $n$ (testing the CRT case of the proof). Keep $n = 3233 = 61\times 53$, $e=17$, $d=2753$ from Example 1, but now encrypt

which shares the factor $61 = p$ with $n$, so $\gcd(m,n) = 61 \ne 1$ — exactly the case Euler's basic theorem does not directly cover, and which our proof handled via the $p \mid m$ case. Compute $c \equiv 244^{17} \pmod{3233}$. First reduce modulo $p=61$ and $q=53$ separately (legitimate by CRT, and a useful shortcut mirroring the proof): Modulo $61$: $244 = 4\times 61 + 0$, so $244 \equiv 0 \pmod{61}$, hence $244^{17}\equiv 0^{17} = 0\pmod{61}$. Modulo $53$: $244 = 4\times 53 + 32$, so $244\equiv 32\pmod{53}$. Compute $32^{17}\bmod 53$ by Fermat: since $\gcd(32,53)=1$ and $53$ prime, $32^{52}\equiv1\pmod{53}$, but we need $32^{17}$ directly. Square-and-multiply:

So $c \equiv 0 \pmod{61}$ and $c \equiv 31 \pmod{53}$. Solve by CRT: we want $c = 61k$ with $61k \equiv 31 \pmod{53}$. Since $61\equiv 8\pmod{53}$, solve $8k\equiv31\pmod{53}$. The inverse of $8$ mod $53$: $8\times 20 = 160 = 3\times53+1=159+1$, so $8^{-1}\equiv20\pmod{53}$. Then $k \equiv 20\times31 = 620 \equiv 620-11\times53=620-583=37\pmod{53}$. So $k=37$ gives $c = 61\times37=2257$, and we check $2257 < 3233$. So $c=2257$.

Decryption recovers $m=244$: by the theorem (Case 1 of the proof, $p\mid m$), $c^d \equiv 0 \pmod{61}$ automatically matches $m\equiv0\pmod{61}$; and modulo $53$, since $\gcd(32,53)=1$, Fermat's theorem applies to give $32^{17\times2753}\equiv 32^{1+15\times3120}\equiv 32\pmod{53}$ exactly as in the generic argument, so $c^d \equiv 244 \pmod n$ by CRT recombination — confirming that even though $m$ shared a factor with $n$, decryption still exactly recovers $m$, as guaranteed by the full (not restricted-to-units) correctness theorem.