Asymmetric key cryptography

In contrast with symmetric encryption, asymmetric encryption, a user has their computer produce two different keys, related mathematically so that data encrypted with one can only be decrypted with the other. One key is the public key and can be published. The other is the private key and is kept secret, never leaving the user's computer. "Public" need not mean that it be available to anyone who requests it; it is used relative to only authorized users in an organization. Many military cryptosystems use asymmetric encryption, but the average person would not be able to obtain the public key for a high-security network such as JWICS.

The method was first published in a 1976 paper by Whitfield Diffie and Martin Hellman. . Public key cryptography is constructed so that calculation of the private key is computationally infeasible from knowledge of the public key, even though they are necessarily related. Instead, both keys are generated secretly, as an interrelated pair. The historian David Kahn described public-key cryptography as "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance".

The encryption alone does not make a complete system. Public key infrastructure is necessary, which consists of a set of services for generating the key pair and securely sending the public key to a repository, for users to obtain public keys, determine that they are valid, let the issuer revoke one when necessary, etc.

There were some cryptanalytic vulnerabilities, however, until Diffie and Hellman showed that public-key cryptography was possible by presenting the Diffie-Hellman key exchange protocol. In 1978, Ronald Rivest, Adi Shamir, and Len Adleman invented the RSA algorithm, another public-key system It had been released as an MIT "Technical Memo" in April 1977, and published in Martin Gardner's Scientific American "Mathematical Recreations" column. In 1997, it finally became publicly known that asymmetric cryptography had been invented by James H. Ellis at GCHQ, a British intelligence organization, in the early 1970s, and that both the Diffie-Hellman and RSA algorithms had been previously developed (by Malcolm J. Williamson and Clifford Cocks, respectively).

Unlike symmetric encryption which assumes both sender and receiver already know the private key, public-key exchange allows you to securely issue a key to anyone so that person can then send you encrypted information. Only the intended recipient can read the ciphertext, by applying a private decryption key. A separate key pair is needed for each direction of transmission.

Mathematical basis

Public-key algorithms are most often based on the computational complexity of "hard" problems, often from number theory. The hardness of RSA is related to the integer factorization problem, while Diffie-Hellman and DSA are related to the discrete logarithm problem. More recently, elliptic curve cryptography has developed in which security is based on number theoretic problems involving elliptic curves. Methods have also been proposed based on the subset sum problem (though those have been broken) and the algebra of braid groups.

Because of the complexity of the underlying problems, most public-key algorithms involve operations such as modular multiplication and exponentiation, which are much more computationally expensive than the techniques used in most block ciphers, especially with typical key sizes. As a result, public-key cryptosystems are commonly "hybrid" systems, in which a fast symmetric-key encryption algorithm is used for the message itself, while the relevant symmetric key is sent with the message, but encrypted using a public-key algorithm. Similarly, hybrid signature schemes are often used, in which a cryptographic hash function is computed, and only the resulting hash is digitally signed.

Generating session keys

Public-key encryption is slower than conventional symmetric encryption. The primary usage of public-key encryption is in hybrid cryptosystems where a symmetric algorithm does the bulk data encryption while the public key algorithm provides other services. For example, in PGP email encryption the sender generates a random key for the symmetric bulk encryption and uses public key techniques to securely deliver it to the receiver. In the Diffie-Hellman key agreement protocol, used in IPsec and other systems, public key techniques provide authentication.

An advantage of asymmetric over symmetric cryptosystems is that all symmetric system keys must be kept secret, and the logistics of key management become complex. Asymmetric systems allow public keys to be distributed freely.

Digital signatures

In addition to encryption, public-key cryptography can be used to implement digital signature schemes. A digital signature is somewhat like an ordinary signature; they have the characteristic that they are easy for a user to produce, but difficult for anyone else to forge. Digital signatures can also be permanently tied to the content of the message being signed; they cannot be 'moved' from one document to another, for any attempt will be detectable. In digital signature schemes, there are two algorithms: one for signing, in which a secret key is used to process the message (or a hash of the message or both), and one for verification, in which the matching public key is used with the message to check the validity of the signature. RSA and DSA are two of the most popular digital signature schemes. Digital signatures are central to the operation of public key infrastructures and to many network security schemes (SSL/TLS, many VPNs, etc). Diffie-Hellman and RSA, in addition to being the first publicly known examples of high quality public-key cryptosystems, have been among the most widely used. Others include the Cramer-Shoup cryptosystem, ElGamal encryption, and various elliptic curve techniques.