Cryptography

When a student in Nairobi pays for lunch by phone, a doctor in Chennai opens a patient record, or a family in São Paulo video-calls relatives in Lisbon, their messages cross networks that anyone might be watching. The messages are encrypted. But encryption needs a key, and the two ends must share it. How did they agree on a key, if every message they ever exchanged could have been overheard?

For most of history this key-distribution problem was solved by couriers, codebooks and trusted meetings, and it seemed obvious that there was no other way: to share a secret, you must first share a secret. In 1976 Whitfield Diffie and Martin Hellman showed otherwise, and in 1977 Ron Rivest, Adi Shamir and Leonard Adleman found a way to let anyone encrypt a message that only one person can read. (It later emerged that James Ellis, Clifford Cocks and Malcolm Williamson had found the same ideas at the British signals agency GCHQ a few years earlier, in secret.) Both inventions are applications of congruences, and both rest on a striking asymmetry: some arithmetic is easy to do and, as far as anyone knows, very hard to undo.

Multiplying two 300-digit primes takes a computer a fraction of a millisecond. Recovering the two primes from their product is, with the best known methods, far beyond the reach of every computer on Earth. Raising a number to a 600-digit power modulo a prime is quick; recovering the exponent from the result — the discrete logarithm — appears to be just as hopeless. Functions like these, easy to compute and (apparently) hard to invert, are the raw material of public-key cryptography.

The mathematics replaces paint by a commutative operation: exponentiation. Since $(g^a)^b = g^{ab} = (g^b)^a$, the square below commutes, and the two parties travel round it in opposite directions.

The oldest ciphers are symmetric. Caesar's cipher shifts each letter: with letters numbered $0$ to $25$, $E_k(x) = x + k \bmod 26$. The affine cipher $E(x) = ax + b \bmod 26$ is decryptable exactly when $a$ is invertible modulo $26$, i.e. $\gcd(a, 26) = 1$, and then $D(y) = a^{-1}(y - b)$. Both are broken by frequency analysis — in any language some letters are much more common than others, and a substitution cipher preserves those frequencies — a method described by the Arab scholar al-Kindī in the ninth century.

Is there an unbreakable cipher? Yes, provided the key is as long as the message.

Shannon also proved the converse: perfect secrecy requires at least as many possible keys as messages. The one-time pad is therefore perfect but impractical — the key-distribution problem returns in full — and if a pad is used twice, $c_1 \oplus c_2 = m_1 \oplus m_2$ leaks the combination of the two messages. Modern symmetric ciphers (such as AES) use short keys and are not perfectly secret; their security is a well-tested conjecture, not a theorem.

RSA and Diffie–Hellman compute $b^e \bmod n$ with $e$ hundreds of digits long. Multiplying $b$ by itself $e - 1$ times would take longer than the age of the universe. Instead we use the binary expansion of $e$.

For a 2048-bit exponent that is at most about $4\,100$ multiplications of numbers below $n$, and every intermediate number is below $n^2$ — never the astronomically large $b^e$. For $e = 65537 = 2^{16} + 1$, a popular choice of public exponent, it takes $16$ squarings and a couple of multiplications.

Notice that the proof handles messages $m$ that share a factor with $n$ as well — a case that a proof using Euler's theorem alone ($m^{\varphi(n)} \equiv 1$ for $\gcd(m, n) = 1$) would miss. Since $\varphi(pq) = (p - 1)(q - 1)$, the condition is the textbook $ed \equiv 1 \pmod{\varphi(n)}$.

Why is RSA believed to be secure? To decrypt, an eavesdropper who knows $(n, e)$ wants $d$, and $d$ is easy to compute from $(p - 1)(q - 1)$. But knowing $\varphi(n) = (p - 1)(q - 1)$ is as good as knowing the factors: $p + q = n - \varphi(n) + 1$ and $pq = n$, so $p$ and $q$ are the roots of $x^2 - (n - \varphi(n) + 1)x + n$. Computing $d$ from $(n, e)$ is likewise known to be as hard as factoring $n$. Whether decrypting RSA without finding $d$ is as hard as factoring is an open question, and whether factoring is hard at all is unproved.

