Public-key cryptography was invented in 1976 by Whitfield Diffie and
Martin Hellman in order to solve the key management problem. In the new
system, each person gets a pair of keys, called the public key and the
private key. Each person's public key is published while the private
key is kept secret. The need for sender and receiver to share secret
information is eliminated: all communications involve only public keys,
and no private key is ever transmitted or shared. No longer is it
necessary to trust some communications channel to be secure against
eavesdropping or betrayal. Anyone can send a confidential message just
using public information, but it can only be decrypted with a private
key that is in the sole possession of the intended recipient.
Furthermore, public-key cryptography can be used for authentication
(digital signatures) as well as for privacy (encryption).
Here's how it works for encryption: when Alice wishes to send a message
to Bob, she looks up Bob's public key in a directory, uses it to
encrypt the message and sends it off. Bob then uses his private key to
decrypt the message and read it. No one listening in can decrypt the
message. Anyone can send an encrypted message to Bob but only Bob can
read it. Clearly, one requirement is that no one can figure out the
private key from the corresponding public key.
Here's how it works for authentication: Alice, to sign a message, does a computation involving both her private key and the message itself; the output is called the digital signature and is attached to the message, which is then sent. Bob, to verify the signature, does some computation involving the message, the purported signature, and Alice's public key. If the results properly hold in a simple mathematical relation, the signature is verified as genuine; otherwise, the signature may be fraudulent or the message altered, and they are discarded.