4
$\begingroup$

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.

$\endgroup$
  • $\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 Shen Sep 21 '16 at 11:03
4
$\begingroup$

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:

  1. Test different key lengths, and look for a length where the letters in each column look like they might plausibly be consecutive.

  2. 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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.