Week 1 9/26/2019 · RB Math Club

RB Math Club

Welcome

Calendar

Book Reviews

Math In The Real World

Email Archive

Explore

Email Archive

⁠

Class #1 Was A Success - Thanks for everyone who was able to join. I tried to cover a little too much material, but next week will be easier, and more interactive, when we talk about the math behind Netflix's recommendation engine. Watch out for weird spy codes and an invisible ink pen at home.

New Web Site - Check out the new

RB Math Club website⁠

(actually a coda doc, from my college friends). You'll find our calendar for the year, links to problems, math book recommendations, and some Math In The Real World articles.

Class Materials - Vocabulary

here⁠

, Strategy - Draw A Picture

here⁠

, In class problems

here⁠

Extra MO Problems -

Here⁠

. Problems, problems with hints, and then solutions. These were on the back of the Spies packet the kids brought home.

Math Book Suggestions

⁠

Top Secret: A Handbook of Codes, Ciphers, and Secret Writing⁠

- If your kid liked the talk today, get them this book to dive deeper into codes.

⁠

How To Be An International Spy⁠

- This one is much broader, but also much more interesting to kids.

⁠

The Code Book⁠

- If you don't want your kid to know more than you about spies and codes, get this book. It's a very good overview if you're into that kind of stuff.

Mailing List - Up to 58 subscribers. Spread the math love, even if they can't join in person. Sign up

here⁠

or email me at rbarrows@alum.mit.edu

Math In The Real World (pdf for printing

here⁠

)

⁠

Spies

⁠

There would be no spies (left alive) if it weren’t for secret codes. We’ll learn about codes, ciphers, how cracking them helped us win World War II, sharing secrets with strangers, and uncrackable codes.

First let’s talk about codes. Some are secret, but some are not secret at all. Codes are anything that uses one thing as a symbol for another thing. Do you know the code for "peace"? ✌️ Do you know the code for "throw a fastball". 👇 How about the number code that people use to say which town you live in? Do you know that there's a numeric code on the back of every single book? Who knows any other codes?

Now let’s move on to secret codes. What's the secret code you say to open up a magic door? Do you ever use secret code names for teachers, friends, or enemies? If so, don't tell me! But if you do, you are in some pretty good company. Do you know who used secret codes all the time? Thomas Jefferson, the third President of the United States and the author of the Declaration of Independence. As you can imagine, he had to get pretty good at keeping secrets from the British while he was working on his plans for rebellion.

One of the simplest codes he used was with a guy named Meriwether Lewis. Does anybody recognize that name? He's half of "Lewis and Clark." They went on this nice long trip discovering the parts of America that had rarely been seen by anybody other than Native Americans. Before Lewis went on that journey, he was in charge of rating all of the military officers so that President Jefferson could fire a bunch of them. Can you imagine how this would look if any of them found out what he was saying about them?! So Lewis and Jefferson came up with a secret code to hide his insults. Here are the actual symbols on the left and what they meant on the right.

⁠

This is pretty good if you just need to send over a few possible categories for each person, but what if you want to send more details? You'd need a long book to hold a secret code for every single word. But there are a few choices.

First we can look at something called a Caesar Cipher. This is named after Julius Caesar, who lived 2,000 years ago. The good thing about this is that you don't need any kind of code book. All you do is shift each letter by three places up the alphabet. So "I like math" becomes "F Ifhb jxqe". This was actually secure back in his day, because there was no twitter to spill the details to everybody. In fact, most people were illiterate so they'd just assume the code was in a foreign language and not worth trying to figure out.

The second method is a simple cipher, also called a substitution cipher. Rather than just shifting letters of the alphabet, you create random mappings for each letter to another letter. So replace every 'a' with 't', every 'b' with 'f', every 'c' with 'x' etc. You don't even need to use letters, you could use numbers or random symbols. This is harder for people to figure out, but the downside is that you need to write the secret code down somewhere. Spies are always trying to steal secret codes, or better yet, just copy them without letting the person know that it's been found. Mary, Queen of Scots, got caught using a substitution cipher and they ended up putting her to death! Here's what her cipher looked like (which was a little too easy to crack).

⁠

A third code is called a dictionary cipher. Take a dictionary and look up the word you want to encode. Lets say it is "steal" which is the 14th word on page 642. Move forward 4 pages (page 638) and look up the 14th word there, which in this case is "sporadic". The person who received this message looks up "sporadic", moves back 4 pages, and finds the word "steal." This was actually used in the presidential election of 1876. Some people in New York wired a message to Florida to illegally buy votes. If they had decoded it correctly, a different person would have won the election. The senders of this code were found out when they used a weird word that was only in a few dictionaries "geodesy", which let the rest of it be cracked.

One final method is amazingly simple, but also unbreakable. Use a code talker. There were around 400 of these code talkers used in the US during World War II. They were Native Americans who worked in pairs and just translated messages into their native language. Not only did none of our enemies speak these languages, they couldn't figure them out either. The vocabulary didn't map one to one (submarine was "iron fish"), the tone of your voice mattered (like in Chinese, but not really in English) and even the spaces between words mattered.

OK - that's a lot of talk about codes, but where does the math come in? Math first showed it's brilliance when cracking the Caesar cipher. The way to do this is something called "frequency analysis."

