The RSA Cryptosystem — Mathematics Knowledge System

Overview

RSA, named for its inventors Ron Rivest, Adi Shamir, and Leonard Adleman (1977), was the first practical public-key cryptosystem: it lets anyone encrypt a message using a public key while only the holder of a matching private key can decrypt it. Its security rests on a number-theoretic asymmetry — multiplying two large primes p and q together is fast, but factoring the product n = pq back into p and q is believed to be computationally infeasible for large enough primes. Key generation picks an encryption exponent e coprime to φ(n) = (p−1)(q−1) and computes the decryption exponent d as e's inverse modulo φ(n); encryption is c ≡ mᵉ (mod n) and decryption is m ≡ cᵈ (mod n). Correctness of decryption — that (mᵉ)ᵈ ≡ m (mod n) — follows directly from Euler's theorem (the generalization of Fermat's little theorem to composite moduli), since ed ≡ 1 (mod φ(n)) makes mᵉᵈ = m·m^{k·φ(n)} ≡ m·1ᵏ = m (mod n) whenever gcd(m,n)=1.

Intuition

Think of n = pq as a padlock that's trivial to build (multiply two primes) but effectively impossible to pick apart (factor) once it's large — that asymmetry is what makes n safe to publish. Raising to the e-th power mod n scrambles a message in a way that looks random without knowing φ(n); but because ed ≡ 1 (mod φ(n)), raising the scrambled value to the d-th power exactly 'undoes' e turns of the scrambling, landing back on m — the same way Fermat's little theorem lets aᵖ⁻¹ collapse to 1, Euler's theorem lets m^{φ(n)} collapse to 1 mod n (when gcd(m,n)=1), and ed = 1 + k·φ(n) is engineered precisely so this collapse cancels out every extra 'wrap-around' from the encryption step.

Formal Definition

Definition

Key generation: choose distinct large primes p, q; compute n = pq and φ(n) = (p−1)(q−1); choose e with gcd(e, φ(n)) = 1; compute d ≡ e⁻¹ (mod φ(n)). The public key is (n, e), the private key is (n, d).

n = pq, \qquad \varphi(n) = (p-1)(q-1)

Modulus and totient

e \cdot d \equiv 1 \pmod{\varphi(n)}, \qquad \gcd(e, \varphi(n)) = 1

Public/private exponent relationship

c \equiv m^{e} \pmod n \quad \text{(encryption)}, \qquad m \equiv c^{d} \pmod n \quad \text{(decryption)}

Encryption and decryption

Worked Examples

Compute the modulus n and totient φ(n).
$n = 61 \cdot 53 = 3233, \qquad \varphi(n) = 60 \cdot 52 = 3120$
Check e = 17 is coprime to φ(n) = 3120 (gcd(17, 3120) = 1 since 17 is prime and does not divide 3120).
$\gcd(17, 3120) = 1$
Find d ≡ 17⁻¹ (mod 3120) via the extended Euclidean algorithm.
$d = 2753, \qquad 17 \cdot 2753 \equiv 1 \pmod{3120}$
Encrypt m = 65: compute c ≡ 65^17 (mod 3233).
$c \equiv 65^{17} \equiv 2790 \pmod{3233}$
Decrypt c = 2790: compute c^d mod n and confirm it recovers m.
$2790^{2753} \equiv 65 \pmod{3233}$

Answer: Public key (n,e) = (3233, 17), private key d = 2753; m=65 encrypts to c=2790, which decrypts back to 65.

Practice Problems

Difficulty 3/10

Given p = 61, q = 53, compute n and φ(n).

Difficulty 7/10

Verify that e = 17 and d = 2753 satisfy ed ≡ 1 (mod 3120).

Difficulty 6/10

Why would using p = 61 and q = 53 be catastrophically insecure in a real RSA deployment, even though the arithmetic above is correct?

Quiz

Summary

RSA key generation: pick primes p, q; n = pq, φ(n) = (p−1)(q−1); choose e coprime to φ(n); compute d ≡ e⁻¹ (mod φ(n)).
Encryption c ≡ mᵉ (mod n); decryption m ≡ cᵈ (mod n); correctness follows from Euler's theorem since ed ≡ 1 (mod φ(n)).
Security depends entirely on n = pq being hard to factor — the classic textbook example (p=61, q=53, n=3233) is intentionally tiny and insecure, illustrating the mechanics only.

References

WebsiteWikipedia — RSA (cryptosystem)