Asymmetric key algorithm

In cryptography, an asymmetric algorithm uses a pair of different cryptographic keys to encrypt and decrypt the plain text. Typically, the two keys are related mathematically; a message encrypted by the algorithm using one key can be decrypted by the same algorithm using the other. In a sense, one key "locks" a lock (encrypts); but a different key is required to unlock it (decrypt).

One 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 a symmetric key system, Alice first puts the secret message in a box, and then padlocks the box using a lock 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 obtained previously) to open the box, and reads the message.

In an asymmetric system, instead of opening the box when he receives it, he simply adds his own personal lock to the box, and returns the box through public mail to Alice. Alice uses her key to remove her lock, and returns the box to Bob, with Bob's lock still in place. Finally, Bob then uses his key to remove his lock, and reads the message from Alice.

The critical advantage in an asymmetric system is that Alice never needs to send a copy of her key to Bob. This reduces the possibility that a third party (for example, an unscrupulous postmaster) will copy the key while it is in transit to Bob, allowing that third party to spy on all future messages sent by Alice. In addition, if Bob is careless and allows someone else to copy his key, Alice's messages to Bob will be compromised, but Alice's messages to other people will remain secret.

Not all asymmetric algorithms operate in precisely this fashion. The most common have the property that Alice and Bob each own two keys; and one key is not (so far as is known) deducible from the other. These are the 'public key / private key' algorithms, since one key of the pair can be published without affecting security of messages. In our analogy above, Bob might publish instructions on how to make a lock ("public key"); but the lock is of a type where it is very difficult 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.

Of course, there is the possibility that someone could "pick" either of Bob's or Alice's locks. Unlike the case with 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. Their security is based on estimates of how difficult the underlying mathematical problem is to solve; and such estimates have changed with both increasing computer power, and new mathematical discoveries.

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 a known piece of 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; and it is an area of active research to discover and protect against new and unexpected attacks.

The first known asymmetric key algorithm was invented by Clifford Cocks[?] of GCHQ in the UK. It was not made public at the time, and it was reinvented by Rivest, Shamir and Adelman at MIT in the 1970s. It is usually referred to as RSA as a result. RSA relies for its security on the difficulty of factoring very large integers. A breakthrough in that field would call into question RSA's security. Currently, RSA is vulnerable to an attack by factoring the modulus part of the public key, even when keys are properly chosen, for keys shorter than perhaps 700 bits. Most authorities suggest that 1024 bit keys will be secure for some time, barring a fundamental breakthrough in factoring practice, but others favor even longer keys.

At least two other algorithms were invented after the GCHQ work, but before the RSA publication. These were the Ralph Merkle puzzle cryptographic system[?] and the Diffie-Hellman system.

A relatively new addition to the class of asymmetric key algorithms is elliptic curve cryptography. While it is more complex computationally, it is believed by many to represent a more difficult mathematical problem than either the factorisation or discrete logarithm problems which form the basis of other popular asymmetric algorithms.

One drawback of asymmetric key algorithms is that they are much slower (factors of 100+ are typical) than comparably secure symmetric key algorithms. In many quality crypto systems, both algorithm types are used. The receiver's public key encrypts a symmetric algorithm key which is used to encrypt the main message. This combines the virtues of both algorithm types when properly done.