Breaking the Columnar Transposition Cipher

Breaking the Columnar Transposition Cipher: When Frequency Analysis Finds Nothing Wrong

Introduction

Every cipher broken so far in this series, Caesar, Affine, Vigenère, Beaufort, is a substitution cipher: it replaces each letter with a different one. This article is the series’ first pure transposition cipher instead: nothing gets replaced, only rearranged, which means the attack has to look completely different too. That’s exactly what makes frequency analysis work: E is still the most common letter, it’s just wearing a disguise. Columnar transposition does something fundamentally different: it doesn’t touch letter identity at all, only letter position. Every E in the plaintext is still an E in the ciphertext. There are just as many of them, in exactly the same proportion. Run a frequency count on columnar transposition ciphertext and it looks completely normal. The attack has to be entirely different.

Table of Contents

• Why Frequency Analysis Is Useless Here
• The Attack: Brute-Force the Arrangement, Not the Letters
• Scoring Without Spaces
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Why This Doesn’t Scale Forever
• Limitations of This Attack
• FAQ
• References

Why Frequency Analysis Is Useless Here

Every attack so far in this series has leaned on one fact: English letters aren’t used equally often, and substitution ciphers can’t hide that imbalance, only relabel it. Columnar transposition breaks that assumption completely. It writes the plaintext into a grid row by row, then reads the grid back out column by column in an order set by a keyword. No letter is ever replaced by another one, only moved. The ciphertext’s letter frequencies are, letter for letter, identical to the plaintext’s. Its Index of Coincidence is identical too, for the same reason: IC only measures the letter distribution, and rearranging letters doesn’t change that distribution at all.

This means every technique used earlier in this series, chi-squared analysis, the Index of Coincidence, even the common-word matching that cracked Caesar and Affine, provides zero signal about the key here. A completely different weakness has to be exploited instead: the fact that there are only so many ways to arrange a short keyword’s worth of columns.

The Attack: Brute-Force the Arrangement, Not the Letters

The actual weakness is combinatorial rather than statistical. A keyword of length n produces exactly n! (n factorial) possible column orderings. For the keyword lengths transposition ciphers realistically use by hand (rarely more than 8-10 letters), that number is small enough for a computer to check exhaustively:

5 columns  →  120 orderings
6 columns  →  720 orderings
7 columns  →  5,040 orderings
8 columns  →  40,320 orderings

The attack doesn’t need to know the keyword itself, only the order it produces. That order is all that actually matters for decryption. So for each candidate column count:

1. Reconstruct the grid for every one of that count’s n! possible column orderings, filling columns in the candidate order.
2. Read the grid back out row by row to produce a candidate plaintext for each ordering.
3. Score every candidate and keep the best one for that column count.

Repeat across a range of candidate column counts (2 through 8 covers almost every hand-cipher keyword), and the single best-scoring result across all of them is almost certainly correct.

Scoring Without Spaces

There’s one wrinkle that doesn’t come up in the substitution ciphers earlier in this series. Columnar transposition conventionally strips spaces and punctuation before encrypting. So both the ciphertext and the correct decryption are one unbroken block of letters. The word-boundary matching used to crack Caesar and Affine (\bthe\b, matching only a standalone word) finds nothing here, because there are no spaces to form a boundary.

The fix is simple: match common English substrings without requiring word boundaries. Just count how many times "the", "and", "ing", "tion", and similar fragments appear anywhere in the candidate text. Short 1-2 letter words like “a” or “to” get dropped from the list entirely. They’d turn up constantly by pure chance in any block of English-like letters, adding noise rather than signal. Fragments of three or more letters are rare enough by chance, and common enough in real English, to separate the correct arrangement from the other thousands cleanly.

This fixed substring list is a deliberately simple heuristic, not the only option. The Autokey and Enigma breakers score with digram log-frequencies instead, which is a more statistically principled approach and would work here too. The substring list is kept here because it’s simpler to explain, and it’s already decisive enough for this cipher’s much smaller search space.

A Worked Example

Using a 494-letter ciphertext encrypted with the 6-letter keyword "CIPHER":

• Checking every column count from 2 through 8, the score for each candidate’s best ordering comes out as: 2 columns → 7, 3 → 8, 4 → 7, 5 → 10, 6 → 32, 7 → 11, 8 → 12.

• Column count 6 wins by a wide margin, nearly 3× the next-best score, because it’s the only one whose best ordering actually reconstructs real English.

• That winning ordering, read as original column positions in the order they were read, is 1 → 5 → 4 → 2 → 3 → 6. That’s not a coincidence. It’s exactly the order you get by sorting "CIPHER"’s own letters alphabetically (C, E, H, I, P, R) and noting which original column position each one came from: column 1 holds C, column 5 holds E, column 4 holds H, and so on. Alphabetizing the letters alphabetizes the columns right along with them.

  Column	1	2	3	4	5	6
  Keyword letter	C	I	P	H	E	R
  Alphabetical rank	1	4	5	3	2	6

  Reading the columns in ascending rank order, lowest to highest, 1 → 5 → 4 → 2 → 3 → 6, gives exactly the winning order the breaker found. The breaker never sees the word "CIPHER" at all; it only ever recovers this rank order directly.

• Decrypting with that ordering recovers the full original passage exactly, starting "COLUMNARTRANSPOSITIONSCRAMBLESTHEORDEROFLETTERSINSTEADOFTHEIRIDENTITY...". It’s the same passage used to build this worked example.

Python Implementation

The interactive visualizer above runs this exact attack in JavaScript. Here’s the same brute-force-plus-substring-scoring approach in Python.

Key Features

• No keyword recovery, just column order: break_columnar never guesses at letters. It searches directly over column orderings, since that’s the only thing decryption actually depends on. Many different keywords can produce the same ordering; recovering the ordering is the complete answer.
• Handles irregular column lengths: when the ciphertext length isn’t a clean multiple of the column count, the last few columns are one row shorter than the rest. get_column_lengths mirrors the exact same remainder rule the cipher itself uses, so reconstruction lines up correctly even for messages that don’t fill the grid evenly.
• Substring scoring, not word-boundary matching: score counts raw occurrences of common fragments, deliberately without \b word boundaries, since this cipher’s plaintext has no spaces to anchor them to.

Code

# columnar_breaker.py
#
# Breaks a columnar transposition cipher by brute-forcing every possible
# column reading order for each candidate column count. Unlike Vigenere
# or Beaufort, transposition doesn't scramble letter identities -- only
# their positions -- so the Index of Coincidence and chi-squared analysis
# don't apply here. Instead: try every permutation of column order,
# decrypt, and score by how many common English substrings show up.

import re
from itertools import permutations

# Words/fragments length 3+ only -- this cipher's plaintext has no spaces,
# so 1-2 letter words like "a" or "to" would match as noise almost
# anywhere and carry no real signal.
COMMON_SUBSTRINGS = ['the', 'and', 'ing', 'her', 'was', 'for', 'that', 'with',
                      'you', 'this', 'have', 'from', 'not', 'are', 'but', 'all',
                      'they', 'one', 'his', 'ent', 'tion', 'ere']


def clean(text):
    return re.sub(r'[^A-Z0-9]', '', text.upper())


def get_read_order(keyword):
    chars = list(keyword.upper())
    return sorted(range(len(chars)), key=lambda i: (chars[i], i))


def get_column_lengths(text_len, cols, rows):
    remainder = text_len % cols
    return [rows if (remainder == 0 or c < remainder) else rows - 1 for c in range(cols)]


