About the Ciphers

The last two weeks we have been working on substitution ciphers (monoalphabetic and polyalphabetic). Recall that substitution ciphers are ones in which each letter is replaced by another letter (or symbol) in some systematic way. However, the order in which the letters appear stays the same. This week, we're going to work on a few transposition ciphers; ones for which the letters stay the same, but the order is all mixed up!

One of the oldest ways to do this was created by the ancient Egyptians and Greeks. It uses a stick called scytale . They would have used wooden sticks and parchment, but we're going to use poster tubes and adding machine tape!

How the scytale cipher works

1. Get a scytale and a strip of parchment.
   
   
2. Wrap your parchment around your scytale until the stick is covered. Try to avoid overlapping and gaps.
   
   
3. Write your message along the length of the stick, one character per pass of the paper. If you need more space, rotate the stick away from you and keep writing.
   
   
4. Unwrap the scytale and send the scrambled message to a friend with the same-diameter stick.
   
   
5. The friend then wraps his scytale with the encoded parchment. Since the diameters are the same, the message is clearly legible!
   
   

This technique was very useful in ancient battles; the Spartans are known to have used this rather extensively. Each general was given a stick of uniform diameter so that he could quickly encipher and decipher any message sent from other generals. Notice how quick and easy this is to use!

However, it is also rather easy to crack. In a battle situation, the most likely way to crack this would be to steal a general's scytale. Then, each message could be read easily. However, it can be cracked even without stooping to theivery. As it ends up, the scytale is just a very old (and rather simple) version of a greater class of ciphers called matrix transposition ciphers. The way the simplest of these works is by picking a matrix of a fixed size (say, 6x10) and then writing your message across the rows. The encipherment step consists of writing down the letters in the matrix by following the columns. Here's a simple 6x10 example:

Where we've written the message:

row by row into the matrix. Then, to encipher this, we simply read off the columns to get:

The scytale cipher is just like one of these. Note that the number of "rows" in your message is determined by the diameter of your stick and the size of your writing. Cracking them, as you may guess, is just a matter of systematic guess-and-check.

How to crack the simple matrix transposition ciphers:

1. Count how many letters are in the ciphertext (for this example, assume the ciphertext is 99 letters long)
   
   
2. Make all of the matrices that would fit such a length (e.g. 2x50, 3x33, 4x25, 5x20, 6x17, 7x15, 8x13, 9x11, 10x10). Use TWO of each size.
   
   
3. For each size matrix, write out the ciphertext across the rows on one copy. On the other copy, write out the ciphertext down the columns.
   
   
4. At each stage, see if you can find anything legible, reading perpendicular to how you put the ciphertext in.
   
   

A harder version of the matrix transposition cipher is the column-scrambled matrix transposition cipher. Just like the ones above, you find a matrix of suitable dimensions and write your text in row-by-row. If there are blank cells left, fill them in with a dummy character (sometimes an 'X'). However, before writing down the ciphertext from the columns, you first scramble the columns. This generates a new matrix of the same size. Now read off the text down the columns, as before. This is a harder cipher, but there is a systematic way to crack it.

How to crack the column-scrambled matrix transposition ciphers:

1. Count how many letters are in your ciphertext (for example, 75) and factor that number (75 =5*5*3).
   
   
2. Create all of the possible matrices to fit this ciphertext (in our case, 3x25, 5x15, 15x5, 25x3).
   
   
3. Write the ciphertext into these matrices down the columns.
   
   
4. For each of your matrices, consider all of the possible permutations of the columns (for n columns, there are n! possible rearrangements). In our case, we hope that the message was enciphered using one of the last two matrices (the 15x5 and the 25x3), since in those cases, we have only 6 and 120 possibilites to check (3! = 6, 5! = 120, 15! ~ 1.31x10^12, 25! ~ 1.55x10^25).
   
   
5. Rearrange each matrix to see if you get anything intelligible. Read the message off row-by-row. Note that this is much more easily done by a computer than by hand, but it is doable (for small matrices).

Examples

1. Play around with the scytales; write messages using each different-diameter tube and try to read them by using the other tubes. Try to stump your friends with your ciphers.
   
   
2. Decipher the following message (it was enciphered using a simple matrix transposition cipher - note that the letters are in groups of five):
   DEEFY HSTEH TFIEO IVOUI ARSOO IAYSI WULLU CEULN
   NLBRU LFLBN OSLPW HRWDD GIEEW EEIED OWHYH EYOF

   Answer
   
   

3. Decipher the following message (it was enciphered with a column-scrambled matrixtransposition cipher - the letters are again in groups of five).

   NNRTA NNFTO IONEL IEKSD MRTLE LRTNE EGRTA NTAEI HXOIO
   EMOIO DMRTI HLDHR SNEEG UHLEG IHNNB GMAND NBTX

   Answer
   
   

4. Think of how you might program a computer to decipher some column-scrambled matrix transposition ciphertext.

   Answer
   
   

Challenge Problems

After you have tried the examples above, try the ciphers on the challenge sheet.

• The Double Transposition Cipher
• Transposition cipher encryption over the internet

* These links are for informational purposes only and are from sources outside MEC and Cornell University