Public-key cryptography is the method that allows two parties who have never met, and who are communicating over a channel anyone can read, to establish a shared secret. It is the reason online banking, encrypted messaging, and secure browsing are possible, and its invention in the 1970s solved a problem that had defeated cryptographers for two thousand years.

Every earlier cipher required both parties to already share a secret key. That works between two embassies willing to send a courier, and it fails completely for commerce between strangers: the number of keys required grows with the square of the number of participants, and there is no safe way to distribute them at scale.

In 1976 Whitfield Diffie and Martin Hellman published a method by which two parties could agree on a shared secret over a public channel, using mathematical operations that are easy to perform and hard to reverse. An eavesdropper who sees everything transmitted still cannot feasibly compute the resulting key. Shortly afterwards Ron Rivest, Adi Shamir, and Leonard Adleman produced RSA, which also allowed digital signatures, so a message could be proved to come from a particular sender.

It later emerged that researchers at the British signals agency GCHQ, principally James Ellis, Clifford Cocks, and Malcolm Williamson, had discovered equivalent methods several years earlier, but the work was classified and could not be published or used commercially.

Whitfield Diffie, who with Martin Hellman published in 1976 the first public method for two parties to agree a shared secret over a channel that anyone can read.
Whitfield Diffie, who with Martin Hellman published in 1976 the first public method for two parties to agree a shared secret over a channel that anyone can read.Credit: Duncan.Hull (CC BY-SA 4.0).
Martin Hellman. The Diffie-Hellman key exchange made secure communication between strangers possible and underpins most encrypted traffic on the internet today.
Martin Hellman. The Diffie-Hellman key exchange made secure communication between strangers possible and underpins most encrypted traffic on the internet today.Credit: User .:Ajvol:. on en.wikipedia (CC BY-SA 3.0).

A precise distinction matters here. The protocols are proved correct: given the assumptions, the mathematics is sound and the security proofs are rigorous. What is not proved is that the underlying problems, such as factoring large numbers or computing discrete logarithms, are actually hard. No one has proved a lower bound on their difficulty. Their security rests on the fact that a great many capable people have tried and failed to break them, which is strong evidence and not a proof.

This is why a proof that P equals NP would be so consequential, and why quantum computing matters: Shor's algorithm, if run on a sufficiently large quantum computer, would break both factoring and discrete logarithms. That prospect has driven the development of post-quantum cryptography, built on mathematical problems believed to resist quantum attack.

Adi Shamir, the S in RSA. The algorithm he developed with Ron Rivest and Leonard Adleman added digital signatures, allowing a message to be proved to come from a particular sender.
Adi Shamir, the S in RSA. The algorithm he developed with Ron Rivest and Leonard Adleman added digital signatures, allowing a message to be proved to come from a particular sender.Credit: Ira Abramov from Even Yehuda, Israel (CC BY-SA 2.0).