Symmetric vs. Asymmetric Encryption: The Key Exchange Problem

TL;DR

Symmetric ciphers (AES) use one key $k$ for both encryption and decryption, $C = E_k(P)$, and run near hardware speed — but two parties must already share $k$ over a secure channel before any traffic can flow, and an $n$-party network needs $\binom{n}{2}$ pairwise keys. Asymmetric cryptography solves distribution by splitting the key: RSA generates a modulus $N = p \times q$ from two large primes and derives a public exponent $e$ and private exponent $d$ with $ed \equiv 1 \pmod{\varphi(N)}$; Diffie-Hellman lets two parties compute a shared secret $g^{ab} \bmod p$ over a public channel without ever transmitting it. Both rest on problems (factoring, discrete log) that are classically hard but fall to Shor's algorithm. TLS uses asymmetric primitives only to bootstrap a symmetric session key, then hands bulk data to AES — asymmetric operations are too slow for high-throughput encryption.

Symmetric Encryption: AES and the Key Distribution Problem

AES is a substitution-permutation network operating on 128-bit blocks under a single shared key $k$:

Encryption and decryption use the same key, and each round is a fixed sequence of byte substitution, row shifting, column mixing, and key XOR — no exponentiation, no modular arithmetic over large integers. This is why AES throughput on hardware with AES-NI reaches gigabytes per second, several orders of magnitude faster than any public-key operation of comparable security margin.

The cost is distribution. Before $C = E_k(P)$ means anything, both parties must possess $k$, and $k$ must reach the second party without being observed. For a network of $n$ participants who all need pairwise secure channels, the number of distinct keys required is

which is quadratic in $n$ and does not scale to the open internet: there is no pre-existing secure channel between a browser and a server it has never contacted. AES gives no mechanism for establishing $k$ in the first place — that problem requires a different mathematical structure entirely.

Asymmetric Encryption: RSA

RSA replaces a single shared secret with a key pair, generated as follows.

1. Choose two large primes $p$, $q$ and compute the modulus:

2. Compute Euler's totient of $N$:

3. Choose a public exponent $e$ coprime to $\varphi(N)$ (commonly $e = 65537$), then compute the private exponent as its modular inverse:

The public key is $(N, e)$; the private key is $(N, d)$. Encryption and decryption are modular exponentiation:

Correctness follows from Euler's theorem given $ed \equiv 1 \pmod{\varphi(N)}$. Security follows from the opposite direction: recovering $d$ from $(N, e)$ requires $\varphi(N)$, and computing $\varphi(N)$ without $p, q$ is believed to require factoring $N$ — classically sub-exponential, and the exact problem Shor's algorithm solves in polynomial time on a quantum computer.

Diffie-Hellman Key Exchange

Diffie-Hellman does not encrypt a key for transport — it lets two parties derive an identical secret from public values, without either value ever crossing the wire.

Public parameters: a large prime $p$ and a generator $g$ of the multiplicative group $\mathbb{Z}_p^*$.

Alice and Bob exchange $A$ and $B$ over the open channel, then each computes the same value independently:

An eavesdropper who observes $p, g, A, B$ but not $a$ or $b$ must solve the discrete logarithm problem — recover $a$ from $A = g^a \bmod p$ — to reconstruct $s$. No efficient classical algorithm does this for well-chosen parameters.

Elliptic Curve Diffie-Hellman (ECDHE) replaces $\mathbb{Z}_p^*$ with the group of points on an elliptic curve over a finite field, and modular exponentiation with scalar point multiplication:

where $G$ is a fixed base point. The hard problem — the elliptic curve discrete logarithm problem — has no known sub-exponential classical attack, so ECC reaches RSA-2048-equivalent security with a ~256-bit key, which is why TLS 1.3 defaults to ECDHE over classical Diffie-Hellman or RSA key transport.

Why the Modern Web Needs Both

Neither primitive is sufficient alone. Asymmetric operations — modular exponentiation over 2048-bit integers, or scalar multiplication over elliptic curve groups — cost microseconds to milliseconds per operation and do not scale to encrypting a video stream or a large file. Symmetric ciphers scale to that throughput but have no answer to the distribution problem described above.

TLS 1.3 resolves this with hybrid encryption: an ECDHE exchange runs once per connection to derive a shared secret, which is fed through a key derivation function to produce a symmetric session key. Every subsequent record on that connection is encrypted with AES (typically AES-GCM), not with the asymmetric primitive. RSA or ECDSA signatures separately authenticate the handshake, binding the exchange to a certificate so the shared secret cannot be intercepted by a man-in-the-middle. The asymmetric layer solves distribution and identity; the symmetric layer does the encryption work at line rate. Removing either half breaks the protocol — this is also why the migration to post-quantum cryptography touches the asymmetric layer (KEMs replacing RSA/ECDHE) while leaving AES itself largely untouched.