17 March 2016

Modular arithmetic is math that happens on a number circle instead of the traditional number line. The circle starts at 0. But instead of stretching on to infinity like the number line, the number circle wraps around on itself when it reaches a certain value.

For example, if math occurs “mod 26”, then the moment you reach 26, you immediately wrap around to 0. In other words, the circle contains the numbers 0 through 25 and 0 is equivalent to 26 mod 26, or to 52 mod 26. The number 1 is equivalent to 27 mod 26, or to 53 mod 26.

When you work with the alphabet mod 26, you can express "A" as 0, "B" as 1, and so forth, with "Z" being 25. You can even ask questions like what is "D" multiplied by "V"? (Hint: It's "L".)

**Challenge:** What is 23+7 equivalent to, mod 26? What might -1 be equivalent to, mod 26?

You are probably one of the millions of people around the world who use Facebook every day. Every time you log in to Facebook, you need to send your password to the company’s server. That server is likely located thousands of kilometres from where you live. On its way from your device to the server, your password might pass through dozens of computers. So how can you make sure that no one can eavesdrop on your communications, steal your password, and get access to your account?

The answer lies in **encryption** (or "enciphering"), which transforms a message that anyone could read into a message that only intended recipients can read. This process requires two important tools: an algorithm and a key.

An **algorithm** is a method used to transform the message. The Caesar algorithm is a classic example. It changes each letter in a message into a different letter by adding a secret value “mod 26” to each letter. If the secret value were 3, the Caesar algorithm would “add 3 mod 26” to each letter. In this case, "A" becomes "D", "B" becomes "E", and "C" becomes "F". The “mod 26” refers to looping back to the start of the alphabet after you reach the 26th letter. So "X" becomes "A", "Y" becomes "B", and "Z" becomes "C".

Using the Caesar algorithm, the message "Hi you" would be enciphered to "Kl brx". To decipher the message, the recipient would have to "subtract 3 mod 26" to reverse the process.

A **key** is a small, secret bit of knowledge that the sender needs to share with the recipients so they can decipher the message. In the example above, the secret value of how much to add to each letter (3) is the key. But there is no reason that the people exchanging messages have to choose 3 as their key. The Caesar algorithm has 26 possible keys. But one of them would create an encrypted message identical to the original. Can you figure out which one?

Of course, modern encryption algorithms are much more complex than rotating individual letters around the alphabet. In fact, these algorithms are so complicated that experts spend years designing and studying them. They also have billions and billions of possible keys, rather than just 26.

There are two main types of encryption algorithms: symmetric and asymmetric. The main difference is how many keys are used to encipher and decipher the message.

**Symmetric encryption** uses a single secret key shared among the sender and all recipients. For example, Alice, Bob, and Carol all have a secret key that no one else knows. That means any one of them can encipher a message in such a way that only the three of them can decipher and read it.

There are also times when you would want to have a symmetric key that nobody else knows. That way, you could store your private data in such a way that no one else could steal it (unless they also stole your key!).

**Did you know?** Certificate authorities such as Verisign and Thawte use asymmetric encryption to “sign” the public keys released by websites like Facebook. This lets you verify that the public key you get from Facebook really is from Facebook and not from an imposter.

**Asymmetric encryption,** also called public-key encryption, uses two different keys. This "key pair" includes both a public and a private key. Only the opposite key in the key pair can decipher what the other key has enciphered.

For example, everyone might know Alice's public key, but only she would know her private key. That way anyone could encipher a message that only Alice will be able to read. Amazingly, if Bob enciphers a message using Alice's public key, not even he will be able to decipher it! But maybe that isn’t such a big problem, since Bob was the one who wrote it.

Public-key cryptography can even be used to verify who wrote a message. For example, Alice could encipher a message using her private key and send it to everyone. They could all read it, since everyone knows Alice's public key. But the fact that only Alice's public key can decipher the message also proves that Alice must have been the one that wrote it. That’s because only Alice knows the private key that enciphered the message.

Most enciphered messages exchanged on the Internet use symmetric encryption. That’s because computers can perform symmetric enciphering and deciphering much, much faster than asymmetric enciphering and deciphering. Internet communications are therefore significantly faster when symmetric encryption is used, instead of asymmetric encryption.

**Did you know?** Encryption is one branch of a broader field of study called cryptography.

In public-key encryption, only the private key can decrypt what the public key encrypts. Of course, this means that people must not be able to compute the private key based on the public key! How is this accomplished?

In the case of the famous RSA public-key algorithm, both keys are computed at the same time, based on some randomly generated temporary numbers that will relate the two keys to each other. Those temporary numbers must be destroyed, or at least kept secret like the private key, after the new key pair is computed.

However, there is a problem with symmetric encryption: the sender and all of the recipients need to share a secret key. For instance, if you want to send your password to Facebook using symmetric encryption, you need to share a secret key with Facebook. But you can’t just send Facebook a secret key to use (or have Facebook send you a secret key) unencrypted over the Internet every time you want to connect. If you were to do that, anyone eavesdropping on the Internet could easily steal the unencrypted key. That would allow them to decipher all your later encrypted messages to Facebook, including your password.

The trick to achieving communication that is both fast and secure is to use a combination of symmetric and asymmetric encryption. For example, when you use the protocol called Transport Layer Security (TLS), the one that makes the little lock appear in your browser, you begin with slow (asymmetric) encryption. TLS uses Facebook's public key to start communicating with Facebook, but just long enough to agree on a temporary shared secret key. You can then start using this shared key to communicate with Facebook using fast (symmetric) encryption.

In fact, it’s only after TLS and Facebook have agreed on a temporary shared secret that the Facebook login page loads and you can enter your password. When you log off of Facebook, both your computer and the Facebook server throw away the temporary key. TLS will create a new one the next time you visit Facebook.

In this way, both asymmetric and symmetric cryptography are critical to protecting everyday Internet communications. Without the clever solution of hybrid encryption, everything from your passwords to messages you send to your friends could be read by anyone on the Internet. So always be sure, when sending sensitive information like a password, that you are connected to a site using “https://” instead of “http://” (the “s” stands for “secure”), and that the little lock icon appears in your web browser.

**Did you know?** Modern encryption algorithms such as AES (Advanced Encryption Standard) can have up to 2^{256} different keys. That’s about eight billion times more possible keys than there are atoms in the entire galaxy.

Discussion of the mathematics and theory behind cryptography:

Handbook of Applied Cryptography (1996)

A. J. Menezes, P. C. van Oorschot & S. A. Vanstone, CRC Press

Magazine article on cryptography:

This cryptography game is also a navy recruiting tool (2015)

J. Wenz, Popular Mechanics

Online games and activities pertaining to cryptography:

CryptoClub

CryptoClub Project

America’s CryptoKids® Future Codemakers & Codebreakers (2010)

National Security Agency