Public-key encryption

Public-key encryption is an assymetric encryption method in which 2 complementary keys are used. What gets encrypted by one of the keys can only be decrypted by the other. Generally one key of the pair is kept safe by an individual and the other key is distributed as widely as possible, after which 2 things can be done.

If a message can be decrypted using the widely distributed ("public") key, it proves that the author of the message is the individual that holds the private key. Conversely, if a message is encrypted by the public key, it can only be decrypted by the key that was kept safe (the "private" key), making it possible to send a confidential message to the holder of the private key knowing only the public key. While this is the general principle of operation, many modifications are made in order to ensure practical and quick encryption.

Well-known public-key encryption algorithms include Diffie-Hellman and RSA. In Diffie-Hellman, the hardness is based on 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 of a number in the group G. It was invented by Whitfield Diffie and Martin Hellman in 1976. The protocol proceeds in three steps:

1. Alice and Bob 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. She sends g^a mod p to Bob.
3. Bob chooses a different integer b, and sends g^b mod p to Alice.
4. Alice computes (g^b)^a, while Bob computes (g^a)^b.

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.

RSA encryption

"RSA" stands for "Rivest–Shamir–Adelman", the three MIT researchers who discovered the RSA algorithm in 1977.

RSA is based on the fundamental difficulty of factoring large integers into primes.

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.

Example

Fred needs to send documents to many people. They don't need to be secure, but its important that they know for certain that the message actually came from Fred.

• Fred encrypts the message using his private key. (only fred knows this key)
• Fred sends the encrypted message
• George gets the message (so do many other people , it's not important)
• George decrypts the message using Fred's Public key.
• Only a message coded with the private key can be decoded wth the public key so George knows it came from Fred.

• George drafts a reply and encrypts it with Freds Public key.
• only Freds private key can decrypt the message , so it is secure
• Fred receives the message and decrypts it
• it's a valid message but Fred cant know who sent it , anyone with the public key could send to him.

This form of public key encryption works best with sets of private and public keys.

See Also

1. | Public key encryption for Dummies
2. http://www2.krellinst.org/UCES/archive/modules/charlie/pke/