Mathematical Foundations for Cryptography: Part I

Cryptography is the science of secure communication. Two entities (people) want to communicate in some sort of public space without anyone being able to understand what is being said, except for the two entities involved. While this field has ancient roots, it is a very important study today, when millions of people are sending sensitive information over the internet every day. The processes to achieve secrecy on the web are complex and sophisticated, but underlying them are some fundamental mathematical concepts.

The goal of this series is to convince the reader that it is possible for two entities to communicate securely on a public network using pure math — no electronics required (although a calculator would be handy). “Securely” here means two things:

• The parties know that the person they are communicating with is who they say they are
• The messages that they send cannot be understood by anyone else that may be reading them

I recommend grabbing a pad of paper and a pencil to write out some of the math that we will be going through.

HTTPS

The methods we will explore are the basis of modern web security. HTTP (Hypertext transfer protocol) is a standard that defines how two machines on the web communicate with each other. The two machines are typically the client (the browser running on your machine) and the server (the website you are interacting with). In regular HTTP, the messages sent between the two parties are essentially in plain text. So if you type your email or credit card details into a form and press “submit”, then that information — as you typed it — travels along the network. If anyone else is listening in on the network, then they can peer in and see your information. HTTPS (note the S) ensures both aspects of security mentioned as part of our goal: Authentication and encryption. We are going to focus on the mathematical principles that underlie this layer of security.

Setting the Scene

To help illustrate this scenario, we are going to set up a contrived microcosm of the web. Suppose a group of mathematicians, tired of a world where math is under-appreciated, have decided to live a secluded and monastic mathematical life in the Himalayas. They don heavy maroon robes that cover their bodies and faces, and they take a vow of silence. There are 24 of them, so each is assigned a Greek letter as their new name (Alpha, Beta, Gamma, … Omega). In the common area of their temple is a large whiteboard. The only way they are allowed to communicate is by drawing on the whiteboard. This means that all the other mathematicians will be able to read what everyone else has written. There are no secrets. Since they are fully cloaked with their faces covered, the only way one could tell who is writing is if they sign their name.

Communication might proceed as follows. The mathematician named ‘Theta’ might write the following on the whiteboard, signed with his Greek letter name:

Theta: The sum of the square roots of any two sides of an isosceles triangle is equal to the square root of the remaining side.

Then the mathematician named ‘Iota’ might reply below it:

Iota: That’s a right triangle, you idiot!

Life starts out well for these mathematical monks, but eventually friendships and rivalries begin to form. One in particular, Alpha, decides she wants to send a private message to another mathematician, Beta. But she also wants to stick to her vows. So here is a summary of the situation:

• Alpha wants to send a private message to Beta
• She can only communicate by drawing on the whiteboard
• Anything written on the whiteboard can be seen by everyone
• No one can be uniquely identified, other than by signing their name on the whiteboard after writing a message

Again, this is a very contrived scenario to illustrate communication over the web. We want to send private information to certain websites, without the messages being readable to outside observers, and we want to be able to know that the entity we are communicating with is who they say they are.

PART I: CIPHERS

Caesar Cipher

Being mathematicians, everyone in the temple is familiar with the various cryptographic systems out there. One such system is the Caesar cipher, and it could work as follows. Suppose Alpha wants to send the following message to Beta, and only to Beta:

“MY REAL NAME IS ALICE”

She can’t simply write that on the board, since then everyone else will be able to see it. She needs to use a cipher. Let’s assume for now that Alpha and Beta have somehow planned in advance to communicate using a Caesar cipher with a key of 5.

So instead of writing “MY REAL NAME IS ALICE” on the whiteboard, Alpha would do the following:

1. Convert every letter to a number (A = 1, B = 2, C = 3, …. Z = 26)

2. Use her “key” of 5, and add 5 on to each new letter

3. She would then convert the new letter back to a number (1 = A, 2 = B, … 26 = Z). If any of the numbers went over 26 when she applied her key, she would restart back at 1. So 27 would be the same as 1, 28 is the same as 2, 29 is 3, and so on.

