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\mathrm{mod}n$ and $M^d\mathrm{mod}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 $\phi (n)$ — the count of integers in $\{1,\dots ,n\}$ that are relatively prime to $n$ — and on Euler's theorem:

$$a^{\phi (n)}\equiv 1(\mathrm{mod}n)\text{for every }a\text{ with }\gcd (a,n)=1.$$

When $n=pq$ is a product of two distinct primes, $\phi (n)=(p-1)(q-1)$. Fermat's little theorem is the special case $a^{p-1}\equiv 1(\mathrm{mod}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 $\phi (n)=(p-1)(q-1)$.
3. Pick a small odd $e$ with $\gcd (e,\phi (n))=1$ (often $e=65537$).
4. Compute $d=e^{-1}\mathrm{mod}\phi (n)$ with EXTENDED-EUCLID (lesson 8.1).
5. Publish $P=(e,n)$; keep $S=(d,n)$ secret. Discard $p$, $q$, $\phi (n)$.

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

Why decryption inverts encryption

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

$$C^d=(M^e{)}^d=M^{ed}=M^{1+k\phi (n)}=M\cdot (M^{\phi (n)}{)}^k\equiv M\cdot 1^k=M(\mathrm{mod}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 $\phi (n)=60\cdot 52=3120$. Choose $e=17$ (it is coprime to $3120$); EXTENDED-EUCLID gives $d=17^{-1}\mathrm{mod}3120=2753$. To send $M=65$:

• Encrypt: $C=65^{17}\mathrm{mod}3233=2790$.
• Decrypt: $M=2790^{2753}\mathrm{mod}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\mathrm{mod}n$, and anyone verifies with the public key by checking $M={\sigma }^e\mathrm{mod}n$. Only the secret-key holder could have produced $\sigma$.

Security rests on the hardness of factoring: recovering $d$ requires $\phi (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.)