An introduction to cryptography
Posted on December 17, 2018 By Dennis
Do you have a burning desire to learn about cryptography? Maybe it’s just a very slow workday and your office blocks YouTube. Regardless of the reason, you’re in for a thorough, step-by-step explanation of what cryptography is, what it is used for and some of its key principles.
Don’t worry, because this introduction to cryptography will take things slow and build up your knowledge step by step. We won’t be making any huge jumps through complicated concepts, so by the end you will have a good foundation of knowledge that helps you understand how we keep much of our global communication channels secure.
What is cryptography?
Cryptography is the art, science, practice and study of securing communications. At its essence, cryptography is used to keep messages and data away from anyone who may be snooping, but it can also be applied in many other ways.
From two children inventing a secret language to complex encryption methods like AES, cryptography is a broad discipline with numerous uses. The more complicated types rely on a range of mathematical properties and are used to keep much of our online world and other communications secure.
A quick glossary
We will introduce a few major terms that are fundamental to understanding the various aspects of cryptography. Others will be covered later on in the article when we talk about topics in depth, but these seven terms will help you get by until then:
Encryption is the process of using a code to hide a message or data. When something has been encrypted, only those who have the key can view it. Encryption is used to keep information private and prevent attackers from viewing our data.
Decryption is the opposite. If data or a message has been encrypted, then it needs to be decoded so that it can be accessed again. This decoding process is called decryption.
Keys are the information that determines the result of an algorithm. They are used to either encrypt or decrypt data, and in some situations they can act in a similar way to passwords. Private keys, like their name suggests, need to be kept secret. In public-key cryptography, they are paired with a public key, which can be shared openly.
Plaintext is data or a message that hasn’t been encrypted. Because of this, it can be accessed by anyone.
Ciphertext is plaintext that has been encrypted. It normally looks like a complex jumble of characters.
In a broad sense, algorithms are essentially sets of instructions that lead to a predictable result. A recipe can be an algorithm, and a computer program is also an algorithm. In this article, most of the time we use the term algorithm, we will be referring to a set of instructions that are used for encryption, decryption and other cryptographic processes.
A cipher is an algorithm that is used for encryption and decryption. In cryptography, the terms cipher and algorithm are often used interchangeably.
Why do we need cryptography?
Cryptography has a number of useful properties that we can use in various situations. These are confidentiality, authentication, integrity and non-repudiation. Together, these aspects of cryptography help us in a wide range of applications. Some examples are:
- Securing our communications
- Emails, encrypted messaging apps like Signal and WhatsApp
- Protocols such as TLS, IPsec and SSH
- Encrypting data at rest
- Programs such as VeraCrypt and BitLocker
- Erasing data
- Digital rights management and copy protection
Confidentiality lies at the center of cryptography. It involves locking information down so that only those who are authorized can access it. It’s tremendously useful for keeping private information away from anyone who may stumble upon it, and from those who are actively trying to seek it out.
Once data has been encoded with cryptography, the original information can no longer be accessed. All that will be seen is a jumble of useless letters.
Of course, this assumes that the right type of cryptography is used and in the correct way. The important thing to note is that when cryptography is used properly, it can keep our data safe. The only ones who can access it are those who know the key.
If you’re an accountant and your boss tells you to transfer $100 into an account, you know that the message is authentic because it is coming straight from her and she is standing right in front of you. The only way you could be fooled is if someone was wearing a mask of your boss and had modulated their voice to sound the same. This is extremely unlikely.
If your boss sent you a letter telling you to make the same transaction, then you could see the handwritten signature at the bottom and trust that the message is truly from your boss. But what if your boss gives you the same instructions through email or some other form of online communication?
How can you know that the message really came from your boss? You can’t see her face, hear her voice or see her signature. How do you know that it isn’t someone impersonating your boss as part of some fiendish scam?
To solve this problem and be relatively certain that a party is who they say they are, we turn to cryptography. There are three key elements that we use to prove authenticity. They are certificates, digital signatures and keys.
We will cover certificates, digital signatures and keys in more detail later on, but the short version is that certificates are granted by trusted organizations called certificate authorities (CAs). CAs run checks to verify that an entity who claims to own a public key really is the owner.
If a CA grants a certificate, then anyone who trusts both the CA and the certificate level (there are a few different ones, some are more trustworthy than others) can trust that the public key is genuine. Public keys are paired with private keys, and private keys can be used to digitally sign messages in a similar way to handwritten signatures.
If data has been signed by a private key, it can be verified by checking it with the public key. As long as no one else knows the private key, then you can be sure that the data was sent by the correct individual. This is how cryptography can be used to give authenticity.
Let’s return to our example of your boss asking you to send $100 to an account. If your boss wanted to prevent impostors from manipulating her employees, the first step would be to establish a public and private key pair. She would then get a certificate for this key pair which verifies that she truly is the owner.
Your boss would then type out the message “Please send $100 to account xyz”. She would then sign it with her private key. When you receive the message, you can verify whether it is authentic by using her public key.
If everything checks out, then you know that it was signed by her private key. You also know that the key is truly owned by your boss, because you trust her certificate. These two elements allow you to assume that the message is authentic. The only way that it could be an impostor is if her private key has been compromised.
This system is used for far more than just authenticating messages. It is also a crucial part of authenticating that servers and clients are who they say they are.
Now that we have a way to prove that messages from your boss really are from them, all of our problems are solved, right?
Well, not really. What if the message is actually from your boss, but someone has intercepted it and changed it along the way? Maybe an attacker could have caught the message and changed it from $100 to $1,000. How could we prevent this from happening?
Cryptography uses the exact same system that we mentioned above to prove that a message retains its original integrity. If your boss digitally signs her message, you can check its integrity using her public key.
The details of how this works are elaborated on in the digital signatures section below. For now, all you need to know is that this mechanism makes it easy to tell if even a single character of the text has been altered.
In a general sense, non-repudiation refers to whether an individual can dispute that they are the responsible party. If they can prove that they aren’t responsible or if there is enough reasonable doubt, they can “repudiate” and not be held liable. A mechanism provides non-repudiation if it ties the user to an action in an indisputable way.
Non-repudiation is a complex concept, so we will discuss a few separate examples before we get to how it applies to cryptography. Let’s take handwritten signatures as an example. In our society, we use them to prove that we really are the individual who is signing a contract or purchasing something with a credit card.
If the document was signed with an incorrect signature, then it may not be legally valid. If the signature really is our own, then we are legally responsible for whatever the agreement says. But there’s a problem–signatures can sometimes be forged.
Sure, forgery is hard and signature analysis can pick up the vast majority of fakes, but there still remains the slight possibility that a signature may not be legitimate.
So, are signatures non-repudiable? Our society generally considers them to be, but there are always exceptions.
Now, let’s consider fingerprints. If your prints are found at the scene of a crime, then it will be hard to explain the reason why to detectives. Although fingerprints can be forged and analysis techniques aren’t perfect, you’re going to have a difficult time exonerating yourself if you don’t have another legitimate explanation.
So, are fingerprints non-repudiable? In the overwhelming majority of situations, yes, but there are always outliers.
This brings us back to cryptography. One of its advantages is that it can give us non-repudiation, but just like with signatures and fingerprints, it’s not so straightforward. Cryptography allows people to digitally sign data with their private key, linking them to whatever has been signed.
People are supposed to keep this key private, but there are situations where it can be compromised and exposed to attackers. Social engineering and keyloggers are just two examples of ways that attackers can steal keys. Some key owners may also be careless and leave their password lying around for anyone to see.
The point is that if a key has been leaked in any way, then it is possible that the key’s owner was not the person who provided a digital signature. As long as the private key is secure and private, then a key owner can’t repudiate their digital signature.
So does cryptography give us non-repudiation? For the most part yes, but there is some debate (pdf p6) in the cryptographic community about its limitations.
The major principles of cryptography
In this guide, we’ll use examples to teach you about the many concepts involved in cryptography. To start, imagine two children wanting to talk without their parents being able to understand what they are saying.
The children, Alice and Bob, might use a code such as Pig Latin to try and hide their conversations from their parents. Pig Latin involves moving the first letter of a word to the end, then adding the suffix “ay”.
Under this system, knowledge of how the letters are moved and what is added at the end would be the encryption algorithm. Using this code, “Let’s ditch school” becomes:
Et’slay itchday oolschay
This code has two major features. The first is transposition, and the second is padding, which essentially means to add extra information (the “ay”).
This is one of the oldest forms of cryptography. It involves rearranging the characters of the plaintext to different positions. In our earlier example, the first letter of each word is moved to become its last letter. These ciphers can be very simple, like writing a sentence backwards:
loohcs hctid s’teL
An example of a more complex form is the columnar transposition cipher. This cipher involves putting the message into rows of a fixed size. Let’s choose rows of three characters:
l e t
‘ s d
i t c
h s c
h o o
l x t
You will notice that in the last row, we have added two extra letters, “x” and “t”. These have been randomly selected to make the columns the same length and don’t have anything to do with the coded message.
Now that we have our columns, we will number them:
3 1 2
l e t
‘ s d
i t c
h s c
h o o
l x t
This number will be the key. The next step is to arrange our letters by each column, starting with column number one, then moving onto two, then three. This gives us:
When these kinds of classical ciphers are implemented, they tend to leave out the punctuation, but we’ve kept it in to keep things simple.
As you can see, the ciphertext looks like gibberish and would be hard for anyone to figure out without the key. If Alice were to send this ciphertext to Bob, she would first exchange the key of “312” with him, and let him know that they would be using a columnar transposition cipher.
When Bob receives the message of “estsoxtdccotl’ihhl” he will know exactly what to do to decrypt it. Since the key is three digits long, he would divide the text into three sections and assemble them as columns:
e t l
s d ‘
t c i
s c h
o o h
x t l
Now, the key of “312” tells Bob the order that the columns are supposed to be in. The first column is actually supposed to be the third, the second is supposed to be the first, and the final column is supposed to be the second:
l e t
‘ s d
i t c
h s c
h o o
l x t
Now that the columns are in the right order, all that Bob has to do is rearrange the rows back into one sentence:
It’s easy enough to see where the spaces go, so Bob has been able to decode the message in just a few simple steps.
If you wanted to make the cipher more complicated, you could apply columnar transposition twice to make it a double transposition cipher. There are many more transposition ciphers, but these examples should give you a basic idea of how they work and how they can be made more complex.
Let’s say that the Pig Latin code from above works great when Dad is around, but Mom was a mischievous kid and became well-versed in Pig-Latin in her younger days. Alice and Bob need a new code, to keep their communications secret, so they decide to try a substitution cipher instead.
Substitution ciphers involve changing the characters of the plaintext to other characters according to a specific code. One of the simplest forms of substitution is the Caesar cipher, which involves shifting each character a set number of places.
If the Caesar cipher had a shift of one place, then every “a” would be written as “b”, every “b” would be written as “c”, every “c” written as “d”, and so on. Under this code, “Let’s ditch school would become:
Mfu’t ejudi tdippm
As you can see, it immediately masks the actual meaning of the text, but if you had enough time, you would be able to figure out the relationships. Alice and Bob could choose to shift the number of places even further if they wanted to. If they chose a shift of seven, “a” would become “h”, “b” would become “i” and so on.
To decrypt a Caesar cipher, the recipient just needs to know the number of places that each letter was shifted, then move each letter back by that number.
These ciphers can be made more complex by using a key word. The word is generally added to the front of the alphabet to rearrange it to what is known as a deranged alphabet. Let’s use the word “zero” as our keyword:
a b c d e f g h i j k l m n o p q r s t u v w x y z
z e r o a b c d f g h i j k l m n p q s t u v w x y
As you can see, we took “z”, “e”, “r” and “o” out of the alphabet and put them at the front, which shifted the entire alphabet. Using the keyword of “zero”, “Let’s ditch school” would become:
Ias’q ofsrd qrdllh
There are a number of ways that substitution ciphers can be made more complex, but this should give you the general idea of how they work. Most of the encryption that is currently in use involves far more complicated algorithms but their exact mechanisms are outside of the scope of this article.
The different types of cryptography
The four types that we will talk about are symmetric-key cryptography, public-key cryptography, key exchanges and hash functions.
Symmetric key cryptography will be the type that you are most familiar with. It involves using the same key to both encrypt and decrypt data. All of the codes that we have used so far share this property, because the same key is used in both processes, just in reverse.
Symmetric key cryptography is a great option if you are encrypting things for yourself, or if you have a secure channel where you can share the key with whoever needs it. Some of the most common examples of symmetric key algorithms include:
Let’s say Alice and Bob have grown up now and Alice has moved to the other side of the country to go to college. Unfortunately, their Mom is quite invasive and listens in on their phone calls whenever the two children talk. Because of this, they continue to use their Caesar cipher whenever they want to talk about any of their secrets.
The only problem is that Mom has been acting strangely. It’s almost like she knows something, but she won’t let on what it is. Alice and Bob begin to suspect that their code has been compromised, and that Mom knows the key to decrypt their secrets.
They decide that they need a new code, just to be safe. The problem is, how can they share it without their Mom finding out? If she is monitoring all of their calls, then she could hear them discussing the code, and be able to decrypt every secret message that uses the new code. Mom might also open any letters that they try to send, as well as check their emails and their instant messaging apps.
This brings us to what was once one of the central problems of cryptography. How can you securely exchange data with someone when you don’t have a safe way to share the key beforehand?
If you don’t encrypt the data, anyone who intercepts it will be able to read it. If you encrypt it without sending your recipient the key, then they won’t be able to access it. If you send the key alongside the data, then anyone who intercepts the encrypted data and the key will be able to view the message.
This presents a problem for those whose keys have been compromised and don’t have a secure communication channel to distribute new keys, as well as for those who have never previously met and would like to securely exchange information.
It was only solved in the 1970s, with the invention of public-key cryptography. Also known as symmetric-key cryptography, it uses a key pair instead of just a single key to both encrypt and decrypt data.
Alice and Bob would both generate a public and private key. The public key is openly shared, while the private key is kept secret. To send a message that is encrypted with public key cryptography, Alice would first need to find Bob’s public key.
Once the message has been encrypted with Bob’s public key, it can only be decrypted by his private key. Even his public key can’t be used to decrypt it. This is due to some complexities to do with factoring prime numbers, but we won’t go into the math behind it today.
This property allows public keys to be shared openly, because even if an attacker finds out the public key, it can’t be used to break the ciphertext. As long as a private key hasn’t been exposed or compromised, then the only person who can access the plaintext is the owner of the key pair.
The first public-key algorithm to be widely available was RSA, and it is still one of the most commonly used. The only problem with public-key cryptography is that it is quite slow and uses a significantly larger amount of computational resources than symmetric-key cryptography. Because of this, algorithms like RSA aren’t normally used to encrypt whole files or messages. Instead, they are usually used to encrypt symmetric keys.
It works like this: A file or a message is encrypted with symmetric-key encryption, because it is much more efficient. Since there is no secure channel where the symmetric key can be sent to the intended recipient, the sender then encrypts the symmetric key with the public key of the recipient.
The symmetric key isn’t a very big file in comparison to the main message or data, so encrypting just the key with public-key encryption works out to be much quicker and easier.
Now that the symmetric key has been encrypted with the public key of the recipient, it can safely be sent alongside the encrypted data or message. Even if an attacker intercepts both of them, they won’t be able to access the plaintext. Only the person with the matching private key will be able to unlock the symmetric key. Without the symmetric key, the message or data cannot be accessed.
This allows Alice and Bob to safely exchange messages, even if they haven’t had a chance to share a new code without mom listening in. Whenever they want to send a secure message, all they have to do is encrypt the symmetric key with their sibling’s public key.
Now that they have a secure way to communicate, they can either continue using this system, or they could use it to establish a new code that they can use over the phone to resume their secret conversations.
All of this tends to be done automatically with most PGP and other public-key encryption implementations. The most common public-key algorithms include:
- El Gamal
Diffie-Hellman key exchange
The Diffie-Hellman key exchange is an alternative system that can bring about similar results, although it does have different applications. Like RSA, the Diffie-Hellman key exchange can be used to establish secure communications even if no safe channel is available.
It involves two parties building up a shared secret together, which is a symmetric key that they can both use to encrypt further transmissions. The algorithm allows them to create this key together, without ever sending across the whole key.
The mathematical specifics of how it actually works are a bit out of the scope of this guide, but it involves both parties agreeing on two numbers at the start.
Then Alice and Bob will each choose a secret number. Both of them will then apply a formula that uses their two mutually agreed numbers, as well as the secret number they have chosen for themselves.
Alice sends the result of this calculation to Bob, and Bob sends his result to Alice. Next, they both apply a new formula that combines the result they were sent with the secret number that they chose at the start. This formula gives each of them the same result, which is their shared secret.
This shared secret is their symmetric key, which they can use to encrypt any future data or messages. Even if an adversary was monitoring the channel, they wouldn’t have received enough information to figure out the symmetric key.=
This is because the key itself was never transmitted, nor were the secret numbers. The result of the formula that was sent over the channel isn’t enough for an attacker to figure out the secret key.
Hash functions are another type of algorithm that are critical to cryptography. They take data of any length as their input and have an output that is always a predetermined size, which is known as the hash or message digest of the input data.
As an example, when we put the number “1” into an online SHA-1 hash calculator, it gives us a value of:
If we put something much longer into the same generator, like the lyrics from Mambo No. 5, we get the following result:
The important thing to notice is that each hash is the same length, regardless of how big the input was. Another critical aspect of cryptographic hash functions is that the same input will always give you the exact same result. These functions are also essentially impossible to invert, which means that you can’t calculate the original input from its hash value.
Other useful features of hash functions are that they are fast to compute, and it is essentially impossible for two separate messages to result in the same hash. Even the slightest change to the input value will have dramatic effects on the final result.
These properties allow cryptographic hash functions to be put to a number of uses. One of the most important is as a part of digital signatures, which are used to prove authentication and integrity. Some of the most common cryptographic hash functions include:
How can cryptography help us with authenticity and integrity?
As we said earlier, cryptography is used for more than just making messages confidential. It can show whether data is authentic and if it retains its integrity. This is done through a system that involves both digital signatures and certificates.
Now that the two children have a new and secure way to communicate, all of their problems are solved, right? Maybe not.
How do they know that the messages they receive are truly coming from their sibling, and not from their Mom or another attacker? How can they be sure that their messages aren’t being tampered with after they are sent, and that their messages still retain their original form?
These are issues of authenticity and integrity, which can be addressed with digital signatures. Digital signatures can be added before or after a message has been encrypted, or they can even be used without encrypting the message.
If a message has been digitally signed but not encrypted, then its authenticity and integrity can be proven, but it won’t be confidential. In most cases, it is recommended to sign a message before encrypting it.
We’ll use an example to give you a better idea of how digital signatures can work. If Alice wants to sign her message to show Bob that the message is authentic and that it retains its integrity, she would first type out her message, then run it through a hash function like SHA-256.
If you remember the section on hash functions above, this algorithm will give a fixed-size output that is always the same for a given input. The other important thing to remember here is that it is unfeasible for two separate inputs to give the same output. Hashes are used instead of the entire data set because it saves on time and computing power.
Alice then signs the hash value of the message with her private key. This encrypted hash value is the digital signature. If Alice wants the message to be confidential, they she can encrypt it as well. She then sends the digital signature to Bob alongside her message.
When Bob receives the message, he can check the authenticity and integrity of the message by using the same hash function on the message. He also decrypts Alice’s digital signature with her public key and compares the two results.
If the hash value of the decrypted digital signature and the hash value of the message are the same, then this means that the message has not been tampered with, and that it was signed by Alice’s private key. As long as Alice’s private key has not been compromised, then the message is authentic and retains its integrity.
Most of this happens automatically, but these steps should give you a rough approximation of what is actually taking place when digital signatures are used. The process requires both a public-key algorithm and a cryptographic hash function, such as those that were discussed earlier in the article.
Since the children can use digital signatures to prove that their messages are authentic and arriving intact, they don’t have anything else to worry about, right?
Unfortunately, there are still some ways that this system can be undermined.
Let’s turn back time and examine how things could have worked out if Mom was more diabolical. Let’s say that Mom was never able to figure out the children’s code. Instead, she came up with an ingenious plan.
What if she sent Alice a message over another channel, in which she pretended to be Bob. She could tell Alice that “Bob” was worried that their mother may have cracked their code and could understand their correspondence.
As long as the story was elaborate enough, Mom would be able to convince Alice that she was actually Bob, and that they needed to find a new way to communicate securely. That’s when she came up with the scheme of using public-key cryptography.
Since Alice and Bob didn’t know much about cryptography, they fell straight into their mother’s trap. When Alice received a message from “Bob”, she genuinely thought that their code had been broken, and she was easily manipulated into adopting the new system.
When Alice thought that she was communicating securely with the Bob, all of her secrets were actually going straight to her Mom. How could the Alice have prevented herself from falling for this trap?
Cryptography’s solution is to use digital certificates. These connect an online identity with a real life person or entity. They form a trusted link between the actual person or organization, their public key, and their digital signature. There are two ways to form this trusted link, with certificate authorities or the web of trust. Each of these are used in different systems.
This is the more commonly used solution and it involves central bodies, known as certificate authorities (CAs) that certify the person or entity who claims to own a public key really is the owner.
Some of the most popular CAs include:
- Let’s Encrypt
There are a number of different certificates that CAs can issue. Each of these requires varying amounts of proof that tie the individual or entity and their public key together. The more thorough the check, the more trustworthy a certificate is considered.
Since the mother is not actually Bob, she would not have been able to acquire a trustworthy certificate that connected her public key to Bob’s identity. This system helps to prevent attacks such as the one that Mom attempted against Alice.
Digital certificates are used in many other situations. Some of the common certificate types include:
- TLS certificates for both clients and servers
- Email certificates
- Root certificates
- Code signing certificates
Web of trust
Certificate authorities have their weaknesses, because they involve trusting a central power. Centralized bodies can always be corrupted, which presents a significant point of weakness. The web of trust was developed for PGP to get around these issues.
Think of the web of trust as an interconnected group of trusted people. If you have two close friends who are both PGP users, you can sign their certificates to say that you verify the link between who they are and their public keys.
If each of your friends has two more trusted friends who use PGP, then they can each sign each other’s certificates to verify that they are who they say they are. These people can do the same to their friends and so on.
The result is a web of trust. Since you trust your friend, they trust their friend and so on, it builds up a large interconnected web of people who trust each other based on the trust in each link. It’s kind of like a game of Six Degrees of Kevin Bacon, where you can use the trust of other PGP users to link you to anyone else who is in the web.
If Alice and Bob were to use the web of trust model to validate their identities, they would need to get their certificates signed by a number of other trusted PGP users to prove that they are who they claim to be.
Is cryptography safe?
We’ve used an example of two children and their Mom throughout this article as a lighthearted way of illustrating how these concepts work. Cryptography can certainly be used by children to keep secrets from their parents, but it sees most of its use in securing our communications.
Cryptography was originally used by governments and militaries to protect their secret information. Now that so much valuable data is shared online, it’s also involved in many aspects of our daily internet use.
Without cryptography, we wouldn’t be able to use the web in the way that we do. If we tried to, our lives would constantly be plagued by stolen information, identity theft, and bank accounts being drained by criminals.
Cryptography helps us in a wide range of applications, but it’s still not perfect. New attacks are always being conjured up, and more complex systems are deployed to keep them at bay.
One of cryptography’s main weaknesses tends to be in how it is implemented. It’s common for algorithms themselves to be secure, but for hackers to use other systematic weaknesses such as side-channel attacks to break the systems.
Another key issue is that confidentiality, authenticity, integrity and non-repudiation all rely on the presumption that a private key has not been compromised. Even with the best key storage techniques, it’s still possible for keys to be stolen from their owners. When this happens, the whole system crumbles.
Despite these potential issues, the reality is that they are pretty rare circumstances. In general, if we use cryptography correctly, it can provide us with a high degree of security. While cryptographic techniques may not be perfect, they make the world much more secure than it would be without them.