D'Agapeyeff Cipher (Part 2) - Brainstorming

I don't know why, but in the last days I used my spare time to think about the good old D'Agapeyeff Cipher. As a reminder, below you see the actual ciphertext like it is presented in his book:

    75628 28591 62916 48164 91748 58464 74748 28483 81638 18174
    74826 26475 83828 49175 74658 37575 75936 36565 81638 17585
    75756 46282 92857 46382 75748 38165 81848 56485 64858 56382
    72628 36281 81728 16463 75828 16483 63828 58163 63630 47481
    91918 46385 84656 48565 62946 26285 91859 17491 72756 46575
    71658 36264 74818 28462 82649 18193 65626 48484 91838 57491
    81657 27483 83858 28364 62726 26562 83759 27263 82827 27283
    82858 47582 81837 28462 82837 58164 75748 58162 92000

Remark: In the first post, i wrote that the puzzle only appeared in the 1939 version of the book but meanwhile i got new information. The puzzle is still contained in the reprinted version from 1949. The first version that comes without the puzzle is the version that was published in 1952. Note that the puzzle was not altered in any way in the 1949 reprint. This can be seen as a clue, that D'Agapeyeff still believes that the puzzle itself was correct (e.g., not printed in a erroneous way).

Is it a dictionary code? - At least not directly

In short, a dictionary code is a code which replaces whole words of a text with 'coordinates' where the word appears in a book on which the two parties previously agreed upon. For example, to encrypt the word 'Hello', search for the word somewhere in the previously chosen key-book. Suppose it appears on page $23$, line $17$, word $8$, then the first ciphertext element would be the integer $23178$. Some rules must be applied if a leading zero can cause ambiguity.

The question is: Which book could D'Agapeyeff have used?

In my opinion, there is only one canonical choice for this - He used his book itself as the key.Why should he choose another book the reader might not possess? The book the reader just holds in his hand (there is are no PDFs in $1939$ ;)) when he reads the puzzle, is also the key. And here comes another argument for this: The version from $1949$ which also contained the puzzle was a re-print. So perhaps no additional material or page-shifting was done. I have not checked it, but perhaps in the $1952$ version the page numbers changed due to editorial changes and that makes a deciphering definitely impossible. Also if D'Agapeyeff forgot some details, he probably remembered his chosen method and hence knew that it was time the remove the cipher, since the reader would not have the correct book(=key) at hand anymore.

The arguments above may sound reasonable, but the non-random decimal representation of the ciphertext in its given form suggests that it is not a dictionary code. Every odd digit comes from the set {6, 7, 8, 9, 0} (except the trailing zeros), and every even digit comes from the set {1, 2, 3, 4, 5}. One way to salvage this approach would be if D'Agapeyeff had encrypted the dictionary code again using an encryption method that would explain the oddity. He also mentioned in his book that encrypting a dictionary code again is an effective way to increase secrecy.

Personally, i am not a big fan of this approach, because all the clues regarding a substitution + transposition cipher are too strong.

It we assume that each five digit block represents one word, than there are $3$ words which appear two times (colored in the picture above). These could be the three most common english words 'the', 'be' and 'to'. If you partition a five digit block into

\begin{equation} \underbrace{d_4d_3}_{page}\;\;\underbrace{d_2d_1}_{line}\;\; \underbrace{d_0}_{word}
\end{equation}

you have to explain, why the page numbers together with the line and word numbers have an index of coincidence which pretty much represent english language (see first blog post).

Substitution+Transposition again

In the meantime i got my own copy of D'Agapeyeffs book:

Figure 1 - My copy of the 1939 version

However, reading the book does not give any new information, besides supporting my believe that it is indeed a transposition and substitution cipher. Precisely, when he talks about deciphering a transposition system on page 151, he mentioned that the ciphertext

$$\text{EBYETT  TREAOS  HTOPPO  HDRKRI  ITTNON  TATUHI}$$

can be arranged as a square, which he writes as

\begin{array}{cccccc}  \text{E} & \text{T} & \text{H} & \text{H} & \text{I} & \text{T}\\  \text{B} & \text{R} & \text{T} & \text{D} & \text{T} & \text{A}\\  \text{Y} & \text{E} & \text{O} & \text{R} & \text{T} & \text{T}\\  \text{E} & \text{A} & \text{P} & \text{K} & \text{N} & \text{U}\\  \text{T} & \text{O} & \text{P} & \text{R} & \text{O} & \text{H}\\  \text{T} & \text{S} & \text{O} & \text{I} & \text{N} & \text{I} \end{array}

