Break the Double Columnar Transposition Challenge (Doppelwürfel)

#cryptology, #cryptography, #cryptanalysis

In this video, we break the famous double columnar transposition (in German "Doppelwürfel") challenge.

The double columnar cipher was one of the most secure hand ciphers used in the Second World War and in the Cold War. It is the columnar transposition performed twice.

The actual challenge was suggested by Otto Leiberich, former head of the BSI, in 1999 and then created by crypto author Klaus Schmeh in 2007.

There was no known solution for many years. Then, it was solved finally in 2013 by George Lasry.

We published a paper about the solution, together with Lasry, which you find here [1].

Also interesting: the blog [2] of Klaus Schmeh, who is the creator of the challenge. On his blog, you will find many interesting articles about cryptological topics.

You may download the latest version of CrypTool 2 from our website [3].

[1] Lasry, George, Nils Kopal, and Arno Wacker. "Solving the double transposition challenge with a divide-and-conquer approach." Cryptologia 38.3 (2014): 197-214.

[AlexeySilichenko]

8:10 (IDP):

2. Prepare an empty matrix B[i, j] and perform for each possible combination of ciphertext
columns i and j the following calculations:

(a) Compute the sum of log frequencies of all the bigrams created by juxtaposing column j
to the right side of column i. To normalize the result, divide this sum by the number of
rows. Store this value in the matrix cell B[i, j].

(b) Repeat this calculation for all possible starting positions of both i and j continuously
updating the matrix cell B[i, j] with the best (highest) value found.

3. As a result from the last operation we have a matrix B[i, j] with the best possible digraphic
values for all pairs of columns i and j. However, in a real transposition, each column (or key
element) can have only one right neighbor, as well as only one left neighbor. Therefore, in order
to further reduce the matrix perform the following operations iteratively:

(a) Select the column pair (i, j) from the matrix B[i, j] with the highest value.

(b) Mark j as the likely right neighbor of i, and i as the likely left neighbor of j. Furthermore,
mark all B[i, ∗] and B[∗, j] cells except B[i, j] as invalid.

(c) Repeat (a) and (b) with columns i which do not yet have a likely right neighbor and columns
j, which do not have yet a likely left neighbor, until all columns have been assigned both
a right and a left likely neighbor.

4. Sum all B[i, j] values of all pairs, considered as likely neighbors. We define this sum as the
value for IDP(K2) for the given key K2.

(c) "Solving the Double Transposition Challenge with a Divide and Conquer Approach" by George Lasry, Nils Kopal

[THS-um]

what if I apply double columnar transposition on an array of numbers instead of letters? the array of numbers could be one output of the cipher system.

[jonna]

Can you please explain what is the use of the Converter component?

[carldettlinger]

I have used column and double transpositions in CT2 but what about disrupted transpositions or Myszkowski? How about Amsco?