Public-key cryptography

In November 1976, at Stanford University, Whitfield Diffie, a 32-year-old cryptography enthusiast who had left a permanent position at the MITRE Corporation, stood on the cusp of a revolution. Alongside Martin Hellman, a 30-year-old electrical engineering professor at Stanford, Diffie had just submitted a paper that promised to fundamentally change the landscape of cryptography. Titled 'New Directions in Cryptography,' and published in the IEEE Transactions on Information Theory, the paper was not just another academic collaboration. It was a bold departure from conventional wisdom in the field. Their proposal outlined a method for two parties to establish a shared secret key over a public channel, even when they had never met or exchanged information beforehand. This groundbreaking idea relied on modular arithmetic and large prime numbers, hinging on the computational complexity of the discrete logarithm problem. As the paper reached the public in November 1976, the field of cryptography was about to be transformed from a closely-guarded practice of national security agencies into a vibrant public science. The implications of this work would become even more pronounced when a follow-up paper from MIT, published in 1978, established the foundations for modern internet security. Yet, as groundbreaking as the Stanford discoveries were, they mirrored an earlier, classified effort by British cryptographers, whose work would remain in the shadows for another two decades.

What had been wrong before

Throughout the 20th century, cryptographic practice was dominated by symmetric ciphers. These algorithms, such as the German Enigma machine, the American Sigaba, and the British Typex, relied on the same key to encrypt and decrypt messages. Symmetric systems like these required that the key be shared in advance by all parties wishing to communicate securely. This need for pre-distributed keys introduced a significant logistical challenge. The only reliable way to exchange these keys was through trusted couriers, a task that consumed a substantial portion of operational budgets for institutions like the U.S. Department of State. This framework, while secure for established parties like embassies or military commands, was untenable for individuals or organizations without prior contact. As the internet began to take shape in the 1970s, the inadequacies of symmetric cryptography became glaringly apparent. The internet's architecture envisioned a network where arbitrary parties could exchange data freely, making the pre-exchange of keys impractical. While symmetric cryptography secured data in transit, it failed to solve the critical problem of key exchange for previously unconnected entities. By the early 1970s, the cryptographic community was acutely aware of this limitation, yet no viable solution had been publicly proposed.

The Diffie-Hellman move

What Diffie and Hellman introduced was a radical shift in thinking about cryptographic keys. They proposed an idea that had not been previously articulated: the separation of encryption and decryption keys. In their model, the encryption key (or 'public key') could be widely distributed, allowing anyone to encrypt a message. However, only the holder of the corresponding 'private key' could decrypt the message. This setup eliminated the need for pre-shared keys and allowed secure communication over public channels. The public and private keys are mathematically related, yet deriving the private key from the public key is computationally infeasible. The initial paper by Diffie and Hellman outlined a key-exchange protocol that allowed two parties to agree on a shared secret over an insecure channel. Although it was not a complete encryption scheme, it provided the conceptual groundwork for public-key cryptography. The full realisation of public-key encryption came two years later with the RSA algorithm, developed by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. Their 1978 paper, 'A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,' presented a practical public-key encryption scheme, which remains the backbone of internet security today.

How RSA works

The RSA algorithm is grounded in the mathematical principles of modular arithmetic and large composite numbers. To create an RSA key pair, one begins by selecting two large prime numbers, denoted as p and q. These primes are then multiplied to produce n, a composite number that serves as the modulus for both the public and private keys. The totient, φ(n), is calculated as (p-1)(q-1). Next, a public exponent e is chosen, typically a small integer like 65537 for efficiency, that is relatively prime to φ(n). The private exponent d is derived by finding an integer such that e × d ≡ 1 (mod φ(n)). The public key is the pair (n, e), while the private key is d. Encryption of a message m is achieved by computing c = m^e mod n, which can be performed by anyone with the public key. Decryption, on the other hand, requires the private key and is done by computing m = c^d mod n. The security of RSA hinges on the difficulty of factoring n into its constituent primes, p and q. As of 2026, with n typically at least 2048 bits in size, factoring remains computationally prohibitive with classical methods. However, Shor's algorithm, proposed in 1994, poses a theoretical threat to RSA should large-scale quantum computers become viable. This has spurred the development of post-quantum cryptographic standards, such as ML-KEM and ML-DSA, endorsed by NIST from 2022 to 2024.