Signatures. Running RSA backwards gives a digital signature: the owner of $d$ signs $m$ by $s = m^d \bmod n$, and anyone can check $s^e \equiv m \pmod n$ with the public key. Theorem 3, with the roles of $e$ and $d$ exchanged, shows that genuine signatures verify. In practice one signs a cryptographic hash of $m$, not $m$ itself — otherwise anyone can pick a random $s$ and claim it is the signature of $m = s^e \bmod n$.

Textbook RSA is not safe as it stands. It is deterministic: an eavesdropper who suspects that $c$ encrypts "yes" or "no" simply encrypts both and compares. It is malleable: $E(m_1)E(m_2) \equiv E(m_1 m_2) \pmod n$, so ciphertexts can be manipulated without being read. Real systems first pad the message with random bits in a carefully designed way (for example OAEP) before applying $m \mapsto m^e$.

Why a generator? If $g$ has small order $r$ — that is, $g^r = 1$ for a small $r$ — then $g^a$ takes only $r$ values and the secret can be found by trying them. By Lagrange's theorem the order of any element divides the order $p - 1$ of the group, and $g$ is a generator exactly when $g^{(p-1)/\ell} \neq 1$ for every prime $\ell \mid p - 1$.

Attacks. Trying every exponent takes up to $p - 1$ steps. Daniel Shanks's baby-step giant-step algorithm writes the unknown $x = im + j$ with $m = \lceil \sqrt{p - 1}\, \rceil$, stores the "baby steps" $g^j$ for $0 \le j < m$, and then walks through the "giant steps" $h g^{-im}$ until one of them matches a stored value — at most about $2\sqrt p$ group operations. For $(\Z/p\Z)^\times$ there are faster, subexponential methods (index calculus), which is one reason why classical Diffie–Hellman needs primes of 2048 bits or more.

Authentication. Diffie–Hellman alone is vulnerable to a man in the middle: an attacker who can intercept and replace messages runs one exchange with Ama and another with Bolat, and relays (and reads) everything. The exchange must be authenticated — for example with digital signatures — which is how it is used in practice.

It is worth being exact about the status of each claim in this lesson.

• Proved: the correctness of RSA (Theorem 3) and Diffie–Hellman (Theorem 4); the efficiency of repeated squaring (Theorem 2); the perfect secrecy of the one-time pad (Theorem 1).
• Believed, on extensive evidence: that factoring products of two large random primes, and computing discrete logarithms in well-chosen groups, are infeasible for classical computers. The best known factoring algorithm, the general number field sieve, takes time roughly $\exp\big(c\,(\ln n)^{1/3}(\ln\ln n)^{2/3}\big)$ — faster than any power of $n$ but slower than any power of $\ln n$. The largest RSA challenge number factored so far, RSA-250 (829 bits), was factored in 2020 with thousands of computer-years of effort.
• Unknown: whether one-way functions exist at all. If they do, then $\mathrm{P} \neq \mathrm{NP}$; so a proof that RSA is secure in this sense would settle one of the great open problems of mathematics (see complexity theory).
• Known to change everything: Peter Shor proved in 1994 that a sufficiently large, fault-tolerant quantum computer could factor integers and compute discrete logarithms in polynomial time. No existing quantum computer is anywhere near large enough, but because of this threat, standards bodies have begun replacing RSA and Diffie–Hellman with post-quantum systems based on other problems, such as hard problems about lattices; the US National Institute of Standards and Technology published its first such standards in 2024.

Lean can prove that cryptographic algorithms are correct; it cannot prove them secure, because their security is an unproved conjecture. Everything below is about correctness.

Fast powering (Theorem 2). The recursive algorithm, and the theorem that it computes $b^e \bmod n$, by strong induction on $e$ exactly as in the human proof. Lean accepts the recursion only after checking that $\lfloor e/2 \rfloor < e$ for $e > 0$, so termination is part of the proof. (The multiplication count is not formalised.)

/-- **Modular exponentiation by repeated squaring.** To compute `bᵉ mod n`, compute
`h = b^⌊e/2⌋ mod n` recursively, square it, and multiply by `b` once more if `e` is odd. Each
call halves `e`, so about `log₂ e` calls suffice, and every intermediate number is below `n²`
(or `n² · b`) — never the astronomically large `bᵉ`. -/
def powMod (b e n : ℕ) : ℕ :=
  if e = 0 then 1 % n
  else
    let h := powMod b (e / 2) n
    if e % 2 = 0 then h * h % n else h * h % n * b % n
