A formula under the hood of a columnar transposition cipher

November 21, 2011, 7:45 am

It’s been a couple of Math Mondays since we last looked at columnar transposition ciphers, so let’s jump back in. In the last post, we learned that CTC’s are really just permutations on the set of character positions in a message. That is, a CTC is a bijective function \( \{0, 1, 2, \dots, L-1\} \rightarrow \{0, 1, 2, \dots, L-1\}\) where \(L\) is the length of the message. One of the big questions we left hanging was whether there was a systematic way of specifying that function — for example, with a formula. The answer is YES, and in this post we’re going to develop that formula.

Before we start, let me just mention again that all of the following ideas are from my paper “The cycle structure and order of the rail fence cipher”, which was published in the journal Cryptologia. However, the formula you’re about to see here is a newer (and I think improved) version of the one in the paper.

To start with, let \(L\) be the length of the message and let \(C\) be the number of columns we are using in the CTC. Denote by \(\pi_{C,L}\) the permutation underlying the CTC. Again, \(\pi_{C,L}\) is a bijection from the set \( \{0, 1, 2, \dots, L-1\}\) to itself. The concept behind the formula for \(\pi_{C,L}\) is best understood by way of example. Consider the message:


which has 20 characters (not counting the spaces), and suppose we used a CTC with 4 columns to encipher it. Have a look at the message once it is written out in columnar form:

Note that the enciphered message would be STREN EORSO NRIAO AAVTN by reading off one column at a time. But what we are more interested in here is where the character in position \(n\) goes after applying the cipher. In other words, we want to find out a general form for \(\pi_{C,L}(n)\). Remember that the very first character in the message has position 0, not position 1 — so the first character is position 0, the second character is position 1, and so on until the last character which is in position \(L-1\).

If the the character we are moving happens to be in the first column of the grid, then finding out its location in the ciphertext is easy. The initial “S” (which is in position 0) stays in position 0. The “T” that is in row 2, which is in position 4 in the plaintext ends up in position 1 in the ciphertext (i.e. the second letter). And so on. In other words, the ending position for the characters that are in the first column of the grid is equal to the number of rows above that character. This makes sense because we are enciphering the text by reading down one column at a time, so we have to count down the rows above a character in order to get to its final position.

What about characters in other columns? To get to the position in the ciphertext of a character in column 2, for instance, we’d have to read through the entire first column (which has 5 characters in it) and down all the rows above that character. So, for example, the “O” that is in the second row starts in position 5 and ends in position 5 + 1 = 6. The “S” in the fourth row starts in position 13 and ends in position 5 + 3 = 8. Likewise, the position of a character in column 3 in the grid would be reached after reading through two full columns preceding that character and then through the rows above that character. And so on. For instance, the “V” that is in column 4, row 3 (with plaintext position 11) has three full columns preceding it and two rows above it, so its final position would be \(5 + 5 + 5 + 2 = 17\).

So to find the ciphertext position of a character, we have to count two things:
(1) The number of characters in columns preceding the character in the grid, and
(2) The number of rows above that character in the grid.

For the time being, let’s assume that \(C\) divides \(L\) as we did in the example. (This can aways be obtained by padding the original message.) Then there are \(L/C\) characters in each column. If we can find the number of columns preceding a plaintext character, we can multiply that number by \(L/C\) and that will give us the count in (1); add on the row count in (2) and we’ll have our final position. That’s the main idea. Now, let’s try to flesh this out by determining those two counts in terms of \(n\), the plaintext position of the character in question.

First, how many columns precede the character in position \(n\) when the message is put into columnar form? This is the same number as the remainder we get if we divide \(n\) by \(C\). For example, if we were using four columns (as in the example), then the characters in column 1 had positions 0, 4, 8, and so on; the characters in column 3 had positions 3, 7, 11, etc. So the number of columns preceding the character in position \(n\) is \(n \, \textrm{mod} \, C\). Let’s call this number \( n’\).

If the number of columns preceding the character in position \(n\) is \(n’\), then the number of characters preceding it is
since there are \(L/C\) characters in each column. This takes care of the column count in (1) above.

Now onto the row count. How many rows are above the character with plaintext position \(n\)? Divide \(n\) by \(C\); it may not divide evenly, but you will get a quotient \(q\) and a remainder — which we already have denoted \(n’\) — such that \(n = Cq + n’\) and \(0 \leq n’ < n\). What does the quotient \(q\) represent? Imagine reading through the enciphering grid one row at a time as you would a newspaper, starting with the first row, moving to the second row when you reach the end of the last column, moving to the third row after reaching the end of the last column again, and so on. The quotient \(q\) would be the number of times you would reach the final column before moving to the row that contains the character in position \(n\). Then you would read \(n’\) characters in that row. But notice: \(q\) counts the number of complete rows above the character you are trying to reach. It’s the second quantity we wanted above. In terms of \(n\) itself, solve the equation \(n = Cq + n’\) for \(q\) to get
$$q = \frac{n – n’}{C}$$

We are now in position to give a basic formula for \(\pi_{C,L}\). The final position in the ciphertext of a character starting in position \(n\) in the plaintext would be just the number of characters in columns preceding the character plus the number of rows above the character. Assuming \(C\) divides \(L\), this comes out to:
$$\pi_{C,L}(n) = \frac{n-n’}{C} + \frac{n’L}{C} = \frac{n + n’(L-1)}{C}$$
where \(n’ = n \, \textrm{mod} \, C\).

We’ll address the situation if \(C\) does not divides \(L\) in another post, since it gets technical and this post is long enough already.

If we specialize to the case of the rail fence cipher. then this formula simplifies nicely. In that case, \(C = 2\) and so \(n’\) is either 0 (if the plaintext position \(n\) is even) or 1 (if odd). The formula simplifies to:
$$\pi_{2,L}(n) = \left\{ \begin{array}{ll}
\frac{n}{2} & \textrm{if} \ n \ \textrm{even} \\
\frac{n+L-1}{2} & \textrm{if} \ n \ \textrm{odd}
This makes sense because in the rail fence cipher, all the even-numbered positions end up on the top “rail” and so they take the position at half their original distance from the beginning.

So now we have a formula for a columnar transposition cipher’s permutation. What can we do with it? Lots of things, but in the next post we’ll start trying to understand the underlying permutation structure of a CTC by using this formula. Stay tuned!

This entry was posted in Abstract algebra, Crypto, CTCs, Math, Math Monday, Number theory and tagged , , , , , . Bookmark the permalink.