I am looking for an idea on how to decipher a columnar transposition cipher without knowing the key or the length of the key.
When I take the cipher text as input to my algorithm I will guess the length of the key to be the factors of the length of the cipher text.
I will take the first factor suppose the length was 20 letters so I will take 2*10
(2 rows and 10 columns). Now I want to arrange the cipher text in the columns and read it row wise to see if there is any word forming and match it with a dictionary if it is something sensible. If it matches the dictionary then it means it is in correct order or else I want to know how to make other combinations of the columns and read the string again row wise.
Please suggest another approach that is more efficient.
1
You have the correct general idea. But I want to point out that the message length doesn’t have to be an exact multiple of the row count, e.g.
A B C reordering A C B
D E ---------> D E
might become AD C BE. Accounting for this is rather difficult, as we don’t know where the shorter columns are. Assuming we are partitioning into three columns, we might get A DC BE, AD C BE or AD CB E. The situation gets worse for a larger number of columns. One solution might be to initially decrypt everything but the last row, so that we know the order of columns. The uncertain characters can then be distributed over the leading columns.
As the columns may be re-ordered, we need a way to determine the original order. Unfortunately, there are r! different combinations. This is trivial for a small number of columns, where brute-forcing all combinations is a viable strategy. Otherwise, we have to employ an heuristic that guides us through all combinations.
One suitable heuristic considers letter transitions. We can build such a table from sufficiently large example data. Given a letter a and a letter b, we can then estimate the probability that a is followed by b in a text. Between two columns, we ususally have multiple transitions, so we can multiply the probability of each pair. Doing this for all columns produces an index we can sort by, and examine the column transition with the highest probability first. Note: This is a rather gross abuse of statistics, but it works out in this simple case where the probabilities are only used to decide one transition.
For example, assume we have the ciphertext eleatytoaryf_s_do_hwre_l, and we are just going to assume we have four columns. This gives us:
1234
et_h
losw
ea_r
arde
tyo_
yf_l
It is irrelevant which column we pick first, so I am going to take #2. We now have probabilities for possible 2nd columns (frequency data obtained from an english dictionary file):
21 23 24
te t_ th
ol os ow
ae a_ ar
ra rd re
yt yo y_
fy f_ fl
| | | raw normalized
| | `-1.6713389025628 e-06 = 0.9985
| `----1.10726823199948e-09 = 0.0007
`-------1.39822078585934e-09 = 0.0008
Just looking at the exponent, we can see that the 2→4 transition is the most probable. We repeat this for the next transition:
241 243
the th_
owl ows
are ar_
rea red
y_t y_o
fly fl_
| | raw normalized
| `-1.9732647912631e-08 = 0.1122
`-----1.5611637229838e-07 = 0.8878
This declares the 4→1 transition most probable. Now only one column is left, so we get the transitions 2→4→1→3, which produces the cleartext the_owls_are_ready_to_fly. This looks like it is English, so we can stop here. If this weren’t the case, we would backtrack to the last decision point, which was the 4→? transition. If choosing 4→3 had produced gibberish as well, backtracking to the previous decision point would have us examine 2→1, and then decide 1→?.
This heuristic may be optimized further. The problem can be expressed in graph theory as lazily sorting all paths through all vertices by their total weight in a directed, weighted graph where the vertices are columns, and the edges are transition probabilities, and the edge weights combine multiplicative. For calculating the transition probability we have to normalize the probabilities so that the weights of all outgoing edges add to 1.
1