Historical encryption had a big private key problem, public key cryptography solved it
We talk a lot about the security applications of public key cryptography, how it accomplishes both encryption and authentication. The role it plays in SSL, Code Signing, Email and Document Signing, personal authentication—everything. What we don’t often talk about is the historical significance of public key encryption.
Today we’re going to talk about the differences between private key cryptography and public key cryptography, the historical significance of the latter and how they both combine to make SSL/TLS and similar cryptosystems possible.
So, without further ado, let’s hash it out.
What is Private Key Cryptography?
Throughout history, there are myriad examples of private key cryptography dating back to about 1900 BC. In Private key cryptography both parties must hold on to a matching private key (or else exchange it upon transmission) that they can use to both encipher plaintext and then decipher it. Famous examples would be Caesar’s cipher, the Enigma machine and Louis XIV’s Great Cipher.
There is a major flaw inherent in private key cryptography though. Today we refer to it as key distribution and it’s an afterthought for 99.9% of people. But historically, key distribution has represented a big problem.
Think about it, both parties had to be in possession of a physical key. If there was any distance between the two parties – which was not uncommon – you had to entrust a courier with your private key or travel there to exchange it yourself. And if the key ever fell into the wrong hands everything could go bust. People have literally died over compromised private keys in the past.
Even in the digital age, private key encryption on its own struggles with key distribution. How do you know that you’re sending the private key (which is referred to as a session key in SSL/TLS) to the correct party without an authentication mechanism?
The invention of Public Key Encryption
Public Key Encryption was actually discovered twice. In 1970, a cryptographer named James Ellis working for the UK’s Government Communications Headquarters (GCHQ) theorized about a public key encryption system, but didn’t know how to implement it at the time. Three years later in 1973, Clifford Cocks figured out a practical method for implementation by mixing in an algorithm that was roughly equivalent to what we know as RSA. A third man, mathematician Malcolm Williamson developed a key exchange system equivalent to Diffie-Helman key exchange.
This information was passed to the American NSA as well, but neither organization understood its significance and owing to the nature of computers at the time the technology was seen as impractical and more of a fun thought experiment. It was declassified in 1997 after 27 years.
To our knowledge, it was never deployed by either party.
So, in 1976, Public Key Cryptography was discovered again, this time by Whitfield Diffie and Martin Hellman, who the system was name after (in 2002 they argued it should be the Diffie-Hellman-Merkle key exchange, after Ralph Merkle, a cryptographer they worked with at Stanford).
A year later, Ron Rivest, Adi Shamir and Leonard Adleman, the eponymous creators of RSA were finalizing their work at MIT.
What is Public Key Cryptography?
Diffie-Helman key exchange and RSA were asymmetric cryptosystems. Up until this point, encryption had been symmetric, with both parties able to encrypt and decrypt with the same private key. As we’ve already touched on, this created all kinds of problems for people.
As you can probably tell from the term “key exchange” the creators of these systems were already thinking about correcting an age-old problem: key distribution.
Public Key Encryption uses a pair of keys. A public key, which can encrypt, and a private key that decrypts. Communication can only go one way with Public Key Encryption, hence it’s called “asymmetric.” The idea is that the authorized party holds on to the private key while the public key is, well, public.
The private key in Public Key Encryption is still as valuable as ever, so extra consideration must be given to keeping it secure. But the public key is absolutely worthless in the wrong hands. There is no risk of public key compromise. So how does public key encryption solve the private key problem?
By enabling more secure symmetric encryption.
Public Key Encryption is a key exchange mechanism
Obviously, the one-way nature of Public Key Encryption makes it a poor choice for communication. But that’s not really what it’s for. It’s a mechanism for authentication as much as it is for encryption. It’s for encrypting information and making sure it arrives at the correct party. And one of the best things to encrypt is a private key.
This is what you see with SSL/TLS. During the handshake, the client generates a symmetric session (private) key, encrypts it, and sends it to the server. If the server has the private key it decrypts the session key and the client and server can start communicating using the symmetric keys.
That also helps authenticate the server, as it wouldn’t be able to decrypt the client’s message without the correct private key.
Public key cryptography was a brilliant breakthrough that laid the foundation for the SSL/TLS protocols we use today. Up until this point, even the most advanced cryptosystem was still only as secure as its private key. That’s true with public key encryption, too. But as a key exchange mechanism, public key encryption eliminates a lot of attack vectors.
And owing to its one-way nature, the Private keys used in public key encryption can be a lot more robust. A strong symmetric private key is 256 bits. That is still plenty of security. But it pales in comparison to a 2048-bit RSA private key. Which makes it an even better key distribution mechanism.
How does Public Key Encryption work in SSL?
In SSL, Public Key Encryption helps with authentication and key exchange. To explain this I’m going to use the TLS 1.3 model since that’s the direction we’re headed. It’s a bit more complicated in earlier TLS versions.
Let’s start by talking about ciphers and cipher suites. Ciphers are algorithms used for encryption. A cipher suite is a group of algorithms that are used in conjunction by the SSL/TLS protocol. Every server and every browser are configured to support certain cipher suites.
Traditionally, the cipher suite has consisted of:
Key Exchange/Authentication Algorithm_WITH _ Symmetric Cipher_Hashing Function
That is changing with TLS 1.3, which combines encryption and authentication algorithms into the authenticated encryption with associated data (AEAD) algorithm—a discussion for another day.
Now let’s put this together. When a user (client) arrives at a website (server) it sends a clientHello message that has a list of supported cipher suites ordered by preference. It also guesses what encryption algorithm will be used and sends a session key. All of this is encrypted using the server’s public key.
The server uses its private key to decrypt the clientHello message and then returns server Hello message with its certificate, its chosen cipher suite and (if necessary) its key.
After receiving the serverHello the client and server begin communicating using the symmetric encryption keys they exchanged.
Now, a quick word about session keys: they are replaced often. It is not uncommon to use a different session key for each message in some contexts.
That would never be feasible without the ability to securely handle key distribution though.
And that’s the historical significance of Public Key Cryptography.