Secret Codes

In 49 BCE, Julius Caesar was leader of the Roman Empire, and his adopted heir Octavian was engaged in a battle

The year is 49BC and Julius Caesar, leader of the Roman Empire has sent a message to his adopted heir , who is engaged in a battle that is not going well and reinforcements are needed. In order to make sure the message arrives he has sent 3 copies with trusted agents of his army. Spies from the opposing army intercept two of the messages, but one copy makes it through to Octavian.

Upon receiving the letter Octavian eagerly opens the message and reads:

“Xlcjerjw, anrwoxalnvnwcb jan xw cqn fjh. Cx jaaren xw orocnnwcq Xlcxkna. Qxum yxbrcrxw dwcru cqnw. SL”

As you can see, the message makes no sense. Knowing that his message might fall into enemy hands, Caesar protected it by using a cipher.

Continue

But Octavian knows how to crack the code: every letter in the message has been swapped with another one.

Here you can see two wheels with all the letters of the alphabet. The outer, blue letters represent the original, correct letters, and the inner, red letters represent the encoded letters.

To encode a message we simply have to swap every blue letter with the corresponding red one, and to decode it, we just have to go the other way.

Try rotating the wheel to different possitions, until the message makes sense:

“Octavian, reinforcements are on the way. To arrive on fifteenth October. Hold position until then. JC”

Octavian breathes a sigh of relief knowing that help is coming, and also that the enemy agents who captured the other two messages won’t be able to read it without the secret key.

This method of encoding a secret message is called the Caesar cipher. We simply "shift" every letter in the alphabet by a certain amount

And because Octavian knew what method Caesar had used to hide the message (an algorithm), and Caesar had told him the key (what letter the A lined up with on his wheel) before they had left Rome, he was able to read Caesar’s hidden message with ease. shifts the alphabet a certain number of places in order to write out the message. This shifting is the algorithm. The key is how many places it is shifted.

Take a look at this message:

“ymj hfpj nx ns ymj kwnilj. ny nx f hmthtqfyj hfpj bnym afsnqqf nhnsl fsi wfnsgtb xuwnspqjx.”

We know that each letter has been replaced with a new letter of the alphabet by shifting the whole alphabet over by a specific number of spaces. For example, if it was shifted 1 space, all A’s would be written as B’s, B’s as C’s, C’s as D’s and so on. Using the wheel above, and some guess work, try to determine the message.

Interactive Elements: an input box where they should write the text “The cake is in the fridge. It is a chocolate cake with vanilla icing and rainbow sprinkles.”

The shift, or key, for this message, is Input Box (5).

We can use devices like this, or even just writing out the alphabet two times, to match up each letter and either encrypt (definition: turn plaintext into cryptotext) or decrypt (definition: turn cryptotext back into plaintext) the message.

Caesar ciphers were quite popular, and secure, for a long time. Inventors even made devices to make the encryption and decryption of these messages easier.

Cryptography

Cryptography (definition: cryptography is two words crypto - hidden, secret; and graphein - to write) is the art of hiding a message using an algorithm (a way of writing the cipher) and a key (the secret to locking and unlocking it). Many people can know an algorithm but only a few people should know the key, and the less people that know it, the more secure the message is.

Cryptography really is the art of hiding or obscuring a message. Early methods used steganography (definition: steganos - covered and graphein - to write), which is the art of simply hiding a message. It can be done in many ways, like using ink that can only be seen under certain conditions (like heat or acid), or hiding a message under something else (like wax, or even hair - though this one takes a long time).

This method physically hides the message but, if detected, the message can still be easily read.

So ciphers, like the Caesar, were designed to hide messages from being read by anyone who didn’t have the key. Sometimes these encrypted messages could be combined with stenography to make them even more secure.

In previous modules (Link to module on Morse Code) you learned how letters and words could be written in different ways and encoded to symbols or sounds (like in Morse code). But this way of writing doesn’t hide the message, it just changes it into a different format (through an algorithm, but without a key); like how letters on a keyboard are converted to ASCII, then binary, and then back again to display on your phone or monitor. But if you know how to convert between the two languages you can read the message easily. Cryptography hides the message so that you need both an algorithm AND a key to read the message.

