Cryptograph underpins most of today’s internet infrastructure. This post goes over the very basics of modern symmetric and asymmetric cryptography to give enough information to be able to understand the technical implications of cryptography on other topics. It is meant to be understandable by someone with no technical knowledge.

A good part of cryptography is encryption: a process by which a message is translated into a form that can only be read by its intended recipient. We’ll talk mostly about that.

Someone with extensive knowledge of cryptography will likely find the text incorrect on certain points. Keep in mind that the intention is to only explain the high-level principles: some shortcuts have been used for the sake of keeping the explanation simple (and it’s already complicated).

A Ridiculously Brief History of Encryption

Most people have played with this as children: there are plenty of books about turning a few sentences into a mysterious series of symbols. It’s a popular narrative device too: for example, Edgar Allan Poe used a “secret message” in its novel The Gold Bug. Real history is also full of ‘secret messages’ and ‘ciphers’.

Secret scheme, secret key. A famous early encryption scheme is the Caesar cipher, where you replace each letter in a text by another one a fixed number of places down the alphabet. For example, if you move 3 places down the alphabet, you turn a into d, b into e, etc. A message like hello world gets turned into khoor zruog. Decrypting the message is done by doing the reverse operation: replacing each letter by one 3 places up the alphabet. It’s simple, easy to work with but is only “safe” if only the sender and the recipient know both the process itself and the number of places to shift. And even so, it’s not that hard to crack.

A very large variety of encryption schemes (ciphers) have been devised throughout history, and up until recently, they relied very heavily on secrecy: for the message to stay secret, only the sender and the recipient must know the encryption process. The big flaw is that it will leak eventually, and when that happens it means the communication is not confidential anymore. Relying on secrecy also means that you need completely different ciphers for each separate group of people you want to confidentially communicate with, which is not very practical.

Public scheme. Then with time, people devised encryption schemes where the message couldn’t be decrypted even if the encryption process was publicly known. The confidentiality then rested on the shared knowledge of an encryption key. In the example of the Caesar cipher, the encryption process is the principle of substituting each letter by another one, and the key is the number of places to move up/down the alphabet.

One example of widely-used encryption schemes where only the confidentiality of the key was critical was the Enigma Machine used during WWII by Nazi Germany. While the encryption was ultimately defeated by the allies, the knowledge of the encryption procedures only helped to some extent, and considerable effort was needed to decrypt the messages without the keys.

Public key. Eventually, some encryption schemes were devised where the knowledge of the key itself by the adversary would not give them any advantage either. How is that possible? Until that point, we talked about ciphers where encryption and decryption are performed using the exact same key, which has to be known by both sender and recipient. By using two different keys (one for encryption, and one for decryption), it becomes possible to have one of them publicly known without breaking the confidentiality. This is called asymmetric or public-key encryption and it is widely used on the internet today.

Symmetric Cryptography

When a process involves the shared knowledge a key, we talk about symmetric cryptography. We briefly describe it because it’s used a lot in practice, and because it helps with understanding asymmetric cryptography.

To establish a communication between Alice and Bob, they first have to agree on a shared encryption key. In practice, this key is a very long number, computed using a publicly-known algorithm. They agree to keep that key secret on their computers: only Alice and Bob know it.

Alice and Bob meeting in the same place, creating a key and each keeping an identical copy.

Alice wants to send a message to Bob: on her computer, she runs the publicly-known encryption algorithm, feeding it the message and the shared encryption key. She then sends the resulting encrypted message to Bob, through a communication channel. It doesn’t matter if this channel is watched by someone malicious: the only thing they can see is the encrypted message, which they can’t make sense of. Upon reception, Bob feeds - on his computer - the encrypted message and the shared encryption key to the decryption algorithm. The result is the clear-text message that Alice initially wrote. The same process happens in reverse when Bob sends his answer (encryption with the shared key on Bob’s computer, transfer, decryption with the shared key on Alice’s computer).

Alice and Bob each in their own house. Alice encrypts a message to Bob using her copy of the key, sends it to Bob, who decrypts it using the same key

This procedure works but has a big downside: Alice and Bob need to trust each other to keep the key secret. And it gets worse if the conversation involves more than two people: you need to trust every person in the conversation to keep the shared key secret. This rapidly breaks down: if even a single person leaks the key, a new shared key is needed, and needs to be communicated securely to everyone.

Asymmetric Cryptography

Also known as Public-Key Cryptography.

Key Creation

Public-key cryptography solves the problem of a shared key by eliminating it entirely. Instead of having a single shared key, each participant in the conversation has two keys associated with them. The principle is simple:

Something encrypted with one of the key can only be decrypted with the other key from the same pair.

The first step is for Alice and Bob to independently run a publicly-known program that will generate a distinct pair of keys for each of them. For reasons that will become clear below, one of those keys is called “public” and the other “private”. The keys have something in common - which is why we talk about a pair - but the important point for confidentiality is that the private key cannot be computed from the public key.

Alice and Bob in their own houses, each creating a key pair, with a public and private key

Sending An Encrypted Message

To send an encrypted message, the public key is used for encryption, and the private key for decryption.

It means that when Alice wants to send a message to Bob, she will use Bob’s public key to encrypt the message, and Bob will use his private key to decrypt it. The other direction is similar: Bob uses Alice’s public key to encrypt a message for Alice, which uses her private key to decrypt it.

Alice encrypting a message for Bob using his public key, Bob decrypting the message using his private key. The diagram is the same as in the case of symmetric encryption, with the crucial difference that two different keys for encryption and decryption are used, instead of a single one.

