Public-key cryptography

Public key cryptography is a form of cryptography which generally allows users to communicate securely without having prior access to a shared secret key. This is done by using a pair of cryptographic keys, designated as public key and private key, which are related mathematically.

The term asymmetric key cryptography is a synonym for public key cryptography though a somewhat misleading one. There are asymmetric key encryption algorithms that do not have the public key-private key property noted above. For these algorithms, both keys must be kept secret, that is both are private keys.

In public key cryptography, the private key is kept secret, while the public key may be widely distributed. In a sense, one key "locks" a lock; while the other is required to unlock it. It should not be possible to deduce the private key of a pair given the public key, and in high quality algorithms no such technique is known.

There are many forms of public key cryptography, including:

public key encryption — keeping a message secret from anyone that does not possess a specific private key.
public key digital signature — allowing anyone to verify that a message was created with a specific private key.
key agreement — generally, allowing two parties that may not initially share a secret key to agree on one.

Typically, public key techniques are much more computationally intensive than purely symmetric algorithms, but the judicious use of these techniques enables a wide variety of applications.

History

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 shared key beforehand.

In 1874, a book by William Stanley Jevons Jevons, William Stanley, The Principles of Science: A Treatise on Logic and Scientific Method, Macmillan & Co., London, 1874, 2nd ed. 1877, 3rd ed. 1879. Reprinted with a foreword by Ernst Nagel, Dover Publications, New York, NY, 1958. described the relationship of one-way functions to cryptography and went on to discuss specifically the factorization problem used to create the trapdoor function in the RSA system. In July 1996, one observer Solomon W. Golomb, On Factoring Jevons' Number, CRYPTOLOGIA 243 (July 1996). commented on the Jevons book in this way:

In his book The Principles of Science: A Treatise on Logic and Scientific Method, written and published in the 1890's The 1890s date for the publication of Jevons' book in this quotation is incorrect., William S. Jevons observed that there are many situations where the 'direct' operation is relatively easy, but the 'inverse' operation is significantly more difficult. One example mentioned briefly is that enciphering (encryption) is easy while deciphering (decryption) is not. In the same section of Chapter 7: Introduction titled 'Induction an Inverse Operation', much more attention is devoted to the principle that multiplication of integers is easy, but finding the (prime) factors of the product is much harder. Thus, Jevons anticipated a key feature of the RSA Algorithm for public key cryptography, though he certainly did not invent the concept of public key cryptography.

The first invention The NSA has also claimed to have invented public-key cryptography, in the 1960s; however, there is currently (as of 2004) little supporting public evidence for this claim ^*. of asymmetric key algorithms was by James H. Ellis, Clifford Cocks, and Malcolm Williamson at GCHQ in the UK in the early 1970s; these inventions were what later become known as Diffie-Hellman key exchange, and a special case of RSA. This fact was kept secret until 1997.

An asymmetric key cryptosystem was published in 1976 by Whitfield Diffie and Martin Hellman, who, influenced by Ralph Merkle's work on public key distribution, disclosed a method of public key agreement. This method of exponential key exchange, which came to be known as Diffie-Hellman key exchange, was the first published practical method for establishing a shared secret key over an unprotected communications channel without using a prior shared secret. Merkle's public key agreement technique known as Merkle's Puzzles was published in 1978.

The Cocks method was reinvented in 1977 by Rivest, Shamir and Adleman, all then at MIT. The latter authors published their work in 1978, and the algorithm appropriately came to be known as RSA. RSA uses exponentiation modulo a product of two large primes to encrypt and decrypt, performing both public key encryption and public key digital signature, and its security is connected to the presumed difficulty of factoring large integers, a problem for which there is no known efficient (i.e., practicably fast) general technique.

Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed in the field of public key cryptography. The ElGamal cryptosystem (invented by Taher ElGamal then of Netscape) relies on the (similar, and related) difficulty of the discrete logarithm problem, as does the closely related DSA developed by the NSA and NIST. The introduction of elliptic curve cryptography by Neal Koblitz in the mid 1980s has yielded a new family of analogous public key algorithms. Although mathematically more complex, elliptic curves appear to provide a more efficient way to leverage the discrete logarithm problem, particularly with respect to key size.

Security

Regarding security, there is nothing especially more secure about asymmetric key algorithms than symmetric key algorithms. There are popular ones and unpopular ones. There are broken ones and ones that are, for now, not broken. Unfortunately, popularity is not a reliable indicator of security. Some algorithms have security proofs with various properties, and of varying quality. Many proofs claim that breaking an algorithm, with respect to some well-defined security goals, is equivalent to solving one of the more popular mathematical problems that are presumed to be intractable, like factoring large integers or finding discrete logarithms. Some proofs have also been shown to be broken. In general, none of these algorithms have been proved secure in as absolute a sense as the one-time pad has. As with all cryptographic algorithms, these algorithms must be chosen and used with care.

