Double Transposition Cipher
May 29, 2009
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.
Programming Praxis 
Attempt in LISP :
(defun index-key (a-key) (loop for c across a-key for i = 0 then (1+ i) collect (list c i))) (defun extract-index (a-key) (loop for (c i) in (sort (index-key a-key) #'char-lessp :key #'car) collect i)) (defun enc-dec (enc-txt a-key &key (encrypt t)) (loop with new-str = (make-string (length enc-txt)) with str-pos = 0 for i in (extract-index a-key) do (loop for y from i below (length enc-txt) by (length a-key) when encrypt do (setf (char new-str str-pos) (char enc-txt y)) else do (setf (char new-str y) (char enc-txt str-pos)) end do (incf str-pos)) finally (return new-str))) (defun enc (txt key1 key2) (enc-dec (enc-dec txt key1) key2)) (defun dec (txt key1 key2) (enc-dec (enc-dec txt key1 :encrypt nil) key2 :encrypt nil)) (format t "~s ~%" (enc "PROGRAMMINGPRAXIS" "COACH" "STRIPE")) ;GNPAPARSRIMOIXMGR (format t "~s ~%" (dec "GNPAPARSRIMOIXMGR" "STRIPE" "COACH")) ;PROGRAMMINGPRAXISYours is right; mine is wrong. I got a different ciphertext because the sort function in the Standard Prelude is unstable, so it returned the wrong set of starting points for COACH. The fix is to either use a stable sort (as I did when developing the exercise on my home computer, where the system sort is stable) or to fix the less-than predicate so it never returns true for equal elements. I changed the predicate, and now point to a new version of the program at codepad.
[…] Praxis – Double Transposition Cipher By Remco Niemeijer Yesterday’s Programming Praxis problem is about the double transposition cypher. Our target is 34 lines (the […]
My Haskell solution (see http://bonsaicode.wordpress.com/2009/05/30/programming-praxis-double-transposition-cipher/ for a version with comments):
import Data.List import Data.List.Split import GHC.Exts zipSort :: Ord a => [a] -> [b] -> [b] zipSort ks = map snd . sortWith fst . zip ks sortCols :: Ord a => [a] -> [b] -> [[b]] sortCols k = zipSort k . transpose . chunk (length k) encrypt :: Ord a => [a] -> [b] -> [b] encrypt k = concat . sortCols k decrypt :: Ord a => [a] -> [b] -> [b] decrypt k c = concat . transpose . zipSort (zipSort k [0..]) $ splitPlaces (map length $ sortCols k c) c main :: IO () main = do print . encrypt "STRIPE" $ encrypt "COACH" "PROGRAMMINGPRAXIS" print . decrypt "COACH" $ decrypt "STRIPE" "GNPAPARSRIMOIXMGR"Had another look at it and removed 2 imports and 1 line of code:
import GHC.Exts zipSort :: Ord a => [a] -> [b] -> [b] zipSort ks = map snd . sortWith fst . zip ks unsort :: (Ord a) => [a] -> [b] -> [b] unsort ks xs = zipSort (zipSort ks [1..length xs]) xs encrypt :: Ord a => [a] -> [b] -> [b] encrypt key = zipSort (cycle $ zip key [0..]) decrypt :: Ord a => [a] -> [b] -> [b] decrypt key = unsort (cycle $ zip key [0..]) main :: IO () main = do print . encrypt "STRIPE" $ encrypt "COACH" "PROGRAMMINGPRAXIS" print . decrypt "COACH" $ decrypt "STRIPE" "GNPAPARSRIMOIXMGR"A shorter version
(defun index-key (a-key) (mapcar #'cadr (sort (loop for c across a-key count c into i collect (list c (1- i))) #'char-lessp :key #'car))) (defun enc-dec (str key &optional (enc t)) (loop with pos = -1 and nstr = (make-string (length str)) for i in (index-key key) do (loop for x from i below (length str) by (length key) do (if enc (setf (char nstr (incf pos)) (char str x)) (setf (char nstr x) (char str (incf pos))))) finally (return nstr))) (print (enc-dec (enc-dec "PROGRAMMINGPRAXIS" "COACH") "STRIPE")) (print (enc-dec (enc-dec "GNPAPARSRIMOIXMGR" "STRIPE" nil) "COACH" nil))Hi,
I study on the Double Transposition Cipher and it’s solution since about 10 years. Right from the beginning, I was studiing on the cryptanalysis of the Double Transposition Cipher. The reason was, because I wanted to write (and in 2001 I did write) my first own software implementation of the Double Transposition Cipher in VB6. Yesterday I finished my new version in VB9.
The task to write as little as possible lines of code is cool. But for the suitability considerations about the security of a concrete sourcecode implementation are also important. Maybe reflections on how to prevent possible cryptanalitical attacks are much more importent than the length of the sourcecode.
Here are some published books for those of you who are intersted in the cryptanalytic issue:
The first cryptanalysis on the Double Transposition Cipher came from Solomon Kullback. In 1934 he wrote his GENEREL SOLUTION FOR THE DOUBLE TRANSPOSITION CIPHER, which, originally classified secret, was first published by the Signal Intelligence Section, War Plans and Training Division, U.S. Army War Department. Over 60 years later (!) this book was declassified by the NSA and a copy was furnished to the NARA. As book it is published by Agean Park Press (ISBN 0-89412-278-9). For more than 60 years everybody thought the Double Transposition Cipher was safe. But for more than 60 years the U.S. Intelligence was able to read Double Transposition Ciphers, at least if certain weaknesses of this method (which can be fixed) were not taken into consideration.
Another cryptanalysis came from Wayne G. Barker. His research on a solution of the Double Transposition Cipher and even his conclusions were more intensive than the those from Solomon Kullback. Wayne G. Barker wrote a CRYPTANALYSIS OF THE DOUBLE TRANSPOSITION CIPHER – INCLUDES PROBLEMS AND COMPUTER PROGRAMS. The release date of the origin of his book is unknown. Anyway, former classified secret, in 1995 it was declassified by the NSA and a copy also furnished to the NARA. As book it is also published by Agean Park Press (ISBN: 0-89412-254-1).
Especially the book from Wayne G. Barker is a must for everyone who implements the Double Transposition Cipher into software. For example, he describes in detail that any Double Transposition Cipher can be expressed as a Single Transposition Cipher. And because of the known solution for a Single Transposition Cipher, which is quiet easy to realize, if a programmer doesn’t take this into consideration, his software produces ciphertexts that are weak and unsafe. This – and other weaknesses – of the Double Transposition Cipher can be avoided if they are taken into programmers considerations.
Another – very poor and simple – consideration: What is the difference between these two keys?
Key 1: E A S Y
Key 2: D E N T
The answer is: There is no difference! Numerical these two keys are the same:
Key 1: E – A – S – Y = 2 – 1 – 3 – 4
Key 2: D – E – N – T = 2 – 1 – 3 – 4
This is important, because the resulting ciphertext is no Double Transposition Cipher but a Single Transposition using the same key twice.
A very essential issue is the following. Wayne G. Barker describes in Chapter IX a method of A Solution Which Requires No Known Plaintext. The heart of this cryptanalytic approach is his rotating matrix. How can a cryptanalysis using this approach can be defended? Well, building a rotating matrix is only possible if the product of key1 times key2 is not a prime number. But if the product of Length-Key1 an Length-Key2 is a prime number, one of the two keys must be length 1, but that doesn’t make sense. But Wayne G. Barker himself describes the limitation of his approach: His approach only works, if the length of the plaintext-message is – not only slightly – longer than the product of the length of the two double transposition keys.
It is also helpful if the length of the plaintext message is a prime number. This makes sure that allways at least one column is shorter than the other columns, otherwise a cryptanalyst could use the possibility of columns of the same length for an attack.
To avoid attacks using multiple anagramming it is useful to fill the plaintext with characters that are less frequent in the language of the plaintext. Using frequency tables one can determine the language of the plaintext because a transposition only confuses the positions of the charakters in the resulting ciphertext. But if the frequency is neutralized a frequency analysis of the plaintext language and the approach of multiple anagramming won’t work.
There are a few other more or less importent issues wihich has to be and can be taken into consideration. Maybe I will continue in another post.
Martin Krüger, Germany
can anyone give the code for double transposition cipher in java?? If so then please do so… i need it…
can you help me to implement keyed transposition cipher for variable length text. suppose key is 3201 and plaintext is probhatgothereok. we have to make it cipher text and vice-versa.