It turns out that when you have a long enough message written in English, there are certain letters that show up more often than others. E, T and A are the most common, and X, Q, J and Z are the least common. Here's what the average letter frequency is:

⁠

So let's take a long message that has been encrypted with a substitution cipher and do a frequency distribution. Here's a sample from the Bible. The green is the plain message, the red is what you get after applying a Caesar cipher.

⁠

https://nakedsecurity.sophos.com/2019/01/20/serious-security-what-2000-years-of-cryptography-can-teach-us/⁠

⁠

If you were trying to crack the red code, all you would have is the frequency list on the right. The first thing you would try was to swap make the most common letter (C in this case) an E, because E's are by far the most common letter. If every C is really an E, then you know that the Caesar shift is 2 characters (so L would map to N, A would map to C, etc).

Caesar shifts are easy, but this actually works for any cipher, even a random mapping. Start by guessing 'E' for the highest frequency letter and write up your message with _ for characters you don't know yet. Do you see a bunch of three letter words that end in E? If so, any guesses for what the other two letters near it are? Probably T and H. So you can fill those in, and fill in any Ts or Hs anywhere else. Now you can look at the other common letters and try to place them. Oh, you have a two letter word that starts with T? What do you think the second letter is? Probably O. Fill that in. Keep doing this and you'll be able to crack codes in no time.

Secret code makers and secret code breakers tended to be mathematicians trying to stay ahead of one another. They would make things trickier and trickier, leading up to the "unbreakable" Enigma machine in World War II. This was a machine that had multiple layers of scrambling that nobody could figure out how to crack. Until a guy named Alan Turing combined two crucial insights with brilliant engineering. First, he realized that no letter in the cipher text could match the same letter in the original text. Second, he noticed that messages often included the same text (for example, messages from weather stations included the german words for "weather report"). With this information, he built a giant mechanical computer that would try many (though not all) of the possible keys at the same time. It usually was able to find a match within the day, but the encryption key was changed every day and they'd have to start all over again.

Computers today are so powerful that they can crack the enigma code in just seconds. So how do we create much much better codes? Math! First, we need to recognize that there is a perfectly uncrackable way to code a message. It's by using something called a "one time pad". It's a very long list that tells you how to transform your message, letter by letter. If your message is 5000 letters long, your one time pad has to be 5000 letters long. And after you've used it once, you need to throw it away and use a new one. And not only that, but both the sender and receiver of the secret message need to agree on the exact one time pad to use for every message. One example for how it would work would be to include a number from 1 to 26 for every single letter in the message and use this value to shift the letter forwards or backwards by that amount. If all of these were random numbers, nobody could ever write a program or do anything else to guess your secret.

So if the perfect system exists, how does anyone have a problem with secret codes? The problem is in the code book. People can't always agree on long codes to use, especially when they're on the other side of the world. And sometimes people don't even know each other. What if you're a North Korean spy but you want to become a double agent so you want to send a message to the USA, but it has to be secret. How would you get an encryption key? Any ideas? This is a really hard problem, but luckily Math has the answer.

Diffie-Hellman key exchange is the funny name that we use to talk about how two strangers can agree on a secret key without anybody else being able to tell what it is, even if they're snooping the entire time. First let’s look at it without math:

⁠

First agree on a common paint color and tell the world. It's OK if everyone knows that it is yellow. Then each person picks a secret paint color and uses it to make a mixture. Orange and light blue in this case. Then both people send a sample of the mixed up color to your partner. Everybody can see this new color (they're snooping in the mail), but it's really hard to figure out which exact color you mixed with yellow that gives you light orange. Was it dark orange? Red? Redish purple? Who knows, it's hard to figure out, so your secret color is still a secret (at least for a while). Now take the paint that your partner sent you and mix in your secret color. This will give you some shade of brown - but the important thing here is that it will be EXACTLY the same shade of brown as your partners. This is the secret that you guys now share and that nobody else in the world can possibly know (for a while).

Now let’s add in some math. First - your secret paint color is actually going to be two simple numbers. We'll call one the Remainderer (it's actually called a modulus) and the other is our base. Here's a chart - secret values are in red and public values are in blue.

⁠

If you make A, B and p really big numbers, then even the fastest computers on earth can't figure out the secret number that you share at the end. Also, this secret number is now bigger, so you can use it as an input to whatever other secret code scheme that you've thought of with friends.

Why does this work? There's a concept in math called a "one-way function." It means that something is easy to figure out in one direction, but really hard to reverse it. For example, it is easy to multiply two large prime numbers together. 97 * 89 = 8,633. But if I asked you to factor 8,633 without that giant hint, it would take you a long time to do it. First you'd divide by 2 (doesn't work, not an even number). Next you'd divide by 3 (doesn't work, the digits sum to 20 which is not divisible by 3). Then by 5 (no), then 7 (no shortcut here, but it doesn't work). You do this all the way until you get to 89 when you finally have some luck. For real codes we make the number very big. Any guesses how big we actually use? About one googol! That's a one with one hundred zeros after the end. That number is 333 bits long, and most encryption keys tend to be 256 to 512 bits long. Secrets that use encryption like this will be safe for thousands of years. Unless quantum computing comes along and ruins everything. But we can talk about that some other time!

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.