Previous
Next

What is a columnar transposition cipher?

October 10, 2011, 10:53 am

http://www.flickr.com/photos/maistora/

We all have secrets to keep. Those secrets could be personal dirt we want to keep from others, or they could be something as mundane as our credit card numbers or medical histories. But all of us have information that we want to keep to ourselves or at least to a small circle of people whom we select. This is why the field of cryptology — the science of making and breaking coded messages, or more generally the notion of communicating in a secure way — is a viable and extremely active field of study these days.

I’ve been interested in cryptology ever since a student came to me in 1999 and asked me to direct an independent study on the subject for her. I’ve since taught topics courses in cryptology to math majors and to liberal arts students, and it always generates an amazing amount of interest. So I thought I’d start putting some of the cryptographic questions I’m interested in here on the blog as a sort of informal rolling seminar.

This week I want to introduce a topic that’s of interest to me, and that is the columnar transposition cipher.

By cipher we mean just a method of encoding a message. Cipher systems can be classified one of two ways: substitution ciphers, which work by replacing characters in a text with other characters in a predefined way (think of the cryptograms you see in the newspaper), and transposition ciphers, which work not by replacement but by mixing characters according to a predefined set of rules. Actually most cipher systems are combinations of these. The proper combination of confusion and diffusion of characters in a message creates a nearly-random collection of cipher characters which should be extremely hard for an unauthorized person to read.

A very simple example of a transposition cipher is one called the rail fence cipher. Here’s how it works. First, we take our message, and for simplicity let’s strip out all punctuation and spaces and capitalize all the letters. For example, the message “Leave the money in the briefcase!” would be

LEAVETHEMONEYINTHEBRIEFCASE

Next, place each character on one of two lines, starting with the first character on the first line, the second character on the second line, and alternating until we reach the end. For example, the message above becomes

The two lines interleave like levels of a split-rail fence, which is where this cipher gets its name. To get the encoded message, copy down the entire first row and append the entire second row. So in this example, the encoded message would be:

LAEHMNYNHBIFAE EVTEOEITERECS

I left the space in the middle to show where the break in the rows happens. We wouldn’t otherwise leave that in.

This is fun and easy — kids would like to use this, probably — but it’s hardly industrial strength. In fact, to break this cipher, all you need to know is its name. If you intercepted this encoded message and knew that it had been enciphered using the rail fence cipher (and according to Kerckoffs’s Principle, we always assume that the method by which we encipher messages is public knowledge), all you’d need to do is split the ciphertext in half, put the ciphertext back into rows, and read the plaintext off by alternating across rows. (Use a top rail one character longer than the bottom one in case the ciphertext has odd length.)

Just like with a real rail fence, what might provide more strength and security is if we used more than just a couple of rows. If we used three rows, the enciphering scheme would look like this:

So the enciphered message would be

LVHOYTBEA EEENIHRFS  ATMENEICE

When we start using multiple rows like this, it makes more sense to write the enciphering scheme using columns. Instead of loading the plaintext vertically across three alternating rows, load it into three columns, wrapping around at the end of each column like a typewriter:

LEA
VET
HEM
ONE
YIN
THE
BRI
EFC
ASE

Then read the ciphertext off by going column-by-column.

This enciphering scheme is the basic form of a columnar transposition cipher (which I will now lazily abbreviate as CTC). The rail fence cipher can be thought of as a CTC with 2 columns. Above you see a CTC with 3 columns. We can choose any number of columns we want (although 1 column is not a good idea, neither would 26 columns in our example; and 10 columns would be the same as choosing 8 columns). With the number of columns available as a choice to the sender of the message, we introduce the most important ingredient of a successful cipher system: a key, which is a piece of information that only the sender and her chosen circle of message recipients knows. Here, the key is simply the number of columns used.

That’s it for an introduction. Later posts on CTC’s will tackle some questions that arise about them, including:

  • Is there a way to tell exactly where a character in the plaintext will get moved under a CTC?
  • Which characters never move under a CTC?
  • Does enciphering once, then again, then again… make a CTC-enciphered message harder to break?

It’ll help to introduce some math in the next post that models transposition ciphers, namely the concept of a permutation. Leave some questions of your own in the comments if you’re interested. Otherwise stay tuned!

This entry was posted in Crypto, Math, Scholarship and tagged , , , . Bookmark the permalink.