Cryptography: Public-Key & Diffie–Hellman
How math built on hard problems (factoring, discrete log) protects modern communications.
Modern cryptography rests on computational hardness assumptions: problems easy in one direction but believed hard in reverse.
Diffie–Hellman key exchange (1976): publicly fix prime $p$ and generator $g$ mod $p$. Alice picks secret $a$, sends $A = g^a \bmod p$; Bob picks $b$, sends $B = g^b \bmod p$. Both compute $K = g^{ab} \bmod p$. Recovering $a$ from $g^a$ is the discrete log problem — believed hard.
RSA (1977): Bob picks primes $p, q$, $n = pq$, $\varphi(n) = (p-1)(q-1)$, public exponent $e$ coprime to $\varphi$. Decryption exponent $d \equiv e^{-1} \pmod{\varphi}$. Encryption $c \equiv m^e \pmod n$; decryption $m \equiv c^d \pmod n$. Security rests on the difficulty of factoring $n$.
Other building blocks:
- Elliptic-curve crypto (ECC): same idea on $E(\mathbb F_p)$, much smaller keys for equivalent security.
- Hash functions (SHA-256): one-way, collision-resistant.
- Symmetric ciphers (AES): block ciphers used after key exchange.
Post-quantum: Shor's algorithm solves factoring and discrete log in polynomial time on a quantum computer; lattice-based and hash-based schemes are leading candidates for quantum-resistant cryptography (NIST standardized Kyber, Dilithium in 2024).