The whole process looks almost identical to the case of symmetric encryption: the only difference (highlighted in red on the image) is the use of two distinct keys instead of one. Both have been generated by the recipient!

Communicating the public keys. We skipped a very important step here: how did Alice and Bob know each other’s public keys? As the name implies, the public key can be shared freely, so they could in principle send them through an unencrypted channel. But Alice still needs to know that the public key she received is indeed Bob’s: someone could be tampering with the communication and replacing the key with another one. So in practice, some precautions need to be taken, for example meeting physically to make sure to communicate the correct keys.

Alice and bob in the same place, exchanging their public keys

Keeping the private key secret. The downside of having a shared secret key we mentioned above doesn’t exist anymore, since each person is responsible for protecting their own private key which is not communicated to anyone. Anyone who wants to send a message to you specifically can encrypt a message using your public key, and you will be the only one able to decrypt it, as long as you keep your private key secret.

Making sure the public key is the one you think. A critical point of asymmetric cryptography is asserting the link between a public key and its owner’s identity. The solution mentioned above - meeting in person - is not always practical. People could be very far away and never meet, or the communication is between two computer systems (e.g. websites) and “meeting in person” makes no sense. One of the solutions widely used is the concept of certificates, which we will not present here.

Signing A Message

Having two distinct keys for encryption and decryption makes certain things possible that are impossible with symmetric cryptography. In particular, digital signatures, which are used to make sure that something originated with a specific person - like a pen-and-paper signature can only be created by a single person.

Using the asymmetry. Previously we used the fact that encryption with the public key makes it possible for everybody to create a message that only one person can read. That enable sending messages to a particular person only. If you take this process in reverse, that is if you encrypt with the private key, you have a way to ensure that something can only come from a specific person: that’s the basis of digital signature.

Cryptographic Hashing. First, we need to introduce another concept: cryptographic hashing. It’s an algorithm that turns an arbitrary message into a single number, called a ‘hash’. No matter how long the message is, the number always has the same length. For example, 20 bytes. The important bit here is that this process cannot be easily reversed: if you know a cryptographic hash, it’s in practice impossible to write a message that will give this exact hash as a result of the hashing algorithm.

A diagram showing an icon of a pdf document on the left, and arrow representing the hashing process, and the result as a number on the right

How is that used in practice? This is where it starts getting hairy.

Alice has a document that she wants to sign. She first computes its hash - using the publicly-known algorithm - then encrypts that hash using her private key. She then sends the document (in clear text) and the encrypted hash to Bob. To verify the signature, Bob recomputes the hash from the document - using the same algorithm -, decrypts the encrypted hash that Alice has sent using Alice’s public key, and checks whether the two results match. If yes, the signature is valid. If anyone has tampered with either the document or the encrypted hash, the two results won’t match.

A valid signature proves that the document is indeed the one that Alice sent.

The signature process: Alice computes a message's hash, then encrypts it with her private key, sends both the message (in clear text) and the encrypted hash to Bob. Bob recomputes the hash from the message, decrypts the hash he received using Alice's public key, and compares them

Encryption and signature

Of course, in practice you often combine encryption and signature. Just for fun, here’s how the flowchart looks like if you want to encrypt and sign a message. We’ve removed a lot of elements compared to the previous diagrams, to keep things manageable. The pound sign (#) represents the hashing algorithm.

Flow chart showing the complete flow of encryption and signature from Alice to Bob. Hashing operations are represented by a pound/sharp symbol '#'. Alice starts with a pdf document, encrypts it using Bob's private key. Then computes the hash of the same document (not encrypted) and encrypts it using her private key. Both encrypted document and encrypted hash are sent to Bob.

Even though the diagram is already pretty complicated, we are still simplifying. In particular it is good practice to use different key pairs for encryption and signing operations, so each person has two pairs of keys (one pair for encryption, one pair for signature).

The chart only shows communication between two people, in one direction. Going the other direction requires another two key pairs (those from Bob). For each person you need to communicate with, you need to have a copy of their two public keys. That’s a lot of keys!

The advantage of this deluge of keys is that if someone’s private key leaks, it only compromises communications involving that person, and not the entire group. That person can re-create another key pair, and share the new public key with all the people they communicate with. However, as soon as a private key leaks, everybody who has the corresponding public key must be notified so that they stop trusting that key. That can be a complicated process.

Apologies To The Specialists

We glossed over a lot of things in this text, for didactic purposes. For example:

  1. The problem of safely communicating public keys is very difficult and can be solved in practice in a number of ways, none of them perfect. It is connected to the problem of enrollment, which is still a research problem which may not have a good answer at all. If you want a rather technical deep dive on this question, see Factors in authentication.

  2. Algorithms used for asymmetric encryption are much slower than those for symmetric encryption, which makes them unsuitable for large data transfer. In practice, a combination of symmetric and asymmetric encryption is used. It also gives other benefits, like throwaway encryption keys: asymmetric cryptography is used to agree on a temporary shared encryption key, which is used for a limited amount of time - sometimes a single message - then deleted. That’s the best way to make sure a message can’t be decrypted in the future by eavesdroppers: get rid of the key!

  3. We also simplified the presentation of the signing process by claiming is was performed by encrypting a document’s hash with the private key. This happens to be true for only a single cryptographic scheme: RSA. Other schemes use different algorithms, but the principle stays the same: the private key is used to compute something from the hash, that can be verified using the corresponding public key.

If this article got you interested in the topic, here are some pointers to go (much) further: