The columnar transposition cipher

A columnar transposition cipher doesn't change a single letter. It only moves them. The message is written in rows under a keyword, then read off column by column in the alphabetical order of the keyword's letters. Every letter survives, so the ciphertext has exactly the letter counts of the plaintext. That's the giveaway, and it's also why the cipher is harder to break than it looks. Applied twice in a row, it was an army field cipher in two world wars.

Try it

Nothing you type here leaves your browser.

Spaces and punctuation are removed first. Choose "Yes" under Pad the last row to fill an incomplete row with extra letters. Leave it on "No" to let the last row run short, which is the harder version to break.

How it works

Pick a keyword, say ZEBRAS, and write the message in rows under it, six letters to a row. Number the key letters by their place in the alphabet: A is 1, B is 2, E is 3, R is 4, S is 5, Z is 6. Now read down the columns in that order. Column 1 goes first (under A), then column 2 (under B), and so on.

The message WE ARE DISCOVERED FLEE AT ONCE has 25 letters, which leaves the last row one letter short in a grid six wide. Leave it short and the ciphertext is EVLNACDTESEAROFODEECWIREE. Fill the five empty places with extra letters (QKJEU) and it becomes EVLNEACDTKESEAQROFOJDEECUWIREE. To decrypt, divide the ciphertext length by the key length to get the number of rows, work out which columns are a letter short, cut the ciphertext into columns in key order, and read across the rows.

A very old idea, used until the 1950s

Transposition is among the oldest ways to hide a message (the scytale is one), but keyed columnar transposition shows up in print in the 17th century. John Falconer's Cryptomenysis Patefacta (1685) describes one of the earliest English versions, and also how to solve it by trial and error.

In the twentieth century the cipher was much more than a curiosity. In the First World War the German Army used a double columnar transposition, running the cipher twice with two different keys, a system the French called Übchi. French cryptanalysts often solved it within days, and after the method was published in a newspaper in 1914, Germany switched to something else. In the Second World War, resistance groups in the Netherlands and France, the British Special Operations Executive and the American OSS all used double transposition keyed from a memorized phrase. Leo Marks, who ran codes for the SOE, wrote that agents' poem-based transposition keys were easy to guess and led to captured agents. His answer was to give them random keys, printed on silk and used once. Soviet intelligence services used columnar transposition too.

Breaking it

• It doesn't hide letter frequencies. The ciphertext's counts are English: E, T and A at the top, an index of coincidence near 0.067. That's how you know it's a transposition and not a substitution (frequency analysis tool).
• Try the column orders. A key of k letters has only k! column orders: 720 for six, 40,320 for eight, 362,880 for nine, 3,628,800 for ten. A program can try every one, decrypt, and keep the ones that read as English. The tool above does that for 2 to 9 columns. On a 136-letter message encrypted with ZEBRAS (6 columns), CIPHER or LEMONS, it tests all 46,232 orders of 2 to 8 columns in about a quarter of a second, and the best-scoring one is the right one each time. The project's test suite checks that.
• Anagramming. By hand, slide pieces of ciphertext against each other and look for fragments that spell words. Guessed words (a name, "report") fix several columns at once.
• Several messages with the same key. If two messages of the same length share a key, line them up. The same permutation scrambled both, so working on one reveals the other.

Double transposition is much harder, because the second pass hides the structure of the first. Computers attack it with hill climbing on the two column orders, but it takes more text and far more effort than a single pass.

The code

// Columnar transposition. Write the text in rows as wide as the key, then read the columns in the alphabetical order of the key's letters.
// A short last row is left short (no filler letters). Repeated key letters are ranked left to right.
function columnar(text, key) {
  var width = key.length;
  var order = key.split('').map(function (c, i) { return [c, i]; })
    .sort(function (a, b) { return a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : a[1] - b[1]; });   // columns, in reading order
  return order.map(function (col) {
    var out = '';
    for (var i = col[1]; i < text.length; i += width) out += text[i];                      // one column, top to bottom
    return out;
  }).join('');
}

Related ideas

The rail fence cipher and the scytale are simpler transpositions. Put a Polybius square in front of a columnar transposition and you get the ADFGVX cipher.

Common questions