Double Columnar Transposition (Part 1)

Even in the 21st century, there still exists cipher methods that can be executed by pencil and paper and that are concurrently strong enough to resists the computational power of modern PCs quite well. One of those cipher systems is the Double Columnar Transposition Cipher (DCTC), or for the german speaking readers Der Doppelwürfel.

[Double Columnar Transposition Cipher]. The DCTC works as follows: Assume a plaintext $\mathcal{P} = n_1 n_2 ... n_k$. Pick two key words from an (e.g.) english dictionary or even better two short sentences: $\mathcal{K}_1$ and $\mathcal{K}_2$ of length $s_1$ and $s_2$ respectively. To encrypt a message, write the plaintext in a block (or matrix) layout with $s_1$ columns. Now sort the columns regarding the first keyword $\mathcal{K}_1$. E.g. using the plaintext THIS IS IMPORTANT and the first keyword DOUBLE:

$$ \begin{bmatrix}
\textbf{D} & \textbf{O} & \textbf{U} & \textbf{B} & \textbf{L} & \textbf{E} \\
- & - & - & - & - & - \\
\text{T} & \text{H} & \text{I} & \text{S} & \text{I} & \text{S} \\
\text{I} & \text{M} & \text{P} & \text{O} & \text{R} & \text{T}\\
\text{A} & \text{N} & \text{T} & & & \\
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
 \begin{bmatrix}
\textbf{B} & \textbf{D} & \textbf{E} & \textbf{L} & \textbf{O} & \textbf{U} \\
- & - & - & - & - & - \\
\text{S} & \text{T} & \text{S} & \text{I} & \text{H} & \text{I} \\
\text{O} & \text{I} & \text{T} & \text{R} & \text{M} & \text{P}\\
 & \text{A} & & & \text{N} & \text{T}\\
\end{bmatrix}  \stackrel{\text{read column by column}}{\rightarrow}$$
(The keyword above the text is only displayed for clarity reasons.) After sorting, read the text column by column from the block, thereby skipping the empty places in the last row. In this order write the text again in block-size form, this time with $s_2$ columns. Again, sort the block according to the second keyword $\mathcal{K}_2$, here CUBE:
 $$ \begin{bmatrix}
\textbf{C} & \textbf{U} & \textbf{B} & \textbf{E} \\
- & - & - & - \\
\text{S} & \text{O} & \text{T} & \text{I} \\
\text{A} & \text{S} & \text{T} & \text{I} \\
\text{R} & \text{H} & \text{M} & \text{N} \\
\text{I} & \text{P} & \text{T} &
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
\begin{bmatrix}
\textbf{B} & \textbf{C} & \textbf{E} & \textbf{U} \\
- & - & - & - \\
\text{T} & \text{S} & \text{I} & \text{O} \\
\text{T} & \text{A} & \text{I} & \text{S} \\
\text{M} & \text{R} & \text{N} & \text{H} \\
\text{T} & \text{I} & & \text{P}
\end{bmatrix}\stackrel{\text{read column by column}}{\rightarrow}$$
Read the text once again column by column from the block, which is the resulting ciphertex:

 TTMTS ARIII NOSHP

The decryption step is more or less the same procedure backwards, but with one additional step. The decrypter must be consider the empty places in the last row when writing the ciphertext in the block layout. Since he knows the ciphertext length and the keyword ($\mathcal{K}_2$ for the first block) he can determine which places have to be skipped.

$$ \begin{bmatrix}
\textbf{C} & \textbf{U} & \textbf{B} & \textbf{E} \\
- & - & - & - \\
\text{*} & \text{*} & \text{*} & \text{*} \\
\text{*} & \text{*} & \text{*} & \text{*} \\
\text{*} & \text{*} & \text{*} & \text{*} \\
\text{*} & \text{*} & \text{*} &\\
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
\begin{bmatrix}
\textbf{B} & \textbf{C} & \textbf{E} & \textbf{U} \\
- & - & - & - \\
\text{*} & \text{*} & \text{*} & \text{*} \\
\text{*} & \text{*} & \text{*} & \text{*} \\
\text{*} & \text{*} & \text{*} & \text{*} \\
\text{*} & \text{*} & & \text{*}
\end{bmatrix}$$So he knows that he must skip the place at 4th row / 3rd column. Now, he fills the matrix column by column and brings the keyword in the correct order.
 $$\begin{bmatrix}
