Public-key cryptography
|
|
Public-key cryptography is a form of modern cryptography which allows users to communicate securely without previously agreeing on a shared secret key. For most of the history of cryptography, a key had to be kept absolutely secret and would be agreed upon beforehand using a secure, but non-cryptographic, method; for example, a face-to-face meeting or a trusted courier. There are a number of significant practical difficulties in this approach to distributing keys. Public-key cryptography was invented to address these drawbacks — with public-key cryptography, users can communicate securely over an insecure channel without having to agree upon a key beforehand.
Public-key algorithms typically use a pair of two related keys — one key is private and must be kept secret, while the other is made public and can be widely distributed; it should not be possible to deduce one key of a pair given the other. The terminology of "public-key cryptography" derives from the idea of making part of the key public information. The term asymmetric-key cryptography is also used because not all parties hold the same information. Some public-key algorithms operate a little differently, and use other methods to enable parties to agree on secret keys without having previously exchanged key material.
Public-key cryptography has two main applications. First, is encryption — keeping the contents of messages secret. Second, digital signatures can be implemented using public key techniques. Typically, public-key techniques are much more computationally intensive than symmetric algorithms.
| Contents |
History
The first asymmetric key algorithm was invented, secretly, 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 Adleman all then at MIT. Their work was published in 1976, and the algorithm was named RSA after the initials of their last names. 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 algorithm 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.
The NSA — the US signals security agency — has also claimed to have invented public-key cryptography, in the 1960s; however, there is currently (as of 2004) little supporting evidence for their claims [1] (http://www.research.att.com/~smb/nsam-160/).
Security
Regarding security, there is nothing special about asymmetric key algorithms. There are good ones, bad ones, insecure ones, etc; none have been proved secure in the absolute sense the one-time pad has, and some are known to be quite insecure. As with all cryptographic algorithms, these algorithms must be chosen and used with care.
Applications
The most obvious application is confidentiality; a message which a sender encrypts using the recipient's public key can only be decrypted by the recipient's paired private key.
In many cases, public-key algorithms can be used for sender authentication. For instance, a user can encrypt a message with his own private key and send it. If another user can successfully decrypt it using the corresponding public key, this provides assurance that the first user (and no other) sent it.
Similarly, in the other direction, a user can be assured that a message using the proper key originates from a specific source.
See also digital signature.
Practical considerations
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 cryptosystems for reasons of efficiency; in such a cryptosystem, a secret key ("session key") is generated for each message and used to encrypt the message; the much briefer session key is then encrypted to each recipient's public key. The recipient uses the corresponding private key to decrypt the session key, which she then uses to decrypt the message.
Associating public keys with identities
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), a local trust model (eg, SPKI), or a statistical web of trust (eg, PGP and GPG). 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 whilst the owner and the connection between owner and key 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.
Examples
Examples of well-regarded asymmetric key algorithms include:
- Diffie-Hellman
- RSA encryption algorithm
- ElGamal
- Elliptic curve cryptography
- Paillier cryptosystem
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).de:asymmetrischer Verschlüsselungsalgorithmus
fr:Cryptographie asymétrique it:Crittografia asimmetrica ja:公開éµæš—å· nl:Asymmetrische cryptografie pl:Kryptografia asymetryczna pt:Criptografia de chave pública