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 messages that can only be decrypted using the private key, and only the private key can create signatures that are verifiable using the public key, 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 don't have to be, but in practice will probably remain digital.

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 neither trivially, nor easily, done.

Furthermore, the binding between a public key and its 'owner' must be correct, lest the algorithm function perfectly and yet be entirely insecure in practice. As with most cryptography, the protocols used to establish and verify this binding are critically important. Associating a public key with its owner is typically done by protocols implementing a public key infrastructure; these allow the validity of the association to be formally verified by reference to a 'trusted third party', either in the form of a hierarchical Certificate Authority (eg, X.509) or a statistical Web of Trust (eg, PGP and GPG). It's important to note that whatever the cryptographic assurance of the protocols themselves, the association between a public key and its owner is ultimately a matter of subjective judgement on the part of the 'trusted third party', since the key is a mathematical entity while the owner is not. For this reason, the formalism of a public key infrastructure provides for explicit statements of the policy followed when making this judgement. For example, the X.509 standard allows a certificate authority to identify its policy by means of an object identifier which functions as an index into a catalogue of registered policies. Policies may exist for many different purposes, ranging from anonymity to military classification.

The first asymmetric key algorithm was invented in secrecy by Clifford Cocks (then a recent mathematics graduate and a new staff member at GCHQ in the UK) early in the 1970s, and reinvented by Rivest, Shamir and Adelman all then at MIT. Their work was published in 1976. Since then, several other asymmetric key algorithms have been developed, but the most widely known remains Cocks/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 from the other is believed to be fundamentally hard without knowing the primes; these are in turn (if large enough) computationally infeasible to determine at the current state of the computer hardware and large integer factorization arts. Another is ElGamal (invented by Taher ElGamal then of Netscape) which relies on the (similar, and related) difficulty of the discrete logarithm problem. A third is a group of algorithms based on elliptic curves, first discovered by Neal Koblitz in the mid '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 informed attacker the other. As with all cryptographic algorithms, these algorithms 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 their practical use. Most are used in hybrid crypto systems for reasons of efficiency.

Examples of well regarded asymmetric key algorithms include:

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