\textbf{B} & \textbf{C} & \textbf{E} & \textbf{U} \\
- & - & - & - \\
\text{T} & \text{S} & \text{I} & \text{O} \\
\text{T} & \text{A} & \text{I} & \text{S} \\
\text{M} & \text{R} & \text{N} & \text{H} \\
\text{T} & \text{I} & & \text{P}
\end{bmatrix}
\stackrel{\text{restore word}} {\rightarrow}
\begin{bmatrix}
\textbf{C} & \textbf{U} & \textbf{B} & \textbf{E} \\
- & - & - & - \\
\text{S} & \text{O} & \text{T} & \text{I} \\
\text{A} & \text{S} & \text{T} & \text{I} \\
\text{R} & \text{H} & \text{M} & \text{N} \\
\text{I} & \text{P} & \text{T} &
\end{bmatrix}
\stackrel{\text{read row by row}}{\rightarrow}$$
Next, the same is done with the keyword $\mathcal{K}_1$.
$$ \begin{bmatrix}
\textbf{D} & \textbf{O} & \textbf{U} & \textbf{B} & \textbf{L} & \textbf{E} \\
- & - & - & - & - & - \\
\text{*} & \text{*} & \text{*} & \text{*} & \text{*} & \text{*} \\
\text{*} & \text{*} & \text{*} & \text{*} & \text{*} & \text{*}\\
\text{*} & \text{*} & \text{*} & & & \\
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
 \begin{bmatrix}
\textbf{B} & \textbf{D} & \textbf{E} & \textbf{L} & \textbf{O} & \textbf{U} \\
- & - & - & - & - & - \\
\text{*} & \text{*} & \text{*} & \text{*} & \text{*} & \text{*} \\
\text{*} & \text{*} & \text{*} & \text{*} & \text{*} & \text{*}\\
 & \text{*} & & & \text{*} & \text{*}\\
\end{bmatrix}$$
Three places have to be skipped. Next, the matrix is filled column by column.
$$ \begin{bmatrix}
\textbf{B} & \textbf{D} & \textbf{E} & \textbf{L} & \textbf{O} & \textbf{U} \\
- & - & - & - & - & - \\
\text{S} & \text{T} & \text{S} & \text{I} & \text{H} & \text{I} \\
\text{O} & \text{I} & \text{T} & \text{R} & \text{M} & \text{P}\\
 & \text{A} & & & \text{N} & \text{T}\\
\end{bmatrix} \stackrel{\text{restore word}} {\rightarrow}
 \begin{bmatrix}
\textbf{D} & \textbf{O} & \textbf{U} & \textbf{B} & \textbf{L} & \textbf{E} \\
- & - & - & - & - & - \\
\text{T} & \text{H} & \text{I} & \text{S} & \text{I} & \text{S} \\
\text{I} & \text{M} & \text{P} & \text{O} & \text{R} & \text{T}\\
\text{A} & \text{N} & \text{T} & & & \\
\end{bmatrix} \stackrel{\text{read row by row}}{\rightarrow}$$
After bringing the columns back in order of the keyword $\mathcal{K}_1$ the plaintext can be found after reading the matrix row by row.

The literature about the cryptanalysis of the DCTC is not that extensive. In most cases, like in the declassified documents of the NSA from 1934 (see books ISBN 0-89412-278-9 and 0-89412-069-7), special cases or known plaintext scenarios are discussed. I am not aware of any rigorous proof of complexity for the DCTC. Sure, a rough calculation of the bruteforce complexity can be given quite easily:

Assume the keylength $s_1$ and $s_2$ are known (this is not an unusual assumption, since the keylength are even recommend only to be in range around $20$)

1. Guess which of the positions in the last row of the first decryption matrix are empty. So $\binom{s_2}{k_2}$ different columns can be picked.
2. Since one knows that all longer columns (that ones which no empty place in the last row) are have to be on the left side after reordering and all shorter columns have to be on the right side, one only has to consider the permutations of these two partitions. Hence $(s_2-k_2)!$ for the longer columns and $k_2!$ for the short columns. 
3. So in total for the first decryption matrix one has $\binom{s_2}{k_2}k_2!(s_2-k_2)!$.
4. This is repeated for the seconds decryption matrix as well $\binom{s_1}{k_1}k_1!(s_1-k_1)!$.
5. This yields in total $\binom{s_1}{k_1}k_1!(s_1-k_1)!\binom{s_2}{k_2}k_2!(s_2-k_2)! = s_1!s_2!$.

