11. Introduction to Public Key Cryptography

Up until this point all the ciphers discussed, from the age of Caesar to those used in modern cell phone encryption, are what’s known as symmetric ciphers, meaning that knowing the key used to encrypt a message is sufficient to also decrypt the message. Much like a physical key used to lock an item in a locker, the encryption key can be used to both store and retrieve encrypted information. While such a system is both convenient and secure for storing and retrieving your own information, it becomes difficult to maintain when attempting to share encrypted information. How do you securely transmit the key for the encryption method to anyone you wish to share the message? If you had a way to share securely share a key with the other person, why not send the message via that channel instead? Traditionally keys would be exchanged in a face-to-face setting, or in a code book that would be changed out regularly. However, when attempting to encrypt online communications with various businesses, individuals, and the government, face-to-face meetings are not just impractical (“Hello, Instagram? I’d like to post a photo… who can meet me to receive my encryption key this morning?”) but impossible.

Fortunately, the problem of exchanging keys can be solved if an encryption method could be devised such that a key is split into two parts, with each key’s pair being the only key that can undo the operation of the other. If one key was used to encipher a message, then only the other could be used to decipher, and vice-versa. Not even the key used to encrypt a message could be used to decrypt a message, only it’s paired key! Such a system seems impossible given that all the systems you’ve studied so far do not operate this way. However, it turns out that there are several systems that can operate in this fashion, eliminating the need to keep your key secret from the world. In fact, in this type of system you would want everyone to have part of your key, so they could encrypt messages to send you that only the other key could decrypt. The desire to widely share part of your key publicly is what gives this type of encryption it’s name: Public Key Cryptography.

Required Elements for a Public Key System

There are several different commonly used public key cryptography systems. While the details vary from system to system, they all share the following common elements:

• It’s easy to create pairs of keys (one public, one private)

• The public key should be shared widely

• The private key must remain secret to the originator of the keys

• The public and private keys can both be used to encipher and decipher messages, but a single key can’t decipher a message that it created itself

• It must be infeasible to calculate the private key from the public key (and vice-versa)

We’ll see in all the systems covered in this course that the first and the last bullet points, are the most important. We need a way to generate a pair of keys quickly and easily, but in a way that it’s near impossible to determine one part of the pair from the other. We’ll see that we need some sort of “one way” function that is easy to perform, but difficult to undo.