Railfence Cipher and the frequency analysis attack

by Jerome Bradenbaugh
Courtesy of Fravia's pages of reverse engineering


Groups 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.