Public Key Encryption

The Problem

Historically, secure transmission of documents used single key encryption, where both the sender of a document and the receiver of the document had the "key" used to encrypt and decrypt documents. The key would be delivered to the receiver of a document using some secure message of transmission. Often it would be physically handed to the the receiver of the document who would then take it away with them. The secure transmission of the key is impossible over a computer network, so other methods were developed which could be used over communication networks where eavesdroppers could conceivably listen in on every message. These new methods involve using two different keys and are called Public Key Encryption Methods

Public key encryption is a system of encryption that uses 2 keys, one to encrypt a message (the public key) and one to decrypt the message (the private key). Both a users public key and the decryption method can be known, but messages will still be very difficult to decrypt (i.e. take many years of computing using the worlds fastest computers). Public keys are stored in databases (or key certificate authorities) that are "trusted" by the users. If the public key is not obtained from a "trusted" source, a 3rd party could substitute their public key, and thereby decrypt message with their private key.

An example

ENCRYPTION and DECRYPTION using Public Keys

Bob wants to send Alice a secret message. How does he do it? All he has to do is to obtain Alice's public key from a known and reliable source (how can he know it is reliable? We'll come back to that later). Bob then takes his message (M) and encrypts it using Alice's Public key (PKa). Only Alice can now decrypt this message, since only Alice's private key (pKa)can decrypt ("Unlock") messages sent by encrypting with her public key.

i.e. The message that Bob sends is EPKa(M) and then Alice does a DpKa(EPKa(M))

where E means Encrypt and D means Decrypt and PKa is a's Public Key and pKa is a's private key.

But how does Alice know that the message actually came from Bob? Perhaps someone else has sent her a message pretending to be Bob.

The answer is simple if the particular public key system allows the private key to be used for encryption and the public key for encryption. If this is true, then Bob just sends Alice a digital signature which has been created by using his private key. For instance he could first encrypt the document with Alice's public key, and then encrypt the already encrypted document with his private key. Alice would then have to decrypt the resulting document twice, once with Bob's public key, and then once again with her private key. The message would only make sense if it was sent from Bob, otherwise his public key wouldn't decrypt it correctly and the message would be junk when further decrypted using Alice's private key.

This operation would look something like this:

Bob would send

E pKb(EPKa(M)) and Alice would retrieve and simultaneously verify that the message was from Bob by:

DpKa(DPKb(EpKb(EPKa(M))))

This should retrieve the original message.

Some problems ....

In actual practice, the world is more complicated. Public key encryption systems are quite slow, so instead of encrypting the whole message with the public key encryption, the public key method is used to securely distribute a single "secret" key that can be used to both encrypt and decrypt the document.

Using this method, Bob can still send his secure message to Alice but it takes a few more steps (but less computing time).

Bob first uses Alice's public key and his private key as described above to send a digitally signed message to Alice which both verifies that it is from Bob, and contains the "secret" key he will use to send his long document.

He then encrypts the document with the secret key that he and Alice now share and sends it to her.

Key Certificate Authorities

But how do we know that we have reliably obtained someone's public key. We need a trusted third party who has a key ring of everybody's public key and gives out copies on request.

There are many variations to the above, depending on the particular characteristics of the public key encryption system used.

For more information on the mathematics involved, go to the NASA Ames pages which have a course on Public Key Encryption.

Trap Doors

One major issue is whether or not the government should be able to decrypt any message (with suitable authority). The US government has proposed a solution (the Clipper chip) which would allow the government access to a 2nd private key that would unlock a message in cases of national emergency.  This has civil liberty types up in arms, but is strongly supported by the Executive branch and law enforcement authorities.