public-key encryption

A method of encryption by which secure communications may be established without initially using a secure channel. Relies on keys being in two parts: a public and private half. Each half may decode the messages encoded by the other, so messages encoded&with the public key may only be read by the intended recipient. Popularized by PGP. See also asymetrical.

An encryption method in which all involved parties have two keys. A public key which is known to all, and freely available, and a private key which is known only to the owner of the key. A message encrypted with the public key can only be decrypted with the correspoinding private key. This allows secure communication between people who do not nessecarily know of each others existance. PGP uses a hybrid version of public-key encryption and symmetric encryption.

Another useful part of public-key encryption is authentication in digital communication. "Normal" public key encryption of a message from Albert to Betty might go something like this:

|<--Albert's computer -->|<--transmission-->|<--Betty's Computer----->|

source --> encryption  ---------------------> decryption --> plaintext
            algorithm                         algorithm
               ^                                  ^
               |                                  |
               |                                  |
        Betty's Public                      Betty's Private
              Key                                  Key

However, there is a problem with this sequence: when Betty recieves the message, she knows that she's the only one who could read it but she can't be sure that Albert is the one who sent it. So what's a couple of paranoids to do? Use the other feature of public-key encryption -- digital signatures. It could go like this:

|<-------------Albert's computer -->|<--transmission-->|<--Betty's Computer---------------->|

source --> encryption --> encryption ----------------> decryption --> decryption--> plaintext
            algorithm      algorithm                   algorithm      algorithm
               ^               ^                            ^             ^
               |               |                            |             |
               |               |                            |             |
        Betty's Public   Albert's Private           Albert's Public   Betty's Private
              Key               Key                        Key              Key

So, Betty recieves an encrypted message claiming to be from Albert; to prove this, she attempts to decrypt the message with the public key she has for Albert. She then decrypts the message using her private key, sees his message, and knows for sure that he's the one who sent it¹.

1: That is, she knows for sure if and only if she can trust her public key for Albert. If that was somehow compromised (for instance, if the authority from which she acquired his public key was hacked), it is concievable that she could be using a public key for, say, Colin the opponent, who signed the message using a private key after planting the matching public key in the authority's database. This also depends on the algorithm used to generate the keys and the one used in the encryption/decryption. If the key generation isn't random, an opponent may be able to guess the private key that matches the freely available public key, and impersonate anyone. Additionally, if the encryption/decryption process isn't completely infeasible to attack, a naughty person could snoop on the encrypted messages during the transmission phase.

A few background issues about public-key cryptography (I'll use the traditional names "Alice" and "Bob" for the parties communicating, with "Alice" sending messages and "Bob" receiving them if the communication is one-way.)

• All public key cryptography is based around some mathematical problem that is believed to be hard to solve in the general case, but becomes trivial with some extra piece of information, a so-called trapdoor function. For RSA this is factoring (though RSA is not proved to be as strong as factoring - in fact, it is proven that an oracle against RSA will not help in cracking factoring), and for Diffie-Hellman, ElGamal, DSA, KEA, etc it is Discrete Logarithms. Systems has been attempted built on other problems, but none of them has so far gained full trust.
• Public key cryptography is usually expensive. As a result of this, it is used sparingly when designing cryptographic protocols. For instance, the cryptographic protocol described by flamingweasel above wouldn't actually be used - instead, you would use this protocol for a randomly generated key for a symmetric cipher.
• flamingweasel mention that the private key may be available if the key generation process isn't completely random. This is correct, and it is the most common failure when implementing cryptography. However, the private key can be calculated from the public key, too. This is what the trapdoor function mentioned above is supposed to protect against - it should be so hard to calculate the private key from the public key that it is completely unfeasible for an attacker.
• It is also possible to use public-key encryption to sign a message without encrypting it. This is done by Alice calculating a secure hash of the message she wants to send to Bob, encrypting the secure hash using her private key, and sending the encrypted result along with the message to Bob as a signature. When Bob receives this, he computes the secure hash of the message using the same algorithm as Alice, decrypts the signature from Alice using her public key, and is satisfied Alice sent the message if the decrypted value match the calculated hash value.
• Public key cryptography is hard to implement correctly. As an example: One seemingly reasonable way for Alice to authenticate that Bob is Bob (and thus has Bob's private key) is for Alice to generate a random number, send the number to Bob, have Bob encrypt it with his private key, send the result back to Alice, and have Alice check that when she decrypts it using Bob's public key the result match what she sent to "Bob". And, indeed, this will prove that "Bob" possess Bob's private key. However, if Alice is in fact Mallory, and the algorithm used is RSA, it will also give Mallory a copy of Bob's private key - as specially constructed numbers can, when encrypted with RSA, be used to extract the private key.