As Laurence Smith points out,
transposition ciphers are to some extent analogous to jigsaw
puzzles. In such puzzles and ciphers, if all the pieces are present
and in proper order, a clear picture of the message exists. If they
are mixed up, all of the elements are still present, but have no
apparent meaning. If the disorder is brought about by random
shuffling, only long and painstaking attempts by trial and error can
bring them back to normal order. Since practical cryptography is not a
puzzle aiming to test the patience, but is the science of secret
communication, its object is to arrange some sort of systematic
disorder, which can be set right quickly and accurately by the one for
whom the secret message is intended.” (Smith, Laurence
Dwight. Cryptography: The science of secret writing. Dover
Publications, INC. 1955. New
York. 31-32)
As we explain more fully below, in the Rail Fence Cipher, the message is broken into columns of alternating rows. The rows of characters resemble the rails of a fence, hence the name.
Historical Background
The first uses of the transposition cipher are traced back to the ancient Greeks. They used a device called a scytale to encrypt and send messages. The scytale, a transposition machine, was comprised of a cylinder and a parchment, similar to a ribbon, which was wrapped around the cylinder. The message to be encrypted was then written on the coiled ribbon. The letters of the original message would be rearranged when the ribbon was uncoiled. However, the message was easily decrypted when the ribbon was rewrapped on a cylinder of the same diameter as the encrypting cylinder. In this case the diameter of the encrypting cylinder would be the key to encrypting and ultimately decrypting the secret message. The diameter of the cylinder determines how the ribbon coils on the cylinder and therefore how the letters in the plaintext message would be rearranged.
Encrypting a Message with Rail Fence
Similar to the diameter of the cylinder in the scytale machine, the number of rows of the Rail Fence Cipher is the key to encrypting and decrypting secret messages. In fact, the scytale used by the ancient Greeks can produce the exact same encrypted messages as the Rail Fence cipher if the diameter of the cylinder produced the same number of ribbon coils as the number of rows of the Rail Fence cipher. Thus, for our implementation of Rail Fence Cipher, the number of rows used to break up the message serves as the cryptographic key. It determines the exact form that the secret message will take.
To take an example, suppose we want to encrypt the message this is a test using a Rail Fence Cipher. In a Rail Fence Cipher, after removing the spaces from the original message, we would write the characters in the message in columns of alternating rows, which resemble the rails of a fence.
An Example of a Four Rail (row) Fence
t i e h s s i a t s t a
Plaintext: this is a test Ciphertext: tiehssiatsta
Padding. Note that in this case one padding letter (a) was added to this message. Padding letters ensure that all rows are evenly filled. In our example only one row needed to be filled, so one letter was added. The padding letter is chosen according its position in the alphabet and the number of rows that need to be filled. For instance, in this example only one row needed to be filled so the first letter (a) of the alphabet is chosen as the padding letter. If six rows needed to be filled, the sixth letter of the alphabet (f) would have been chosen as the padding letter and 6 f's would have been appended to the message and included in its decryption. If the rows are evenly filled, padding is still added to the text. In this case, the amount of padding is determined by the number of rows, the key, because an entire column of padding is added. The correspondence between the amount of padding needed and the padding letter becomes very important when decrypting the message.
After the message is encrypted, it is placed in blocks of five characters. Thus, the encrypted message would be written as tiehs siats ta.
Decrypting a Message with Rail Fence
To decrypt a secret message, first all spaces are deleted from the text. Then the ciphertext, with padding, is written to a 2 dimensional array. In our example, the array would have 4 rows and 3 columns. Generally, the number of rows is equal to the key and the number of columns of the 2 dimensional array is equal to the quotient obtained by dividing the length of the ciphertext by the key. In our case, the array would look like this.
t i e h s s i a t s t a
Next, the characters are written to one string by inserting the characters column by column.
The message would be decrypted as thisisatesta
The padding is then removed from the string. The last letter in the string, which is a padding letter, determines the amount of padding that must be removed. In this example, 'a' is the last letter in the text so only one letter is removed from the string. However, if 'f' were the last letter in the text, then 6 letters would be removed from the string. The original spacing is not recovered when the message is decrypted, but the message is recognizable.
The decrypted message with all padding removed would appear as one String. thisisatest
Recognizing Transposition Ciphers
The Rail Fence cipher and transposition ciphers in general are relatively easy to distinguish from substitution ciphers because the letter frequencies in the encrypted message remain the same as in unencrypted messages. For example, in a transposition cipher, you would expect to find that the letter 'E' is the most frequent letter if the language used is English. In general, the frequency distribution of all 26 English letters would be same in a transposition cipher as they would in plain English messages.
Analysis of Transposition Ciphers
What if you don't have the key to
a transposition cipher, how hard would it be to decipher a message?
In general, transposition ciphers become more complex and harder to
decipher as the number of letters being rearranged increases. This is
a simple consequence of the fact that when rearranging a larger block
of letters, more permutations are possible, as the following table
shows. For example, for a block of 3 characters (abc), there are 6
ways to rearrange them (abc, acb, bac, bca, cab, cba). And in general,
for a block of
n characters, there are n! (n factorial) ways to
rearrange them. The following table shows that n! grows
exponentially as n gets larger.
N
N!
3
6
4
24
5
120
6
720
7
5040
8
40320
9
362880
10
3628800
11
39916800
12
479001600
13
6227020800
14
87178291200
15
1307674638000
16
20922789880000
17
355687427960000
18
6402373703280000
19
121645100362320000
20
2432902007246400000
In the case of the Rail Fence Cipher, the analysis isn't quite so
difficult. If you know (or suspect) that a message was encrypted with
a Rail Fence Cipher, you could try to decipher it by reading every
other letter in the ciphertext, and if that didn't work, then every
third letter, or every fourth letter, and so on, until you cracked the
message. In our example, the secret message tiehssiatsta would be revealed by reading every third
letter, skipping over any padding letters and wrapping around to the
beginning of the string if you run out of letters. So we would read
letters 1, 4, 7, 10, 2, 5, 8, 11, 3, 6, 9, which would give: t-h-i-s-i-s-a-t-e-s-t-a.
Obviously, if your plan for rearranging the letters consists simply
of taking every other letter, or every third letter, and so on, the
number of possible rearrangements will be relatively small. Therefore,
the Rail Fence Cipher is not a particularly secure cipher.
Although, the scytale dates back to ancient Greece, transposition
ciphers were not widely used before computers became widespread
because they were difficult to do manually and prone to errors.
Today, many modern cipher algorithms use transposition algorithms.
For Further Study and Enjoyment