RSA & public-key cryptography

Public-key cryptography: the asymmetry

In a public-key system each party has two keys: a *public* key $P$ anyone may use, and a *secret* key $S$ kept private. They are inverse transformations — $S(P(M)) = M$ and $P(S(M)) = M$ for every message $M$ — but knowing $P$ does not reveal $S$. RSA realizes this with modular exponentiation: the public and secret operations are $M^e \bmod n$ and $M^d \bmod n$, where $e$ and $d$ are exponents that undo each other modulo $n$.

The number theory behind it

RSA depends on Euler's phi function $\varphi(n)$ — the count of integers in $\{1,\dots,n\}$ that are relatively prime to $n$ — and on Euler's theorem:

$$a^{\varphi(n)} \equiv 1 \pmod n \quad\text{for every } a \text{ with } \gcd(a,n)=1.$$

When $n = pq$ is a product of two distinct primes, $\varphi(n) = (p-1)(q-1)$. Fermat's little theorem is the special case $a^{p-1}\equiv 1 \pmod p$ for prime $p$ — it patches the correctness proof when $M$ happens to share a factor with $n$.

Key generation

1. Choose two large random primes $p \ne q$ (1024 bits each in practice).
2. Compute the modulus $n = pq$ and $\varphi(n) = (p-1)(q-1)$.
3. Pick a small odd $e$ with $\gcd(e,\varphi(n)) = 1$ (often $e = 65537$).
4. Compute $d = e^{-1} \bmod \varphi(n)$ with EXTENDED-EUCLID (lesson 8.1).
5. Publish $P = (e,n)$; keep $S = (d,n)$ secret. Discard $p$, $q$, $\varphi(n)$.

Encryption of a message $M$ (an integer with $0 \le M < n$): $C = M^e \bmod n$. Decryption: $M = C^d \bmod n$. Both are single modular exponentiations — the algorithm from 8.1.

Why decryption inverts encryption

By construction $ed \equiv 1 \pmod{\varphi(n)}$, so $ed = 1 + k\varphi(n)$ for some integer $k$. Then

$$C^d = (M^e)^d = M^{ed} = M^{1 + k\varphi(n)} = M \cdot \big(M^{\varphi(n)}\big)^k \equiv M \cdot 1^k = M \pmod n,$$

using Euler's theorem (and Fermat + the Chinese Remainder Theorem to cover the rare $\gcd(M,n) > 1$ case). The round-trip is *exact*, not approximate.

Worked example — the classic small instance

Take $p = 61$, $q = 53$. Then $n = 3233$ and $\varphi(n) = 60 \cdot 52 = 3120$. Choose $e = 17$ (it is coprime to $3120$); EXTENDED-EUCLID gives $d = 17^{-1} \bmod 3120 = 2753$. To send $M = 65$:

- Encrypt: $C = 65^{17} \bmod 3233 = 2790$. - Decrypt: $M = 2790^{2753} \bmod 3233 = 65$. ✓

Signatures, and why it is secure

Running the keys in the other order gives a digital signature: the owner signs with the *secret* key, $\sigma = M^d \bmod n$, and anyone verifies with the *public* key by checking $M = \sigma^e \bmod n$. Only the secret-key holder could have produced $\sigma$.

Security rests on the hardness of factoring: recovering $d$ requires $\varphi(n) = (p-1)(q-1)$, which requires the factorization $n = pq$. No polynomial-time factoring algorithm is known — the best (general number field sieve) is sub-exponential — so for 2048-bit $n$ this is infeasible. (Note: finding the *primes* $p,q$ in step 1 is easy — primality testing, e.g. Miller–Rabin, is fast; it is *un-multiplying* $n$ that is hard. That gap is the whole game.)