Secret messages

eetmn emt ybc lueba illhx
When I was in elementary school, my friends and I came up with a "secret language" which we used to send messages to each other without others (e.g. teachers, classmates) knowing what the message said. It was not really a new language more than it was a variation of Pig Latin. What we did was we would write the message in English, then take the first letter of each word, shift it to the end, and then add an arbitrary letter to the end of the resulting word. For example, to translate the word "hill" into our secret language, take the first letter 'h' and move it to the end so that the word becomes "illh". Then, add any letter you want to the end of that. The intent of the last letter was to throw people off, leading them on into thinking the last letter was meaningful, when it really was just arbitrary, and it also meant that the same English word can be represented in at least 26 ways. To translate back into English, you would simply reverse the process: shift the second-to-last letter of the word to the beginning and simply discard the last letter.

The phrase eetmn emt ybc lueba illhx therefore means "meet me by blue hill" in our Pig Latin variation. It wasn't the most brilliant scheme, and I'm sure that if anyone stared at the messages we wrote long enough, it would have been broken eventually, but for elementary school, it worked well enough. In fourth grade, there was a kid who had a tendency to become excessively physical or even violent when playing at recess, so my friends and I started trying to avoid him. However, he would always overhear our conversations and show up where we were meeting at recess despite us asking him to stop. We used our secret language to pass notes like "eetmn emt ybc lueba illhx" to each other as a means of avoiding him. As far as I am aware, the kid never figured it out – to him, it looked like we were just passing gibberish to each other.

The messages we wrote weren't really in a new language, but instead a cipher of an existing language. In a rudimentary way, we took an English sentence and encrypted it, rearranging the letters so that the message was understood by people familiar with the encryption scheme, but confusing to those unfamiliar. In the world beyond elementary school, there are numerous legitimate reasons why someone might want to send an encrypted message. Whenever you do online shopping, for example, you are typically asked to provide your credit card number. It is possible for an attacker to intercept the transmission between you and the online merchant, and if the message is not encrypted, then that person will now have your credit card number. Oops.

The scientific study of sending secret messages is called cryptography. Interest in cryptography blossomed at the beginning of the twentieth century during the two world wars. These were among the first major wars in which electronic communications played an integral role. Each side of the war actively intercepted messages sent by the opposing side. Accordingly, they needed to find a way to encrypt their communications so that the enemy wouldn't be able to read them even if they intercepted them. Conversely, they needed to find a way to decrypt the enemy's communications in order to read them. The governments and militaries of some of the most powerful countries threw their best intellectual minds into cryptography research.

One German engineer named Arthur Scherbius invented an encryption machine called the Enigma machine which became integral to German military communications during World War II. If you're interested in how it works, I recommend watching this YouTube video presented by the phenomenal mathematician Dr. James Grime on the channel Numberphile. British cryptanalysts during World War II discovered a flaw in the way that the Germans were using the Enigma machine (which is explained by Dr. Grime in the Numberphile video). Exploiting the flaw, a British mathematician named Alan Turing developed a machine called the Bombe which could find the settings to the Enigma machine, enabling the Allies to decrypt German communications. It's difficult to say for certain, but some historians have estimated that this work may have shortened World War II by as much as two years, saving fourteen million lives. The story is dramatized in the 2015 film The Imitation Game, starring Benedict Cumberbatch.

Today, electronic communications have ingrained themselves as a fundamental part of our everyday lives. Computers have enabled us to perform mathematical calculations quicker than ever before, and ability of computers to perform more and more complex operations only increases every year. This has made communications security and cryptography central fields of study in mathematics and computer science. How can we train computers to encrypt and decrypt data in a way that is secure and in a way that is difficult for another computer to break?

RSA

For the rest of this post, I would like to describe a method of encrypting information called RSA. RSA stands for Rivest–Shamir–Adleman, the designers of the system. The method is a bit more math-heavy than the Pig Latin variation that my friends and I came up with in elementary school, but I claim that it is actually not that difficult to understand once you wrap your head around a few key ideas. It is widely used in the world today as a means to encrypt communications, and because it is so important, I think everyone should at least strive to get a broad understanding of how it works.

