Main Page | See live article | Alphabetical index

Public-key cryptography

Asymmetric-key cryptography, also known as public-key cryptography, is a form of cryptography in which two digital "keys" are generated, one private and one public. These keys are used for encrypting or signing messages -- one key is used to encrypt a message and another is used to decrypt it, or one key is used to sign a message and another is used to verify the signature. The public key can encrypt or sign messages that can only be verified using the private key, and vice-versa, so it is critical that the private key be kept secret. Currently known asymmetric key algorithms are all computationally intensive (ie, slow, even on fast computers) and so such keys are nearly always digital (ie, bit sequences). They need not, but in practice will probably continue to, be.

The public key of a pair can be known by anyone since, for some of these algorithms, there is no known way to deduce one key of a pair given the other. But it is critical to the security of messages encrypted by these algorithms that the corresponding private key of a pair be kept absolutely secret. The creation of these public/private pairs must be done with great care, must be effectively random and not predictable by an attacker, and must meet the requirements of the asymmetric key algorithm with which they are to be used. Like all key management, this is not trivially done.

The theory behind asymmetric key algorithms was first published by Whitfield Diffie and Martin Hellman in 1975, and since then, several implementations have been created. One widely-used asymmetric key algorithm is RSA. It uses exponentiation modulo a product of two large primes to encrypt and decrypt. The public key exponent differs from the private key exponent, and determining one exponent from the other is believed to be fundamentally hard without knowing the primes. Another is ElGamal (developed by Taher ElGamal then of Netscape) which relies on the difficulty of the discrete logarithm problem. A third is a group of algorithms based on elliptic curves, first discovered by Neil Koblitz in the late '80s.

Note that there is nothing 'special' about asymmetric key algorithms. There are good ones, bad ones, insecure ones, etc. None have been proved 'secure' in the sense the one-time pad has, and some are known to be insecure (ie, easily broken). Some have the public key / private key property in which one of the keys is not deduceable from the other; or so it is believed by knowledgeable observers. Some do not, it having been demonstrated that knowledge of one key gives an attacker the other. As with all cryptographic algorithms, these must be chosen and used with care.

Public-key algorithms can be used, depending on the protocol, for either confidentiality or sender authentication. For instance, a user can encrypt a message with their private key and send it. That it can be decrypted using the corresponding public key provides assurance that that user (and no other) sent it. Unless the private key has been compromised, of course. These algorithms can also be used for confidentiality; a message which is encrypted by the receipient's public key can only be decrypted by a person in possession of the paired private key.

Note that so far, all these algorithms are very computationally costly, especially in comparison with many symmetric key algorithms of essentially equivalent security. This fact has important implications for practical use of the these algorithms.

Examples of well regarded asymmetric key algorithms include:

examples of not well regarded asymmetric key algorithms include: examples of protocols using asymmetric key algorithms include: See also: GNU Privacy Guard, Pretty Good Privacy, Secure Sockets Layer, Secure Shell, pseudonymity, Quantum cryptography, Key escrow, public key infrastructure (PKI).