I have been given a 77 character message for decryption, but no matter where I look all the Columnar Transposition scripts out there are all requiring of a key. I believe the number of columns to be 7, but I am looking for a code that output all permutations of those 7 columns so that I can use a dictionary attack to find the messages that have readable words in them and reduce the number of outputs to look through.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ You mean all permutations of the 7 column numbers? But that's a pure math problem, not crypto. Look in a library for a text book on algorithms in combinatorics for your coding. $\endgroup$– Mok-Kong ShenCommented Sep 21, 2016 at 11:03
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I wrote an answer to a related question earlier showing an example of how to break a columnar transposition cipher by hand. The basic steps are two-fold:
Test different key lengths, and look for a length where the letters in each column look like they might plausibly be consecutive.
Once you've picked a key length, shuffle the columns around until they start to line up into meaningful fragments of text.
In the linked example, these steps are made easier by knowing a distinctive word that appears in the plaintext, and specifically the fact that the ciphertext contains a single Q and a single U, which are almost guaranteed to be consecutive in English text, but the same general method can be used even in the absence of such clues.
It would probably be possible to automate this process using a stochastic optimization algorithm like randomized hill climbing: basically, pick a random initial ordering for the columns, calculate how similar the resulting plaintext looks to English (using $n$-gram frequency statistics), and then repeatedly try to move one or move consecutive columns around and see whether this makes the plaintext look more like English. If it does, make the change and keep trying to improve it further; if not, reject the change and repeat.
For 7 columns, just trying all the 7! = 5040 possible column orders would also be feasible for a computer, although the number grows rapidly as the number of columns increases. As noted, generating all possible permutations of the columns is a standard computations problem, for which several well known algorithms exist.
answered Sep 22, 2016 at 15:10
$\begingroup$
$\endgroup$
The common way to break transposition cipher is by studying the frequency of digrams combining the columns in different ways or anagraming and comparing it to typical frequencies for your language.
http://norvig.com/mayzner.html
The following document shows how to apply the method and automatizes it by generating a matrix of probabilities...
http://homepages.math.uic.edu/~leon/mcs425-s08/handouts/breaking_tranposition_cipher.pdf
If you also add trigrams you will improve the results.
