Railfence Cipher and the frequency analysis attack
by Jerome Bradenbaugh
Courtesy of Fravia's pages of reverse engineering
The Railfence cipher is a transposition cipher based on rearranging the order of the plaintext letters according to a rising and falling pattern resembling a railfence.
Consider ciphering the message Bulls win by six with a "three-rail" fence. The message would cipher as follows:
b s n
u l i y s x
l w b i
Notice the "railfence" created by plotting the letters (and in this case, spaces, too) in this order. From there, strings are created
left to right, top to bottom and concatenated to produce the cipher text. The three strings look like this:
bsn
ul i ysx
lwbi
Finally, concatenating the three strings produces bsn ul i ysxhlwbi.
Unlike the other ciphers in this demonstration, the spaces stay in. That's a personal preference. Since letters are simply being rearranged, you
can include any or all characters. There's also one other consideration to using the Railfence cipher.
Not only can you specify the number of "rails" (to which the application below refers to as groups),
but you can also determine the rail at which you want to start placing the plaintext letters. In the above example the plaintext letters start from the
first rail of the fence. That is, b goes in the first rail, u goes in the second, l in the third, and so forth. However, you can start
with the second group, putting the b in the second, the u in the third, and so forth. The application below refers to this as displacement.
All the receiving party needs is the number of groups and the displacement, if any. Here's the application. This particular applcation has some
validation features, and assigns default values to Groups and Displacement if those validation conditions are not met. The defaults are
three groups and zero displacement.
To cipher enter the plaintext in the text area, select the number of groups and a displacement amount, then choose the Cipher button. It's
that easy. This application will handle as much as 8-9K of text. After that, you run the risk of sucking
up all your system's resources.
To decipher enter your ciphertext in the textarea, enter the number of groups and the displacement (if any),
then choose the Decipher button. Notice that the plaintext has retained its spaces.
This application does some form validation for basic common sense restrictions. For example, you can have at most
(message.length - 1) groups, and you must have at least three groups. Could you change this? Sure, but if you have more than (message.length - 1) groups,
you'll wind up with the ciphertext in the same order as the plaintext (plus null characters in excess of message.length groups). You could have one or two
groups, but one group will again produce identical ciphertext as plaintext, and two groups doesn't produce much of a ciphertext.
The displacement is also restricted to a maximum of ((2 * groups) - 3) places. Consider plaintext with five groups. This application restricts you to
a maximum displacement of seven places. After ((2 * groups) - 3), the displacement sequence repeats itself. In this case, a displacement of 0 is the same as
a displacement of 8. The same goes for 1 and 9, 2 and 10, 3 and 11, and so forth.
Should you violate the group or displacement restrictions, the applications sets a default(s). The group defaults to 3, the displacement to 0.
The Crack
You can attack this one in several different ways. The amount of possible groups is the difference of the maximum and
minimum number of groups. You can generate a that many possible group translations. Then, since displacement also has a limited range (from 0 to ((2 * groups) - 3)),
an offset can be applied to each of the possible group translations. In other words, if you have 7 possible groups and 14 (0 - 13) possible offsets, you can decipher
the text with a maximum of 98 combinations.
Transposition ciphers such as the railfence cipher have another major weakness: they don't
hide letter frequencies at all. What does that mean? Since this is a monoalphabetic cipher (each substituted letter always represents
the same plaintext letter), you can check for the frequency each letter appears in the cipher. The most frequently appearing letters of the
English language are E-T-A-O-I-N-S-H-R-D-L-U, respectively (See Frequencies of
Letters in English Text for more info). You can start the cracking there.
There's always the brute force attack. Since the plaintext has only been rearranged (transposed) and not substituted, rearranging the
ciphertext in every possible combination will eventually reveal the plaintext. Of course, the number of permutations rises exponentially. Long messages
might make this approach impractical.