Why this changed everything

The advent of public-key cryptography revolutionised secure communication, enabling activities that were previously impossible. The HTTPS protocol, used to secure the majority of web traffic, relies on RSA and related algorithms to establish secure channels between users and websites they have never interacted with before. This capability underpins the global e-commerce market, facilitating approximately $7 trillion in annual transactions as of 2024, by securing payment information, authenticating sellers, and verifying transactions. Public-key cryptography also enables digital signatures, allowing for the verification of a document's origin and integrity. This is critical for software updates, cryptocurrency transactions, and legal documents. Furthermore, encrypted messaging services like Signal and WhatsApp use public-key protocols to ensure end-to-end encryption, even from the service providers themselves. Without public-key cryptography, the internet would be a vastly different environment—less commercial, with reduced privacy and weaker authentication mechanisms. The work of Diffie, Hellman, Rivest, Shamir, and Adleman laid the groundwork for the digital infrastructure that supports modern civilisation.

The British classified history

While the American breakthroughs were publicised, a parallel story unfolded in secret within the British government. At GCHQ, the British signals intelligence agency, three cryptographers independently developed ideas remarkably similar to those later articulated by their American counterparts. James Ellis, a senior cryptographer, first conceptualised 'non-secret encryption' in a 1969 memorandum. Clifford Cocks, a young mathematician, devised a scheme in 1973 that was mathematically akin to RSA. In 1974, Malcolm Williamson developed a key-exchange protocol analogous to Diffie-Hellman's method. However, the British efforts were shrouded in secrecy, classified under the Official Secrets Act, and remained unpublished. As American cryptographers brought their innovations to the public, Ellis, Cocks, and Williamson observed in silence, unable to claim credit. It wasn't until 1997 that this work was declassified, four years after Ellis's death. In a December 1997 lecture, Cocks publicly shared their contributions. Despite their lack of influence on public developments, the British team's work is recognised as an independent discovery of the same fundamental concepts, highlighting one of the most notable instances of simultaneous invention in modern science.

What it has not yet done

Despite its profound success, public-key cryptography has not solved every security challenge. Key management, particularly at large scales, remains complex. The authenticity of a public key is contingent upon a trusted certificate authority infrastructure, which has been compromised numerous times. Instances of incorrect certificate issuance, state-level surveillance interventions, and theft of private keys highlight vulnerabilities. Moreover, the security of RSA and other public-key systems depends on unproven mathematical assumptions, such as the difficulty of factoring large numbers. The potential advent of quantum computing threatens these assumptions, prompting the development of post-quantum cryptographic standards. End-to-end encryption, while beneficial for privacy, has also facilitated criminal activity, leading to ongoing debates about whether such systems should allow 'lawful access' for authorities. These issues underscore a fundamental tension between the capabilities public-key cryptography provides and the new governance challenges it introduces.

Every secure interaction on the internet today begins with a public-key exchange. Whether accessing online banking, shopping, or communicating with governmental services, the foundation of these activities lies in a protocol that starts with public-key cryptography. This involves verifying the other party's certificate with a certificate authority's public key and establishing a symmetric session key through a public-key exchange. The data transfer that follows occurs over a secure, symmetric channel. This intricate process, invisible to users, is executed billions of times every second. The underpinning mathematical framework was formalised in 1976 by Diffie and Hellman, independently anticipated by British cryptographers like Cocks a few years earlier, and brought to practical fruition by Rivest, Shamir, and Adleman in 1978. As of 2026, Whitfield Diffie continues to engage in cryptographic policy discussions, and Martin Hellman focuses on global security. Rivest, Shamir, and Adleman, whose work earned them the Turing Award in 2002, remain active in academia. Clifford Cocks, recognised with a CBE in 2008, occasionally reflects on witnessing the public rediscovery of his secretive early work. Collectively, their contributions form the bedrock of modern digital life, shaping how we communicate and transact in today's interconnected world.