For thousands of years, cryptography suffered from a fatal Achilles’ heel known as the Key Distribution Problem. To communicate in secret, two distant parties had to first meet in private or employ a trusted physical courier to exchange a secret symmetric key. If the channel used to exchange the key was insecure, encryption was impossible. In 1976, Whitfield Diffie and Martin Hellman shattered this universal constraint by introducing Public-Key (Asymmetric) Cryptography. They demonstrated that two strangers can publicly agree on a shared secret across an insecure channel observed by all the spies in the world, inaugurating modern e-commerce, digital authentication, and the global cryptographic internet.
1. The Concept of One-Way Trapdoor Permutations
Diffie and Hellman proposed that public-key cryptography requires a mathematical function $f: X to Y$ possessing two asymmetrical properties:
- Easy to Compute: Given $x$, computing $y = f(x)$ is computationally trivial ($mathcal{O}(text{poly}(n))$).
- Hard to Invert: Given $y$, computing $x = f^{-1}(y)$ is computationally intractable for any adversary.
- Trapdoor Information: If an authorized party possesses a secret “trapdoor” $k$, computing $f^{-1}(y)$ collapses back to trivial polynomial time.
Public-key encryption uses the public key to compute the easy forward direction $y = f(x)$, while the recipient uses their private trapdoor key to compute the inverse.
2. The Diffie-Hellman Key Exchange Protocol
Diffie and Hellman realized this trapdoor asymmetry over the multiplicative group of integers modulo a large prime $p$, denoted $mathbb{Z}_p^*$, using a generator element $g$.
Protocol Execution:
- Alice and Bob publicly agree on a large prime $p$ (e.g., 2048 to 4096 bits) and a base generator $g in mathbb{Z}_p^*$.
- Alice chooses a secret random private integer $a in [2, p-2]$, computes her public value $A$, and transmits it across the public channel:
[
A = g^a bmod p
] - Bob independently chooses a secret private integer $b in [2, p-2]$, computes his public value $B$, and transmits it:
[
B = g^b bmod p
] - Upon receiving $B$, Alice computes the shared secret:
[
s = B^a bmod p = (g^b)^a bmod p = g^{ab} bmod p
] - Upon receiving $A$, Bob computes the shared secret:
[
s = A^b bmod p = (g^a)^b bmod p = g^{ab} bmod p
]
Both Alice and Bob now possess the identical shared secret $s = g^{ab} bmod p$. An eavesdropper (Eve) who intercepted $p, g, A,$ and $B$ cannot compute $s$ without solving the Computational Diffie-Hellman (CDH) problem, which is believed to be computationally equivalent to the Discrete Logarithm Problem (DLP): finding $a = log_g(A) bmod p$.
3. The RSA Cryptosystem: Number-Theoretic Trapdoors
In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman at MIT formulated the first practical general-purpose asymmetric encryption algorithm: RSA.
Key Generation:
- Generate two distinct, large random prime numbers $p$ and $q$ of equal bit-length.
- Compute the modulus $n = p cdot q$ and Euler’s totient function:
[
phi(n) = (p-1)(q-1) = n – (p + q) + 1
] - Choose a public encryption exponent $e$ such that $1 < e < phi(n)$ and $gcd(e, phi(n)) = 1$ (standardly chosen as $e = 65537 = 2^{16} + 1$).
- Compute the private decryption exponent $d$ via the Extended Euclidean Algorithm:
[
d equiv e^{-1} pmod{phi(n)} iff e cdot d equiv 1 pmod{phi(n)}
] - The Public Key is $(n, e)$; the Private Key is $(d, p, q)$.
Encryption and Decryption:
To encrypt message $m in [0, n-1]$:
[
c = m^e bmod n
]
To decrypt ciphertext $c$:
[
m = c^d bmod n
]
Proof of Correctness via Euler’s Theorem
Because $e cdot d equiv 1 pmod{phi(n)}$, there exists an integer $k$ such that $e cdot d = 1 + k phi(n)$. By Euler’s Totient Theorem, for any integer $m$ coprime to $n$:
[
m^{phi(n)} equiv 1 pmod n
]
Therefore:
[
c^d equiv (m^e)^d equiv m^{ed} equiv m^{1 + k phi(n)} equiv m cdot (m^{phi(n)})^k equiv m cdot 1^k equiv m pmod n
]
The security of RSA rests entirely on the assumption that factoring $n$ into primes $p$ and $q$ is classically intractable. As explored in Part 10 of our Quantum Computing series, Shor’s quantum algorithm solves both prime factoring and discrete logarithms in polynomial time, driving the global transition toward post-quantum asymmetric alternatives.
