Symmetric encryption requires a shared secret key established before communication begins. For two parties who have never met, this is a circular problem: to communicate securely, they need a shared key; to share a key, they need to communicate securely. For decades this seemed like an unavoidable limitation. In 1976, Diffie and Hellman published a paper that broke the circle: two parties can agree on a shared secret over a completely public channel, in full view of any eavesdropper, and the eavesdropper learns nothing. The trick is that the underlying mathematical operation is easy to perform but hard to reverse. This paper created the field of public key cryptography.

The central insight is not just a clever trick - it is a structural shift in what cryptography can do. Symmetric schemes require trust and coordination to be established offline, before any message is sent. Public key schemes push that trust into the hardness of mathematical problems. If factoring large integers is hard, or if computing discrete logarithms in cyclic groups is hard, then encryption can happen between strangers, at scale, over open networks. The internet as we know it depends on this.

Helpful context:

The Key Distribution Problem

In a network of $n$ parties who each want to communicate privately with any other, symmetric cryptography requires $\binom{n}{2}$ pre-shared keys - one per pair. For $n = 10^6$ (a small internet), that is $5 \times 10^{11}$ keys, each established through a secure channel that does not yet exist. The problem is circular.

Public key cryptography resolves this with an asymmetric setup:

  • Each party has a key pair: a public key $pk$ (published openly) and a secret key $sk$ (kept private).
  • Anyone can encrypt to party $i$ using $pk_i$.
  • Only party $i$ can decrypt using $sk_i$.
  • No pre-shared secret is needed.

With $n$ parties, only $n$ key pairs are needed - one per party. The public keys can be posted to a directory. Any two parties can communicate securely without ever having met, without any prior coordination, using only the public key infrastructure.

Diffie-Hellman Key Exchange

Setup. Fix a cyclic group $\mathbb{G}$ of prime order $q$ with generator $g$ (e.g., $\mathbb{Z}_p^*$ for a large prime $p$, or an elliptic curve group). These parameters are public.

Protocol:

  1. Alice samples $a \leftarrow \mathbb{Z}_q$, sends $A = g^a$.
  2. Bob samples $b \leftarrow \mathbb{Z}_q$, sends $B = g^b$.
  3. Alice computes $B^a = g^{ab}$.
  4. Bob computes $A^b = g^{ab}$.

Both parties arrive at the shared secret $g^{ab}$ without ever transmitting it. An eavesdropper sees $g^a$ and $g^b$ but must compute $g^{ab}$ - this is the computational Diffie-Hellman (CDH) problem, believed to be hard.

DH is not encryption - it establishes a shared secret. To encrypt, use the shared key as input to a symmetric cipher. The output of DH is typically hashed to produce a symmetric key of the right length.

The security of DH depends entirely on the group. In $\mathbb{Z}_p^*$, computing discrete logs with index calculus algorithms is subexponential, so $p$ must be very large (2048+ bits). Elliptic curve groups have no known subexponential attack, so 256-bit keys provide equivalent security.

The DDH Assumption

Decisional Diffie-Hellman (DDH). The following two distributions are computationally indistinguishable:

$$(g^a, g^b, g^{ab}) \approx_c (g^a, g^b, g^c)$$

where $a, b, c \leftarrow \mathbb{Z}_q$ are uniform. No PPT adversary can distinguish the real DH triple from a random triple with non-negligible advantage.

DDH is stronger than CDH (which only asks to compute $g^{ab}$, not distinguish it). If CDH is hard, it does not automatically follow that DDH is hard - the gap matters. DDH fails in $\mathbb{Z}_p^$ for certain primes: the Legendre symbol $\left(\frac{g^{ab}}{p}\right)$ can be computed from $g^a$ and $g^b$, leaking the parity of the discrete log. DDH does hold in prime-order subgroups of $\mathbb{Z}_p^$ and in well-chosen elliptic curve groups.

The DDH assumption is the algebraic foundation for proving CPA security of ElGamal encryption. Concretely: if an adversary could distinguish ElGamal ciphertexts, it could distinguish DH triples, contradicting DDH.

ElGamal Encryption

Construction. Parameters: group $\mathbb{G}$, generator $g$, order $q$.

  • Key generation: sample $x \leftarrow \mathbb{Z}_q$. $sk = x$, $pk = h = g^x$.
  • Encryption: to encrypt $m \in \mathbb{G}$, sample $r \leftarrow \mathbb{Z}_q$:

$$\text{Enc}_{pk}(m) = (g^r,\ h^r \cdot m) = (c_1, c_2)$$

  • Decryption: $m = c_2 \cdot (c_1^x)^{-1}$.

Correctness follows: $c_1^x = g^{rx} = h^r$, so $c_2 \cdot (c_1^x)^{-1} = h^r \cdot m \cdot (h^r)^{-1} = m$.

CPA security. ElGamal is CPA-secure under DDH. The reduction: the ciphertext $(g^r, h^r \cdot m)$ looks like $(g^r, g^c \cdot m)$ to a DDH adversary (since $h^r = g^{xr}$ and $g^c$ is a random group element when DDH holds - the adversary cannot distinguish $g^{xr}$ from a uniform $g^c$). The fresh randomness $r$ is chosen per encryption, so the same message encrypts to a different ciphertext each time, giving CPA security.

