Transposition Systems

And where the padding is added matters. [Arthaśāstra-Inspired Cryptography as a Symmetric Cipher System] records a real bug in this book's own code: padding after the substitution step meant the inverse substitution turned the pad into a different letter, and a message round-tripped as SENDTHEARMYATDAWNYYYYYYY.

Both, run

"""Transposition, worked: rail fence and columnar."""
import string
A = string.ascii_uppercase

def clean(t):
    return "".join(c for c in t.upper() if c in A)

def rail_pattern(n, rails):
    out, r, step = [], 0, 1
    for _ in range(n):
        out.append(r)
        if r == 0:
            step = 1
        elif r == rails - 1:
            step = -1
        r += step
    return out

def rail_fence(text, rails, decrypt=False):
    n = len(text)
    pat = rail_pattern(n, rails)
    order = [i for rr in range(rails) for i in range(n) if pat[i] == rr]
    if not decrypt:
        return "".join(text[i] for i in order)
    out = [""] * n
    for pos, i in enumerate(order):
        out[i] = text[pos]
    return "".join(out)

def columnar(text, key, decrypt=False, pad="X"):
    k = [c for c in key.upper() if c in A]
    cols = len(k)
    order = sorted(range(cols), key=lambda i: (k[i], i))
    if not decrypt:
        body = text + pad * ((-len(text)) % cols)
        rows = [body[i:i + cols] for i in range(0, len(body), cols)]
        return "".join("".join(r[c] for r in rows) for c in order)
    rows_n = len(text) // cols
    chunks, at = {}, 0
    for c in order:
        chunks[c] = text[at:at + rows_n]
        at += rows_n
    return "".join(chunks[c][r] for r in range(rows_n) for c in range(cols))

MSG = clean("SEND THE ARMY AT DAWN")
print("plaintext", MSG, "(%d letters)" % len(MSG))

print()
print("rail fence, three rails: the pattern of rails, then the read-off")
pat = rail_pattern(len(MSG), 3)
for r in range(3):
    print("  rail %d  %s" % (r, "".join(MSG[i] if pat[i] == r else "." for i in range(len(MSG)))))
ct = rail_fence(MSG, 3)
print("  ciphertext %s" % ct)
print("  decrypted  %s" % rail_fence(ct, 3, decrypt=True))

print()
print("rail fence with two to five rails")
for rails in range(2, 6):
    c = rail_fence(MSG, rails)
    print("  %d rails  %-20s round trip %s" % (rails, c, rail_fence(c, rails, decrypt=True) == MSG))

print()
print("columnar transposition under the key ZEBRAS")
KEY = "ZEBRAS"
k = list(KEY)
order = sorted(range(len(k)), key=lambda i: (k[i], i))
body = MSG + "X" * ((-len(MSG)) % len(k))
rows = [body[i:i + len(k)] for i in range(0, len(body), len(k))]
print("  key      %s" % "  ".join(k))
print("  read in  %s" % "  ".join(str(order.index(i) + 1) for i in range(len(k))))
for r in rows:
    print("  row      %s" % "  ".join(r))
ct2 = columnar(MSG, KEY)
print("  ciphertext %s" % ct2)
print("  decrypted  %s" % columnar(ct2, KEY, decrypt=True))

print()
print("the repeated key letter, which is where a careless columnar breaks")
for key in ("ANNA", "ZEBRAS", "AAAA"):
    c = columnar(MSG, key)
    back = columnar(c, key, decrypt=True)
    print("  key %-8s ciphertext %-26s round trip %s" % (key, c, back.startswith(MSG)))

print()
print("letter counts are unchanged by transposition")
from collections import Counter
print("  plaintext  ", sorted(Counter(MSG).items()))
print("  ciphertext ", sorted(Counter(rail_fence(MSG, 3)).items()))
print("  identical:", Counter(MSG) == Counter(rail_fence(MSG, 3)))

plaintext SENDTHEARMYATDAWN (17 letters)

rail fence, three rails: the pattern of rails, then the read-off
  rail 0  S...T...R...T...N
  rail 1  .E.D.H.A.M.A.D.W.
  rail 2  ..N...E...Y...A..
  ciphertext STRTNEDHAMADWNEYA
  decrypted  SENDTHEARMYATDAWN

rail fence with two to five rails
  2 rails  SNTERYTANEDHAMADW    round trip True
  3 rails  STRTNEDHAMADWNEYA    round trip True
  4 rails  SETEHAADNTRYANDMW    round trip True
  5 rails  SRNEAMWNEYADHADTT    round trip True

