Simple Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 7

1.4 Transposition Ciphers
The preceding encryption mechanisms are all substitution ciphers, in which the primary operation is to replace
each input character, in place, with some other character in a reversible way. Another general class of ciphers
mentioned briefly above is transposition ciphers (or permutation ciphers), in which instead of characters be-
ing substituted for different ones, they are shuffled around without changing the actual characters themselves.
This preserves the actual contents of the characters but changes the order in which they appear. For example,
one of the simplest transposition ciphers is simply to reverse the characters in the string — cryptology be-
comes YGOLOTPYRC .
In order for a transposition cipher to be secure, its encryption mechanism can't be so obvious and simple as
merely reversing the string, since even an amateur eye can easily see what is happening. In the following sec-
tions, we explore some of the more popular and effective methods of implementing transposition ciphers.
1.4.1 Columnar Transpositions
Probably the most common, simple transposition cryptographic method is the columnar transposition cipher.
A columnar transposition works in the following way: We write the characters of the plaintext in the normal
way to fill up a line of a rectangle, where the row length is referred to as k ; after each line is filled up, we write
the following line directly underneath it with the characters lining up perfectly; to obtain the ciphertext, we
should read the text from top to bottom, left to right. (Often, spaces can be removed from the plaintext before
processing.)
For example, to compute the ciphertext of the plaintext all work and no play makes johnny a
dull boy with k = 6, write the message in a grid with six columns:
a l l w o r
k a n d n o
p l a y m a
k e s j o h
n n y a d u
l l b o y
Now, reading from the first column, top to bottom, then the second column, and so forth, yields the following
message. Spaces are added for clarity.
AKPKNL LALENL LNASYB WDYJAO ONMODY ROAHU
To decrypt such a message, one needs to know the number of characters in a column. Decryption is then just
writing the characters in the same order that we read them to obtain the ciphertext, followed by reading the text
left to right, top to bottom.
The key can then be viewed as the integer k , the number of columns. From this, we can calculate the number
of rows ( r ) by dividing the message length by k and rounding up.
1.4.2 Double Columnar Transpositions
It does not take an advanced cryptanalyst to see an immediate problem with the above columnar transposition
cipher — we can easily guess the number of columns (since it is probably a low number for human-transform-