Applications

The most obvious application of a public key encryption system 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.

Public-key digital signature algorithms can be used for sender authentication and non-repudiation. 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.

To achieve authentication, non-repudiation and confidentiality, the sender would first encrypt the message using his private key, then a second encryption is performed using the recipient's public key.

These characteristics are useful for many other, sometimes surprising, applications, like digital cash, password-authenticated key agreement, multi-party key agreement, etc.

Practical considerations

A postal analogy

An analogy which can be used to understand the advantages of an asymmetric system is to imagine two people, Alice and Bob, sending a secret message through the public mail. In this example, Alice has the secret message and wants to send it to Bob, after which Bob sends a secret reply.

With a symmetric key system, Alice first puts the secret message in a box, and then locks the box using a padlock to which she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he uses an identical copy of Alice's key (which he has somehow obtained previously, maybe by a face-to-face meeting) to open the box, and reads the message. Bob can then use the same padlock to send his secret reply.

In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.

The critical advantage in an asymmetric key system is that Bob and Alice never need send a copy of their keys to each other. This substantially reduces the chance that a third party (perhaps, in the example, a corrupt postal worker) will copy a key while it is in transit, allowing said third party to spy on all future messages sent between Alice and Bob. In addition, if Bob were to be careless and allow someone else to copy his key, Alice's messages to Bob would be compromised, but Alice's messages to other people would remain secret, since the other people would be providing different padlocks for Alice to use.

Actual algorithms — two linked keys

Not all asymmetric key algorithms operate in precisely this fashion. The most common have the property that Alice and Bob each own two keys, one for encryption and one for decryption. In a secure asymmetric key encryption scheme, the decryption key should not be deducible from the encryption key. This is known as public-key encryption, since the encryption key can be published without compromising the security of encrypted messages. In the analogy above, Bob might publish instructions on how to make a lock ("public key"), but the lock is such that it is impossible (so far as is known) to deduce from these instructions how to make a key which will open that lock ("private key"). Those wishing to send messages to Bob use the public key to encrypt the message; Bob uses his private key to decrypt it.

Weaknesses

Of course, there is the possibility that someone could "pick" Bob's or Alice's lock. Unlike the case of the one-time pad or its equivalents, there is no currently known asymmetric key algorithm which has been proven to be secure against a mathematical attack. That is, it is not known to be impossible that some relation between the keys in a key pair, or a weakness in an algorithm's operation, might be found which would allow decryption without either key, or using only the encryption key. The security of asymmetric key algorithms is based on estimates of how difficult the underlying mathematical problem is to solve. Such estimates have changed both with the decreasing cost of computer power, and with new mathematical discoveries.

This might not be as weak as imagined though. If an estimate of how long (by brute force) it takes to crack a code is say 1000 years (and there is no better attack found) then if it were used to encrypt your credit card details, they would be perfectly safe – because the time to decrypt the details is longer than the useful life of those details (your credit card expires after a few years).

Weaknesses have been found for promising asymmetric key algorithms in the past. The 'knapsack packing' algorithm was found to be insecure when an unsuspected attack came to light. Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys. Thus, use of asymmetric key algorithms does not ensure security; it is an area of active research to discover and protect against new and unexpected attacks.

Another potential weakness in the process of using asymmetric keys is the possibility of a 'Man in the middle attack', whereby the communication of public keys is intercepted by a third party and modified to provide the third party's own public keys instead. The encrypted response also must be intercepted, decrypted and re-encrypted using the correct public key in all instances however to avoid suspicion, making this attack difficult to implement in practice. The attack is not impossible, and an evil staff member at Alice or Bob's ISP might find it outright easy. This form of attack is being addressed by the development of key distribution methods that can ensure sender authenticity and message integrity, even over insecure channels. This attack is especially interesting when the attacker is the government: They potentially have the power to persuade a Certificate Authority to sign a bogus public key. Then the government can plug off the cable at Bob's ISP and insert their bogus web server. The function of this server is to present itself as Alice (validated by the certificate obtained by coercion), log all messages and forward them to the "real" Alice web server.

Computational cost