The first key idea you should wrap your head around is that a message in words can be represented by a number. You may have heard before that computers store data as a series of ones and zeroes. Most computers use a standard called ASCII (pronounced "askee"; short for American Standard Code for Information Interchange) to convert letters into numbers. In ASCII, the capital letter A is the number 65, the capital letter B is the number 66, and so on until the capital letter Z, which is the number 90. A space is the number 127. If, for example, I wanted to write my first name, MICHAEL, in ASCII, I would send the numbers 77 (M), 73 (I), 67 (C), 72 (H), 65 (A), 69 (E), 76 (L). (This is a simplification; computers store data in binary, so ideally I would be sending a bitstring with every eight bits in the string referring to a character in ASCII. Here is a nifty table with a number of different characters and their number in ASCII.)

So, I have my number, 77, which my recipient can read and turn into the first letter of my name, M. Now I want to encrypt this number so that my intended recipient can easily decrypt it, but not anyone else. The solution lies in keys. Imagine I give you and everyone else in the world a "key" that allows you to encrypt messages to me – we'll call this the public key. Now suppose I have a different "key" that allows me to decrypt messages that others send to me – we'll call this the private key. You can imagine this scheme might be useful for an online merchant like Amazon. Amazon would publish its public key so that it is visible by anyone in the world, whereas only it would have access to its private key. That way, anyone can encrypt messages – e.g. my credit card number – using the public key, send it over to Amazon, and only Amazon would be able to use its private key to decrypt the message. Sound good? All right, let's implement it!

The second key idea that you should wrap your head around is the concept of a prime number. You probably know what a prime number is if you've studied algebra in high school. It is a number that cannot be evenly divided by any number besides 1 and itself. 17 is a prime number, for example, and 15 is not a prime number because it is divisible by 5 and 3 (incidentally, 5 and 3 are prime numbers).

The third key idea is modular arithmetic. You use modular arithmetic everyday whenever you tell time. If you use a 24-hour clock, the hours go from 0 to 23, but there is no such thing as hour 24 – instead, the numbers wrap back around to 0 and the cycle repeats. Actually, we can say that there is a notion of hour 24: in the world of clocks, 24 is equivalent to 0. In other words, in the mathematics of clocks, 24 is the same number as 0. We typically use a triple equals sign to denote this equivalence: 24 ≡ 0 (mod 24). Mathematicians call this universe of clocks "modulo 24". Modulo 24 is a universe of just the natural numbers from 0 through 23. We can perform arithmetic operations using just these numbers. Which hour is five hours after 23:00 (i.e. 11:00 pm)? Well, first add 23 + 5 ≡ 28 (mod 24). Then find the number that 28 is congruent to, modulo 24. That number is 4: think of 4 as the remainder of dividing 28 by 24. Thus, 23 + 5 ≡ 4 (mod 24). Indeed, 4:00 is five hours after 23:00. Subtraction and multiplication can be done in a similar fashion.

Division can also be done in modular arithmetic, but it is a little harder, and you have to be a little more careful. If you have an equation like 12x ≡ 60 (mod 100), where 12 evenly divides 60 and both numbers are valid numbers modulo 100, then you can divide normally to find that x ≡ 5 (mod 100). However, in the modular world, we only have integers. We don't deal with fractions, so an equation like 9x ≡ 1 (mod 11) cannot be x = 1/9 (normally, we would divide both sides by 9 to get a fraction).

To find the solution to 9x ≡ 1 (mod 11), we have to think about the algebra a bit. What are we really doing when we "divide both sides by 9" in normal arithmetic? We want to get rid of that coefficient 9 so that the x is isolated on the left side of the equation, and the right side of the equation is the value that x is equal to. When we divide both sides by 9, we are turning the 9 into a 1 (9/9 = 1), and 1 times x is just x, meaning x is now isolated! What we are really doing is multiplying both sides by the multiplicative inverse of 9. The multiplicative inverse of a number n is the number that produces 1 when multiplied with n. In the real numbers, 1/9 is the multiplicative inverse of 9 because 1/9 times 9 is 1. Similarly, 1/10 is the multiplicative inverse of 10 (because 10 * (1/10) = 1), and 1/2 is the multiplicative inverse of 2 (because 2 * (1/2) = 2).