The Skytale

One of these methods was called a scytale, and it involved wrapping either a plaintext message, or an encrypted message for even more security, around a stick or tube of a specific size. You could only read the message properly if you had a stick or tube of the exact same size.

Interactive Elements: An animated picture of a paper with text being wrapped around a stick and being readable, then wrapping around a different sized stick and no longer having the text line up.

Interactive Element: A text box where students can write a message and then an animation of the message being cut and then wrapped around tubes of different sizes. Only one of the tubes will be the right size to have the message line up properly and be read; all other messages will be gibberish.

To make a message even more difficult they could encrypt it and then wrap it around a tube. Meaning the person intercepting it would have to first find a tube of the correct size to line up the message before they could even begin to decipher it. And because the message would appear to be gibberish to start with, it would make it nearly impossible to find a tube the correct size (or would require a LOT of guesswork).

Interactive Element: A text box students can write a message in, encrypt using the cipher wheel, and then an interactive ‘tube size selector’ that then wraps their message around the tube. This message could be sent to another user who then has to select the correct sized tube in order to read the message and decrypt it on their end (see the end of the Vigenere section for additional communication between users). There would also be an option to print out the encrypted message and instructions on how to choose a tube size from items found around the home to make a physical scytale and then share it with friends and family.

Frequency Analysis

A Caesar, or substitution, cipher is one of the easiest ciphers to create, but it’s also one of the easiest to break (or crack). This is because all someone needs to do is figure out the shift being used and they can easily read the whole message. To break the encryption you’d just have to try shifting each letter in the ciphertext to see if it created a plaintext that made sense. If it does, you’ve got the key, if it doesn’t, then you try the next shift until you get it; and you’d only have to try Input Box (25) different times (at maximum).

Of course this is looking at a basic Caesar cipher, which shifted the letters, but it kept them in order. But what would happen if we shuffled the letters and put them in a different order?

Let’s start with the letter A, we could map it with itself, so A → A, but that would be rare and wouldn’t make much sense, but it’s still an option. Or we could map A → B, or A → C, or A → D and so on. This would give us Input Box (26) different possible options for A. We would then choose the next letter, let’s say B, assuming it wasn’t mapped to A, and do that one next. Well we know it can’t be mapped to A, as A is already mapped to another letter, but it could map to itself so that gives us Input Box (25) different options for B. We then pick our next letter and map it to other letter giving us Input Box (24) different options and so on…

Interactive Element: Two rows of the alphabet and students can join a line from one letter to another, mapping them (like the image below). There will also be a counter that goes from 26 down to 1 for each mapping, showing the remaining choices for letters. This can then generate a substitution alphabet that students can use to encrypt and send a message with.

This would give us 26 * 25 * 24 * 23 * … * 5 * 4 * 3 * 2 * 1 = 4.03 x 10^26 (Pop-up: multiplying a sequential chain of numbers like this can also be written as 26! where the ! means factorial. You can learn more about factorials here https://mathigon.org/world/Combinatorics ) different choices. Far too many choices to try a brute force attack (definition: trying one possibility after the other until you find one that works. This can be done systematically or at random) on to decipher. So instead we turn to frequency analysis to help us crack this code.

To start with frequency analysis involves looking at how many times a specific letter (or letters) appear in a block of text and comparing it to the most commonly used letters in that language). For example, in English, the most commonly used letter is the letter E. The least common letters are Z, X, Q and J.

Here is what a general frequency analysis of the English language looks like:

Image: frequency analysis chart There is a good generator here: https://www.braingle.com/brainteasers/codes/frequencyanalysis.php#form

So, for someone intercepting a secret message using a simple Caesar substitution cipher, all they would have to do is look for the letter that appears the most, assume it was an E, and then count how many letters it is from the letter E to determine the shift (or key). Let’s see how accurate it is. Using your mapping from above let’s encrypt a block of text and then run a frequency analysis on it to see how close it got.

