RSA: The Mathematics of Large Primes

Every time your browser shows a padlock, RSA is likely involved. Published in 1977 by Rivest, Shamir, and Adleman, RSA was the first practical public-key cryptosystem. Its security reduces to a simple question: given n = p × q for two enormous primes, how hard is it to find p and q?

1. The Public-Key Idea

Before RSA, secure communication required a pre-shared secret key — a physical meeting to exchange a codebook. Public-key cryptography eliminates this: everyone can publish a public key E. Anyone uses E to lock a message. Only the holder of the matching private key D can unlock it. The lock is one-way: easy to apply, computationally infeasible to reverse.

RSA achieves this with the integer factorisation trapdoor: multiplying two large primes is instant, but factoring their product is believed to require exponential time in the number of digits.

2. Modular Arithmetic

RSA works in modular arithmetic: all computation is done "mod n" — only the remainder after dividing by n matters. This "clock arithmetic" creates finite cyclic groups where exponentiation is easy and logarithm is hard.

a mod n = remainder of a \div n Examples: 17 mod 5 = 2, 100 mod 7 = 2 Properties: (a \times b) mod n = ((a mod n) \times (b mod n)) mod n This means: modular exponentiation can be done efficiently via repeated squaring

Modular inverse: For an integer e, its inverse d satisfies e × d ≡ 1 (mod φ(n)). Finding d is done using the Extended Euclidean Algorithm in O(log²n) — fast.

3. Euler's Theorem

The heart of RSA is Euler's theorem: for any integer m coprime to n:

m^φ(n) \equiv 1 (mod n)

Where φ(n) is Euler's totient function — the number of integers from 1 to n that are coprime to n. For n = p × q (two distinct primes):

φ(p \times q) = (p - 1)(q - 1)

This is the key insight: to compute φ(n), you must know the prime factors of n. If an attacker can't factor n, they can't compute φ(n), and therefore can't find the private key d from the public key e.

4. RSA Key Generation

Choose two large distinct primes p and q (2048-bit RSA: each prime is ~617 decimal digits). Use probabilistic primality tests (Miller-Rabin).

Compute n = p × q and φ(n) = (p−1)(q−1). The modulus n is public; φ(n) is kept secret.

Choose e — a public exponent coprime to φ(n). Typically e = 65537 (= 2¹⁶ + 1). This value has efficient exponentiation and is known safe.

Compute d = e⁻¹ mod φ(n) using the Extended Euclidean Algorithm. This is the private key.

Public key: (n, e). Distribute freely. Private key: (n, d). Keep secret. Destroy p, q, φ(n).

5. Encryption & Decryption

To encrypt plaintext m (where m < n) with public key (n, e):

c = m^e mod n (ciphertext)

To decrypt ciphertext c with private key (n, d):

m = c^d mod n = (m^e)^d mod n = m^(ed) mod n Since ed \equiv 1 (mod φ(n)), we have ed = kφ(n) + 1 for some integer k. By Euler's theorem: m^(ed) \equiv m^1 \equiv m (mod n) ✓

Toy example: p=61, q=53, n=3233, φ(n)=3120, e=17, d=2753.
Encrypt m=65: c = 65¹⁷ mod 3233 = 2790.
Decrypt: 2790²⁷⁵³ mod 3233 = 65. ✓

6. Why It's Secure

RSA security depends on the integer factorisation problem and the RSA problem (recovering m from c without d). Currently, no polynomial-time classical algorithm is known for either.

Best known attack: General Number Field Sieve (GNFS). For a 2048-bit RSA key (617-digit modulus), the estimated time on the world's fastest computer is ~10¹⁸ years — much longer than the age of the universe.

Quantum computers: Shor's algorithm runs in polynomial time on a quantum computer and would break RSA. A quantum computer with ~4000+ logical qubits (millions of physical qubits) could crack RSA-2048. Current quantum computers have ~1000 noisy physical qubits. Post-quantum cryptographic standards (NIST 2024: ML-KEM, ML-DSA based on lattice problems) are being deployed now as preparation.

Practical RSA requires padding schemes (OAEP) to prevent known attacks. Textbook RSA (as shown here) is deterministic and susceptible to chosen-plaintext attacks — never use it in production.

7. Modern RSA & Alternatives

RSA-2048 is the current standard for key exchange (e.g., TLS certificate keys). RSA-4096 provides a 30+ year security margin. Key sizes below 2048 are deprecated.

Elliptic Curve Cryptography (ECC) provides equivalent security with much shorter keys: ECC-256 ≈ RSA-3072 in security, with faster computation. TLS 1.3 prefers ECDH (Elliptic Curve Diffie-Hellman) for key exchange.

RSA is still used extensively for digital signatures and certificate authorities.
RSA key exchange (RSA-KEM) provides no forward secrecy; ECDHE does.
Post-quantum: NIST standardised ML-KEM (CRYSTALS-Kyber) and ML-DSA (CRYSTALS-Dilithium) in 2024 as lattice-based alternatives resistant to quantum attacks.