So in order to find what the solution to 9x ≡ 1 (mod 11) is, we have to find what the multiplicative inverse of 9 is modulo 11. It is not 1/9 because fractions don't exist in modular arithmetic. We have to ask ourselves, what number multiplied by 9 gives 1 modulo 11? Thinking about it a bit, perhaps guessing and checking a bit, we can deduce that x ≡ 5 (mod 11). 9 times 5 is 45 in normal arithmetic, and 45 is the same number as 1 modulo 11. Hence, 9 * 5 ≡ 1 (mod 11). In practice, we have an efficient algorithm called the extended Euclidean algorithm, which we can use to find multiplicative inverses without the need for guess-and-check. (Sometimes there is no multiplicative inverse; this sometimes happens when the coefficient shares a common factor with the modulus. For example, 9x ≡ 1 (mod 12) has no solution. Think of it this way: there is no multiple of 9 that would result yield a remainder of 1 when you divide it by 12. As long as the coefficient and the modulus share no common factors, then the coefficient has a multiplicative inverse in that modulus.)

So we have our three key ideas in place:
  1. A message in words can be represented by a number.
  2. A prime number is a number which cannot be evenly divided by any number besides 1 and itself.
  3. Modular arithmetic is arithmetic over a field of numbers that wrap around themselves. Division in modular arithmetic is done by multiplying by the multiplicative inverse.
Got it? Okay! Here is the RSA scheme.
  • Pick two distinct prime numbers. We'll call them p and q. These should be very large prime numbers.
  • Let N be the product of multiplying p and q. In other words, let N = pq. Pick a whole number e which shares no common factors with the product of multiplying the quantities (p - 1) and (q - 1).
  • Our public key is this number N along with e.
  • Our private key is a number d, the multiplicative inverse of e modulo (p-1)(q-1).
  • Let the message we want to send be the number m. To encrypt the message, we raise m to the power of e modulo N. In other words, we find the product of multiplying m with itself e times in modulo N. In symbols, our encrypted messages is me (mod N).
  • To decrypt the received code-message me, we raise it again to the power of our private key, d, modulo N. In other words, med ≡ m (mod N).
Let's use our number 77 (which is the letter M on the ASCII table) as an example! We'll start by picking two prime numbers p and q. Let p = 5 and q = 17. Thus, let N = pq = 85. Let e = 3. Choosing e is kind of arbitrary, but it needs to be a number that has a multiplicative inverse modulo (p-1)(q-1), which is 64 in this case. 3 shares no common factors with 64, so it does have a multiplicative inverse. The multiplicative inverse of 3 modulo 64 is 43, so 43 will now become our private key, d.

Ideally, p and q should be very large prime numbers (like, prime numbers that are 2048 digits long in binary). The security of RSA stems from the proposition that very large numbers are very hard to factor. If an attacker were able to determine p and q from N, then RSA would be broken. With small prime numbers, it is very easy to factor out 5 and 17 from 85, and an attacker can then deduce that the private key is 43 with this information. On the other hand, with our current computing power, no one has ever been able to factor a 2048-bit number into its constituent prime factors without knowing at least one factor beforehand. A brute force algorithm (checking every possible number by seeing if it divides evenly) would take a longer time than the universe has existed.

So let's encrypt and decrypt the message 77! To encrypt the message, we have to raise 77 to the power of e modulo N. In this case, we need to find the result of 773 (mod 85). The answer is 83. Thus, if an attacker intercepts my message, they will get the number 83. Even if they know what N and e are (85 and 3 in this case), they will need to know the decryption key d (43 in this case) to actually decrypt the message. Without knowing d, they will have no information about how to decrypt the message. (As I mentioned in the last paragraph, it is easy to find d from 85 because 85 is easily factorable. However, very large prime numbers are decidedly not so easy to factor.)

To decrypt the message, the person with the private key d needs only to raise the encrypted message, 83, to the power of d modulo N to get back the original message, 77. In this case, d is 43 and N is 85, and indeed, 8343 ≡ 77 (mod 85).

For a more detailed explanation of RSA and a proof of its correctness, check out this set of notes published by the instruction team at UC Berkeley for the class that introduced me to RSA.
Posted by