Programming Praxis

Transposition ciphers work by rearranging the letters of a plaintext to form a ciphertext; both the length of the text and the frequency distribution of the letters are identical between plaintext and ciphertext. The rail-fence cipher is a well-known transposition cipher; another is the columnar transposition that is the subject of today’s exercise.

To illustrate columnar transposition, we will encipher the plaintext PROGRAMMINGPRAXIS with the keyword COACH. First, COACH is converted to the numeric key 25134 by noting the alphabetic ordering of its letters; the two Cs have the same rank, so they are ordered left to right. Then, the plaintext is written in rows under the key, each row the same length as the key:

C O A C H
2 5 1 3 4
P R O G R
A M M I N
G P R A X
I S

The ciphertext is read off by colums, taking the columns in numeric order; first OMR, then PAGI, and so on, ending with RMPS:

O M R P A G I G I A R N X R M P S

Decryption is the opposite operation. The shape of the grid is determined by the number of letters in the ciphertext and the number of letters in the key:

C O A C H
2 5 1 3 4
_ _ _ _ _
_ _ _ _ _
_ _ _ _ _
_ _

Then the letters of the ciphertext are filled in to the grid starting with the lowest-numbered column, then the second column, and so on, respecting the given column lengths; here is the grid with the first two columns filled

C O A C H
2 5 1 3 4
P _ O _ _
A _ M _ _
G _ R _ _
I _

Columnar transposition is fairly easy to break; guess a key length, write out the columns, then look for common letter-sequences like QU or THE or ING. Columnar transposition can be made much more secure by double-encrypting the input with two keys of differing length: encrypt the plaintext with the first key, then encrypt the intermediate ciphertext with the second key.

Double transposition ciphers were routinely used for military field-grade encryption through the Second World War, because they are reasonably secure but manageable by hand in less-than-ideal circumstances. It is said that the French could normally read German ciphers due to poor radio discipline by German cipher clerks; search for Übchi to learn more of this fascinating story. In recent times, double transposition ciphers have been cryptanalyzed and attacks are known.

Your task is to write functions to perform double-transposition encryption and decryption. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2