Setting for example $s_1 = s_2 = 20$, one has complexity of a round $2^{122}$.

To demonstrate the hardness of the DCTC even in nowadays, the author Klaus Schmeh published 2008 a crypto-puzzle around the DCTC, with a parameter setup that was recommend by Otto Leiberich, the former president of the Federal Office of Information Security from Germany. It has not been solved since then, despite getting a quite well level of public attention.

As with many cipher systems, the DCTC has some weak setups that should not be used and some strong recommend setup to make the cryptanalysis the hardest.

First, i will present here a cryptanalysis for the ciphertext only case, but with the simplified setup that $$s_1 | k\;\;\text{and}\;\;\frac{ k } {s_1} = s_2 $$ whereof $k$ is the length of the plaintext. I will reduce the simplification step after step.

We assume that the plaintext has been translated into a integer representation, e.g., A $\rightarrow 1$, B $\rightarrow 2$ etc.. The lexicographical ordering according to the selected keyword can be represented via a Permutation matrix $\mathsf{P}$. The first matrix that contains the plaintext (in integers form) is denoted as $\mathsf{K}$. So we can write
$$ \mathsf{K} \cdot \mathsf{P_1} $$ for the first ordering step using the first permutation matrix $\mathsf{P}_1$. Since one needs to write column by column and has to fill row by row, this is equal to a matrix transposition. Hence $$ \left(\mathsf{K} \cdot \mathsf{P_1}\right)^{t} = \mathsf{P}^t_1 \cdot \mathsf{K}^t$$ Because of our requirement $\frac{ k } {s_1} = s_2$, the dimensions fit together and also because there are not empty cells in the last row, we can directly apply the second transposition matrix $$ \left(\mathsf{K} \cdot \mathsf{P_1}\right)^{t}\cdot \mathsf{P}_2 = \mathsf{P}^t_1 \cdot \mathsf{K}^t\cdot \mathsf{P}_2 =\mathsf{C}$$
The ciphertext is now located column by column in the matrix $\mathsf{C}$. Since permutation matrices are always invertible, we have
$$ (Eq.1)\;\;\mathsf{K} = \left(\mathsf{P}_1^{-t}\cdot \mathsf{C}\cdot \mathsf{P}^{-1}_2\right)^t = \mathsf{P}_2^{-t}\cdot \mathsf{C}^{t}\cdot \mathsf{P}_1^{-1}$$ As one could see from Eq. 1, there are no mathematical restriction. That means, $\mathsf{P}_1$ and $\mathsf{P}_2$ could indeed be any permutations matrix possible. So given only the ciphertext, does not reduce the possible key space. To proceed, one has to involve some kind of language detection or word guessing.

Remark: I am aware that in this special case the (at least practical) cryptanalysis would be rather simple. Each column in the ciphertext matrix represents a complete row of the ciphertext matrix. The approach would be to look for a potential word that could be formed with the letters. Transpose the matrix and rearrange the columns to form that word and test if also the other rows reassemble fractions of english text. However, the ideas and descriptions from this setup can be carried over and can be adapted when we relax the requirements.

# A direct approach #

First, let me say something about a more direct approach. Suppose that $\alpha\%$ of characters of a text are enough to reconstruct the entire text.  Let us simply guess $d$ columns from $\mathsf{P}_1$ and $\mathsf{P}_2$, hence there are $\prod^{d-1}_{j=0}(s_1-j) \prod^{d-1}_{j=0}(s_2-j) \leq (s_1s_2)^d$ possibilities to choose a position for the $1$ in those $d$ columns each. Applying those partial permutation matrices to Eq 1. reveal $d^2$ plaintext characters in $\mathsf{K}$. These are exactly the cross-sections from the selected $d$ rows from $\mathsf{P}_2$ and the columns from $\mathsf{P}_1$.

Therewith those $d^2$ character make up $\alpha\%$ of the plaintext it is $d = \sqrt{\alpha k / 100}$. So the possibilities are bounded by $$(s_1s_2)^d = (s_1s_2)^\sqrt{\alpha k / 100} = (s_1s_2)^{\sqrt{\alpha k} / 10}$$
Note, that since there is no hard fact to rule a possibility out, we assume that some kind of language detection mechanism can determine which solutions is correct.

