Saturday, August 27, 2005

Double Columnar Transposition

In this computer era, we could easily forget that cryptology goes back for thousands of years. Some encryption methods, performed by pencil and paper, are even today pretty secure, and can be applied 'in the field' without any devices. One of them is the Double Columnar Transposition. It was one of the strongest field ciphers, commonly used in World War II. If the key was used only for a limited number of small messages, it provided a very high security.

To perform a Double Columnar Transposition we write out the key as column header. The key is numbered in alphabetical order. If two letters of the key are the same, the first in the key gets the lowest number.

Plain text : THIS IS A SECRET MESSAGE
1st Columnar Key: LEONARDO
2nd Columnar Key: DAVINCI

Note that, in reality, two keywords or frazes with a length up to 20 letters each were used to encipher a message.

The plain text is written out in successive rows beneath the headers:

L E O N A R D O
4 3 6 5 1 8 2 7
---------------
T H I S I S A S
E C R E T M E S
S A G E

De code message is read off in columns in order of the headers:

First cipher text: ITAEHCATESSEEIRGSSSM

Next, we write it down again, in successive rows, and perform the second transposition.

D A V I N C I
3 1 7 4 6 2 5
-------------
I T A E H C A
T E S S E E I
R G S S S M

Again, we read off the ciphertext by the column and write down the text in groups of five:

The final cipher text: TEGCE MITRE SSAIH ESASS

To decode the message we first use the 2nd columnar key and than the 1st columnar key. We write out the header and reconstruct the table with long and short rows. We fill in the code column by column in the order of the key.

Although I would not advice this method to encrypt an encyclopedia (unless you expect to reach the age of 275), it can be used to secure a small amount of information you want to remember, using two passwords. If you want to play more with classic ciphers, check out the Cipher Classics program.

4 comments:

Anonymous said...

Dirk,

I've added a bit to Wikipedia about where the double transposition was used (and solved) in history here.

The most obvious drawback is that you'd need a secure way to generate the permutations. Choosing actual words or names as passwords would mean that a computer dictionary attack would recover the plaintext very rapidly.

Matt Crypto said...

Oops, that was from me, btw.

Dirk said...

Hi MAtt,

using a combination of 4 words would give 625E12 possibilities, for a language with an average of 5000 words. We have to consider the time it was used. These days, a dictionary attact is rather easy, but back then, two well selected permutations were a nightmare, especially on a small message.

Matt Crypto said...

Oh, certainly a dictionary attack wouldn't have been feasible when this was in actual use. I was commenting on its strength today; I think a ciphertext-only attack on a short message would still be hard work, provided that the permutations were generated securely.