termination_by e
decreasing_by omega

/-- **Repeated squaring computes the right number:** `powMod b e n = bᵉ mod n`. Strong induction
on `e`, using `e = 2⌊e/2⌋` or `e = 2⌊e/2⌋ + 1` and the fact that reducing mod `n` before
multiplying does not change the result mod `n` (`Nat.mul_mod`). -/
theorem powMod_eq (b e n : ℕ) : powMod b e n = b ^ e % n := by
  induction e using Nat.strong_induction_on with
  | _ e ih =>
    rw [powMod]
    split_ifs with h0 h2
    · simp [h0]
    · have he : e = e / 2 + e / 2 := by omega
      have ih' := ih (e / 2) (by omega)
      simp only [ih']
      conv_rhs => rw [he, pow_add, Nat.mul_mod]
    · have he : e = (e / 2 + e / 2) + 1 := by omega
      have ih' := ih (e / 2) (by omega)
      simp only [ih']
      conv_rhs => rw [he, pow_succ, pow_add, Nat.mul_mod, Nat.mul_mod (b ^ (e / 2))]
      simp [Nat.mul_mod]

RSA (Theorem 3). The key lemma handles one prime at a time, splitting on whether $p \mid m$ and using Mathlib's Fermat (ZMod.pow_card_sub_one_eq_one); the main theorem writes $ed = t(p - 1)(q - 1) + 1$ and combines the two primes with the Chinese remainder theorem (Nat.modEq_and_modEq_iff_modEq_mul). Note that the theorem holds for every natural number $m$, with no coprimality hypothesis. Then $\varphi(pq) = (p - 1)(q - 1)$ from the library, the toy example from the RSA paper checked by the kernel, and malleability.

/-- **The key lemma for RSA:** for a prime `p` and *every* natural number `m` (whether or not
`p` divides it), `m^(k(p - 1) + 1) ≡ m (mod p)`. If `p ∣ m` both sides are `0 (mod p)`; otherwise
Fermat gives `m^(p-1) ≡ 1`, so `m^(k(p-1)+1) = (m^(p-1))^k · m ≡ m`. -/
theorem pow_mul_sub_one_succ (p : ℕ) [Fact p.Prime] (k m : ℕ) :
    m ^ (k * (p - 1) + 1) ≡ m [MOD p] := by
  rw [← ZMod.natCast_eq_natCast_iff]
  push_cast
  by_cases hm : (m : ZMod p) = 0
  · rw [hm, zero_pow (Nat.succ_ne_zero _)]
  · rw [pow_succ, mul_comm k, pow_mul, ZMod.pow_card_sub_one_eq_one hm, one_pow, one_mul]

/-- **RSA decryption works.** Let `p ≠ q` be primes, `n = pq`, and `ed ≡ 1 (mod (p-1)(q-1))`.
Then `(mᵉ)ᵈ ≡ m (mod n)` for **every** natural number `m`. Write `ed = t(p-1)(q-1) + 1`; the key
lemma gives `m^(ed) ≡ m` modulo `p` and modulo `q` separately, and because `p` and `q` are
coprime the two congruences combine to one modulo `pq` (the Chinese remainder theorem, Mathlib's
`Nat.modEq_and_modEq_iff_modEq_mul`). -/
theorem rsa_correct {p q e d : ℕ} (hp : p.Prime) (hq : q.Prime) (hpq : p ≠ q)
    (hed : e * d ≡ 1 [MOD (p - 1) * (q - 1)]) (m : ℕ) : (m ^ e) ^ d ≡ m [MOD p * q] := by
  have : Fact p.Prime := ⟨hp⟩
  have : Fact q.Prime := ⟨hq⟩
  have hp2 := hp.two_le
  have hq2 := hq.two_le
  -- `(p - 1)(q - 1) > 1`, so `ed` leaves remainder `1`.
  have hφ : 1 < (p - 1) * (q - 1) := by
    rcases Nat.lt_or_ge 2 p with h | h
    · calc 1 < 2 * 1 := by norm_num
        _ ≤ (p - 1) * (q - 1) := Nat.mul_le_mul (by omega) (by omega)
    · have hq3 : 3 ≤ q := by omega
      calc 1 < 1 * 2 := by norm_num
        _ ≤ (p - 1) * (q - 1) := Nat.mul_le_mul (by omega) (by omega)
  have hrem : e * d % ((p - 1) * (q - 1)) = 1 := by
    rw [hed, Nat.mod_eq_of_lt hφ]
  set t := e * d / ((p - 1) * (q - 1))
  have hsplit : e * d = t * (p - 1) * (q - 1) + 1 := by
    have := Nat.div_add_mod (e * d) ((p - 1) * (q - 1))
    rw [hrem] at this
    rw [← this]
    ring
  rw [← pow_mul, hsplit]
  have hmodp : m ^ (t * (p - 1) * (q - 1) + 1) ≡ m [MOD p] := by
    have h := pow_mul_sub_one_succ p (t * (q - 1)) m
    rwa [show t * (q - 1) * (p - 1) = t * (p - 1) * (q - 1) by ring] at h
  have hmodq : m ^ (t * (p - 1) * (q - 1) + 1) ≡ m [MOD q] :=
    pow_mul_sub_one_succ q (t * (p - 1)) m
  exact (Nat.modEq_and_modEq_iff_modEq_mul ((Nat.coprime_primes hp hq).mpr hpq)).mp
    ⟨hmodp, hmodq⟩

/-- For distinct primes, `φ(pq) = (p - 1)(q - 1)`: Mathlib's `Nat.totient_mul` (φ is
multiplicative on coprime arguments) and `Nat.totient_prime`. So the condition in `rsa_correct`
is the textbook `ed ≡ 1 (mod φ(n))`. -/
theorem totient_pq {p q : ℕ} (hp : p.Prime) (hq : q.Prime) (hpq : p ≠ q) :
    Nat.totient (p * q) = (p - 1) * (q - 1) := by
  rw [Nat.totient_mul ((Nat.coprime_primes hp hq).mpr hpq), Nat.totient_prime hp,
    Nat.totient_prime hq]

/-- **A toy RSA key** (the small example in Rivest, Shamir and Adleman's 1978 paper):
`n = 47 · 59 = 2773`, `φ = 46 · 58 = 2668`, `e = 17`, `d = 157`, since `17 · 157 = 2669`. The
message `1234` encrypts to `1234¹⁷ mod 2773 = 1793`, which decrypts back to `1234`. The kernel
checks the arithmetic (`decide +kernel`). -/
theorem rsa_toy :
    17 * 157 % ((47 - 1) * (59 - 1)) = 1 ∧ 1234 ^ 17 % 2773 = 1793 ∧ 1793 ^ 157 % 2773 = 1234 := by
  decide +kernel

/-- **Textbook RSA is malleable:** the encryptions of `m₁` and `m₂` multiply to the encryption of
`m₁ m₂`, because `m₁ᵉ m₂ᵉ = (m₁ m₂)ᵉ`. An attacker can transform a ciphertext into the
ciphertext of a related message without knowing either — one reason real systems pad messages
with randomness before encrypting. -/
theorem rsa_malleable (m₁ m₂ e n : ℕ) :
    (m₁ ^ e % n) * (m₂ ^ e % n) % n = (m₁ * m₂) ^ e % n := by
  rw [← Nat.mul_mod, mul_pow]

Diffie–Hellman (Theorem 4) and the toy exchange modulo $101$:

/-- **Diffie–Hellman key agreement.** With public `g` and `p`, one party publishes `A = gᵃ mod p`,
the other `B = gᵇ mod p`; then `Bᵃ ≡ Aᵇ (mod p)`, since both are `g^(ab) mod p`. Reducing mod `p`
in between does not matter (`Nat.pow_mod`), and `(gᵇ)ᵃ = g^(ba) = g^(ab) = (gᵃ)ᵇ`. -/
theorem dh_agree (g a b p : ℕ) : (g ^ b % p) ^ a % p = (g ^ a % p) ^ b % p := by
  rw [← Nat.pow_mod, ← Nat.pow_mod, ← pow_mul, ← pow_mul, mul_comm]

/-- A toy exchange in the group of non-zero residues mod `101`, where `2` is a generator. Ama keeps
`a = 37` and publishes `2³⁷ mod 101 = 55`; Bolat keeps `b = 58` and publishes `2⁵⁸ mod 101 = 47`.
Both compute the shared secret `82`. -/
theorem dh_toy :
    2 ^ 37 % 101 = 55 ∧ 2 ^ 58 % 101 = 47 ∧ 47 ^ 37 % 101 = 82 ∧ 55 ^ 58 % 101 = 82 := by
  decide +kernel

The one-time pad. Decryption undoes encryption, and the combinatorial heart of Theorem 1: for each message and ciphertext there is exactly one key. The probabilistic statement itself is not formalised here (Mathlib has the probability theory to do so).

/-- **The one-time pad decrypts correctly:** encrypting with a key by bitwise XOR (`^^^`) and
XOR-ing with the same key again returns the message. Core Lean's `Nat.xor_xor_cancel_right`. -/
theorem otp_decrypt (m k : ℕ) : (m ^^^ k) ^^^ k = m := Nat.xor_xor_cancel_right m k

/-- **Why the one-time pad hides everything:** for any message `m` and any ciphertext `c` there
is exactly one key `k` with `m ^^^ k = c`, namely `k = m ^^^ c`. So if the key is chosen
uniformly at random, every message is equally consistent with the ciphertext — Shannon's perfect
secrecy. -/
theorem otp_unique_key (m k c : ℕ) : m ^^^ k = c ↔ k = m ^^^ c := by
  constructor
  · rintro rfl
    rw [← Nat.xor_assoc, Nat.xor_self, Nat.zero_xor]
  · rintro rfl
    rw [← Nat.xor_assoc, Nat.xor_self, Nat.zero_xor]

The first experiment builds an RSA key from scratch: it finds random primes with the Miller–Rabin test, computes $d$ as an inverse modulo $(p - 1)(q - 1)$, encrypts and decrypts with repeated squaring (counting the multiplications — compare with the naive count), demonstrates the two weaknesses of textbook RSA, and finally breaks its own key, because a 36-bit modulus is factored instantly by trial division. Real moduli have 2048 bits or more.

"""Toy RSA from scratch: key generation, fast powering, and why toy keys break.

The experiment finds two random 18-bit primes with the Miller-Rabin
test (seeded, so the run is reproducible), builds an RSA key with
e = 65537 and d = e^(-1) mod (p - 1)(q - 1), and encrypts and decrypts a few
messages with modular exponentiation by repeated squaring, counting the
multiplications. It then shows two weaknesses of textbook RSA: encryption is
deterministic and multiplicative (malleable), and a modulus this small is
factored at once by trial division, which reveals the private key. Exact
arithmetic throughout; a toy, not a secure implementation, and no evidence
about the security of real RSA.
"""

import math
import random

def pow_mod(b, e, n):
    """Right-to-left repeated squaring; returns (b^e mod n, multiplications)."""
    result, base, mults = 1 % n, b % n, 0
    while e > 0:
        if e & 1:
            result = result * base % n
            mults += 1
        e >>= 1
        if e:
            base = base * base % n
            mults += 1
    return result, mults

def is_probable_prime(n, rng, rounds=20):
    """Miller-Rabin with random bases; never wrong when it says 'composite'."""
    if n < 4:
        return n in (2, 3)
    if n % 2 == 0:
        return False
    d, s = n - 1, 0
    while d % 2 == 0:
        d, s = d // 2, s + 1
    for _ in range(rounds):
        x = pow(rng.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, rng):
    """A random probable prime with exactly the given number of bits."""
    while True:
        n = rng.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_probable_prime(n, rng):
            return n

def make_key(bits, rng, e=65537):
    """Return (n, e, d, p, q) with ed = 1 (mod (p - 1)(q - 1))."""
    while True:
        p, q = random_prime(bits, rng), random_prime(bits, rng)
        phi = (p - 1) * (q - 1)
        if p != q and math.gcd(e, phi) == 1:
            return p * q, e, pow(e, -1, phi), p, q

def smallest_factor(n):
    """Trial division up to sqrt(n)."""
    for f in range(2, math.isqrt(n) + 1):
        if n % f == 0:
            return f
    return n

def main():
    rng = random.Random(2024)
    n, e, d, p, q = make_key(18, rng)
    print(f"p = {p}, q = {q}")
    print(f"n = {n} ({n.bit_length()} bits), e = {e}")
    print(f"d = {d}")
    for m in (42, 31337, 2026):
        c, k = pow_mod(m, e, n)
        back, k2 = pow_mod(c, d, n)
        print(f"m = {m:>5} -> c = {c:>11} -> {back:>5}"
              f" ({k} + {k2} mults)")
    print(f"naive powering would need {e - 1} and {d - 1} multiplications")
    print()
    vote = rng.choice([1, 2])  # 1 = "no", 2 = "yes", sent encrypted
    intercepted = pow(vote, e, n)
    guess = [m for m in (1, 2) if pow(m, e, n) == intercepted]
    print("deterministic: an eavesdropper encrypts both possible votes and")
    print(f"  matches the ciphertext: recovers vote {guess[0]}"
          f" (correct: {guess == [vote]})")
    c1, c2 = pow(6, e, n), pow(7, e, n)
    print("malleable: E(6) * E(7) = E(42) (mod n):",
          c1 * c2 % n == pow(42, e, n))
    print()
    f = smallest_factor(n)
    phi = (f - 1) * (n // f - 1)
    print(f"trial division factors n: {f} * {n // f}")
    print("private key recovered from the factors:", pow(e, -1, phi) == d)
    print()
    print("Epistemic status: exact computations on one seeded toy key. They")
    print("check RSA's correctness on examples (the lesson proves it for all")
    print("messages) and show weaknesses of textbook RSA with tiny keys. They")
    print("say nothing about the security of 2048-bit RSA, which is unproved.")

if __name__ == "__main__":
    main()

The second experiment runs a Diffie–Hellman exchange modulo the prime $2^{31} - 1$ and then attacks discrete logarithms for primes of increasing size. Exhaustive search grows like $p$; baby-step giant-step like $\sqrt p$. Neither comes close to threatening a 2048-bit prime — but the experiment measures two particular algorithms, and says nothing about algorithms nobody has found yet.

"""Diffie-Hellman in a small group, and how the cost of a discrete logarithm grows.

Two parties agree on a key over a public channel using powers of a generator
g modulo a prime p. An eavesdropper sees g^a and g^b and must find a or b: a
discrete logarithm. The experiment runs a toy exchange, then measures, for
primes of increasing size, how many group operations two attacks need:
trying every exponent (about p steps) and Shanks's baby-step giant-step
(about sqrt(p) steps). Step counts are exact for these examples; the trend
illustrates, but does not prove, that discrete logarithms are hard - no
efficient classical algorithm is known, and none is proved impossible.
"""

import math
import random

def is_prime(n):
    """Trial division (fine for the sizes used here)."""
    return n > 1 and all(n % d for d in range(2, math.isqrt(n) + 1))

def prime_factors(n):
    """The distinct prime factors of n."""
    out, f = [], 2
    while f * f <= n:
        if n % f == 0:
            out.append(f)
            while n % f == 0:
                n //= f
        f += 1
    return out + ([n] if n > 1 else [])

def is_generator(g, p):
    """g generates (Z/pZ)^x iff g^((p-1)/r) != 1 for each prime r | p - 1."""
    return all(pow(g, (p - 1) // r, p) != 1 for r in prime_factors(p - 1))

def smallest_generator(p):
    """The least generator of the multiplicative group modulo the prime p."""
    return next(g for g in range(2, p) if is_generator(g, p))

def brute_force_log(g, h, p):
    """Find x with g^x = h (mod p) by trying x = 0, 1, 2, ...; (x, steps)."""
    value = 1
    for x in range(p - 1):
        if value == h:
            return x, x + 1
        value = value * g % p
    return None, p - 1

def bsgs_log(g, h, p):
    """Shanks's baby-step giant-step; returns (x, group operations used)."""
    m = math.isqrt(p - 1) + 1
    table, value = {}, 1
    for j in range(m):  # baby steps g^j
        table.setdefault(value, j)
        value = value * g % p
    giant = pow(g, -m, p)
    gamma = h
    for i in range(m):  # giant steps h * g^(-im)
        if gamma in table:
            return i * m + table[gamma], m + i + 1
        gamma = gamma * giant % p
    return None, 2 * m

def main():
    rng = random.Random(1976)
    p = 2_147_483_647  # the prime 2^31 - 1
    g = smallest_generator(p)
    a, b = rng.randrange(2, p - 1), rng.randrange(2, p - 1)
    A, B = pow(g, a, p), pow(g, b, p)
    print(f"public: p = {p}, g = {g}")
    print(f"Ama sends A = g^a = {A}; Bolat sends B = g^b = {B}")
    print(f"shared key B^a = {pow(B, a, p)}, A^b = {pow(A, b, p)}")
    print()
    print("Recovering a secret exponent x from g^x mod p:")
    print("         p   brute force (this x)   baby-step giant-step (this x)")
    for target in (1_009, 100_003, 10_000_019, 1_000_000_007):
        q = next(n for n in range(target, 2 * target) if is_prime(n))
        g = smallest_generator(q)
        x = rng.randrange(1, q - 1)
        h = pow(g, x, q)
        brute = brute_force_log(g, h, q)[1] if q < 10**6 else None
        found, steps = bsgs_log(g, h, q)
        assert found == x
        shown = f"{brute:>12}" if brute else "   (skipped)"
        print(f"{q:>10}   {shown}           {steps:>10}  (sqrt p = {math.isqrt(q)})")
    print("Brute force needs up to p - 1 steps, baby-step giant-step about")
    print("2 sqrt(p): for a 2048-bit p, about 2^1025 steps.")
    print()
    print("Epistemic status: exact step counts for these primes and seeds. The")
    print("growth (about p, about sqrt p) matches the analysis of these two")
    print("algorithms only. Faster attacks exist (index calculus), and whether")
    print("discrete logarithms are truly hard is an open problem.")

if __name__ == "__main__":
    main()

Square roots appear throughout cryptography for the same reason they appear in the baby-step giant-step attack: among $k$ random values from $N$ possibilities, a repeat becomes likely once $k$ is around $\sqrt N$. With $N = 365$ birthdays, $23$ people suffice for a better-than-even chance of a shared birthday. For a hash function with $N = 2^{256}$ outputs, a collision is expected after about $2^{128}$ tries — so hash outputs must be twice as long as the security level one wants. Try group sizes around $\sqrt{365} \approx 19$.

• Classical ciphers. Substitution and transposition ciphers are ancient. The Arab polymath al-Kindī (ninth century, Baghdad) wrote the earliest known description of frequency analysis, which breaks substitution ciphers. Ibn al-Durayhim and al-Qalqashandī later compiled extensive treatments of ciphers and their solution.
• The twentieth century. Polish mathematicians Marian Rejewski, Jerzy Różycki and Henryk Zygalski broke the German Enigma machine in the 1930s using permutation group theory, and passed their methods to Britain in 1939, where Alan Turing and others at Bletchley Park extended them. Claude Shannon's "Communication Theory of Secrecy Systems" (1949) put cryptography on a mathematical footing and proved the perfect secrecy of the one-time pad.
• Public key. Whitfield Diffie and Martin Hellman published "New Directions in Cryptography" in 1976, building on ideas of Ralph Merkle. Ron Rivest, Adi Shamir and Leonard Adleman found RSA in 1977 (published 1978). At GCHQ, James Ellis had proposed "non-secret encryption" in 1970, Clifford Cocks devised an RSA-like scheme in 1973 and Malcolm Williamson a Diffie–Hellman-like one in 1974; this was declassified in 1997. Taher ElGamal (1985) built encryption and signatures on discrete logarithms, and Neal Koblitz and Victor Miller independently proposed elliptic-curve cryptography in 1985.
• The quantum era. Peter Shor's algorithm (1994) showed that quantum computers would break RSA and Diffie–Hellman; Charles Bennett and Gilles Brassard had proposed quantum key distribution in 1984. In 2024 NIST published standards for post-quantum key establishment and signatures, chosen through an open international competition.

• Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, An Introduction to Mathematical Cryptography (2008; 2nd ed. 2014) — the mathematics of RSA, discrete logarithms, elliptic curves and lattices, at exactly this level.
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography (2007; 3rd ed. 2020) — precise definitions of security and proofs by reduction.
• Neal Koblitz, A Course in Number Theory and Cryptography (1987; 2nd ed. 1994) — number theory developed with cryptography in view.
• Simon Singh, The Code Book (1999) — a readable history from ancient ciphers to public-key cryptography.
• Claude E. Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal (1949) — the founding paper of mathematical cryptography.