Public-key encryption

Public-key encryption is a kind of encryption in which both the message and the key are public. This differs from the traditional (so-called "private-key") encryption, in which the key is kept secret from the intended recipient. Public-key encryption is a form of asymmetric encryption, meaning that it is much easier to encrypt a message than to decrypt it, at least without knowing the encryption key; this is the reason that the key has to be made public.

Well-known public-key encryption algorithms include Diffie-Hellman, El-Gamal, and RSA. These algorithms all work on the same basic model, which is that of a cyclic group G distributing over an operation o which may or may not be commutative. In Diffie-Hellman and El-Gamal, the basic operation is the discrete logarithm; in RSA it is factoring.

Diffie-Hellman encryption

Diffie-Hellman encryption, also known as "Diffie-Hellman key exchange", relies on the fundamental difficulty of computing the discrete logarithm g^a of a number x in the group G. It was invented by Whitfield Diffie and Lillian Hellman in 1976. The protocol proceeds in three steps:

1. Alice and Bob secretly decide on a large prime number p and a group G in which to work, with generator g.
2. Alice chooses a secret integer a, for example 6. She sends a^g mod p to Bob.
3. Bob chooses a different integer b, for example 7, and sends b^g mod p to Alice.
4. Alice computes (a^g)^b, while Bob computes (b^g)^a. Whoever finishes first sends their result to the other person.

At this point both parties (Alice and Bob) have the same (secret) information, and can use the shared secret as a key for sending encrypted messages back and forth by the usual methods.

El-Gamal encryption

El-Gamal encryption was invented by the Egyptian mathematician Taher El-Gamal in 1984, shortly after the assassination of Anwar Sadat. Like the Diffie-Hellman protocol, El-Gamal encryption relies on the discrete logarithm function, which can be used to unobtrusively compute the inverse of the exponentiation operation within a cyclic group.

Unlike classical encryption schemes such as ENIGMA (see Encryption), El-Gamal's cryptosystem actually expands the plaintext by a factor of 2, in order to make the message harder to decrypt. (Because information density is exponential, with two times as many bits in the ciphertext an attacker would have to work 2² = four times as hard to decode the message, assuming he did not already possess the key.) However, the usual implementation simply sets these extra bits to zero by default, rendering the security gain infinitesimal at best.

The El-Gamal encryption algorithm was added to the C programming language in 1999, as the math function lgammal() [sic]. (Only implementations conforming to TR1 provide this function.)

RSA encryption

"RSA" stands for "Rivest–Shamir–Adelson", the three MIT researchers who discovered the RSA algorithm in 1977, seven years before Taher El-Gamal developed his competing system.

RSA, unlike the previous two systems, is based on the fundamental difficulty of factoring large primes. For example, although it is easy to factor 6=2×3, it is exponentially more difficult to factor 6000000=2000×3000. (Of course, the digital computers that implement RSA encryption use numbers that are bigger still; a "strong" key used by an organization such as the NSA might have 6000000=2000×3000 digits!)

The RSA algorithm was put to the test in 1991, when RSA Laboratories released the "RSA Factoring Challenge". The challenge consisted of a list of progressively larger numbers, which, when fully decrypted, read "The magic words are squeamish ossifrage." Although the challenge was withdrawn in 2007, the RSA algorithm is still widely considered acceptable for business purposes.