Capstone: public-key cryptography with RSA and Diffie–Hellman

For most of history, secret communication required a shared secret. Julius Caesar shifted each letter three places along the alphabet, encryption by \(x \mapsto x + 3 \pmod{26}\), and his correspondents had to know the shift. Every cipher until the 1970s, from Renaissance codebooks to the Enigma machine to the government ciphers of the Cold War, had the same weakness: before two parties could talk securely, they had to meet or trust a courier to exchange a key. With millions of strangers wanting to buy things from one another over a network, that is impossible. In 1976 Whitfield Diffie and Martin Hellman proposed a way around it, and in 1977 Ron Rivest, Adi Shamir and Leonard Adleman found the first practical public-key cipher. (It later emerged that James Ellis, Clifford Cocks and Malcolm Williamson had discovered equivalent ideas a few years earlier at the British signals agency GCHQ, where the work stayed classified until 1997.) Both systems are pure number theory: Fermat's and Euler's theorems, primitive roots, the Euclidean algorithm and fast primality testing. This capstone puts the course together.

Classical ciphers as modular arithmetic

Number the letters A = 0, …, Z = 25. A shift cipher encrypts \(x \mapsto x + k \bmod 26\), and there are only 26 keys, so it is broken by trying them all. An affine cipher \(x \mapsto ax + b \bmod 26\) requires \(\gcd(a, 26) = 1\) so that decryption \(x \mapsto a^{-1}(x - b)\) is possible, which by lesson 4 leaves \(\varphi(26) \cdot 26 = 312\) keys, still trivial to search. More seriously, any cipher that replaces each letter by a fixed letter is broken by frequency analysis, described by the ninth-century scholar al-Kindi: E is the most common letter in English, so the most common symbol in a long ciphertext is probably E. These systems are symmetric: the same key encrypts and decrypts, so whoever can read messages can also forge them, and the key must be shared in advance.

The idea of public-key cryptography is to split the key in two. A public key, which anyone may know, is used to encrypt; a private key, known only to its owner, is used to decrypt. For this to work, deriving the private key from the public one must be infeasible. Number theory supplies functions that are easy to compute but hard to invert: modular exponentiation, whose inverse is the discrete logarithm, and multiplication of primes, whose inverse is factoring.

Diffie–Hellman key agreement

Diffie and Hellman solved the key distribution problem directly: two people who have never met can agree on a shared secret while an eavesdropper hears every word. The protocol uses a large prime \(p\) and a primitive root \(g\) modulo \(p\), both public.

• Alice picks a secret random exponent \(a\) and sends \(A = g^a \bmod p\).

• Bob picks a secret random exponent \(b\) and sends \(B = g^b \bmod p\).

• Alice computes \(B^a = g^{ab}\) and Bob computes \(A^b = g^{ab}\). Both now hold the same number \(K = g^{ab} \bmod p\), which they use as the key for a fast symmetric cipher.

The figure runs the protocol with toy numbers. An eavesdropper, Eve, sees \(p = 23\), \(g = 5\), \(A = 8\) and \(B = 19\). To find the key she needs \(g^{ab}\), and the obvious way is to recover \(a\) from \(g^a = 8\), a discrete logarithm. Modulo 23 she can simply try all 22 exponents. With a prime of 2048 bits, the best known algorithms would take far longer than the age of the universe, while Alice and Bob each do a few thousand multiplications. No one has proved that the Diffie–Hellman problem is hard, but decades of effort have produced no fast method.

Two refinements matter in practice. First, \(p - 1\) should have a large prime factor, typically \(p = 2q + 1\) with \(q\) prime, because the Pohlig–Hellman algorithm computes discrete logarithms quickly when \(p - 1\) has only small prime factors: the Chinese remainder theorem splits the problem into small pieces. Second, the protocol as described protects against eavesdropping but not against an active attacker who intercepts the messages and runs separate exchanges with each side, a man-in-the-middle attack. Real systems therefore combine key agreement with digital signatures, so that each side can verify who sent the public values. Today's web connections usually run the same protocol in the group of points on an elliptic curve, where shorter keys give the same security.

RSA: generating keys

RSA goes further than key agreement: anyone can encrypt a message that only the key's owner can read. Bob creates his keys as follows.

• Choose two large random primes \(p\) and \(q\), using a primality test such as Miller–Rabin from lesson 11. Today each has about 1024 bits, roughly 310 digits.

• Compute \(n = pq\) and \(\varphi(n) = (p - 1)(q - 1)\).

• Choose an exponent \(e\) with \(\gcd(e, \varphi(n)) = 1\). The common choice is \(e = 65537 = 2^{16} + 1\), a prime with only two 1s in binary, so encryption is fast.

• Compute \(d \equiv e^{-1} \pmod{\varphi(n)}\) with the extended Euclidean algorithm of lesson 2.

