Class 4: Historical Ciphers

Overview: In this section I introduce our large first assignment and the basics of each of these encryption schemes.  I don't think all of you will break all five of your encryptions.  So don't freak out.  You'll have to do some shotgun-hillclimbing and code all sorts of cool stuff you never thought you would code.  If you give it enough hours I'm convinced you can get them all.  This hard assignment is designed to show you that you're tougher than you think.

Chapter 4: Historical Ciphers and the Blackhat Challenge

You've intercepted five emails each encrypted in one of five distinct schemes:

• Playfair
• Substitution
• Hill 2x2
• Column Transposition
• Vigenere

Your job is to read the messages. In this Lesson I'll walk you through how each of these five work. We've already done Vigenere.

If you are curious here is the Python that encrypted the messages:

Kata: Break Substitution Ciphers

This is old-school logic-puzzle style. Each letter has been replaced by another letter throughout the message. Figure out who goes where.

Key Space What's the key space of a random substitution cipher?

n-grams Use google to find not just the single letter frequencies but the 2-letter and 3-letter frequencies.

A Special Flag For You:

"🇺🇿 🇱🇻🇺🇾🇺🇿🇿🇼🇯🇴 🇱🇻🇺🇾🇹🇱🇱🇻 🇱🇻🇺🇾🇺🇿🇨🇵 🇨🇵🇲🇭🇱🇸🇱🇻 🇲🇭🇨🇭 🇸🇳🇺🇿🇸🇽🇺🇾🇵🇹🇱🇸 🇺🇿🇨🇵 🇧🇼🇹🇿🇸🇳🇺🇾 🇵🇹🇹🇱🇨🇵🇺🇿🇵🇹🇱🇸 🇵🇦🇺🇾🇵🇹🇿🇼 🇨🇵🇸🇽🇹🇱🇸🇳🇵🇹🇨🇵 🇹🇱🇱🇸🇵🇹 🇺🇿🇿🇼🇸🇳🇵🇷🇹🇿🇬🇼🇵🇹🇬🇼 🇬🇼🇲🇭🇿🇼'🇱🇻 🇸🇱🇲🇭🇹🇿? 🇲🇼🇱🇻🇵🇦 🇱🇻🇺🇾🇵🇹 🇨🇭🇵🇷🇹🇱🇬🇧 🇺🇿🇨🇵 🇿🇼🇺🇿🇿🇼🇳🇴🇹🇱{🇧🇼🇲🇭🇿🇼🇱🇻🇸🇱_🇸🇽🇸🇱🇱🇻🇺🇾🇲🇭🇿🇼🇨🇵_🇿🇼🇵🇹🇱🇻🇨🇭🇵🇷🇺🇿🇷🇸_🇸🇳🇺🇿🇱🇸🇸🇳🇹🇿🇨🇵}"

Kata: Break Column Transposition Ciphers

This one doesn't map the letters around it is instead based on a geometric-arrangement. A key is chosen as a permutation of k columns (often a word which clues you into the order of the columns). The message is then written in a grid with k columns. Finally, in the order of the permutation, the columns are taken as the cipher text.

Might come out as NIHEAYTBTDSES

Research What other position based ciphers can you imagine or find?

Padding My code didn't pad the last row, but other codes might. How will this impact your attacks?

Kata: Break Playfair Ciphers

In Playfair we pick a phrase which is put into a 5 by 5 grid ignoring duplicate letters (and tossing one letter). After that pad with the alphabet to create something like (forgive me for using wikipedia images):

This cipher works on pairs of letters, so a pair will dictate a square in your grid. We use the convention that if you are encrypting a repeated letter you replace the second letter with "x". (If you are encoding something like "XXX is the best movie of all-time" then you'll have to make a different choice.)

Now that you have two distinct letters to encrypt we have three cases:

A square: when you have a square you then use the opposite corners (same row):

A row: when your two letters are in the same row then shift to the right by one (wrapping around):

A column: same story just down instead of right.

So with the above square we would encrypt: "ANDYHOWWOULD" into "logadsygnvac"

Create a key matrix: Take the phrase "It's all about the money" and spit out the 5x5 key matrix.

Encrypt a message: make a simple message of 10 characters or so (secret) and encrypt with the above key. Put your secret in the Piazza for this section.

Decrypt: Now pick one from the Piazza to decrypt.

Kata: Break a Hill 2x2 Cipher

This is a little linear algebra love in crypto. The idea is this, create an invertible matrix with entries in \( \mathbb{Z}_{26}\). Encode your message as a vector and multiply it by that matrix to get your cipher characters.

In our case I picked 2x2 matrices so you can solve it by hand if needed. So for instance \( M = \left(\begin{array}{rr} 25 & 3 \\ 9 & 20 \end{array}\right) \) has inverse \( \left(\begin{array}{rr} 4 & 15 \\ 19 & 5 \end{array}\right) \)

If I were to encrypt the message "ANDY" I would see it as \( M \cdot \left(\begin{array}{r} 0 \\ 13 \end{array}\right) = \left(\begin{array}{r} 13 \\ 0 \end{array}\right)\) and \( \left(\begin{array}{r} 17 \\ 13 \end{array}\right) \) for "DY". This would then encrypt to "narn"

Interpret: What does an eigenvector mean in this context?

Frequency: Is the letter frequency preserved in some way? How about the 2-grams?