Double Transposition Cipher
May 29, 2009
For any given key and message length, the transposition will always visit the letters in the same order; for instance, with key COACH and a text of seventeen letters, the visit order will be 2 7 12 0 5 10 15 3 8 13 4 9 14 1 6 11 16. Make-next creates a function that closes over the key and text length to return the next position to be visited, returning -1 when the text is exhausted:
(define (make-next key text)
(let* ((klen (string-length key))
(tlen (string-length text))
(ks (make-key key))
(i tlen))
(lambda ()
(cond ((< (+ i klen) tlen)
(set! i (+ i klen)))
((pair? ks)
(set! i (car ks))
(set! ks (cdr ks)))
(else (set! i -1)))
i)))
Make-next uses make-key to convert a keyword like COACH into the list of column-starting positions (2 0 3 4 1), which is more useful than the manual key 2 5 1 3 4:
(define (make-key word)
(map cadr
(sort (lambda (a b) (char<? (car a) (car b)))
(zip (string->list word)
(range 0 (string-length word))))))
Then encryption and decryption use the function created by make-next to visit the letters in order; encryption collects the plaintext letters into a ciphertext list, and decryption sets the ciphertext letters in order into the appropriate plaintext positions:
(define (encrypt key text)
(let ((next (make-next key text)))
(let loop ((i (next)) (cipher '()))
(if (negative? i)
(list->string (reverse cipher))
(loop (next) (cons (string-ref text i) cipher))))))
(define (decrypt key cipher)
(let ((next (make-next key cipher))
(text (make-string (string-length cipher))))
(do ((i (next) (next))
(cipher (string->list cipher) (cdr cipher)))
((negative? i) text)
(string-set! text i (car cipher)))))
With keys COACH and STRIPE, double transposition of PROGRAMMINGPRAXIS looks like this:
> (encrypt "STRIPE" (encrypt "COACH" "PROGRAMMINGPRAXIS"))
"GNPAPARSRIMOIXMGR"
> (decrypt "COACH" (decrypt "STRIPE" "GNPAPARSRIMOIXMGR"))
"PROGRAMMINGPRAXIS"
Sort, zip and range are from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/W4i2kueL.
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.