Notes on 'Public Key Cryptography'

Short summary of New Directions in Cryptography written by Diffie and Hellman in 1976. More commonly known nowadays as the paper that introduced public key cryptography.

The main idea is to make cryptography more accessible. Traditionally you need a shared private key that is exchanged out of band in order to safely communicate. With public key cryptography you have a private and public key, and you can send public key over the wire. This makes it easier for two parties that have never met to send secret messages to each other. This is a bigger deal than one might first realize at first. It is truly a revolution from the genesis of cryptography, which was about using a secret key alone to encrypt a message.

It can also be used to sign a message, so Alice can use her private key to sign some message, and then later on sign another message. Bob can then check that the public key is the same and know that someone with possession of Alice’s private key signed both those messages. This is much more robust than handwritten signatures, which as far as I can tell are, in most circumstances, easily forged.

How is this possible? This is possible because we can construct a function that makes it easy to go one way, but very computationally expensive to go the other way. This property can be achieved in several ways. One of the more common ways is to use the fact that it is hard to find a large prime number, but it’s fairly easy to verify that a number is a prime number. It’s more involved than that, but this makes it easy to go from a private key to a public key but very hard to get the private key from the public key. This can be fairly easily quantified and scaled to any desirable difficulty, as far as I understand it.

In hindsight, key management has turned out to be a hard problem regardless. People don’t seem to use private keys individually that much, despite PGP and key servers. There are initiatives like Keybase, but they don’t see a lot of wide adoptation.


Further reading