Public-key cryptography

Public-key cryptography rests on trapdoor problems: operations that are cheap in one direction and infeasible to reverse without a secret. RSA (Rivest, Shamir and Adleman, 1977) relies on the difficulty of factoring n = pq; Diffie-Hellman (1976) and its elliptic-curve form (ECC, proposed independently by Koblitz and Miller in 1985) rely on the discrete-logarithm problem. The ideas were discovered earlier at GCHQ by Ellis, Cocks and Williamson, but that work stayed classified until 1997. Because generic algorithms such as the number field sieve and Pollard's rho give shortcuts, key sizes are not comparable with symmetric ones: NIST SP 800-57 rates RSA-2048 at about 112 bits of security and needs RSA-3072 or a 256-bit curve such as P-256 or Curve25519 for 128 bits.

In practice public-key primitives are used for three jobs, never for bulk data: key establishment (ECDHE in TLS 1.3, X25519 per RFC 7748), key transport or encapsulation (RSA-OAEP, and key-encapsulation mechanisms), and digital signatures. Real systems are hybrid: an asymmetric step agrees on or transports a random symmetric key, and AES-GCM or ChaCha20-Poly1305 encrypts the payload. TLS 1.3 removed static RSA key transport entirely, so every handshake uses ephemeral Diffie-Hellman and gets forward secrecy.

Textbook RSA is insecure: it is deterministic and malleable, so padding is mandatory. PKCS#1 v1.5 encryption padding enabled Bleichenbacher's 1998 adaptive chosen-ciphertext attack, which reappeared in TLS stacks as ROBOT in 2017; OAEP is the safe choice where RSA encryption is still used. Elliptic-curve implementations must validate that received points lie on the curve to avoid invalid-curve attacks, and all implementations must be constant-time to resist timing and cache side channels.

Shor's algorithm would break RSA, finite-field DH and ECC in polynomial time on a sufficiently large fault-tolerant quantum computer, and "harvest now, decrypt later" makes this a present concern for long-lived confidential data. NIST published the first post-quantum standards in August 2024: FIPS 203 (ML-KEM, a lattice-based key-encapsulation mechanism), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA). Deployment is hybrid for now, for example the TLS key-exchange group X25519MLKEM768 combining classical and post-quantum secrets, and the draft NIST IR 8547 (November 2024) proposes deprecating quantum-vulnerable algorithms at the 112-bit level after 2030 and disallowing all of them after 2035. A persistent misconception is that the public key authenticates its owner by itself; without a certificate, a pinned key or out-of-band verification, a man in the middle can simply substitute their own public key, which is the problem PKI exists to solve.