Sender authentication part 24: Public key encryption

The basic idea behind secret key encryption is the following:

  1. You don't have to keep the algorithm a secret.
  2. You do need to keep the key a secret.
  3. To increase the security of the contents, you lengthen the size of the key.

This is all well and good, except for one problem?  How do you distribute the key to your recipients?  And what do you do if you want to update your key?

This is where public key encryption comes in, and it works much like it sounds.  With public key encryption, you use two different keys in the process, one to encrypt and one to decrypt.  Whereas with secret key encryption, the same key is used to encrypt the message as it is to decrypt it, with public key, they are different.  The algorithm is similar to secret key encryption except that the keys are pairs and are designed to work together.  You cannot decrypt a message encoded with one key without the other (if you lose one, then you're out of luck).  The keys are unique (or nearly unique) to each other.  Here's how the process works:

  1. Alice picks two keys and makes one public and keeps the other private.
  2. Bob wants to send a message to Alice.
  3. Bob asks Alice for her public key, and Alice gives it to him.
  4. Bob encrypts the message with Alice's public key and transmits the message to Alice.
  5. Alice receives the message and decrypts it with her private key.  Alice is the only one that can decrypt the message with her private key.

Note that after Bob encodes his message, he can't decrypt the message with the public key to double-check the contents of the message.  Once it's encoded, it's encoded and he can't check it over (I don't know why he would but suppose he had some reason to do it).  So, Bob can transmit the message to Alice and just like secret key encryption, without the secret key to decrypt the message, the message contents are protected.  Eventually, it could be broken but it is time-prohibitive to do so.

Public key encryption solves the problem of key distribution.  Using public key encryption, you don't have to worry about distributing your key to others, they simply ask you for your public key, you give it to them and then they send you the message (or you ask them for their public key and then send them the message).  Note that you can use either key to encrypt or decrypt, but you have to keep one of them secret.  Again, the strength of the algorithm is that you don't have to keep the algorithm or the public key secret, only your private key.