Note that the Y (25) becomes 30 when 5 is added to it. This is a case where we would “restart” back at the beginning of the alphabet. 27 corresponds to A, 28 = B, 29 = C, and 30 = D, which is equivalent to 4. Alpha would perform these calculations on her own, and then on the whiteboard she would write:

Alpha: R D W J F Q S F R J N X F Q N H J

This process of encryption gives an encrypted text, also called the ciphertext. Since Beta knows that Alpha is communicating using a Caesar cipher with a key of 5, he would just need to work backwards. He would convert each letter into a number, subtract 5, and then convert back to a letter. This is the process of decryption. He would be able to calculate that the message reads “M Y R E A L N A M E I S A L I C E”.

This is a very simple and intuitive cipher, but it is also incredibly easy to break. Suppose Omega wants to eavesdrop on the conversation. She can read the encrypted message from Alpha, since everything is public. Even if she doesn’t know the key of 5, if she suspects they’re using a Caesar cipher, she can easily crack the code.

She knows that some letters appear more than others in the English language. ‘E’ is much more common than letters like ‘Z’, ‘Q’, or ‘X’. So if a certain letter shows up quite often in a Caesar Cipher, then it’s a good indicator that it corresponds to the letter E. So if Omega reads the ciphertext, she notices that both F and J appear 3 times each. So she starts by supposing that F corresponds to E. F is 1 letter ahead of E, so if that corresponds to a key of 1. So Omega makes this guess and works backwards from the ciphertext that she sees. She ends up with the following: “Q C V I E P R E Q I M W E P M G I”

This is nonsense, so Omega concludes the key is not 1, and moves on to her next guess, J. J is 5 letters away from E, so that corresponds to a key of 5. Working backwards, subtracting 5 from each letter, she will get the original text. The code would be cracked in only 2 tries. The Caesar cipher is not a very secure key. Alpha understands this drawback very well, so she decides she will not be using a Caesar cipher.

The Polyalphabetic Cipher

Alpha and Beta must agree on a more sophisticated encryption scheme if they are to communicate privately. Instead of a Caesar cipher, Alpha considers the Polyalphabetic cipher (also called the Vigenere Cipher). In this case, instead of choosing a single number (like 5), she is going to pick a longer key, say 1–5–7–6.

To use this key, she starts by once again lining up the letters of her plain text “M Y R E A L N A M E I S A L I C E” and converting to the appropriate numbers. Next, she will line up her key, which consists of 4 digits, in a repeating pattern below those numbers, and then add the corresponding amount to the original letters. Once again, she can convert these back into letters.

On the whiteboard, Alpha could then write:

Alpha: N D Y K B Q U G N J P Y B Q P I F

This is going to be quite a bit harder to crack, since Omega won’t be able to simply look at the frequency of letters and work backwards. However, If Omega is able to guess the length of the key, which in this case is 4 (number of digits in 1576), then she can start to look for patterns within those chunks. So she could look at all the letters that are 4 spots apart and see if there are any higher frequency patterns that stand out. This is still breakable, but it’s an extra layer of security that may just deter Omega from trying. Alpha weighs the pros and cons of this approach, and decides this type of cipher is safe enough for her purposes.

There are many other encryption schemes that could be used. A common one used in modern web security is AES (Advanced Encryption Standard). We will not cover it here, but it is enough to know that like these first two ciphers, it relies on a special “key” that must be kept secret.

So Alpha has decided on the polyalphabetic cipher, but there is still a major issue with this system. Remember, all communication in this temple is public and takes place on the whiteboard. So how does Alpha communicate to B that she wants to use the Polyalphabetic cipher with a key of 1576? Suppose she writes the following on the board:

Alpha: Hey Beta, let’s communicate using a polyalphabetic cipher with key 1576

Since all communication is public, Omega can see this as well, and there is no point in encrypting anything, since the attacker knows the key and the encryption method. So we need a way for Alpha and Beta to generate a secret key that only the two of them will know, and this must be done while communicating in the open. Sounds impossible, right? Not if you have the right mathematical tools.

The second part of this 3-part series will address this.