In 1976, Whitfield Diffie and Martin Hellman revolutionized human communication by publishing “New Directions in Cryptography,” solving the millennia-old problem of secure key exchange over an eavesdropped channel. Public-key cryptography rests upon Trapdoor One-Way Permutations: functions that are trivial to compute in the forward direction, intractable to invert without private auxiliary information (the trapdoor), but instantly invertible once the trapdoor is known. This treatise explores the computational number theory underlying RSA, the Diffie-Hellman protocol, and the sub-exponential algorithms that govern their security.
1. The RSA Cryptosystem & Integer Factorization
Invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, RSA operates in the multiplicative group (mathbb{Z}_N^*) where (N = pq) is the product of two large prime numbers of comparable bit-length. Euler’s Totient function is:
[
phi(N) = (p – 1)(q – 1)
]
Key generation selects an encryption exponent (e) coprime to (phi(N)) (typically (e = 65537 = 2^{16} + 1)) and computes the private decryption trapdoor (d) via the Extended Euclidean Algorithm:
[
e cdot d quiv 1 pmod{phi(N)}
]
Encryption and decryption are modular exponentiations:
[
c quiv m^e pmod N, quad m quiv c^d quiv (m^e)^d quiv m^{1 + kphi(N)} quiv m pmod N
]
by Euler’s Totient Theorem (and the Chinese Remainder Theorem for all (m in mathbb{Z}_N)). The security of textbook RSA reduces to the RSA Problem: computing (e)-th roots modulo composite (N). While solving the RSA problem is computationally equivalent to factoring (N) under most operational reductions, textbook RSA is multiplicatively homomorphic ((E(m_1)E(m_2) = E(m_1 m_2))) and completely insecure against chosen-ciphertext attacks unless paired with randomized padding standards like RSA-OAEP.
2. The Diffie-Hellman Protocol & Discrete Logarithms
Let (G) be a cyclic group of prime order (q) generated by (g). The Discrete Logarithm Problem (DLP) posits that given ((g, h = g^x)), finding the exponent (x in mathbb{Z}_q) requires super-polynomial time. The Diffie-Hellman key exchange establishes a shared secret over an insecure channel:
- Alice samples secret (a leftarrow mathbb{Z}_q) and transmits (A = g^a).
- Bob samples secret (b leftarrow mathbb{Z}_q) and transmits (B = g^b).
- Both compute the shared group element: (K = B^a = (g^b)^a = g^{ab} = (g^a)^b = A^b).
Security rests on the Computational Diffie-Hellman (CDH) assumption (given (g, g^a, g^b), computing (g^{ab}) is hard) and the stronger Decisional Diffie-Hellman (DDH) assumption (distinguishing (g^{ab}) from a random group element (g^c) is computationally infeasible).
3. Sub-Exponential Attacks: Index Calculus & GNFS
Why must RSA moduli and finite field Diffie-Hellman primes be at least 2048 to 3072 bits long to achieve 112 to 128 bits of security? Because unlike generic groups where discrete logarithms require exponential (mathcal{O}(sqrt{q})) time via Pollard’s Rho, multiplicative groups of finite fields (mathbb{F}_p^*) and RSA integers admit Index Calculus algorithms.
Using the (L)-notation:
[
L_n[alpha, c] = xpleft( (c + o(1)) (ln n)^alpha (ln ln n)^{1 – alpha}
ight)
]
The General Number Field Sieve (GNFS) factors integers and computes discrete logs in sub-exponential time:
[
L_N[1/3, (64/9)^{1/3}] approx L_N[1/3, 1.923]
]
GNFS constructs algebraic number fields over irreducible polynomials, collects relations that factor smoothly over a predetermined prime factor base, and solves a massive sparse linear system over (mathbb{F}_2) to produce congruent squares (x^2 quiv y^2 pmod N). Because (alpha = 1/3), scaling key sizes produces diminishing returns in asymptotic security, motivating the transition to Elliptic Curve Cryptography.