columnar transposition under the key ZEBRAS
  key      Z  E  B  R  A  S
  read in  6  3  2  4  1  5
  row      S  E  N  D  T  H
  row      E  A  R  M  Y  A
  row      T  D  A  W  N  X
  ciphertext TYNNRAEADDMWHAXSET
  decrypted  SENDTHEARMYATDAWNX

the repeated key letter, which is where a careless columnar breaks
  key ANNA     ciphertext STRTNDAAWXEHMDXNEYAX       round trip True
  key ZEBRAS   ciphertext TYNNRAEADDMWHAXSET         round trip True
  key AAAA     ciphertext STRTNEHMDXNEYAXDAAWX       round trip True

letter counts are unchanged by transposition
  plaintext   [('A', 3), ('D', 2), ('E', 2), ('H', 1), ('M', 1), ('N', 2), ('R', 1), ('S', 1), ('T', 2), ('W', 1), ('Y', 1)]
  ciphertext  [('A', 3), ('D', 2), ('E', 2), ('H', 1), ('M', 1), ('N', 2), ('R', 1), ('S', 1), ('T', 2), ('W', 1), ('Y', 1)]
  identical: True

Reading the output

The rail pattern is printed, so the zigzag is visible rather than described. Rail 0 takes every fourth letter, rail 2 takes every fourth offset by two, and rail 1 takes the rest.

Four rail counts all round-trip, which is the minimum test for any cipher: encipher, decipher, compare.

The columnar working is printed as the grid, with the key, the reading order and the rows, so the hand method and the program agree line for line.

Three keys including a repeated letter all round-trip. ANNA has two Ns, and the two N columns must be read in a fixed order or the message does not come back. The program sorts by the letter and then by the position, which is a stable sort, and that is what makes ANNA work. A sort that is not stable would give two different column orders on two different machines, and the message would decipher on one and not the other.

And the last block is the defining property. The letter counts of the plaintext and of the ciphertext are identical, and the program compares them rather than asserting it.

What that property means for an attacker

Frequency analysis is useless against a pure transposition. The ciphertext's letter frequencies are the plaintext's, which are English's, and they say nothing about the key.

But the same fact identifies the cipher. An attacker who sees a ciphertext with normal English letter frequencies and no readable words knows at once that it is a transposition and not a substitution. The defining property is also the giveaway.

And what does break it. Anagramming: try likely arrangements and look for common letter pairs. A transposition preserves which letters are present, so a pair like TH must be somewhere, and the attacker looks for arrangements that bring likely pairs together. For the rail fence, trying every rail count is enough.

Why both primitives are needed

Neither alone survives. Substitution leaves the frequencies to be read; transposition leaves the letters to be rearranged.

Composed, each covers the other's weakness. The substitution disturbs the frequencies so anagramming has less to go on, and the transposition breaks up the letter positions so frequency analysis cannot be confirmed by reading words. That is why every practical classical system used both, and it is what MU's label "substitution and transposition systems" is naming as a pair.

Quick revision

• Transposition permutes positions and leaves symbols alone, so the letter counts are exactly preserved.
• Rail fence: zigzag across a number of rails, read off rail by rail. The key is the rail count, so the key space is tiny.
• Columnar: rows of the key's width, columns read in the alphabetical order of the key's letters.
• Padding is needed to fill the last row, which lengthens the ciphertext, must be removable, and must be added at the right stage.
• A repeated key letter needs a stable sort, or the column order is not reproducible.
• Frequency analysis is useless against a transposition, and the normal frequency profile is what identifies it as one.
• Neither primitive survives alone; composed, each covers the other's weakness.

Test yourself

1. Encipher ATTACK with a three-rail fence, showing the rails.

Rail 0 takes A and C; rail 1 takes T, A and K; rail 2 takes T. Reading rail by rail gives AC TAK T, that is, ACTAKT.

2. Why must a columnar transposition sort a repeated key letter by position as well as by letter?

Because two identical key letters give two columns with the same sort key, and an unstable sort may order them either way. The order must be the same when enciphering and deciphering, so the position is used as a tie-break.

3. What does the preservation of letter counts cost the attacker, and what does it give them?

It costs them frequency analysis, since the ciphertext's frequencies are the language's and say nothing about the key. It gives them the identification: a ciphertext with normal letter frequencies and no readable words is a transposition.

4. Why is a composition of the two primitives stronger than either?

Because substitution disturbs the frequency profile, which is what anagramming a transposition relies on for confirmation, and transposition scatters the positions, which is what reading words off a substitution relies on. Each covers the other's weakness.