• Publish the public key \((n, e)\). Keep \(d\) private, and discard or protect \(p\), \(q\) and \(\varphi(n)\).

To send a message, Alice encodes it as a number \(m\) with \(0 \le m < n\) and sends \(c = m^e \bmod n\). Bob decrypts by computing \(c^d \bmod n\).

The figure shows the classic textbook example. With \(p = 61\), \(q = 53\), \(n = 3233\) and \(\varphi(n) = 60 \cdot 52 = 3120\), the exponent \(e = 17\) is coprime to 3120, and the extended Euclidean algorithm gives \(d = 2753\), since \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\). The message \(m = 65\) encrypts to \(65^{17} \bmod 3233 = 2790\), and \(2790^{2753} \bmod 3233 = 65\).

Why decryption works

Theorem. If \(n = pq\) with \(p \ne q\) prime and \(ed \equiv 1 \pmod{\varphi(n)}\), then \(m^{ed} \equiv m \pmod n\) for every integer \(m\).

Proof. Write \(ed = 1 + k(p - 1)(q - 1)\) with \(k \ge 0\). We show \(m^{ed} \equiv m\) modulo \(p\); the same argument works modulo \(q\), and then the Chinese remainder theorem, or the fact that the coprime numbers \(p\) and \(q\) both divide \(m^{ed} - m\), gives the result modulo \(n\). If \(p \mid m\), both sides are \(\equiv 0 \pmod p\). Otherwise Fermat's theorem gives \[m^{ed} = m \cdot \big(m^{p-1}\big)^{k(q-1)} \equiv m \cdot 1 = m \pmod p.\]

When \(\gcd(m, n) = 1\) this is just Euler's theorem, but the proof shows decryption works for every \(m\), including the rare messages sharing a factor with \(n\). (Such a message would reveal a factor of \(n\) through \(\gcd(m, n)\), but with 300-digit primes the chance of hitting one at random is negligible.)

Signatures

RSA also provides digital signatures, which solve the authentication problem. To sign a message \(m\), Bob computes \(s = m^d \bmod n\) with his private key. Anyone can verify the signature with the public key by checking that \(s^e \equiv m \pmod n\). Only someone who knows \(d\) could have produced \(s\), and the same theorem guarantees that the check succeeds for a genuine signature. In practice Bob signs a short cryptographic hash of the message rather than the message itself. Signatures are how a browser checks that a website's public key really belongs to that website, and how a phone checks that a software update really comes from its manufacturer.

Why RSA is believed secure

An attacker knows \(n\), \(e\) and \(c\). If she could factor \(n\), she could compute \(\varphi(n)\) and then \(d\) exactly as Bob did. Conversely, knowing \(\varphi(n)\) gives the factors: \(p + q = n - \varphi(n) + 1\), and \(p, q\) are the roots of \(x^2 - (p + q)x + n\). It is also known that knowing \(d\) allows \(n\) to be factored efficiently. So recovering the private key is exactly as hard as factoring. Whether one could decrypt messages without the private key, by taking \(e\)-th roots modulo \(n\) some other way, is not known, but no method is known that avoids factoring.

The sizes come from lesson 11. Factoring a 250-digit number took about 2,700 core-years with the number field sieve in 2020; the 617-digit moduli now standard are believed out of reach for decades, while key generation needs only a few Miller–Rabin tests on random numbers of the right size, roughly one in every 355 odd numbers near \(2^{1024}\) being prime, by the prime number theorem.