ElGamal is not CCA-secure. It is multiplicatively malleable: given $(c_1, c_2) = \text{Enc}(m)$, the ciphertext $(c_1, c_2 \cdot m')$ decrypts to $m \cdot m'$. An adversary with a decryption oracle can submit this modified ciphertext, learn $m \cdot m'$, and recover $m$ by dividing out $m'$. Malleability is an inherent structural weakness, not a matter of parameters or key size.

RSA

Setup. Choose large primes $p, q$ (each $\sim 1024$ bits), compute $N = pq$. Choose $e$ with $\gcd(e, \phi(N)) = 1$ where $\phi(N) = (p-1)(q-1)$. Compute $d = e^{-1} \bmod \phi(N)$.

  • $pk = (N, e)$, $sk = (N, d)$ (equivalently, $(p, q, d)$).

Textbook RSA encryption:

  • $\text{Enc}_{pk}(m) = m^e \bmod N$
  • $\text{Dec}_{sk}(c) = c^d \bmod N$

Correctness: $c^d = m^{ed} \bmod N$. Since $ed \equiv 1 \pmod{\phi(N)}$, Euler’s theorem gives $m^{ed} = m^{1 + k\phi(N)} = m \cdot (m^{\phi(N)})^k = m \bmod N$ (for $\gcd(m,N) = 1$).

RSA assumption. Given $N, e, c = m^e \bmod N$, it is computationally hard to find $m$. The best known attack computes $d$ by factoring $N$ - which is believed to be hard (the integer factoring assumption). The relationship between RSA hardness and factoring is not formally proven: we know factoring implies RSA inversion is easy, but whether RSA hardness implies factoring hardness remains open.

Chinese Remainder Theorem for RSA. Decryption $c^d \bmod N$ is slow for large $d$. Using CRT:

  1. Compute $d_p = d \bmod (p-1)$, $d_q = d \bmod (q-1)$.
  2. $m_p = c^{d_p} \bmod p$, $m_q = c^{d_q} \bmod q$.
  3. Combine via CRT: $m = \text{CRT}(m_p, m_q, p, q)$.

This reduces the exponent size by roughly half in each modulus. Since modular exponentiation cost is quadratic in the modulus size, working modulo $p$ and $q$ (each half the bit-length of $N$) and then combining is approximately $4\times$ faster than exponentiating directly modulo $N$.

Why Textbook RSA Is Broken

Textbook RSA is deterministic: the same message always encrypts to the same ciphertext. As established in CPA security definitions, any deterministic encryption scheme fails CPA. An adversary submits two messages $m_0, m_1$, receives $c^* = m_b^e \bmod N$, and wins by checking which plaintext produces $c^*$. Beyond CPA failure:

Small message attack. If $m$ is small relative to $N$ and $e = 3$, then $c = m^3 < N$ exactly (no modular reduction occurs), so $m = c^{1/3}$ recoverable by integer cube root - no cryptographic work required.

Common modulus attack. If the same $m$ is encrypted to the same $N$ with two different exponents $e_1, e_2$ with $\gcd(e_1, e_2) = 1$: find $u, v$ with $ue_1 + ve_2 = 1$ (extended Euclidean algorithm); then $c_1^u c_2^v = m^{ue_1 + ve_2} = m^1 = m$. Two ciphertexts, no key.

Multiplicative malleability. $(2^e \cdot c) \bmod N$ decrypts to $2m$. An adversary can query the decryption oracle on this related ciphertext and trivially recover $m$.

These attacks are not about key size. They are structural - they follow from the algebraic properties of the raw RSA function. Fixing them requires changing the structure, not increasing parameters.

PKCS#1 v1.5 and RSA-OAEP

PKCS#1 v1.5. Add structured random padding before encrypting:

$$\text{Enc}(m) = (0x00 | 0x02 | \text{random bytes} | 0x00 | m)^e \bmod N$$

The random bytes make encryption non-deterministic, defeating small-message and common-modulus attacks. This was the standard for TLS for many years.

But broken under CCA: Bleichenbacher’s 1998 attack showed that if a TLS server reveals whether a decrypted ciphertext begins with $0x00\ 0x02$ (a PKCS conformant message - often just an error code), an adversary can iteratively query the server with crafted ciphertexts and narrow down the plaintext. The attack requires roughly $10^6$ adaptive queries. The padding format itself becomes an oracle. This attack is still relevant today: variants surface regularly in TLS implementations.

RSA-OAEP (Optimal Asymmetric Encryption Padding). The current standard. The message is mixed with randomness through a pair of hash-based mask generating functions before encrypting:

  1. Choose random $r \leftarrow \{0,1\}^k$.
  2. Compute $X = (m | 0^{k_0}) \oplus G(r)$ and $Y = r \oplus H(X)$, where $G, H$ are mask generating functions built from a hash.
  3. Encrypt $(X | Y)^e \bmod N$.

In the random oracle model (where $G$ and $H$ are modeled as truly random functions), RSA-OAEP is CCA-secure: any CCA adversary can be reduced to an inverter for the raw RSA function. The random oracle model is an idealization, but RSA-OAEP has withstood extensive cryptanalysis and is the padding scheme mandated by modern standards.

Summary

Concept Key idea
DH key exchange $g^a$ + $g^b$ $\to$ $g^{ab}$ without transmitting the secret
CDH / DDH Hard to compute / distinguish DH triples; underlying assumption
ElGamal CPA-secure under DDH; malleable (not CCA-secure)
RSA setup $N = pq$; $ed \equiv 1 \pmod{\phi(N)}$; $c = m^e$, $m = c^d$
RSA assumption Hard to invert $m^e \bmod N$ without knowing $\phi(N)$
CRT for RSA Speeds up decryption by factoring through $\mathbb{Z}_p$ and $\mathbb{Z}_q$ separately
Textbook RSA failures Deterministic; small message; common modulus; malleable
PKCS#1 v1.5 Randomized padding; broken by Bleichenbacher (padding oracle)
RSA-OAEP CCA-secure in random oracle model; current standard

Read next: