Public Key Cryptography: The Mathematics That Secured the Internet

Zusammenfassung

For most of history, two people who wanted to communicate secretly had to first share a secret — a key, a codebook, a cipher — through a secure channel. If they had a secure channel, they arguably did not need encryption. The invention of public key cryptography in 1976–1977 dissolved this paradox: two strangers who had never met and shared no secrets could, by exchanging information over a completely public channel observed by adversaries, establish a shared secret that no eavesdropper could reconstruct. The mathematics behind this insight is the foundation on which all secure internet commerce, communication, and identity verification now rests.

The Key Distribution Problem

Every encryption system before 1976 shared the same fundamental weakness: the key that encrypted a message was the same key that decrypted it — or was derivable from it by straightforward calculation. This meant that two parties who wanted to communicate securely had to first agree on a key, and that key-agreement had to happen through a channel that was already secure.

During World War II, this was manageable: Allied forces shipped codebooks on courier vessels, distributed one-time pads by diplomatic pouch, and maintained physical security over key materials. The logistics were expensive, operationally complex, and occasionally catastrophic when keys were captured (the German ENIGMA keys, when recovered, unlocked months of intercepted traffic).

As the internet emerged in the 1970s, the problem became acute. Banks wanted to transact electronically. Governments wanted to encrypt communications. Businesses wanted to share proprietary data. All of these applications required key distribution at scales and across distances where physical courier logistics were impossible. Something new was needed.

Diffie-Hellman: The First Solution

In November 1976, Whitfield Diffie and Martin Hellman at Stanford University published “New Directions in Cryptography” — one of the most important papers in the history of computing. It introduced the concept of public key cryptography and provided the first practical key exchange protocol.

The core insight was mathematical: there exist operations that are easy to perform but computationally infeasible to reverse. Specifically, modular exponentiation — computing g^x mod p, where g and p are public parameters and x is a private value — can be done quickly for any x, but recovering x from g^x mod p (the discrete logarithm problem) is computationally intractable for appropriately large parameters.

Diffie-Hellman key exchange works as follows: Alice and Bob publicly agree on large numbers g and p. Alice picks a secret number a and sends g^a mod p to Bob. Bob picks a secret number b and sends g^b mod p to Alice. Alice computes (g^b)^a mod p = g^ab mod p. Bob computes (g^a)^b mod p = g^ab mod p. Both now have g^ab mod p — a shared secret that neither ever transmitted. An eavesdropper who saw only g^a mod p and g^b mod p cannot recover g^ab mod p without solving the discrete logarithm problem.

Diffie-Hellman did not provide encryption by itself — it provided key agreement, from which a symmetric encryption key could be derived. The 1976 paper also proposed the concept of digital signatures (using asymmetric mathematics to authenticate the sender of a message), though it did not yet have a concrete implementation.

Diffie and Hellman received the ACM Turing Award in 2015 — nearly forty years after their breakthrough. The citation credited their 1976 paper with introducing “the ideas of public-key cryptography and digital signatures, which are the foundation for most regularly-used security protocols on the internet today.”

RSA: The Sleepless Night

The Diffie-Hellman paper inspired three MIT mathematicians — Ron Rivest, Adi Shamir, and Leonard Adleman — to search for a concrete public-key encryption system. They spent months working through candidate approaches, with Shamir regularly proposing ideas and Rivest finding the breaks.

In April 1977, on the night following a Passover seder at a student’s home, Ron Rivest could not sleep. He lay awake thinking through the mathematical conditions a public-key system would need to satisfy. By morning, he had written the complete RSA algorithm on paper. He typed up the paper that night; it was circulated as an MIT technical report.

RSA is based on the computational difficulty of integer factorization: multiplying two large prime numbers together is easy; factoring the result back into its prime components is computationally infeasible for sufficiently large numbers. In RSA, a user generates a public key (the product of two large primes, plus an exponent) and a private key (derived from the prime factors). Anyone can encrypt a message using the public key; only the holder of the private key (who knows the prime factors) can decrypt it.

The mathematics: choose primes p and q; compute n = pq; compute φ(n) = (p−1)(q−1); choose e coprime to φ(n); compute d = e⁻¹ mod φ(n). The public key is (n, e); the private key is (n, d). Encryption: c = m^e mod n. Decryption: m = c^d mod n.

The scheme also provides digital signatures: the owner of a private key can sign a message by encrypting its hash with the private key; anyone with the public key can verify the signature by decrypting and comparing. The mathematical properties of RSA ensure that only the private key holder could have produced the signature.

RSA Security was incorporated in 1982 to commercialize the algorithm. The US government classified RSA as a munition under export control regulations — attempting to prevent strong cryptography from being used outside the United States. The patent filed on RSA expired in September 2000, after which the algorithm became freely available. Rivest, Shamir, and Adleman received the ACM Turing Award in 2002.

The GCHQ Prior Invention

In 1997, the UK Government Communications Headquarters (GCHQ) revealed that its researchers — James Ellis, Clifford Cocks, and Malcolm Williamson — had independently developed public-key cryptography in the early 1970s, before Diffie, Hellman, and RSA. Cocks had developed an equivalent to RSA in 1973; Williamson had developed an equivalent to Diffie-Hellman key exchange in 1974. The work was classified and withheld from the public for over twenty years. This meant that the cryptographic revolution that changed the internet had been independently invented twice — once by government intelligence researchers who could not publish, and once by academic researchers who could.

PGP: Bringing Crypto to the People

In 1991, software engineer Phil Zimmermann released Pretty Good Privacy (PGP) — a program that implemented RSA encryption for email, making strong public-key cryptography accessible to ordinary computer users for the first time.

Zimmermann’s motivation was political: he was a nuclear freeze activist, and he believed that governments and corporations would increasingly surveille citizens’ private communications. PGP was his answer. He distributed the first version free over the internet.

The US government’s reaction was swift: it opened a criminal investigation under the Arms Export Control Act, on the grounds that strong cryptography was a munition and distributing it internationally via the internet was illegal arms export. The investigation ran for three years. Zimmermann was never charged; the government dropped the case in 1996, partly because the export control regime was clearly becoming untenable as the internet spread cryptography globally regardless of US law.

PGP established the concept of the web of trust — a decentralized alternative to the certificate authority model, in which users sign each other’s public keys to build a network of mutual authentication. The web of trust remains in use in communities that distrust centralized certificate authorities.

SSL/TLS: The Lock Icon

The practical barrier to internet commerce was not computation — it was trust. A user entering credit card numbers into a web form needed to know that (a) the data was encrypted in transit and (b) the server they were communicating with was actually the company they believed it to be, not an imposter.

Netscape solved both problems with SSL (Secure Sockets Layer), introduced with Netscape Navigator 1.1 in 1995. SSL combined asymmetric encryption (to establish a shared key) with symmetric encryption (to encrypt the actual data, using the shared key for efficiency) and digital certificates (to verify server identity). The visual indicator — a padlock icon in the browser — became the internet’s most recognized symbol of security.

The certificate authority (CA) model underpins SSL/TLS: a small number of trusted organizations (Comodo, DigiCert, Let’s Encrypt, and others — currently approximately 150 root CAs) issue digital certificates that verify a website’s identity. When a browser connects to a server, it checks that the server’s certificate is signed by a trusted CA and that the server possesses the corresponding private key. Browsers ship with a list of trusted CAs hard-coded into the software.

This model has a structural weakness: any trusted CA can issue a certificate for any domain, and CA compromise or malfeasance can enable impersonation attacks. Several CA incidents have demonstrated the problem: Comodo (2011, nine fraudulent certificates for high-profile domains including google.com), DigiNotar (2011, the Dutch CA was completely compromised by Iranian hackers, hundreds of fraudulent certificates issued, DigiNotar eventually bankrupted by the incident).

SSL was replaced by TLS (Transport Layer Security), standardized by the IETF as RFC 2246 in 1999, with major updates in TLS 1.2 (2008) and TLS 1.3 (2018). The practical distinction between SSL and TLS is technical; colloquially “SSL” remains the common term for the technology.

Elliptic Curve Cryptography

RSA and Diffie-Hellman require large key sizes for security: a 2048-bit RSA key is considered a minimum for modern use, and 4096 bits provides long-term security. Elliptic curve cryptography (ECC), independently proposed by Neal Koblitz (University of Washington) and Victor Miller (IBM) in 1985, provides equivalent security with much smaller keys — a 256-bit ECC key is roughly equivalent to a 3072-bit RSA key.

ECC is based on the difficulty of the elliptic curve discrete logarithm problem: given a point P on an elliptic curve and a point Q = kP (the result of adding P to itself k times, using elliptic curve addition), recovering k is computationally infeasible for appropriate curves.

The smaller key sizes have significant practical advantages: faster computation, reduced memory requirements, and lower bandwidth consumption. ECDSA (Elliptic Curve Digital Signature Algorithm) is used in Bitcoin and most modern TLS connections. Curve25519, designed by Daniel Bernstein in 2006 for high performance and security, is the default key exchange curve in modern TLS 1.3 implementations and in Signal.

Post-Quantum Cryptography: The Coming Reckoning

Shor’s algorithm, published by Peter Shor at Bell Labs in 1994, demonstrated that a sufficiently large quantum computer could factor integers and solve discrete logarithm problems in polynomial time — breaking RSA, Diffie-Hellman, and ECC simultaneously. At Shor’s publication, no quantum computer existed that could implement the algorithm for meaningful key sizes. By the 2020s, that remained true — but the trajectory of quantum computing research made the threat real on a 10–30 year horizon.

The National Institute of Standards and Technology (NIST) began a post-quantum cryptography standardization process in 2016. After multiple rounds of analysis by the global cryptographic community, NIST announced in 2024 three finalized standards:

ML-KEM (based on CRYSTALS-Kyber): a key encapsulation mechanism for key exchange
ML-DSA (based on CRYSTALS-Dilithium): a digital signature scheme
SLH-DSA (based on SPHINCS+): a hash-based signature scheme as a conservative alternative

All three are based on mathematical problems — lattice problems and hash functions — that are believed to be resistant to both classical and quantum attack. The standards were published in August 2024.

The transition to post-quantum cryptography involves upgrading essentially every piece of internet infrastructure: TLS libraries, certificate authorities, hardware security modules, VPN software, and the code embedded in billions of devices. The process is expected to take years and to be complicated by the long lifespan of embedded systems that cannot easily be updated.

The mathematical audacity of Diffie and Hellman’s original 1976 insight — that public information could establish private secrets — has proven so powerful that the infrastructure built on it now protects virtually every private communication on the internet. For the protocols that deploy this cryptography, see The Open Standards Process: How the Internet Governs Itself. For the historical background of secret communication, see Cryptography: The Secret Science.