Page 3: Public Key Encryption

Unit 4, Lab 2, Page 3

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.

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.

IOC-2.B.5

Public key encryption uses a pair of keys: a public key for encryption and a private key for decryption. The sender uses the public key to encrypt the message, and receiver uses their private key to decrypt it.

Here is a visual model of public key encryption (from wikimedia.org).

Diagram of public key encryption showing a message being encrypted with a public key and decrypted with a private key

Here is a video that uses paint mixing as a metaphor for public key encryption.

Set Up Your Headphones or Speakers

If your connection blocks YouTube, watch the video here, but start it at 2:25.

Symmetric cryptography uses the same secret key to encode and to decode a message, and it’s been around for thousands of years. Its weakness is that the key becomes another message that needs to be transmitted securely.

Who created public key encryption?

The public key idea was first published by Whitfield Diffie and Martin Hellman in 1976. But it turns out that it had been invented earlier but kept secret by governments.

Public key (asymmetric) cryptography was created in the 1970s. It uses two different keys for encryption and decryption, so sharing the public key doesn’t give away the private key. Public key encryption is the primary method of encryption today because of its high level of security.

  1. You learned about symmetric encryption on Page 1: Cryptography.

    Talk with Your Partner Describe how public key encryption offers better message transmission security than symmetric encryption. Would you trust this method to work to send a credit card number?

This endnote references composition of functions, but I think it’s the first time in the curriculum that this idea has appeared. –MF, 6/15/20

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.

This comic was written by Randall Munroe (source: xkcd).
A comic with 4 panels. In each panel, a person is sitting at a computer. In panel 1, they say 'I've been posting my public key for 15 years now, but no one has ever asked me for it or used it for anything as far as I can tell.' In panels 2 and 3, the person sits quietly. In panel 4, they say 'Maybe I should try posting my private key instead.'

Secure HTTP

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

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.

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. New research developments in 2019 make practical quantum cryptanalysis seem not so far away.)

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

IOC-2.B.6

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

Instead of trusting that the website is who they say they are, you now have to trust that the Certificate Authority is reliable.

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 his message to Alice using Eve’s fake key, and then only Eve can read the message meant for Alice. 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. It may seem incredible that a sender (e.g., Alice) can make her encryption key public and yet no one except her can decrypt her message. The public key method relies both on mathematics and on current limitations on the speed of computers. Read “Secrecy Changes Forever” (Blown to Bits pages 178-181) to understand some of how this works.
  2. Read “The Key Agreement Protocol” and “Public Keys for Private Messages” (Blown to Bits pages 181-183) for more details on Public Key Encryption.
  1. Do some research about modern encryption systems such as the RSA cryptosystem, which is used to do secure transactions on the Internet.