What is Public Key Cryptography?

We all make use of public key cryptography in our day to day lives but it's one of those technologies we rarely think about.

For starters, you're reading this post over HTTPS which uses public key cryptography as does your banking app and most other web services you access test days. WhatsApp messenger uses public key cryptography to provide end to end encryption for your messages and the cryptocurrencies like Bitcoin couldn't exist without public key cryptography.

To answer the title question though, I'll wind the clock back a bit to ask...

What is Cryptography?

Cryptography is is the practice and study of hiding information. The goal generally being to take information that could be read by anyone and process it to make it unreadable to anyone other than the intended reader.

I've been careful with my language there in that cryptography isn't just about sending and receiving information. When you read about cryptography you'll find that most of the time people do talk in terms of sending information, typically between fictional characters 'Alice' and 'Bob' with the dastardly 'Eve' attempting to eavesdrop on their communications.

This is really just a form of short-hand to keep explanations simple but the concepts extend beyond sending messages to storing or even validating information. Similarly, the information being sent is typically referred to as 'plain text' and the encrypted data as 'cipher text' but the data could just as easily be documents, images, videos, software, etc.

How does Cryptography work?

Cryptography has origins as far back as ancient Egypt, but one of the best documented early uses is by the Roman emperor Julius Caesar.

Caesar used cryptography to send secret messages to generals during wartime by swapping each letter in a document with the letter three places up in the alphabet, with D becoming A, E becoming B, etc.

This is known as a substitution cipher, or the Caesar cipher. The challenge with this approach is that once an attacker has cracked the rule, it's pretty easy to decrypt the whole message. Instead of simply shifting the alphabet, another approach is to randomize the substitutions. Randomising the digits is a great step forward, even better if you use a different set of substitutions each time, but both techniques were vulnerable to a technique called cryptanalysis.

Cracking the Code

The problem with simple substitution ciphers is that whilst the original message may appear scrambled, the translation remains static. In a given language there's typically a pattern behind how words are constructed from the alphabet. In English for instance, the most commonly used letters are 'E', 'T', 'A' and 'O' whilst the least used are 'Z', 'Q', 'X' and 'J' (the good scorers in Scrabble).

So if you're looking at plain text scrambled using a simple substitution cipher, it might look random but the distribution of the letters will be the same. This means that with a sufficient amount of cipher text you'd be able to reverse engineer the key.

Fast Forward to Modern Cryptography

The principles of early cryptography outlined above may be basic but in some sense cryptography is still the same today. The methods by which we encrypt data have become more sophisticated over time, but equally the attacks on those methods have always been close behind.

Perhaps the most famous example is the brilliantly clever Enigma machine and the equally brilliant codebreakers at Bletchley Park under Alan Turing.

As an aside I'd strongly urge you to visit Bletchley Park, it's a national treasure and they've suffered terribly through lockdown.

So far though, each of the encryption mechanisms being used are examples of Private Key cryptography. Each message is encrypted with the use of a secret code that acts as a key to decode the message for anyone with access to that key.

The big problem with private key cryptography is that you have to find a secure, reliable way to distribute those keys. Equally, you can't reuse keys for private communication between multiple parties because everybody would be able read everybody else's messages. In 1976 however, this all changed as Whitfield Diffie and Martin Hellman of Stanford invented the new concept* of Public Key cryptography.

* actually, it was independently invented a few years earlier by British spies James Ellis, Clifford Cocks and Malcolm Williamson. This great Wired article beautifully tells the secret history of public key cryptography.

Public Key Cryptography Changes Everything

In 1977 Ron Rivest, Adi Shamir and Leonard Adleman from MIT found a way to make the Diffie-Hellman concept practical, creating what is known as the RSA algorithm. Public Key cryptography up-ends the whole concept of key management. Instead of having a private key that you must only share with the intended recipients of a message, you now have two keys - a private key and a public key. This is known as a 'key pair'.

The private key this time however need not be shared with anyone, but instead you can share the public key with the whole world. Anyone that wishes to send you a message can encrypt it with your public key, but the message can only ever be decrypted with your private key - which you never share with anyone. If you wish to send a reply, you can encrypt it using the recipient's public key. This means that you can send and receive messages securely without having to exchange any sensitive information with anyone, ever.

This model whereby one key is used to encrypt and another to decrypt is also sometimes called asymmetric key cryptography, whereas the traditional model is known as symmetric key cryptography. There are certain mathematical problems that are hard to solve, the RSA approach

This approach opened up an array of new possibilities, but one key factor is missing. With a pre-shared private key Bob would know that a message came from Alice as only the two of you have the key. With public key cryptography however, anyone could encrypt a message with your public key and you'd have no means of certifying the author. Thankfully, this problem was solved by the concept of 'signing' a message.

What is Hashing?

Creating a digital signature relies on another concept called 'hashing'. A hash function takes any input data, processes it and produces an output that doesn't contain the original plaintext but is directly linked to it.

An important distinction to make is that a hash isn't encryption, the output may look like encrypted text but it's a one-way process. If you put the same data into a hash function you'll always get the same data back out, but it's impossible to calculate the original data from the hash. There are lots of different hashing algorithms available, from older ones like MD5 and SHA1 which are not considered sufficient today to more modern algorithms include SHA-256 and Keccak.

To give you an example, if I generate a hash of the text "PrivateKey.dev" using SHA-256 I get the following:

93b7c3a1a5baccff0f3825e8595805d84a3fed83d3d5725ce7fbb639e04c0cac

However, if I change that to lower case "privatekey.dev" I get this:

bdbd349579342a66548ed266294c3cf5317b0e912d9913ddc6db71344149a885

And if I hash the first five paragraphs of this blog post I get this:

97672a8492c5a57751de9e2a202fd3e0465b8c128bf2ac16f4549f703cce65db

As you can see, it doesn't matter what the length of the input text is, the output is the same fixed length even if you has the whole of War & Peace. Crucially, however if you change just one character out of the whole book you'd get a completely different hash value.

Creating a Digital Signature

Imaging the scenario where you need to communicate with someone, and it's important to verify that you're communicating with the right person. Public Key cryptography can be used together with hashing to do so, even if you don't need to encrypt the whole message:

  • Alice wants to send a message to Bob, but needs Bob to be sure that the message came from Alice.
  • Alice hashes his original message and encrypts the hash with his private key.
  • Bob sends the message and the encrypted hash to Alice
  • Alice receives the message, then decrypts the hash using Bob's public key.
  • Alice performs her own hash of the document and it matches Bob's hash, proving that the message came from Bob.

So, the concept of a Digital Signature it's really just a combination of hashing and public key cryptography. The two concepts above can be combined to create an encrypted message digital signature with a digital signature too.

That's the thing with cryptography, the concepts behind it are often simple, elegant and make sense. The other thing about cryptography is that despite the elegance, it's extremely hard to do it well, hence the common warning "don't roll your own crypto".

You should also read:

What is the Metaverse?