16.3 Transposition Ciphers

Another approach to cryptography is transposition cipher.

A scytale: a wooden rod with a long narrow strip of pale parchment wound around it in a close spiral so that successive wraps sit edge to edge. A message written along the rod is scrambled once the strip is unwound and reads correctly again only when it is wrapped on a rod of the same diameter. 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.

MESSAGE = "Buy some milk and eggs"      # EDIT
KEYWORD = "MONEY"                       # EDIT: its length sets the row length
PAD = "PK"                              # filler letters, cycled, to finish the last row

def column_order(word):
    # Read the column whose keyword letter comes first in the alphabet, then the next...
    return [i for _, i in sorted((c, i) for i, c in enumerate(word.upper()))]

def to_grid(msg, k, pad):
    letters = [c for c in msg.upper() if c.isalnum()]
    j = 0
    while len(letters) % k:
        letters.append(pad[j % len(pad)])
        j += 1
    return [letters[i:i + k] for i in range(0, len(letters), k)]

def encrypt(msg, word, pad):
    grid = to_grid(msg, len(word), pad)
    order = column_order(word)
    return grid, " ".join("".join(row[c] for row in grid) for c in order)

def decrypt(cipher, word):
    letters = [c for c in cipher if c.isalnum()]
    k = len(word)
    grid = [[""] * k for _ in range(len(letters) // k)]
    it = iter(letters)
    for c in column_order(word):
        for row in grid:
            row[c] = next(it)
    return "".join("".join(row) for row in grid)

order = column_order(KEYWORD)
grid, secret = encrypt(MESSAGE, KEYWORD, PAD)
print(f"keyword {KEYWORD}: rows are {len(KEYWORD)} characters long")
print(f"   read the columns in the order {[i + 1 for i in order]} "
      f"(alphabetical order of {', '.join(KEYWORD.upper())})\n")
print("   " + "  ".join(KEYWORD.upper()))
for row in grid:
    print("   " + "  ".join(row))
print(f"\nencrypted   {secret}")
print(f"decrypted   {decrypt(secret, KEYWORD)}")
print(f"round trip? {decrypt(secret, KEYWORD).startswith('BUYSOMEMILKANDEGGS')}")

print("\nthe book's harder one, going backwards:")
got = decrypt("RHA VTN USR EDE AIE RIK ATS OQR", "PRIZED")
print(f"   RHA VTN USR EDE AIE RIK ATS OQR  with keyword PRIZED  ->  {got}")

print("\nnotice what transposition does NOT do:")
from collections import Counter
plain = "".join(c for c in MESSAGE.upper() if c.isalnum())
print(f"   letter counts before: {sorted(Counter(plain).items())[:6]} ...")
print(f"   letter counts after:  {sorted(Counter(''.join(secret.split())).items())[:6]} ...")
print("   the letters are only shuffled, so frequency analysis still works on them")

Example 1

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

Show solution

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

$M E E T A T F I$

$R S T A N D P I$

$N E A T M I D N$

$I G H T P X N R$

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 2

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

Show solution

Since there are total of 20 characters and each row should have 5 characters, then there will be $20 / 5 equals 4$ rows.

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

$C A L L M$

$E I N T H$

$E M O R N$

$I N G V W$

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).

Your Turn

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.

$F O R T$

$I F Y T$

$H E E M$

$B A S S$

$Y P L R$

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 4

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

Show solution

The keyword PRIZED tells us to use rows with 6 characters. Since D comes first in the alphabet, we start with 6^thcolumn. 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.

					R
					H
					A
					V

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

				T	R
				N	H
				U	A
				S	V

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

A	I	R	S	T	R
I	K	E	O	N	H
E	A	D	Q	U	A
R	T	E	R	S	V

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

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.