Note that most public key algorithms are relatively computationally costly, in comparison with many symmetric key algorithms of apparently 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 shared secret key ("session key") is generated by one party, this much briefer session key is then encrypted by each recipient's public key. Each recipient uses the corresponding private key to decrypt the session key. Once all parties have obtained the session key, they can use a much faster symmetric algorithm to encrypt and decrypt messages.

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 (e.g., X.509), a local trust model (e.g., SPKI), or a statistical web of trust (e.g., 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.

Relation to real time

A public key is known to a large and possibly unknown set of users. All security-related events requiring a public key to be revoked or replaced can take a long time to complete. For this reason, systems that must be able to react to events in real time (safety-critical systems) should not apply public-key encryption without taking great care. There are four issues of interest.

Privilege of key revocation

A malicious (or erroneous) revocation of some or all of the keys in the system is likely to cause a system-wide failure. This is always a possibility if the keys can all be revoked individually. However, one can greatly reduce the chance of this occurring. For example, by means of certificates we can create what is called a "compound principal"; one such principal could be "Alice and Bob have Revoke Authority". Now only Alice and Bob (in concert) can revoke a key, and neither Alice nor Bob can revoke keys alone. However, revoking a key now requires both Alice and Bob to be available, and this creates a problem of reliability. In concrete terms, from a security point of view there is now a single point of failure in the system: A successful Denial of Service attack against either Alice or Bob (or both) will paralyze the authority to revoke. In fact, any partition between Alice and Bob will have this effect, regardless of how it comes about.

Because the principal having authority to revoke keys is very powerful, the mechanisms used to control it should involve as many participants as possible to guard against malicious attacks, while at the same time as few as possible to ensure that a key can be revoked without delay.

Distribution of a new key

After a key has been revoked, a new key must be distributed in some pre-determined manner.

Assume that Carol's key has been revoked. Until a new key has been disseminated, Carol is effectively silenced. No one will be able to send her data without violating system security, and data coming from her will be discarded for the same reason. Or, in other words, the part of the system controlled by Carol is disconnected and so unavailable. The need for security was deemed higher than the need for availability in this design. One could lump together the authority to create new keys (and certify them) with the authority to revoke keys, but there is no need to do so. In fact, for reasons of security, this is likely a bad idea. The problem is that on the one hand the message revoking the key should be spread as fast as possible while on the other hand, (parts of) the system might be paralyzed before a new key can be installed. The time window can obviously be made to be zero by always issuing the new key together with the certificate that revokes the old one, but this again requires a co-location of the authority that revokes and the one that "restarts" the system. It is most likely a system-wide failure if the (possibly combined) principal that issues new keys fails by issuing unwarranted keys. As usual, one can make the reliability of this service as high as one deems necessary at the cost of availability.

Spreading the revocation

The notification that a key has been revoked and should not be used again must be spread to all those that potentially hold the key, and as rapidly as possible.

There are two means of spreading information (e.g., a key revocation here) in a distributed system: either the information is pushed to users from a central point(s), or it is pulled from a central point(s) to end users.

Pushing the information is the simplest solution in that a message is sent to all participants. However, there is no way of knowing that all participants actually receive the message, and if the number of participants is large and their physical distance great, the probability of complete success (ideally, required for system security) of this approach will be rather low. In this state the system is particularly vulnerable to denial of service attacks as security has been breached and the window is open as long as messages are hindered. In other words, pushing is not very securable nor very reliable.

The alternative to pushing is pulling. In this setup, all keys are included within a certificate that requires the one using them to verify that the key is valid. The problem is that in this case the user is blocked if he can not reach the verification service. Again, this service can be made as reliable as one wishes, at the cost of lowering security (the more servers to update in case of a revocation the longer the window of vulnerability).

Another tradeoff is to use a somewhat less reliable but more secure verification service, but issue the verification certificates with a lifetime. But, again, how long this timeout is, will again be a tradeoff between availability and security that needs to be determined in advance, at system design or revision time.

Recovery from a leaked key

Assume that the principal authorized to revoke a key has decided that a certain key must be revoked. In most cases this happens after the fact; it becomes known that at some time in the past an event occurred that endangered the (secret part of a) public key. Let us denote the time at which it is decided that the compromise occurred with T.

The compromise has two implications: Messages encrypted with the public key (at any time) can no longer be assumed to be secret, and signatures made with the key after time T can no longer be assumed to be authentic without scrutinizing of the events leading up to where the signature being made.

If loss of secrecy and/or authenticity is a system-wide failure, a strategy for recovery must be in place. This strategy will determine who has authority to revoke the key, how to spread the revocation, but also how to deal with all messages encrypted with the key since time T. This recovery procedure can be utterly complicated, and while it is in progress the system might be very vulnerable against Denial of Service attacks, among other things.

Examples

Examples of well-regarded public key techniques include:

Diffie-Hellman
DSS (Digital Signature Standard), which incorporates the Digital Signature Algorithm
ElGamal
Various Elliptic Curve techniques
Various Password-authenticated key agreement techniques
Paillier cryptosystem
RSA encryption algorithm (PKCS)

Examples of poorly regarded asymmetric key algorithms include:

Merkle-Hellman the 'knapsack' algorithms

Examples of protocols using asymmetric key algorithms include:

GPG an implementation of OpenPGP
IKE
PGP
ssh
Secure Socket Layer now implemented as an IETF standard -- TLS
SILC

Notes

External links

An account of how GCHQ kept their invention of PKE secret until 1997

Cryptography | Asymmetric-key cryptosystems

Gourt Home::Gourt :: Public-key cryptography