Public-key cryptography

Asymmetric-key cryptography, also known as public-key cryptography, is a form of cryptography in which asymmetric key algorithms are used for encryption, signature, etc. In these algorithms, 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 key used to decrypt or sign must be kept secret ('private') and cannot (so algorithm designers hope) be derived from the public key, which is used to encrypt or verify, and which may be known to any.

Several asymmetric key algorithms have been developed beginning in the 1970s. One widely-used 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 fundamentally hard without knowing the primes. Another is ElGamal (developed by Taher ElGamal) which relies on 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 for either confidentiality or sender authentication. A user can encrypt a message with their private key and send it. That it can be decrypted by the 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 to 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.

Examples of well regarded asymmetric key algorithms include:

• RSA encryption algorithm
• ElGamal
• elliptic curve encryption algorithms

examples of not well regarded asymmetric key algorithms include:

• Merkle-Hellman the 'knapsack' algorithms

examples of protocols using asymmetric key algorithms include:

• DSS Digital Signature Standard which incoporates the Digital Signature Algorithm
• PGP
• GPG an implementation of OpenPGP
• ssh
• Secure Socket Layer now implemented as an IETF standard -- TLS

See also: GNU Privacy Guard, Pretty Good Privacy, Secure Sockets Layer, Secure Shell, pseudonymity, Quantum cryptography, Key escrow, public key infrastructure (PKI).