So he reads the square column wise to create the ciphertext, hence, i am even more sure that Representation 2 from the first blog post is the correct starting point.

In his book, D'Agapeyeff also uses the Polybius square on several pages in his book, but, if i am right, only once with figures and not characters. This is on page 127 where he talks about possibility to use figures in ciphers and not characters. As an example he gave an Polybius square of the form

\begin{array}{c|ccccc}
              & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} \\\hline  \text{1} &  &  &  &  & \\  \text{2} &  &  &  &  & \\  \text{3} &  &  &  &  & \\  \text{4} &  &  &  &  & \\  \text{5} &  &  &  &  & \end{array}

as it is common and not the unusual way to pick the leading digits from the set ${6,7,8,9,0}$. If this is really a perfect executed substitution and transposition cipher it maybe very difficult to decipher. Nevertheless, the following two approaches i tested so far are:

Approach 1.

Since (probably) two steps are involved, substitution and transposition, and the full execution of both steps maybe too computational expensive (at least for me), it would be helpful, if one step could be roughly estimated in a fast way. Typically, this is done by the means of a scoring function that expresses the probability that the next step is worthwhile to be executed or not. For my approach i used the vowel/constant ratio that appears in each of the $14$ rows of the ciphertext, when a substitution is guessed. The probability that a letter is vowel is roughly $38\%$, hence one would expect that in each row there will be around $5$ vowels.

I loaded an english dictionary and with each word i filled up a polybius square using it as the keyword as shown below:

\begin{array}{c|ccccc}               & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} \\\hline  \text{6} & \text{K} & \text{E}&  \text{Y}&  \text{W}& \text{O} \\  \text{7} & \text{R} & \text{D}&  \text{A}&  \text{B}& \text{C} \\  \text{8} & \text{F} & \text{G}&  \text{H}&  \text{I/J}& \text{L} \\  \text{9} & \text{M} & \text{N}&  \text{P}&  \text{Q}& \text{S} \\  \text{0} & \text{T} & \text{U}&  \text{V}&  \text{X}& \text{Z} \end{array}

This is fast and it scores a full english dictionary of $>$300K words in a matter of seconds. For a lot keywords, there are none, one or only two vowels in a row, which makes it very unlikely that the substituted ciphertext is the result of a columnar transposition. Although, after parsing three dictionaries, i did not find a single word that yields at least $5$ vowels in each row. If i set the bound to $4$, i found the following keywords:

1. BUTTONHOLD
2. CONIOTHYRIUM
3. LOCUTORSHIP
4. JURISDICTIONAL
5. CIRCUMSCRIPTION

I used CryptCrack and tried 'Complete Columnar Transposition' with the substituted ciphertext, but got no result so far. If i left out the last row of the ciphertext, which looks a little bit suspicious with all its rare figures, then the number of keywords increases to several hundred but less than thousand.

Approach 2.

In Representation $2$, the line line $4$ contains only $7$ unique integer pairs. $$ 85, 82, 82, 81, 82, 63, 81, 91, 91, 64, 84, 82, 82, 82 $$ Since we assume that the source alphabet is 25 characters long (i and j paired), there are $${25 \choose7} = 480700$$ possible subsets of $7$ characters. Each of this subsets can be used to substitute the $7$ characters in Line 4 of the ciphertext, however, there are also $7!$ possible ways to permute these characters among the integer pairs. So in total, there are $${25 \choose 7}\cdot 7! = \frac{25!}{18!} = 2.422.728.000$$ possible configurations. Generating all these sets and permutations as well as the substitution is not a big deal and is done in a matter of minutes. However, after the substitution you obviously have to do something useful, which tells you if the current substitution is good or bad. Using the vowel/constant ratio from approach 1 does not make sense, since only 7 characters are substituted. I tried a some kind of Hill Climbing and computed bigram scores, which slows down the whole computation a lot. However, i am not very pleased with this, since my Hill Climbing may not be perfect and maybe the correct solution does not score very well. And, as you probably guess, i have no result so far...