def encrypt(text, keyword):
    cols = len(keyword)
    rows = -(-len(text) // cols)  # ceil division
    read_order = get_read_order(keyword)
    grid = [[None] * cols for _ in range(rows)]
    for i, ch in enumerate(text):
        grid[i // cols][i % cols] = ch

    result = []
    for c in read_order:
        for r in range(rows):
            if grid[r][c] is not None:
                result.append(grid[r][c])
    return ''.join(result)


# Reconstructs the grid by filling columns in the given read order
# (respecting each column's own length), then reads it row by row -- the
# exact inverse of encrypt(), except it takes a raw column order instead
# of a keyword, since breaking this cipher recovers the order directly.
def decrypt_with_order(ciphertext, cols, read_order):
    rows = -(-len(ciphertext) // cols)
    col_lengths = get_column_lengths(len(ciphertext), cols, rows)
    grid = [[None] * cols for _ in range(rows)]

    idx = 0
    for c in read_order:
        for r in range(col_lengths[c]):
            grid[r][c] = ciphertext[idx]
            idx += 1

    result = []
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] is not None:
                result.append(grid[r][c])
    return ''.join(result)


def score(text):
    lower = text.lower()
    return sum(lower.count(word) for word in COMMON_SUBSTRINGS)


def best_order_for_column_count(ciphertext, cols):
    best_score, best_order, best_text = -1, None, ''
    for order in permutations(range(cols)):
        candidate = decrypt_with_order(ciphertext, cols, order)
        s = score(candidate)
        if s > best_score:
            best_score, best_order, best_text = s, order, candidate
    return {'cols': cols, 'score': best_score, 'order': best_order, 'plaintext': best_text}


def break_columnar(ciphertext, max_cols=8):
    results = [best_order_for_column_count(ciphertext, cols) for cols in range(2, max_cols + 1)]
    best = max(results, key=lambda r: r['score'])
    return best, results


if __name__ == '__main__':
    plaintext_source = (
        "Columnar transposition scrambles the order of letters instead of "
        "their identity which means every single letter frequency in the "
        "ciphertext exactly matches the frequency of the original plaintext "
        "so counting how often each letter appears reveals nothing about the "
        "key an attacker instead searches for the column order that turns "
        "the scrambled letters back into readable words trying every "
        "possible arrangement of a short keyword is completely practical "
        "on a modern computer even when there are thousands of orderings "
        "to check because scoring each candidate takes almost no time at all"
    )
    keyword = 'CIPHER'

    clean_plain = clean(plaintext_source)
    ciphertext = encrypt(clean_plain, keyword)

    print('Ciphertext:', ciphertext)
    print()

    best, results = break_columnar(ciphertext, max_cols=8)
    print('Score per column count:', [(r['cols'], r['score']) for r in results])
    print(f"Best: {best['cols']} columns, read order {[c + 1 for c in best['order']]}, score {best['score']}")
    print()
    print('Recovered plaintext:')
    print(best['plaintext'])

Running this produces:

Score per column count: [(2, 7), (3, 8), (4, 7), (5, 10), (6, 32), (7, 11), (8, 12)]
Best: 6 columns, read order [1, 5, 4, 2, 3, 6], score 32

Recovered plaintext:
COLUMNARTRANSPOSITIONSCRAMBLESTHEORDEROFLETTERS...

This matches the visualizer’s own result exactly: 6 columns, the same read order, and the full recovered passage.

For Fun: The Same Thing, Compressed

In the same spirit as this series’ other compressed variants (not as something to learn the algorithm from), here’s the whole attack in about a dozen lines. The one trick worth pointing out: enc builds the encryption grid as a one-liner by (ab)using list.__setitem__’s return value of None, chained with and, purely to get assignment to happen as a side effect inside a list comprehension. It’s a genuinely bad way to write real code, and a fun demonstration of how far Python’s expression-based tricks can be pushed anyway. It’s verified to produce byte-for-byte identical output to the readable version above.

import re; from itertools import permutations
W=['the','and','ing','her','was','for','that','with','you','this','have','from','not','are','but','all','they','one','his','ent','tion','ere']
C=lambda t: re.sub(r'[^A-Z0-9]','',t.upper())
ro=lambda k: sorted(range(len(k)), key=lambda i:(k[i],i))
cl=lambda n,cols,rows: [rows if (n%cols==0 or c<n%cols) else rows-1 for c in range(cols)]
enc=lambda t,k: (lambda cols,rows,order,g: [g[i//cols].__setitem__(i%cols,ch) for i,ch in enumerate(t)] and ''.join(g[r][c] for c in order for r in range(rows) if g[r][c]))(len(k),-(-len(t)//len(k)),ro(k),[[None]*len(k) for _ in range(-(-len(t)//len(k)))])
def dec(c,cols,order):
    rows=-(-len(c)//cols); L=cl(len(c),cols,rows); g=[[None]*cols for _ in range(rows)]; i=0
    for col in order:
        for r in range(L[col]): g[r][col]=c[i]; i+=1
    return ''.join(g[r][col] for r in range(rows) for col in range(cols) if g[r][col])
score=lambda t: sum(t.lower().count(w) for w in W)
def break_columnar(ct,max_cols=8):
    return max((dict(cols=cols,score=score(p),order=order,plaintext=p) for cols in range(2,max_cols+1) for order in permutations(range(cols)) for p in [dec(ct,cols,order)]), key=lambda r:r['score'])

if __name__ == '__main__':
    plaintext = "Columnar transposition scrambles the order of letters instead of their identity which means every single letter frequency in the ciphertext exactly matches the frequency of the original plaintext so counting how often each letter appears reveals nothing about the key an attacker instead searches for the column order that turns the scrambled letters back into readable words trying every possible arrangement of a short keyword is completely practical on a modern computer even when there are thousands of orderings to check because scoring each candidate takes almost no time at all"
    clean_plain = C(plaintext)
    ct = enc(clean_plain, 'CIPHER')
    r = break_columnar(ct)
    print('Ciphertext:', ct)
    print(f"Best: {r['cols']} columns, order {[c+1 for c in r['order']]}, score {r['score']}")
    print('Recovered plaintext:', r['plaintext'])

Running this prints the ciphertext, the best column count and order, and confirms the recovered plaintext matches the source exactly. That’s the same result as the full version above. That break_columnar function is doing the entire brute-force search, every column count, every ordering within it, decrypt, score, and keep the best, inside a single generator expression passed to max(). It’s the same trick this series’ other “for fun” sections lean on, just with one more nested loop.

For Fun, Round Two: Even Tighter

Same attack, pushed one step further: dec becomes a lambda too, and the whole if __name__ block collapses onto a single line with semicolons. The interesting part is how dec avoids a loop entirely. Instead of walking through the ciphertext character by character and incrementing a position counter, it computes each cell’s position directly: for a given (row, col), it looks up col’s rank in the reading order via order.index(col), sums the lengths of every column read before it, and adds the row offset. It’s a pure expression with no mutation at all: a genuinely different way to think about the same reconstruction. It’s verified to produce identical output to both versions above.

import re, itertools
W = ['the','and','ing','her','was','for','that','with','you','this','have','from','not','are','but','all','they','one','his','ent','tion','ere']
C = lambda t: re.sub(r'[^A-Z0-9]','',t.upper())
ro = lambda k: sorted(range(len(k)), key=lambda i:(k[i],i))
cl = lambda n,cols,rows: [rows if (n%cols==0 or c<n%cols) else rows-1 for c in range(cols)]
enc = lambda t,k: (lambda cols,rows,order,g: [g[i//cols].__setitem__(i%cols,ch) for i,ch in enumerate(t)] and ''.join(g[r][c] for c in order for r in range(rows) if g[r][c]))(len(k),-(-len(t)//len(k)),ro(k),[[None]*len(k) for _ in range(-(-len(t)//len(k)))])
dec = lambda c,cols,order: (lambda rows,L: ''.join(c[sum(L[o] for o in order[:order.index(col)])+r] if r<L[col] else '' for r in range(rows) for col in range(cols)))(-(-len(c)//cols),cl(len(c),cols,-(-len(c)//cols)))
score = lambda t: sum(t.lower().count(w) for w in W)
break_columnar = lambda ct,max_cols=8: max((dict(cols=cols,score=score(p),order=order,plaintext=p) for cols in range(2,max_cols+1) for order in itertools.permutations(range(cols)) for p in [dec(ct,cols,order)]), key=lambda r:r['score'])
if __name__ == '__main__': plaintext = "Columnar transposition scrambles the order of letters instead of their identity which means every single letter frequency in the ciphertext exactly matches the frequency of the original plaintext so counting how often each letter appears reveals nothing about the key an attacker instead searches for the column order that turns the scrambled letters back into readable words trying every possible arrangement of a short keyword is completely practical on a modern computer even when there are thousands of orderings to check because scoring each candidate takes almost no time at all"; clean_plain = C(plaintext); ct = enc(clean_plain, 'CIPHER'); r = break_columnar(ct); print('Ciphertext:', ct); print(f"Best: {r['cols']} columns, order {[c+1 for c in r['order']]}, score {r['score']}"); print('Recovered plaintext:', r['plaintext'])

Every top-level name in this version, W, C, ro, cl, enc, dec, score, break_columnar, is a lambda or a lambda-backed name, not a single def in sight until there simply isn’t one at all. It’s a good demonstration of just how much of ordinary imperative code (loops, counters, mutation) can be re-expressed as pure functions once you’re willing to trade away every shred of readability to do it.

Interactive Visualizer

Try it above: paste any columnar-transposition-encrypted text (no spaces, matching this cipher’s convention), or use the default, and click Break Cipher. The chart shows the best score found for each candidate column count, and the winning column order gets revealed one position at a time once the sweep completes.

Why This Doesn’t Scale Forever

Brute-forcing every column order works cleanly because factorial growth, while explosive, doesn’t get too explosive until well past the keyword lengths this cipher is realistically used with by hand:

For genuinely long keywords, real cryptanalysts switch strategies entirely, typically to a hill-climbing search: start from a random column order, repeatedly try swapping two columns, and keep the swap whenever it improves the fitness score, until no single swap helps anymore. That approach doesn’t guarantee finding the true global best the way exhaustive search does. But it explores a vastly smaller slice of the search space, and it still reliably converges on the right answer for realistic ciphertext lengths. This visualizer sticks to plain brute force because it’s simpler to explain and completely exhaustive for any keyword length transposition ciphers are actually used with in practice.

Historically, this exact weakness is why double transposition, running two successive columnar passes with two different keywords, saw real use. The joint search space for two stages multiplies together instead of adding, which pushes hill-climbing (or brute force) from “impractical past 15 letters” to “impractical almost immediately.” The same underlying idea, search over candidate arrangements and score by how English-like the result looks, still applies in principle. It just has to search a dramatically larger space to get there.

Limitations of This Attack

• Very short ciphertexts weaken the substring scores. With little text to work with, several wrong column orders might coincidentally contain a fragment or two, creating a tie the heuristic breaks arbitrarily. Longer ciphertexts give the correct order more chances to pull decisively ahead.
• The fragment list assumes English. COMMON_SUBSTRINGS is built from English letter patterns. Ciphertext encoding another language would need a different fragment list tuned to that language’s own common substrings.
• This breaker only targets a single columnar stage. Double transposition (see above) defeats it directly, since no single column-order permutation correctly decrypts a ciphertext that’s actually gone through two independent scrambling passes.

FAQ

Why doesn’t frequency analysis work on columnar transposition?

Because transposition never changes which letters appear, only where they sit. The ciphertext contains exactly the same letters, in exactly the same quantities, as the plaintext, just shuffled. Every statistical property that depends on letter frequency (single-letter counts, the Index of Coincidence, chi-squared analysis) is identical between the ciphertext and plaintext, and therefore useless for recovering the key.

How is the key actually recovered if not through frequency analysis?

By brute-forcing the column order directly. A keyword of length n only produces n! possible reading orders, which is small enough to check exhaustively for realistic hand-cipher keyword lengths. Try every ordering, decrypt, and keep whichever produces the most recognizable English.

Why count substrings instead of whole words?

Because columnar transposition strips spaces before encrypting, so both ciphertext and plaintext are unbroken blocks of letters with no word boundaries to match against. Counting substrings (of three letters or more, to avoid noise from very short fragments) sidesteps that entirely.

What happens with a longer keyword, like 12 or 15 letters?

Brute force stops being practical. 12! is about 479 million, and 15! is over a trillion. Real cryptanalysis switches to a hill-climbing search at that point: start from a random ordering, keep any swap of two columns that improves the score, and repeat until no swap helps. It’s not guaranteed to find the exact optimum, but it converges reliably in practice on a tiny fraction of the full search space.

Is columnar transposition secure today?

No. Like every cipher in this series, it offers no real protection against modern cryptanalysis or computing power. Combined with a substitution cipher, though (as in the historical ADFGVX cipher), transposition becomes a genuinely useful building block. Scrambling position on top of scrambled identity resists both frequency analysis and this article’s column-order attack simultaneously.

References

1. Wikipedia. “Transposition cipher.” Available at: https://en.wikipedia.org/wiki/Transposition_cipher

2. Practical Cryptography. “Columnar Transposition Cipher.” Available at: http://practicalcryptography.com/ciphers/columnar-transposition-cipher/

3. Singh, Simon. “The Code Book.” Doubleday, 1999.