24. Cryptographic Mathematics

Level: Expert You'll use this for: actually understanding why RSA, Diffie-Hellman, and elliptic-curve crypto are secure — not just calling openssl.

Modular exponentiation (the core operation of public-key crypto)

Computing a^b mod n for huge b naively (multiply a by itself b times) is infeasible for cryptographic-sized numbers. Fast (modular) exponentiation ("square and multiply") does it in O(log b) multiplications instead of O(b).

def fast_pow_mod(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:                      # if current bit is 1
            result = (result * base) % mod
        exp >>= 1                        # shift to next bit
        base = (base * base) % mod       # square the base
    return result

print(fast_pow_mod(7, 128, 13))          # matches pow(7, 128, 13)
print(pow(7, 128, 13))                    # Python's built-in does this internally

Tracing "square and multiply" by hand for 3^13 mod 7. Write the exponent 13 in binary (1101), then process it one bit at a time from the least significant end, squaring the base every step and folding it into the result only when the current bit is 1:

exp = 13 = 1101 (binary)     result starts at 1, base starts at 3

bit 1 (rightmost, value 1): result = 1×3 mod 7 = 3       base = 3² mod 7 = 2
bit 0            (value 0): result unchanged = 3          base = 2² mod 7 = 4
bit 1            (value 1): result = 3×4 mod 7 = 12 mod 7 = 5    base = 4² mod 7 = 2
bit 1 (leftmost, value 1):  result = 5×2 mod 7 = 10 mod 7 = 3    (last bit, base unused after)

Final result: 3

Only 4 squarings and 3 multiplications were needed for exponent 13 — compare that to naively multiplying 3 by itself 13 times. For a 2048-bit RSA exponent, that's the difference between roughly 2,048 operations and 2^2048 operations — the entire reason this algorithm, not the exponent's size, determines whether modern cryptography is computationally feasible at all.

This is the actual algorithm running every time a server performs an RSA or Diffie-Hellman operation — without it, cryptography using 2048+ bit numbers would be computationally impossible.

RSA, derived end to end

1. Pick two large primes p, q. Compute n = p·q.
2. Compute φ(n) = (p-1)(q-1) (Euler's totient, Ch. 19).
3. Pick public exponent e (commonly 65537) such that gcd(e, φ(n)) = 1.
4. Compute private exponent d = e⁻¹ mod φ(n) (modular inverse, Ch. 19).
5. Public key: (n, e). Private key: (n, d).
6. Encrypt: ciphertext = message^e mod n.
7. Decrypt: message = ciphertext^d mod n.

# Toy RSA with small primes (NEVER do this with small primes in real life)
p, q = 61, 53
n = p * q                       # 3233
phi = (p - 1) * (q - 1)         # 3120
e = 17                          # public exponent, gcd(17, 3120) = 1
d = pow(e, -1, phi)             # private exponent (modular inverse)

message = 65
ciphertext = pow(message, e, n)
decrypted = pow(ciphertext, d, n)
print(ciphertext, decrypted)    # decrypted == 65 again

Why this is secure with large primes: anyone can see the public key (n, e), but recovering the private key d requires knowing φ(n), which requires factoring n back into p and q — and factoring a 2048-bit product of two large primes is (currently) computationally infeasible. RSA's core hardness rests on this number-theoretic assumption (Ch. 19), plus correct padding, parameter choices, and implementation.

Diffie-Hellman key exchange — agreeing on a secret over a public channel

Two parties, Alice and Bob, agree on a public prime p and generator g.

p = 23      # public prime (toy size — real DH uses 2048+ bit primes)
g = 5       # public generator

a = 6       # Alice's private key (secret, never transmitted)
b = 15      # Bob's private key (secret, never transmitted)

A = pow(g, a, p)   # Alice's public value, sent to Bob openly
B = pow(g, b, p)   # Bob's public value, sent to Alice openly

alice_shared_secret = pow(B, a, p)   # Bob's public value ^ Alice's private key
bob_shared_secret   = pow(A, b, p)   # Alice's public value ^ Bob's private key

print(alice_shared_secret == bob_shared_secret)   # True — both derive the same secret!

Why an eavesdropper who sees p, g, A, B can't compute the shared secret: doing so requires solving the discrete logarithm problem (recovering a from g^a mod p), which is believed computationally infeasible for large primes — a different hardness assumption from RSA's factoring problem, but the same flavor: an operation that's easy in one direction (exponentiate) and (believed) hard to reverse (take the discrete log).

Elliptic curve cryptography (ECC) — same idea, smaller keys

ECC replaces modular exponentiation with point addition on an elliptic curve (y² = x³ + ax + b mod p). "Multiplying" a point G by a scalar k (i.e., adding G to itself k times using the curve's geometric group law) is easy; recovering k from k·G and G (the elliptic curve discrete logarithm problem) is believed even harder than the classic discrete log problem relative to key size — which is why a 256-bit ECC key (P-256, Curve25519) offers security roughly comparable to a 3072-bit RSA key, with much smaller keys and faster operations. This is why modern TLS and SSH default to ECC (ECDHE, Ed25519) over classic RSA/DH.

The birthday attack — hash collision math

The birthday paradox: in a room of just 23 people, there's a >50% chance two share a birthday — far fewer than the 366 you might intuitively guess, because you're comparing all pairs, which grows quadratically.

P(collision) ≈ 1 - e^(-k²/2N)     for k items into N buckets

Applied to hash functions: to find any collision in an n-bit hash function, an attacker needs only about 2^(n/2) attempts (not 2^n) — this is why a hash function needs double the bit-length of its intended collision-resistance security level. A 128-bit hash only offers ~64 bits of collision resistance, which is why SHA-256 (256-bit output, ~128-bit collision resistance) is the practical minimum for collision-critical uses today, and why MD5 (128-bit, ~64-bit collision resistance, further weakened by structural cryptanalytic attacks) is considered broken.

def birthday_bound(hash_bits):
    return 2 ** (hash_bits / 2)

print(f"{birthday_bound(128):.2e}")   # MD5-scale: ~1.8 * 10^19 attempts to find a collision
print(f"{birthday_bound(256):.2e}")   # SHA-256-scale: ~1.3 * 10^38 attempts

Why RSA decryption gives back the message: the proof

Because e·d ≡ 1 (mod φ(n)), there's some integer k with e·d = 1 + k·φ(n). Then, using Euler's theorem (m^φ(n) ≡ 1, Ch. 19):

c^d = (m^e)^d = m^(e·d) = m^(1 + k·φ(n)) = m · (m^φ(n))^k ≡ m · 1^k = m   (mod n)

Decryption undoes encryption because the exponent wraps around at φ(n). Only someone who knows φ(n), which means knowing p and q, can compute the d that makes the wrap land exactly on 1. (The proof above assumes gcd(m, n) = 1. The CRT from Ch. 19 extends it to every m.)

Why "textbook RSA" is broken: malleability and padding

Raw RSA is multiplicative: Enc(m₁) · Enc(m₂) = (m₁m₂)ᵉ = Enc(m₁·m₂). An attacker who sees c = Enc(65) = 2790 can compute c · 2ᵉ mod n without any key, and that decrypts to 2 · 65 = 130. If the message were an amount of money, the attacker just doubled it.

Real RSA therefore pads the message with structured randomness first (OAEP for encryption, PSS for signatures). Padding has its own maths trap. In 1998 Bleichenbacher showed that a server which merely reveals whether the padding was valid (an error message, or a timing difference) acts as an oracle. Each answer leaks a little information about m, and roughly a million adaptive queries decrypt any ciphertext. The 2017 ROBOT scan found the same flaw still live on major sites. That's why TLS 1.3 removed RSA key transport entirely.

Side channels: square-and-multiply leaks the key

Look at the fast_pow_mod loop above. It multiplies only when the current exponent bit is 1. When the exponent is the private key d, the running time (or the power trace, or the cache footprint) of each step reveals each bit of d. Kocher's 1996 timing attack recovered RSA and DH keys from response timings alone, and later remote attacks did it across a LAN (Brumley & Boneh, 2003).

The fix is mathematical, not cryptographic. A Montgomery ladder performs exactly one multiply and one square per bit, whatever the bit is, and blinding randomizes the input (c · rᵉ, decrypt, then divide out r). That's the same multiplicative property that made textbook RSA malleable, used here as a defence. "Constant-time code" in crypto libraries is fundamentally about making a program's resource usage independent of secret bits.

Diffie–Hellman, symbol by symbol, and why parameters matter

Security depends on more than the size of p:

• Small subgroups. If p - 1 has only small prime factors, the discrete log can be solved separately in each small subgroup and recombined with the CRT (the Pohlig–Hellman algorithm). That's why DH uses safe primes p = 2q + 1 with q also prime, which leaves no small subgroups to hide in. It's also why TLS 1.3 only allows a fixed list of vetted groups (RFC 7919).
• Precomputation. The best discrete-log algorithm (the number field sieve) spends most of its effort on work that depends only on p, not on a or b. The 2015 Logjam paper showed that 512-bit "export" DH could be broken in minutes once that precomputation was done. It also estimated that a nation-state budget could precompute one widely shared 1024-bit prime, enough to passively decrypt a large fraction of VPN and SSH traffic. Shared parameters plus precomputation turned a per-connection cost into a one-time cost.

Elliptic curves, by hand

An elliptic curve over a prime field is the set of points (x, y) with

y² ≡ x³ + a·x + b   (mod p)

plus a special "point at infinity" O, which acts like zero. Points can be added. Geometrically, you draw the line through P and Q, find where it hits the curve a third time, and reflect that point. Algebraically:

slope:  λ = (y₂ - y₁) / (x₂ - x₁)          if P ≠ Q   (the chord)
        λ = (3x₁² + a) / (2y₁)             if P = Q   (the tangent: implicit differentiation, Ch. 12!)

sum:    x₃ = λ² - x₁ - x₂
        y₃ = λ(x₁ - x₃) - y₁

Every "division" here means multiplying by a modular inverse (Ch. 19).

A toy curve: y² = x³ + 2x + 2 (mod 17), base point G = (5, 1). Compute 2G (doubling, so use the tangent):

λ  = (3·5² + 2) / (2·1) = 77 / 2 ≡ 77 · 9 ≡ 9 · 9 = 81 ≡ 13   (mod 17)   [2⁻¹ ≡ 9, since 2·9 = 18 ≡ 1; 77 ≡ 9]
x₃ = 13² - 5 - 5 = 159 ≡ 6     (mod 17)
y₃ = 13·(5 - 6) - 1 = -14 ≡ 3  (mod 17)
2G = (6, 3)        check: 3² = 9,  6³ + 2·6 + 2 = 230 = 13·17 + 9 ≡ 9  ✓

Keep adding G and the points go (5,1), (6,3), (10,6), (3,1), (9,16), …. At 19G you reach O, so the group has order 19, and 20G = G again. That cycle is the "clock" ECC works on.

ECDH with toy numbers. Alice picks secret a = 3 and sends A = 3G = (10, 6). Bob picks b = 7 and sends B = 7G = (0, 6). Alice computes 3·B and Bob computes 7·A. Both get 21G = 2G = (6, 3), because 21 mod 19 = 2. An eavesdropper sees G, (10,6) and (0,6) and must solve the elliptic curve discrete log problem to recover 3 or 7. With 19 points that takes a moment. With about 2²⁵⁶ points (Curve25519, P-256), the best known attack (Pollard's rho) needs about √(2²⁵⁶) = 2¹²⁸ steps. That square root is the birthday bound again (below), and it's why a 256-bit curve gives "128-bit security".

ECDSA nonce reuse: the PS3 hack, in algebra

An ECDSA signature on message hash z with private key d uses a fresh secret nonce k, over a curve whose group has order n:

r = x-coordinate of (k·G)  mod n
s = k⁻¹ · (z + r·d)        mod n

Sign two different messages z₁, z₂ with the same k. Then r is identical in both, and subtracting the two s equations eliminates d:

s₁ - s₂ = k⁻¹·(z₁ - z₂)       ->   k = (z₁ - z₂) / (s₁ - s₂)    (mod n)
then from either signature:        d = (s₁·k - z₁) / r            (mod n)

Two signatures and two lines of algebra give you the private key. On the toy curve (n = 19) with d = 7, k = 10, z₁ = 5, z₂ = 12, the signatures are (7, 13) and (7, 8). Then k = (5-12)/(13-8) ≡ 10 and d = (13·10 - 5)/7 ≡ 7. Sony's PS3 used a constant k (2010). Android Bitcoin wallets with a broken SecureRandom repeated k (2013) and had funds stolen. Even a few biased bits of k are enough when many signatures are available, using lattice attacks (the 2019 Minerva and TPM-Fail attacks recovered keys from timing-leaked nonce bits). That's why modern implementations derive k deterministically from the key and the message (RFC 6979), and why Ed25519 was designed that way from the start.

The birthday bound, derived

Put k items into N equally likely buckets one at a time. Item i+1 avoids all i earlier ones with probability 1 - i/N. So:

P(no collision) = (1 - 1/N)(1 - 2/N)…(1 - (k-1)/N)
                ≈ e^(-1/N) · e^(-2/N) · … · e^(-(k-1)/N)     using 1 - x ≈ e^(-x)  (Taylor, Ch. 12)
                = e^(-(1 + 2 + … + (k-1))/N)
                = e^(-k(k-1)/(2N))                            (arithmetic series, Ch. 6)
                ≈ e^(-k²/(2N))

Set P(collision) = 1/2: k²/(2N) = ln 2, so k ≈ √(2 ln 2) · √N ≈ 1.18·√N. For birthdays (N = 365) that gives 1.18 · 19.1 ≈ 22.5, so 23 people. ✓

How many bits of security? One table to calibrate everything

Bits of security means "the attacker needs about 2ᵇ operations". Each extra bit doubles the work, so 128 bits is about 3.4·10³⁸ operations, which is not reachable with any conceivable classical computer.

Post-quantum: Learning With Errors, the maths behind ML-KEM

Shor's algorithm breaks RSA, DH and ECC because they all hide a secret in the period of modular exponentiation, and quantum computers find periods efficiently. Lattice cryptography hides the secret in noise instead:

b = A · s + e   (mod q)

Without e, this is Ch. 10's A·x = b, which Gaussian elimination solves in milliseconds. With a little noise added, elimination amplifies the errors until the answer is garbage. The best known attacks (lattice reduction) take exponential time, even on quantum computers. That's the Learning With Errors problem (Regev, 2005). ML-KEM (FIPS 203, 2024) uses a structured version over polynomials of degree 256, and Chrome, Cloudflare and OpenSSH already negotiate hybrid X25519 + ML-KEM key exchange by default, so "harvest now, decrypt later" recordings of today's traffic stay safe.

Real-life engineering ties

• Security: this chapter is the mathematical grounding for evaluating cryptographic choices — key sizes, algorithm deprecation decisions (why MD5/SHA-1 are banned for security use), TLS cipher suite selection.
• Network: every TLS handshake performs (EC)DHE key exchange and RSA or ECDSA signature verification live, on every HTTPS connection — this math runs billions of times a second across the internet.
• AI: less direct, but cryptographic hashing underlies content deduplication in training data pipelines, and differential privacy (adding calibrated noise to protect individual data points) borrows concepts from this same hardness-assumption tradition.
• SWE: understanding why you should never write your own crypto — the security rests entirely on decades of cryptanalysis against specific, standardized constructions, not on the general idea being sound.

More real-life examples:

• In 2010, Sony's PlayStation 3 signing system was broken because its ECDSA implementation reused the same "random" nonce k for every signature instead of generating a fresh one each time — with two signatures sharing a nonce, simple algebra recovers the private key directly, a real demonstration of how fragile these assumptions are to implementation mistakes.
• A 2008 bug in Debian's OpenSSL package (CVE-2008-0166) accidentally removed almost all sources of entropy from key generation, meaning the "random" keys it generated came from a pool of only about 32,768 possible values — every key generated on affected systems for nearly two years was trivially guessable, despite using "correct" RSA/DSA math.
• The 2017 ROCA vulnerability (CVE-2017-15361) found that a widely used Infineon smart-card/TPM chip generated RSA primes with a subtle structural weakness, making factoring dramatically faster — millions of real government ID cards and TPM-backed keys were affected.
• Modern TLS 1.3 mandates (EC)DHE for every handshake specifically to guarantee forward secrecy — even if a server's long-term private key is stolen later, past recorded traffic can't be decrypted, because each session's shared secret was never derived from that long-term key.

Common mistake

Believing "hard to reverse" cryptographic assumptions are mathematically proven — they are not (this echoes Ch. 19's point). RSA, DH, and ECC security all rest on unproven computational hardness assumptions that have simply resisted decades of attack. This is precisely why quantum computing (Shor's algorithm) is such a big deal: it would break the factoring and discrete-log assumptions efficiently, which is why NIST finalized post-quantum standards (ML-KEM for key exchange, ML-DSA for signatures) in 2024.