Interactive Element: A large block of text will be encoded using the the student’s mapping from above and then they could push a button that runs a frequency analysis on it and shows their mapping and the frequency analysis ‘guessing’. The block of text to be analyzed though should be pretty accurate to frequency analysis unsubstituted though to give the most accurate results.

Now it’s your turn to try:

https://asecuritysite.com/challenges/scramb

If you picked up on the fact that the code above was generated using a simple Caesar cipher with a shift of Input (14) you may have been able to guess the letters more quickly. However, you can also use it on a more complicated cipher where the letters are not sequential such as:

Interactive Element: The same as above but with a different encrypted text:

Note: the above text decrypts as:

Side note or pop-up: it is important to keep in mind that we are keeping punctuation and spaces in place for our encryptions, in most cases these are removed to make decrypting the text even harder.

There are also combinations of letters that are unique and appear more often together that can make our analysis work easier. In the English language this would be combinations like q and u, or the word “the” or the combination of letters like “th” “wh” and “ing”. All these patterns help to analyze text and determine what letters are being substituted.

Interactive Element: An analysis of the above text that also shows the frequency of the common items (qu, the, th, wh, ing, an). Students could then click on a word or combination of letters in the text and see all the other instances highlighted and a counter of how many appear in the rest of the text.

The science of creating secret codes is called Cryptography and the are of breaking them is called Cryptanalysis.

When designing ciphers, there are several possible objectives:

• Secrecy: A and B can be sure that no third party X can read the message.
• Integrity: A and B can be sure that no third party X can alter the message while it is being transmitted.
• Secrecy: B can be sure that the message actually comes from A, and not from some impostor.

Length of security (hours, years), level of security

The Vignere Cipher

It’s now 1562 and you now find yourself in Rome once again trying to crack a code. This time it is a communication from one of the Pope’s security guards that reads:

“EYDRICFILMRRBEGTYMESQNETVEMZKZXDHSFDLWLLKBRRRLXNRFAKFNEKTVCIUQEEDMYFUNPFOAZGOJLQDLFDGOTR”

It is imperative that the message be decrypted as you have discovered that the guard who sent it is a traitor and is involved in a plot to kidnap and ransom the Pope. But without proof, no one will believe you.

You initially try to decode the message using a simple Caesar cipher and try all 25 combinations, but nothing comes from it. You then try frequency analysis on the text, but it still comes out as gibberish, there are no patterns to be found. So you seek out Blaise de Vigenère, a French diplomat living in Rome as you have a sneaking suspicion you are dealing with a Vigenère cipher.

First credited to Giovan Battista Bellaso, an Italian cryptologist, the Vigenère cipher was named after Blaise de Vigenère, a French cryptographer and translator, who developed an autokey method of encryption about 20 years after Bellaso, based on his work.

A Vigenère cipher starts with the concept of a transposition cipher (definition: a transposition cipher is one where the letters remain the same but their position changes). An example of this is a rail fence cipher where every other letter has been moved to the end of the sentence.

Interactive Element: An animation of first the reverse of this process and then the forward method described here. Take the sentence “Cryptography is a fascinating field of mathematics. It allows people to converse with one another and not allow others to read the message.”. Remove all punctuation and spaces, take every other letter and move it to a row below the original sentence, then remove the spaces from both new lines and put the second line at the end of the first line. It should look like this by the end: cytgahiaacntnfedfahmtcIalwpoltcneswtoenteadoalwtesoedhmsaerporpysfsiaigilomteaistlosepeoovreihnaohrnntloohrtrateesg

Each line was called a rail, and the number of rails could be 2 or more.

Interactive Element: Allow students to write out a sentence, select the number of rails, and then it will reorganize the sentence as above.

Interactive Element: Show the students the sentence “Miiirieoheeoiriaaaaahgnsnneatvtxbotatahsltfneetnfcsnmtfcstoatcetktcaotsgtdht” allow students to try different numbers of rails to decipher the text (the correct input is 3 rails). Input box for the answer: “Mathigon is an interactive textbook that teaches a lot of interesting facts and math facts.”

The Vigenère cipher takes this one step farther and uses a series of alphabets, each shifted by one more for each linke.

