The second major family of encryption techniques is called transposition ciphers. I find transposition ciphers to be
rather dull; in their pure form, they’re very simple, and not very difficult
to crack, even without computers. But some of the most sophisticated
modern ciphers can be looked at as a sort of strange combination of
substitution and transposition, so it’s worth looking at.
A transposition cipher doesn’t change the characters in the plain-text when it generates the cipher-text – it just re-arranges them. It applies some kind of permutation function to the text to produce a re-arrangement, which can be reversed if you know the secret to the the permutation.
For example, the most classic version is called the rail fence cipher. In a rail fence cipher, you pick a number of rows, and then write your text as a zig-zag across those rows. For example, here’s the words “FOR EXAMPLE”
arranged in the rail-fence pattern with three rows:
F X L O E A P E R M
Now, the ciphertext is what you get by reading the rows straight across, left to right: “FXLOEAPEPM”.
Much the same flavor, but a bit more complicated is the column
transposition cipher: arrange the letters into a rectangular grid,
and re-arrange the columns according to some secret key. Then read
the characters off the resulting rows right to left.
For an example, we’ll take the sentence “FOR EXAMPLE THE MOST CLASSIC VERSION IS CALLED THE RAIL FENCE CIPHER”. We’ll run it through four
rows. For simplicity, we generally pad out the end to fill in the rectangle. The padding should attempt to follow the frequency distribution of letters
in the plaintext. Here it is, with the end padded using the characters “CRA”.
FXLETSVISLHINIR OAEMCSEOCEELCPC RMTOLIRNADRFEHR EPHSACSILTAECEA
Now, you take the columns, and re-arrange them, according to some pattern. For example, there are fifteen columns here, and we can use
a five-column permutation, repeated on three groups of five. For example,
(2,1,4,5,3):
XFETL VSSLI IHIRN AOMCE ESCEO LEPCC MROLT RIADN FRHRE PESAH SCLTI EAEAC
Now, we read across, and get the following, with spaces separating groups of four characters for ease of reading (the convenience spacing is deliberately different than the cipher size): “XFET LVSS LIIH IRNA OMCE ESCE OLEP CCMR OLTR IADN FRHR EPES AHSC LTIE AEAC”.
This kind of column transposition cipher can easily be based on
a password. The idea is that you use the password both the
decide the size of the grid to be used for the transposition, and
the order of column transposition. For example, if we used the password
“chowder”, we’d use a grid with width 7; and we’d define the transposition
by the alphabetic order of the characters in the password: 1457236.
So let’s do that to our example. It’s got 58 characters,
and we want 7 columns, so we’ll use 9 rows, and pad the end. Here’s
the initial grid, before the transposition.
1 2 3 4 5 6 7 F E L S L L H O T A I E F E R H S O D E R E E S N T N C X M I I H C C A O C S E E Q M S V C R C U P T E A A I P L C R L I P E
Now, we transpose the grid, putting in the order (1, 4, 5, 7, 2, 3, 6):
1 4 5 7 2 3 6 F S L H E L L O I E E T A F R O D R H S E E N T C E S N X I H C M I C A S E Q O C E M C R U S V C P A A P T E I L L I E C R P
Reading that off, we get “FSLH ELLO IEET AFRO DRHS EENT CESN XIHC MICA SEQO CEMC RUSV CPAA PCEI LLIE CRP”.
Decoding is almost the same. We’ll take our ciphertext, and write it out
in rows the width of the password:
1 2 3 4 5 6 7 F S L H E L L O I E E T A F R O D R H S E E N T C E S N X I H C M I C A S E Q O C E M C R U S V C P A A P T E I L L I E C R P
Now, we take our password, and create the reverse permutation. Before,
we mapped column 1 clear to column 1 cipher, column 4 clear to column 2 cipher, 5 to 3, 7 to 4, 2 to 5, 3 to 6, and 6 to 7. So
the reverse is (1:1, 2:4, 3:5, 4:7, 5:2, 6:3, 7:6); or, in
the same form as the encryption mapping, (1, 5, 6, 2, 3, 7, 6).
You can get even more clever, and use a route cipher: in a route cipher, instead of uniformly re-arranging the rows, you follow a particular fixed path through the text. If you make a sufficiently complex path, it can
produce a decent result.
The problem with all of the transposition ciphers is that they’re
easy to crack without knowing the secret. Just start permuting letters, looking for words – starting with the simplest words. For example,
you expect most sentences to have “the” in them; so you look for “t”, “h”, and “e” – and try removing that as a word. Keep doing that, and you can get some simple words from the text. You can also look for relatively
unusual characters in the text, and see what words you can form using characters from the text. For example, the “X” in the our sample text is
very unusual; there aren’t that many common words that include “X”. You can search to see if you can form one of them using the ciphertext characters. And once you’ve found a few words, you can start finding the pattern that
will allow you to decode the entire text.
If it’s a column transposition cipher, you just need to start experimenting with different numbers of columns – eventually, you’ll start
seeing columns containing words!
Some of this can be worked around: for example, perform a column transposition, then do a row-transposition on the result. That breaks
free of the “try different widths” problem. But still, for a typical short encrypted message, the permutation technique will get you the message in a reasonable amount of time.
What makes transposition ciphers interesting is that they work well in combination with other things. Take a rotating substitution cipher, and
do transpositions both before and after the substitution. You’ve just made frequency analysis of anything larger than letters a lot harder.