Previous
Next

Math Monday: Columnar transposition ciphers and permutations, oh my

November 7, 2011, 7:45 am

I hope you enjoyed Ed’s guest posts on NP-complete problems on TV the last couple of Mondays. It’s always great to hear from others on math that they are thinking about. This week it’s me again, and we’re going to get back to the notion of columnar transposition ciphers. In the first post about CTCs, we discussed what they are and in particular the rail fence cipher which is a CTC with two columns. This post is going to get into the math behind CTCs, and in doing so we’ll be able to work with CTCs on several different levels.

A CTC is just one of many transposition ciphers, which is one of the basic cryptographic primitives. Transposition ciphers work by shuffling the characters in the message according to some predefined rule. The way these ciphers work is easy to understand if we put a little structure on the situation.

First, label all the positions in the message from \(0\) to \(L-1\) where \(L\) is the length of the plaintext. We start at \(0\) because it makes the upcoming math easier. The cipher then takes the character in one position and moves it to another position. (It could be the same position as before.) What’s important to note is that

  • Since this is just a shuffling, characters that are in two different positions to begin with must end up in two different positions. That is, there are no “collisions”.
  • Every position has something in it when the cipher is finished. There are no positions that end up “empty”.

This makes a transposition cipher a function from the set of positions \( \{0, 1, 2, \dots, L-1\} \) to itself — and not only that, but the function is a bijection (it is “one-to-one” and “onto” in the sense described above in the bullets). And a bijection from a set onto itself has a special name in mathematics: We call it a permutation.

Permutations are one of the basic building blocks of the area of mathematics known as group theory, and so identifying transposition ciphers as permutations opens the door to using a lot of well-known theory in understanding them. There are two questions in particular about columnar transposition ciphers that we’d like to ask in terms of what we know about permutations.

To get to the first question, here’s a very basic permutation \(p\) on the set \( \{0, 1, 2, 3\} \), set up as a picture:

If this were a cipher, the character in position \(0\) would get moved to position \(1\), what’s in position 1 gets sent to position 2, and so on. In function language, we would say that \(p(0) = 1\), \(p(1) = 2 \), \(p(2) = 3\), and \(p(3) = 0\). So the encrypted form of the word HELP would be PHEL. If we invoke a little more math, we can come up with a formula for this function:

$$p(x) = x+1 (\, \textrm{mod} \, 4)$$

This means, to find the ending position of the character starting in position \(x\), we’d add 1 to \(x\), and then divide the result by \(4\) and keep the remainder.

It’s nice to have a compact, closed-form formula for this permutation for a number of reasons. Since columnar transposition ciphers are a special kind of permutation on the positions in a message of length \(L\), our first question to ask about CTCs is:

Is there a formula that will tell us where a CTC will send a character in position \(n\) (for \(0 \leq n < L\)?)?

The answer is “yes”, and I’ll show you a formula for the permutation underlying a general CTC using \(n\) columns next week. (Or you could go read the Cryptologia paper I wrote about it a few years ago.)

What’s the second thing we want to ask about? Let’s go back to the simple picture example from earlier. Since the inputs and outputs of a permutation all come from the same set, we can perform a permutation repeatedly on the same set, much like we might shuffle a deck of cards multiple times. This repeated application of a permutation is called composition. Here’s what the composition of the simple permutation with itself looks like:

So with two applications of \(p\) to this set, \(0\) gets sent to \(2\), \(1\) gets sent to \(3\), \(2\) gets sent to \(0\), and \(3\) gets sent to \(1\). We could add a third application of \(p\) to the picture if we wanted:

We could do this all day, but something happens if you add a fourth application:

Notice that \(0\), if you follow it all the way from left to right goes to… itself. So do 1, 2, and 3. So in other words, applying four applications of \(p\) amounts to doing absolutely nothing to the message. So does 8 applications, 12, 16, or 400.

Let’s call the “permutation” that does absolutely nothing to the set the identity permutation. That is, the identity permutation is the permutation that sends every element to itself. The identity isn’t very interesting as a cipher, but it plays an important role here because what we’re seeing is that a four-fold application of the \(p\) permutation above is the same thing as the identity. We also saw that four applications is the minimum number of applications of \(p\) of the set needed to get to the identity. We will define the order of a permutation to be this minimal number of applications needed to produce the identity. For our \(p\) above, the order of \(p\) is \(4\).

Does every permutation have an order? That is, given a permutation on a set, do you always end up with the identity permutation after a certain number of applications, or are there some permutations that never return to the identity? It’s a basic result of group theory that, as long as the set you’re permuting is finite (which for our purposes is true, since we are looking at transposition ciphers on finite-length messages), any permutation you use will eventually return to the identity after a certain number of applications depending on the permutation. Each permutation has its own order, but it’s always the case that the order of the permutation divides the total number of possible permutations, which for us is the number \(L!\).

So, again since a columnar transposition cipher is a certain kind of permutation, here’s the second question we’d like to think about:

What’s the order of a columnar transposition cipher? That is, how many applications will it take to get back to the identity?

The fact that this order exists for any CTC brings up an interesting issue. You might think, with a cipher system, than if encrypting a message once gives some measure of security, then encrypting twice should give you more security, three times should give you even more, and so on, like putting more and more deadbolt locks on your front door makes it harder to break into your house. But with CTCs this is not the case. Since every CTC is a permutation on a finite set, it has a finite order, so repeated encryption does not improve security. In fact, repeat the encryption enough times and you will actually decrypt the message.

If you found yourself in possession of a black-box machine that encrypts messages using a CTC, and you also intercepted a message that was encrypted with that CTC, you would not need any special information to break the code: you would just need to load the intercept into the black box and encrypt again and again, and eventually you would be guaranteed to get the plaintext back. So the question is asking, what’s the minimum number of encryptions needed to make that happen?

In the next post, we’ll talk about the formula for a CTC and introduce the all-important notion of a cycle in a permutation. Stay tuned!

Image: http://www.flickr.com/photos/latitudes/

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