Asymmetric algorithm

Asymmetric algorithms are algorithms used in cryptography that use two different keys to encrypt and decrypt the plaintext. 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.

There is no currently known asymmetric key algorithm which has been proved 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 decrytion without either key, or using only the encryption key. Such 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. Thus, mere use of asymmetric key algorithms does not ensure security, leaving aside questions of impementation errors or improper use. They are like all algorithms, aside from the one-time pad or its equivalents, in that they have not been proved unbreakable.

Some asymmetric key algorithms have the property that 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.

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 mid-70s. 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.

Asymmetric key algorithms are mostly much slower (factors of 100+ are typical) than comparably secure Symmetric 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.