16.3: Transposition Ciphers

Another approach to cryptography is transposition cipher.

Transposition Ciphers

A transposition cipher is one in which the order of characters is changed to obscure the message.

An early version of a transposition cipher was a Scytale[1], in which paper was wrapped around a stick and the message was written. Once unwrapped, the message would be unreadable until the message was wrapped around a same-sized stick again.

One modern transposition cipher is done by writing the message in rows, then forming the encrypted message from the text in the columns.

Example 6

Encrypt the message “Meet at First and Pine at midnight” using rows 8 characters long.

Solution

We write the message in rows of 8 characters each. Nonsense characters are added to the end to complete the last row.

\(\mathrm{MEETATFI}\)

\(\mathrm{RSTANDPI}\)

\(\mathrm{NEATMIDN}\)

\(\mathrm{IGHTPXNR}\)

We could then encode the message by recording down the columns. The first column, reading down, would be MRNI. All together, the encoded message would be MRNI ESEG ETAH TATT ANMP TDIX FPDN IINR. The spaces would be removed or repositioned to hide the size of table used, since that is the encryption key in this message.

Example 7

Decrypt the message CEE IAI MNL NOG LTR VMH NW using the method above with a table with rows of 5 characters.

Solution

Since there are total of 20 characters and each row should have 5 characters, then there will be \(20/5 = 4\) rows.

We start writing, putting the first 4 letters, CEEI, down the first column.

\(\mathrm{CALLM}\)

\(\mathrm{EINTH}\)

\(\mathrm{EMORN}\)

\(\mathrm{INGVW}\)

We can now read the message: CALL ME IN THE MORNING VW. The VW is likely nonsense characters used to fill out the message.

More complex versions of this rows-and-column based transposition cipher can be created by specifying an order in which the columns should be recorded. For example, the method could specify that after writing the message out in rows that you should record the third column, then the fourth, then the first, then the fifth, then the second. This adds additional complexity that would make it harder to make a brute-force attack.

To make the encryption key easier to remember, a word could be used. For example, if the key word was “MONEY”, it would specify that rows should have 5 characters each. The order of the letters in the alphabet would dictate which order to read the columns in. Since E, the 4^th letter in the word, is the earliest letter in the alphabet from the word MONEY, the 4^th column would be used first, followed by the 1^st column (M), the 3^rd column (N), the 2^nd column (O), and the 5^th column (Y).

Example 8

Encrypt the message BUY SOME MILK AND EGGS using a transposition cipher with key word MONEY.

Solution

Writing out the message in rows of 5 characters:

\(\mathrm{BUYSO}\)
\(\mathrm{MEMIL}\)
\(\mathrm{KANDE}\)
\(\mathrm{GGSPK}\)

We now record the columns in order 4 1 3 2 5:

SIDP BMKG YMNS UEAG OLEK

As before, we’d then remove or reposition the spaces to conceal evidence of the encryption key.

Try it Now 3

Encrypt the message “Fortify the embassy” using a transposition cipher with key word HELP

Answer

HELP gives column order 2 1 3 4.

\(\mathrm{FORT}\)

\(\mathrm{IFYT}\)

\(\mathrm{HEEM}\)

\(\mathrm{BASS}\)

\(\mathrm{YPLR}\)

Encrypted text: OFE APF IHB YRY ESL TTM SR

To decrypt a keyword-based transposition cipher, we’d reverse the process. In the example above, the keyword MONEY tells us to begin with the 4^th column, so we’d start by writing SIDP down the 4^th column, then continue to the 1^st column, 3^rd column, etc.

Example 9

Decrypt the message RHA VTN USR EDE AIE RIK ATS OQR using a row-and-column transposition cipher with keyword PRIZED.

Solution

The keyword PRIZED tells us to use rows with 6 characters. Since D comes first in the alphabet, we start with 6^th column. Since E is next in the alphabet, we’d follow with the 5^th column. Continuing, the word PRIZED tells us the message was recorded with the columns in order 4 5 3 6 2 1.

For the decryption, we set up a table with 6 characters in each row. Since the beginning of the encrypted message came from the last column, we start writing the encrypted message down the last column.

\(\begin{array}{|l|l|l|l|}
\hline & & & & & \mathrm{R} \\
\hline & & & & & \mathrm{H} \\
\hline & & & & & \mathrm{A} \\
\hline & & & & & \mathrm{V} \\
\hline
\end{array}\)

The 5^th column was the second one the encrypted message was read from, so is the next one we write to.

\(\begin{array}{|l|l|l|l|}
\hline & & & & \mathrm{T} & \mathrm{R} \\
\hline & & & & \mathrm{N} & \mathrm{H} \\
\hline & & & & \mathrm{U} & \mathrm{A} \\
\hline & & & & \mathrm{S} & \mathrm{V} \\
\hline
\end{array}\)

Continuing, we can fill out the rest of the message.

\(\begin{array}{|l|l|l|l|l|l|}
\hline \mathrm{A} & \mathrm{I} & \mathrm{R} & \mathrm{S} & \mathrm{T} & \mathrm{R} \\
\hline \mathrm{I} & \mathrm{K} & \mathrm{E} & \mathrm{O} & \mathrm{N} & \mathrm{H} \\
\hline \mathrm{E} & \mathrm{A} & \mathrm{D} & \mathrm{Q} & \mathrm{U} & \mathrm{A} \\
\hline \mathrm{R} & \mathrm{T} & \mathrm{E} & \mathrm{R} & \mathrm{S} & \mathrm{V} \\
\hline
\end{array}\)

Reading across the rows gives our decrypted message: AIRSTRIKEONHEADQUARTERSV

Unfortunately, since the transposition cipher does not change the frequency of individual letters, it is still susceptible to frequency analysis, though the transposition does eliminate information from letter pairs.

---

[1] en.Wikipedia.org/wiki/File:Skytala%26EmptyStrip-Shaded.png