Cryptology Cryptanalysis of a Columnar Transposition A Systematic Approach

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Lengths of Key and Columns

We want to express the number of columns of a given length the columnar transposition scheme has, depending on the key length. Note that we are dealing also with incompletely filled rectangles.

To this end we divide the length r of the text by the length l of the key, that is also the number of columns. We perform the usual integer division with remainder:

r = q × l + s     where 0 ≤ s < l.

• If s = 0, that is l is a divisor of r, then the text has l columns of length q.
• If s > 0, that is l is not a divisor of r, then the text has s columns of length q+1, and l-s columns of length q.
• In any case all columns have lengths = q or q+1.

The first q letters of the ciphertext must constitute a column of the plaintext (or a column minus the last letter), and likewise the last q letters of the ciphertext must constitute a column of the plaintext (or a column minus the first letter).

These two columns are different (except for the trivial case l = 1 that we may exclude without qualms). And at least one of them is not the last column of the plaintext, therefore it has a right neighbor.

Therefore we can hope to find an entry into the solution by doing two things for each value l = 2, 3, 4, … successively:

1. Take the first q letters from the ciphertext, move them along the complete ciphertext, beginning with position q+1, and calculate the cBLW score for each position.
2. Take the last q letters from the ciphertext, move them along the complete ciphertext, up to position r-2q, and calculate the cBLW score for each position.

Then pick the largest of these values in order and try to attach further columns by anagramming.

Here is an example of this procedure.

Exercise: Discuss the case where one of the test columns is the last one of the plaintext.