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.
There’s a sense in which each ruond of DES is a substitution cipher sandwiched by transposition ciphers. These ideas on letters go all the way up.
Didn’t the romans (or someone) used to wrap a strip of paper (or whatever) around a stick, write a message on that – across the windings, and use the strip of paper as an encoded message?
Paul Murray: yes, the Romans did that. The recipient could only decipher the message if he or she used a stick of the same thickness as the sender. Or just tried a whole range of different sticks until the message made sense, of course.
@Paul:
Incidentally, that’s referred to as a Scytale cipher. See here:
http://en.wikipedia.org/wiki/Scytale
Seeing “transposition” reminded me of a rather devious crypto system that was written up in “Dr. Dobbs” some years ago. Most crypo systems are byte-oriented: whether shifted, transposed, or some other operation, it’s still by byte.
But Dale Thorn’s “BCRP” program transposes the BITS, not the bytes, and suddenly it’s “WHAT frequency analysis?” He even bragged that even a quantum computer wouldn’t help breaking it, and offered a reward for decryption:
http://www.ddj.com/architect/184404414
One year later, he raised the reward:
http://www.ddj.com/architect/184404920
Haven’t heard anything since.
I remember using a transposition+substitution cipher wayyy back in elementary school. Sure, it’s exactly “kids in treehouses” stuff, but it worked for our purposes.
Anyhow, in response to #5…
Dale Thorn’s cipher might be interesting but there’s a few red flags. He really comes off like the “kook in a basement” type with his “I’ve got this amazing cryptosystem that defies all the experts!” stuff. Apart from that, he has his source code (“Compiles under MS Quick-C circa 1991” — not the best thing to publish in 2006) instead of a more proper description.
I can’t comment on the actual algorithem itself (I’m not one of the experts) but the implementation stinks. Writing the thing for MS-DOS is pretty embarassing and specifying passwords on the command line isn’t so hot.
Bit transposition is sort of neat (only because of the depth of false solutions), but if you have two independent messages of the same length then you can apply the same transpositions to each and know that you’re right when they both come out with meaningful answers. So they are at best only secure in the one-time sense (key used once and only once (actually since the number of 1’s and 0’s is fixed it is less than perfect but would still have several meaningful decryptions)). Many of the transpositions form groups so you can just keep applying them over and over (with the same key) until you get a decryption. (sort of neat to show the cryptography class ;-> )
NO, the Romans didn’t! The Greeks did!
Scytale is a Greek word. Knowledge of languages is useful to cryptanalysts 😉
The VB code for BCRP1 is virtually identical to the DOS C or Basic code. If you see a red flag there you don’t know real programming. To understand what I do you have to study large lattices at least. All that aside, what nobody on these forums ever gets (hint) is that the object is to *not* use math, which is a shortcut with weaknesses, rather, to increase randomness by degrees of shuffling, like a lottery. It works, it’s strong, and since it’s very outside the box, isn’t easy for people to grasp.
Dale:
I haven’t looked at your code – I’m not a cryptographer, and you can see how swamped I am between work and illness by how slow the blog’s been lately.
But:
“The object is to *not* use math”? Sorry, but that’s a dead giveaway that you’re clueless.
Permutations are math. Shuffling is math. Randomness is math. Cryptography is math.
One of the subtle and difficult things to grasp about cryptography is how things that seem unshakably random and unpredictable can be broken wide open, because they’ve got some subtle problem.
Math isn’t a weak shortcut that leads us to weak ciphers. Designing strong ciphers is incredibly hard, and math is the tool that lets us analyze the ciphers to understand just what makes a cipher weak or strong.
Part of what makes DES such an interesting thing to study is that when you look at it,
it looks like a damned mess of gibberish. It’s got a ton of funny and completely random-looking functions (the S-boxes), which just make no apparent sense.
The thing, though, is that those functions are designed with a lot of very delicate mathematical properties. If you twiddle them, even just a little bit, without being very careful about your cryptanalysis, you’ll convert DES from a very strong 56 bit cipher to a worthlessly weak piece of junk.
Another example of that is from the world of assymetric cryptography – specifically, public key crypto. Everyone knows about RSA, which is based on prime factoring. There was, for a long time, a rival, which was based on a mathematical problem called the bag-packing problem. The bag-packing problem is a really simple to describe, but NP-hard problem to solve. The crypto system based on it, however, made a small mistake, which turned out to reduce the basis of the algorithm from solving the general problem to solving a restricted subset of the problem, and that subset problem had a fast solution. One, tiny mathematical error reduced it from something that should have taken years of computing time on a high-end supercomputer to something solvable on a laptop.
You can’t avoid the math. And if you try, you’re just virtually guaranteeing that you don’t really understand all of the properties of what you’re doing – and that, generally, leads to a system that has unanticipated failure modes.
In ~1973, the Isley Bros. had a hit “It’s your thing”, and a friend was using the tagline excessively, so I said “I don’t have a thing”, and she responded “then your thing is not having a thing”. Of course all is math, in the sense that all is atoms and molecules. Most of my math education after school was studying the HP app pacs that sold with their computers and calcs from the early 1970’s on. My crypto ed began with cypherpunks, sci.crypt, and so on. Not clueless by any means. The point is I do encryption whose highest form of “math” is sorting an array that’s an existing never-changing lookup table. And my offer of $10,000 to any serious org that can demonstrate a crack for my cipher implementation, with a chosen plaintext challenge, is far more real than naysay.
The point of my version of a modified transposition cipher is to shift most of the security to the user, and away from “randomization” supplied by the code. In advance of any doubts I’d like to mention that it has withstood two large chosen plaintext attacks with a $15,000 award. Anyone who is an expert in lattices might be able to predict the number of attempts in a chosen plaintext/ciphertext attack that would be required to break the scheme, given the strength of the password/key. But if that turns out to be purely a function of the strength of the user key, then it’s a moot point. There are many modern articles on shortcut methods of breaking crypto schemes – differential fault analysis is an early example. I pay attention to those things.
Not to be redundant, but everyone knows that shuffling, as in lotteries and card games, is where you get maximum randomness. But of course crypto can’t be purely random. And so my goal is to use shuffling to approach maximum randomness based on the user’s input, to create multiple shuffle layers. In an actual implementation of course, an XOR layer would be added to disguise the bit distribution.