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.

Questions

• How do we go from the difficulty of prime factorization to the selection of private and public keys? A closer reading and some pen-on-paper math would likely reveal the answer.

• Why is it that end-to-end crypto isn’t more widely used?

• What are some illustrative examples of public-key crypto being used in practice and changing how things are done? What about how it fails?

• When do I use public-key cryptography myself? In the sense that I create, control and use the keys directly, I mostly use it to SSH into servers and interface with some centralized Git repository. Sometimes for package signing in Xcode. Those are both pretty useful. I am sure there are more examples of where I use it, both directly as well as indirectly.

Further reading

• Shannon, 1949 - Communication theory of secrecy systems

• Schneier, Applied Cryptography (came after, but talks about this in a larger context)

• RSA paper (how are they connected?)