Textbook RSA as described here is not safe to use directly, and the pitfalls are themselves number theory. It is deterministic: encrypting the same message always gives the same ciphertext, so an attacker can test guesses. With a small exponent such as \(e = 3\) and a small message, \(m^3 < n\) and the ciphertext is an ordinary cube whose real cube root is the message. If the same message is sent to three people with exponent 3 and different moduli, the Chinese remainder theorem recovers \(m^3\) modulo the product of the moduli, and hence \(m\) (Håstad's broadcast attack). And if two public keys accidentally share a prime, a single gcd computation factors both, which a 2012 survey of keys found on the Internet showed happens surprisingly often with poor random number generators. Real systems therefore pad messages with random bytes in a carefully specified format and generate primes with good randomness.

Speeding up decryption

Bob, who knows \(p\) and \(q\), can decrypt about four times faster using the Chinese remainder theorem. He computes \(m_p = c^{d \bmod (p-1)} \bmod p\) and \(m_q = c^{d \bmod (q-1)} \bmod q\), using Fermat's theorem to shrink the exponents, and then combines \(m_p\) and \(m_q\) into \(m \bmod n\). Each half works with numbers half as long and exponents half as long, so each exponentiation is about eight times cheaper, and two of them make four.

The future

In 1994 Peter Shor showed that a large quantum computer could factor integers and compute discrete logarithms in polynomial time, which would break RSA, Diffie–Hellman and their elliptic curve versions. Machines of the required size do not yet exist, but because encrypted data recorded today might be decrypted later, governments and companies have begun moving to post-quantum cryptography. In 2024 the United States National Institute of Standards and Technology published its first post-quantum standards, most of them based on lattices, where the hard problem is finding short vectors in high-dimensional grids of points. Number theory remains at the heart of the matter: lattices, polynomial rings modulo primes and elliptic curves are the materials of modern cryptography, and the subject Hardy praised for its uselessness now guards the world's communications.

RSA and Diffie–Hellman by computer

The program reproduces the toy examples in the figures, generates a 1024-bit RSA key with Miller–Rabin, encrypts, decrypts and signs a text message, compares ordinary and CRT decryption, recovers the factors from \(\varphi(n)\), and runs Diffie–Hellman with a 128-bit safe prime.

import math, random

def is_probable_prime(n, rounds=40):
    if n < 4:
        return n in (2, 3)
    if n % 2 == 0:
        return False
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2; s += 1
    for _ in range(rounds):
        x = pow(random.randrange(2, n - 1), d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True

def random_prime(bits):
    while True:
        c = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_probable_prime(c):
            return c

# toy example from the figure
p, q, e = 61, 53, 17
n, phi = p * q, (p - 1) * (q - 1)
d = pow(e, -1, phi)
c = pow(65, e, n)
print("toy RSA: n =", n, " d =", d, " c =", c, " decrypted:", pow(c, d, n))

random.seed(2026)
p, q = random_prime(512), random_prime(512)
n, phi, e = p * q, (p - 1) * (q - 1), 65537
assert math.gcd(e, phi) == 1
d = pow(e, -1, phi)
print("modulus bits:", n.bit_length(), " digits:", len(str(n)))

msg = "Number theory guards the internet."
m = int.from_bytes(msg.encode(), "big")
c = pow(m, e, n)
back = pow(c, d, n)
print("ciphertext begins:", str(c)[:30] + "...")
print("decrypted:", back.to_bytes((back.bit_length() + 7) // 8, "big").decode())

sig = pow(m, d, n)
print("signature valid:", pow(sig, e, n) == m, " forged signature valid:", pow(sig + 1, e, n) == m)

dp, dq, qinv = d % (p - 1), d % (q - 1), pow(q, -1, p)
mp, mq = pow(c, dp, p), pow(c, dq, q)
m2 = mq + q * ((mp - mq) * qinv % p)
print("CRT decryption gives the same message:", m2 == m, " exponent bits:", d.bit_length(), "vs", dp.bit_length(), "and", dq.bit_length())

s = n - phi + 1
r = math.isqrt(s * s - 4 * n)
print("factors recovered from phi(n):", {(s - r) // 2, (s + r) // 2} == {p, q})

P, g = 23, 5
a, b = 6, 15
print("toy Diffie-Hellman: A =", pow(g, a, P), " B =", pow(g, b, P), " keys:", pow(pow(g, b, P), a, P), pow(pow(g, a, P), b, P))
while True:
    qq = random_prime(127)
    P = 2 * qq + 1
    if is_probable_prime(P):
        break
g = next(h for h in range(2, 100) if pow(h, 2, P) != 1 and pow(h, qq, P) != 1)
a, b = random.randrange(2, P - 1), random.randrange(2, P - 1)
A, B = pow(g, a, P), pow(g, b, P)
print("safe prime bits:", P.bit_length(), " generator:", g, " shared keys agree:", pow(B, a, P) == pow(A, b, P))

toy RSA: n = 3233  d = 2753  c = 2790  decrypted: 65
modulus bits: 1023  digits: 308
ciphertext begins: 508196163044069336156803386551...
decrypted: Number theory guards the internet.
signature valid: True  forged signature valid: False
CRT decryption gives the same message: True  exponent bits: 1021 vs 510 and 511
factors recovered from phi(n): True
toy Diffie-Hellman: A = 8  B = 19  keys: 2 2
safe prime bits: 128  generator: 2  shared keys agree: True

A modulus of about 1024 bits (here 1023 bits, 308 digits) takes a fraction of a second to generate, and the text survives the round trip. The CRT decryption gives the same message using exponents half as long, modulo numbers half as long, the factors fall out of \(\varphi(n)\) exactly as claimed, and a generator modulo the safe prime \(P = 2q + 1\) is found by checking only the two conditions \(g^2 \ne 1\) and \(g^q \ne 1\), the primitive root test of lesson 8 for \(P - 1 = 2q\). Real deployments use 2048-bit or larger moduli, padding schemes and vetted libraries, never code written from scratch, but the arithmetic inside them is exactly this.