Image: a picture of the alphabet written out 26 times, each line shifted by one, like this: https://en.wikipedia.org/wiki/Vigenère_cipher#/media/File:Vigenère_square_shading.svg

Then a keyword is picked:

Interactive Element: Allow students to type in a 5 - 10 letter keyword of their choice. Show how this keyword would be used to encrypt a series of 15 A’s. This shows that each A is encrypted as a different letter until the keyword starts to repeat. This should be animated to show the path for encrypting each letter. It could be an automatic animation or students could click for each step.

So now that we have our keyword, and we can see how each letter is encrypted, we can use this to encrypt a sentence:

Interactive Element: Allow students to type in a sentence of their choosing and, using their keyword, and the same animation as above show their sentence being encrypted. This site shows this process: https://studio.code.org/s/vigenere/stage/1/puzzle/1

By doing this the Vigenère cipher became an encryption method that was much more secure than a single Caesar cipher. It was essentially a series of Caesar ciphers strung together using a keyword, making it much stronger.

But don’t be fooled. Just because we are using a keyword to mix up the shifts it becomes much harder, but not impossible, to crack. For instance, since the person you are sending the message to needs to know the keyword, it could be intercepted and then the message could be easily read. Or someone could figure out what the keyword was based on what they knew about the person who sent the message (they could have used something easy to guess, like your favourite flower or a pet’s name).

In the case of your message from the Pope’s guard, this is exactly what happened. Using some investigative techniques you learned that the guard has a cat named Mr. Supreme Snuggles and tried that as the keyword.

Interactive Element: Same as above but this time they copy in the sentence “EYDRICFILMRRBEGTYMESQNETVEMZKZXDHSFDLWLLKBRRRLXNRFAKFNEKTVCIUQEEDMYFUNPFOAZGOJLQDLFDGOTR” and the keyword mrsupremesnuggles. The message is shows should be “The Pope is planning on going from the Vatican to the Cathedral at nine oclock in the morning”. The students will have to put in their own spacing to fully read the message.

Luckily you and Vigenère were able to figure out the keyword and saved the Pope. But what about if you didn’t have such information, or the sender had used a random phrase or group of letters. For many centuries the Vigenère cipher remained unbroken because people were unable to figure out how to find patterns that would help them decipher the text without knowing the keyword. And so it became the common method of sending messages for a very long time.

In the 1830’s and 1840’s a new mode of communication was being used, called the telegraph. It was able to send messages, using Morse code, over large distances using cable lines. These lines ran between two points but could be easily spliced into and their messages intercepted. So operators used the Vigenère cipher to protect their messages.

Charles Babbage (1791 - 1871) was an English polymath (definition: someone who knows a lot of different subjects and can use them to solve various complex problems) who became interested in finding a way to crack the Vigenère cipher. Building on the work of others who came before him Babbage was able to crack the cipher using the concept of frequency analysis and looking for repeating patterns in the messages in order to determine keyword lengths and eventually crack the code.

In order to break the Vigenère cipher, Babbage started by looking for patterns to try and find the length of the key. He spent what must have been enormous amounts of time pouring over encrypted blocks of text and studying it for repeating sets of letters that occurred at regular intervals in the text. He did this because he knew that once he knew the key length he could use frequency analysis on each part of the cipher to crack the overall code.

Interactive Element (a slide show) - Text to include “Say you have an encrypted block of text and you know that the key has a length of 6. This means that you know that the first letter of the ciphertext and the seventh letter of the ciphertext are encrypted using the same substitution alphabet; as you are now repeating the key and have returned to the starting letter.” The animation shows how the 1st and 7th letters are encrypted using the same row of the Vignere cipher (this can be pulled from the previous animation showing how the Vignere cipher works). The next slide would be an animation showing the following text being split into its parts (every 7th letter, starting from the 8th, being grouped together). Text: “This means we can then rewrite the original text grouping all the 1st, 7th, 14th, 21st, etc letters together.” The next slide would be a frequency analysis chart being generated for each section of the text. Text: We can then perform a frequency analysis on each part of the text to determine each letter of the key Text: Finally we have a key and we can use it to decrypt the entire text (or put it back together from its parts)