# Guessing a word #

We make use of the following Lemma. (A standard matrix $\mathsf{E}_{i,j}$ is the all zero matrix, that only has one $1$ entry at $(i,j)$.)

Lemma 1. Given the two standard matrices $\mathsf{E}_{i,j}$ and $\mathsf{E}_{u,v}$ as well as the matrix equation $ \mathsf{A}\cdot \mathsf{E}_{i,j}\cdot \mathsf{B} = \mathsf{E}_{u,v}$ then the matrices $\mathsf{A}$ and $\mathsf{B}$ are uniquely determined by the standard matrices $\mathsf{A} = \mathsf{E}_{u,i}$ and $\mathsf{B} = \mathsf{E}_{j,v}$.

Proof. We denote with $\mathsf{E}_{*,j}$ and $\mathsf{E}_{i,*}$ those standard matrices, that have a $1$ in the $j$-th column and in the $i$-th row respectively. Since associativity holds, we first take the product $\mathsf{A} \mathsf{E}_{ij}$. Therewith the $1$ from $\mathsf{E}_{ij}$ is preserved, $\mathsf{A}$ has to have a $1$ in the $i$-th column, i.e. $\mathsf{A} = \mathsf{E}_{*i}$ and hence $\mathsf{E}_{*i}\mathsf{E}_{ij} = \mathsf{E}_{*j}$. Multiplication with $\mathsf{B}$, $\mathsf{E}_{*j} \mathsf{B} = \mathsf{E}_{uv}$ allows to deduce, that $\mathsf{B}$ has to have a $1$ in the $j$-th row, so $\mathsf{B}= \mathsf{E}_{j*}$. This means, one gets the Product $\mathsf{E}_{*j} \mathsf{E}_{j*} = \mathsf{E}_{uv}$ which allows to conclude, that $$ \mathsf{E}_{*j} \mathsf{E}_{j*} = \mathsf{E}_{uj} \mathsf{E}_{jv} = \mathsf{E}_{uv} $$ and therewith $\mathsf{B} = \mathsf{E}_{jv}$.  The matrix $\mathsf{A}$ can be derived from $$ \mathsf{A}\mathsf{E}_{ij} = \mathsf{E}_{*i}\mathsf{E}_{ij} = \mathsf{E}_{uj} $$ hence $\mathsf{A} = \mathsf{E}_{ui}$ as claimed.
Q.e.d.

The Lemma 1 explains, that if we pick a element from the ciphertext matrix $\mathsf{C}$ and guess its position in the plaintext matrix $\mathsf{K}$, this determines a unique $1$-entry in $\mathsf{P}_1$ as well as in $\mathsf{P}_2$.

Now, instead of guessing $d$ entries in the permutation matrices, we take a look at the ciphertext and guess a common word that can be formed and is mostly likely to be part of the plaintext (e.g. "THE", "AND", etc.), the longer the better it is.

Two points have to be considered here:

1. One has to test the guessed word $W$ at all $k-|W|+1$ positions in the ciphertext.
2. There are probably several occurences of each letter that make up the word $W$. Thus one has to test each such combination. 

Regarding point 2., we assume that a word $W$ could be build in $F(W)$ ways. For the word $W$ of length $|W| = d$, we again get $d$ entries in each permutation matrices $\mathsf{P}_1$ and $\mathsf{P}_2$. Hence, we get again $d^2$ plaintext characters.

As explained above $d = \sqrt{\alpha k / 100}$ would be sufficient. So one needs to test $\left(k-\sqrt{\alpha k / 100}+1\right)F(W)$. This formula stands somewhat in a vacuum and its hard to see what it means in practical. 

Assume the parameters from K. Schmeh crypto puzzle, then $k = 599$ and a hint is given that the keylengths are co-prime integers both between $20$ and $25$. That are not many possibilities. E.g., we set $s_1 = 21$ and $s_2 = 23$. For $\alpha = 40\%$ we have $d = 15.48$. That means, the word (or the partial sentence) has to be $16$ characters long. This could be out of scope for a reasonable guess, but could also be in reach if someone knows the topic. Note again, that i assume a language detector behind the scene that is able to recognise a certain language with only $40\%$ of characters available.

If we relax our requirement, some things get worse but suprisingly also some things get better.