Securing messages is a significant problem that people have been trying to solve for well over 2000 years. This problem can be solved in part by using encryption. Historically, militaries and governments have employed encryption, but this technology is rapidly spreading to civilian applications, like sending emails over the internet. For example, your Wi-Fi network probably—really, it should—encrypts its connections using the security protocol WPA2. In this blog series we’re going to walk through the basics of encryption. We’ll see how cryptographic algorithms have developed, how they work, and how they may be threatened by quantum computing.
Let’s meet Alice and Bob, who like to send emails to each other over the internet. Unfortunately, they’re not aware that Eve is eavesdropping on their communications. Some of these emails contain sensitive data on Alice and Bob’s joint business ventures, but Alice and Bob are not protecting their emails. Eve is able to easily glean the details of these business data without Alice and Bob’s knowledge (or permission). This is a very real problem for Alice and Bob. Is there any way for their messages to be protected from Eve? As it turns out, there’s a very simple tool Alice and Bob can employ to protect their communications: Encryption.
Before we get into the nitty gritty, let’s establish some basic definitions that we’ll be using throughout this series. First, plaintext is any unobscured message. For example, Bob may want to send the plaintext “HELLO” to Alice. If he wants to secure his message, he needs to obscure it by using an encryption algorithm, or cipher. In the broadest sense, a cipher takes two inputs: A plaintext and a secret key (denoted k) that is used to encrypt the plaintext. Suppose Bob uses a particular cipher with the key k that encrypts the plaintext “HELLO” as “KHOOR”. Bob is able to send this ciphertext to Alice over an unsecured channel like the internet. Alice can then use the same cipher and key to decrypt the ciphertext to retrieve Bob’s plaintext. This whole scheme works great in principle because Eve has no idea what the ciphertext “KHOOR” means, even if she knows the cipher. Where this breaks down, however, is in the key. The cipher’s key is critical to an encryption scheme’s security.[1] A problem we’ll see soon in this series is how to securely exchange keys between Alice and Bob. For now, though, we’ll assume that Alice and Bob have either agreed upon a key or have exchanged it through a secured channel like a trusted phone line.[2]
Let’s take a look at simplistic classical ciphers: The substitution cipher. In this cipher, we map letters to one another so we can substitute them between plaintext and ciphertext. The Caesar Cipher is one of the best-known substitution ciphers, but it’s also among the weakest. Essentially, the Caesar method “shifts” the 26 letters of the Latin alphabet according to a set amount. We shift to the right to encrypt, and we shift to the left to decrypt. The shift amount is the cipher’s key. Legend has it that Caesar was fond of using the key k = 3. So, “A” would become “D”, “B” would become “E”, and so on. But which letter comes three letters after “X”? Well, there are no letters after “Z”, so we wrap around to “A”. That is, “X” maps to “A”, “Y” to “B”, and “Z” to “C”. Great, but why does this work? Why do we wrap around the alphabet like that? The answer lies in the special arithmetic we use to encrypt (and decrypt) the letters.
Modular arithmetic allows us to wrap around the alphabet in the Caesar Cipher, and it’s fundamental to many of the other ciphers we’ll be seeing in this series. How does it work, though? It turns out we’ve been using modular arithmetic for most of our lives. Imagine it’s 10:00 in the morning, and Bob wants to meet Alice in 20 hours. What time are they meeting? We could say that they’re meeting at 30:00, but that’s silly. The correct time would be 6:00 the next morning. How did we reach that conclusion? If we begin at 10:00 on the clock and wrap around 20 hours, we eventually make it to 6:00. Mathematically, we divide 30 by 24 and get one with a remainder of six. More precisely, we perform modulo: (that is, 30 is congruent to six, modulo 24).[3] In other words, we have a modulus 24, a dividend 30, and a remainder of six. That six corresponds to 6:00 on our clock. Neat!
Let’s get back to the Caesar Cipher. We could operate it by hand, but computers don’t have hands. We want to express this cipher mathematically instead because computers think in mathematical terms. When we encrypt a letter, we shift it to the right by the key amount, and we decrypt by shifting to the left. That is, we add the key to the letter, or we subtract the key from the letter. But, we have to be able to wrap around. That’s where we use modulo. Note that we aren’t adding and subtracting the letters directly because that doesn’t make sense mathematically. Instead, we use the indices, or positions, of the letters in the alphabet. Beginning with “A”, we number from zero to 25.[4]
So, to encrypt a plaintext x with a key k, we say ek (x) ≡ (x+k) mod 26. To decrypt a ciphertext y with a key k, we say dk (y) ≡ (y-k) mod 26. For example, the letter “A” is at position zero in our alphabet. To encrypt the letter “A” with the Caesar Cipher, we say e3 (A ) ≡ (0+3) mod 26 ≡ 3 mod 26. We get three, which corresponds to “D” in our alphabet. To decrypt, we say d3 (D) ≡ (3-3) mod 26 ≡ 0 mod 26. That zero corresponds to “A”. So, if we encrypt the plaintext “HELLO” using the Caesar Cipher, we get the ciphertext “KHOOR”. If we decrypt the ciphertext “KHOOR”, we get the original plaintext “HELLO”. This will be true for any plaintext-ciphertext pair, as long as we use the same key for encryption and decryption within the Caesar Cipher.
Substitution ciphers like the Caesar Cipher are nice, but we really should use stronger algorithms. Any determined person could break these ciphers through trial and error. We would be very upset, then, if weak substitution ciphers were used in our banks’ chip-and-PIN technology or in our Internet of Things devices.[5] Basic substitution ciphers are weak due to their simplicity and their key lengths, but we can easily improve upon them. The interesting part is how we use and share the key. There are two algorithmic families that attempt to solve this problem. Symmetric algorithms use the same key for both encryption and decryption, like with the Caesar Cipher. Asymmetric algorithms use a public key for encryption and a private key for decryption. We’ll see how this all works in this series’ next parts. We’ll also see that best practice is not to rely on one cipher but to combine powerful ciphers to create a securer system.
[1] This is a paraphrase of Kerckhoffs’ Principle, which is fundamental to encryption.
[2] Why not just build and use a permanent, secured network? Well, in theory, you could do this, or you could secure the entire internet. But, these are expensive propositions. It’s actually cheaper to leave the network (relatively) unsecured and secure the communications that traverse the network.
[3] Why the funny three-bar equal sign? In normal arithmetic we deal with strict equivalences signified by the normal equal sign (“=”), but with modular arithmetic we are dealing with congruencies. These values are not strictly equivalent but are congruent under modulo.
[4] We start counting at zero because it’s mathematically convenient. With modular arithmetic, the possible range of values is [0, …, n – 1], where n is the modulus. So, for the Latin alphabet, where n = 26, we have a range of [0, …, 25].
[5] The EMV standard actually specifies use of the symmetric AES and DES algorithms and the asymmetric RSA algorithm. We’ll learn more about these in future posts.