But what happens if you don’t know the length of the key, which in most cases you wouldn’t? Well, in cryptography, patterns are the downfall of a cipher and Babbage knew this. By looking for repetitions of patterns in the ciphertext he was able to break them down to determine the length of the key. He did this by looking for repeated sequences in the text, how long the repeated sequences were, and how many spaces were between the sequences.

Let’s say we had a block of text we knew was encrypted with a Vigenère cipher and we found the following patterns in it that kept repeating at regular intervals: LSB, PMBJT, WJRFL, JCAT. We would then create a chart like the one below and fill in factors of each spacing.

Interactive Element: Students would check off the factor boxes for each pattern (putting in the X’s below). Note: the rest of the chart would be filled in for them.

We can now see that the common factor between the spacings of repeated patterns is 7; meaning our key is 7 characters long. We now have a pattern to work with and a known key length. Now it just becomes a matter of breaking up the text and using frequency analysis, along with a lot of guesswork, to crack the code.

Sadly, Babbage never published his work and the credit for cracking the Vigenère cipher eventually went to Fredrich Wilhelm Kasiski who broke the cipher independently of Babbage’s work and published it in 1863.

The One Time Pad

We now find ourselves in 1894 and in the time of a wonderful new invention: the radio. This wondrous device has made communication much easier and faster as a wire between places is no longer needed; merely a transmitter and a receiver aimed at each other. However, they are also much less secure. To intercept a message you no longer have to splice into a telegraph wire, you just have to aim your own receiver at a transmitter to intercept all the messages you want (including encrypted ones).

During WWI this caused an issue as there were no new unbreakable ciphers being created, they were just using variations on older ciphers (which already had methods to break them). In addition to methods to break these codes, due to the ease of using radio waves, more messages were being sent and intercepted so there was more text to work with (remember, more text = easier to find patterns = easier to decrypt). Another issue with radio waves is the ability to triangulate where the signal is coming from.

Interactive Element: a picture of two receivers (like the two satellites in the image shown) that students can move around to point in different directions. When they are pointed at a certain (hidden) point they will beep - they beep slowly when pointed away from the hidden point and more quickly as they get closer and a sustained tone when pointed directly at the spot. Once both receivers are pointing at the same point it will appear. If sound is not an option then a dotted line can be used (getting darker as it gets closer to the point) when only one transceiver is point at the right spot and then a dot appears when they are both pointed at the same spot.

So not only could you intercept the messages and decode them you could also figure out where they were being sent from. This was especially handy if you were decrypting plans for an attack and now you knew not only what their plans were, but where they were hiding too!

As we know the longer a key is, the harder it is to break. But with a bit of skill and time, even long keys can be broken. Also, keywords would have to be shared among radio operators so if one was lost or captured then all their messages could be read.

This led to the Invention of the one-time pad. This was a large book that contained strings of random letters. Each time a message was sent it was encoded using a page of the book. It was then decoded using the same page on the other end. Then both parties would throw out that page of the book, so that code would never be used again.

This meant there was no repetition for code breakers to use. The random strings meant no easily guessable words, and no easily guessable phrases (Pop-up: sometimes codebreakers would get to know the operators and they would use words like their mother’s name or favourite ice cream flavour). This made one-time pads very secure. But they were also highly impractical as operators needed large code books distributed to them on a regular basis and, if one was captured, they would all become compromised and useless.

Important note: The weakest link in cryptography is often humans and the fact that they simplify things to make them easier to remember, but also easier to guess. The worst thing for a secure encryption is a repeating pattern.

Let’s use what we’ve learned so far to send some messages.

Interactive Element: A text box where students can write an encrypted message and send it to another student. They can choose what type of cipher and if they want to combine different methods (scytale + Caesar, or scytale + Vignere, or rail fence). It’s a selector tool where they can encrypt a message and then send it to someone along with how much info they want to send along (they can tell them nothing, or just the algorithm, or the algorithm and the key). They can make it as hard or easy as they want to. On the other end the student receiving the message would have access to things like tubes, cipher wheels, and frequency analysis tools.