Public Key Encryption

On this page, you will learn about a commonly used method of cryptography that is more secure.

The fundamental problem that cryptography is trying to solve is how to get a message to your friend that can't be intercepted by your enemies. Symmetric encryption has a fundamental weakness: the encryption key is itself a message that needs to be send to your friend but not intercepted by your enemy.

Paul's going to be the decider on whether to keep this box.
The public key idea was invented and first published by Whitfield Diffie and Martin Hellman in 1976. It turns out that it had been invented earlier but kept secret by governments.

Public key cryptography is a mathematical technique to avoid the need to communicate a secret key from one person to another. Instead, each person has two keys: a private key known only to that person and a public key that everyone in the world is allowed to know. If Bob wants to send Alice a secret message, he encrypts it with Alice's public key. Then no one but Alice can decrypt it. Only her private key can undo the encryption, and no one can figure out the private key from the public key.

Set Up Your Headphones or Speakers
If your connection blocks YouTube, watch the video here, but start it at 2:25.
  1. It may seem incredible that Alice can make her encryption key public and still no one except her can decrypt her message. The public key method relies on some mathematics and on some limitations on the speed of current computers. Read "Secrecy Changes Forever" (Blown to Bits pages 178-181) to understand some of how this works.
Here is a model of public key encryption (from wikimedia.org)
Diagram of public key encryption
  1. With a partner, discuss how this method is different from symmetric cryptography described on previous pages. Would you trust this method to work to send a credit card number?
It's also possible to use the private key for encryption and the public key for decryption...
That's no good for secret messages (why not?), but it's useful for digital signatures. I use my private key to encrypt a message; you use my public key to decrypt it. If you get a meaningful message as the result, that proves that the message was encrypted with my private key. (If I want both secrecy and digital signing, I encrypt the message with my private key to sign it, then encrypt the encrypted result again with your public key to keep it secret. You decrypt it twice, first with your private key and then with my public key.) This is a nice example of composition of functions: the output from the first encryption is the input to the second encryption.

Secure HTTP

Secure HTTP connections (those that use https:// instead of http://) use a protocol called Transport Layer Security (TLS) or maybe an older version called Secure Sockets Layer (SSL). Both are based on public key cryptography. With SSL/TLS, the site you are visiting sends its public key, and your browser uses it to encrypt the information you send.

SSL/TLS (secure sockets layer/transport layer security) is the standard used for cryptographically secured information transfer on the Internet.


If your connection blocks YouTube, watch the video here, but start it at 4:40.
Set Up Your Headphones or Speakers
Open standards help security...

In order to work properly, a cryptographic function has to be easy for the private key holder to invert, but hard for anyone else to invert. How do we know what "hard" means? For example, current cryptographic methods rely on the difficulty of finding prime factors of very large numbers. There's no proof that someone won't come up with a fast way to do that, but people are pretty confident about it because the problem has been well studied by many mathematicians. (On the other hand, when quantum computers become practical, factorization will be easy, and new cryptographic methods will be needed.)

What makes it possible for mathematicians to study the difficulty of breaking Internet cryptography is that the method used—the cryptographic function—is openly published. This may seem strange; if you want to keep secrets, shouldn't you keep the technique secret, too? But secret algorithms can have weaknesses that go undiscovered until some bad guy exploits them. Open standards allow an algorithm to be studied before it is used in practice.

Certificate Authorities

Certificate authorities issue digital certificates that verify who owns the encryption keys used for secured communications.

Public key cryptography doesn't solve all the problems, because an eavesdropper (say, Eve) might publish a fake public key pretending to be Alice. Then Bob might accidentally encrypt their message for Alice using the Eve's fake key, and then the Eve can read the message. In practice, this is partly fixed by relying on trusted third parties, called Certificate Authorities, to certify public keys. In your browser's security options you can see all of the Certificate Authorities that it trusts.

But this just pushes the problem back a layer. How does the Certificate Authorities know that you are who you say you are? The problem is a little bit like how your bank knows that you who you say you are when you call them on the phone. Namely, they ask you questions for which they hope only you know the answer.
  1. Read "The Key Agreement Protocol" and "Public Keys for Private Messages" (Blown to Bits pages 181-183) for more details on Public Key Encryption.
  2. Do some research about modern encryption systems such as the RSA cryptosystem, which is used to do secure transactions on the Internet.