The idea of public-key cryptography was invented by Diffie and Hellman in 1976 in the paper . They described a system for encoding and decoding messages where the ``key'' for encoding could be made publicly known without fear that the ``hidden key'' for decoding messages could be discovered. What they proposed for doing this was a ``trapdoor'' function for which values could be easily computed but inverse images could not be easily computed without the extra information provided by the hidden key. In other words, given only the public key and possibly an unlimited amount of encoded messages, it should be computationally infeasible to find the hidden key and thereby decipher the messages. Thus, anyone in possession of the public key may encode messages, but only someone with the hidden key may decode them. Diffie and Hellman did not advance a practical system for doing this, but within a year two competing practical systems were proposed, one based on the ``knapsack'' problem in elementary number theory (the Merkle-Hellman system) and another based on factoring large integers (the Rivest-Shamir-Adleman system, in ).
Here is a diagram of the process: