D'Agapeyeff cipher continues to thwart me

Banging one's head against the wall probably isn't the way most people would choose to spend their free time. But here I am again, giving the D'Agapeyeff cipher another go-round.

This time I took a slightly different path, but revisited used the same ground rules:

1. Remove the 6s, 7s, 8s, 9s, and 0s.
2. Assume a 14x14 square was used for diffusion

From there, you can assume there are only 48 possible routes to fill a 14x14 square:

1. Horizontally
2. Horizontally alternating row directions
3. Vertically
4. Vertically alternating column directions
5. Diagonally up
6. Diagonally up, but alternating directions
7. Diagonally down
8. Diagonally down, but alternating directions
9. Spiral in, clockwise
10. Spiral in, counter-clockwise
11. Spiral out, clockwise
12. Spiral out, counter-clockwise

You can then repeat each of those patterns from the four corners of the 14x14 square.

In terms of encryption, you may write the polybius square digits into the 14x14 square in any one of the 48 patterns, and remove the digits from any of the other 47 patterns. This yields 2,256 possible transpositions. They're not all unique due to some symmetry, but you may use any of the 2,256.

The reason I first devised this test is due to the mysterious "04" at the middle of the ciphertext. If that zero was marking the four as the end of the original ciphertext, you could fill a 14x14 square in some spiral pattern, and then remove the digits in one of a couple diagonal patterns to leave the 4 digit at the exact middle of the ciphertext. My curiosity was piqued so I set about writing a program to solve a cipher such as this.

After solving some test ciphers, I threw the D'Agapeyeff cipher into the program with much pomp and circumstance, but once again came up empty. Nothing scored so much as a 1.3 (0.05) for IC. Shucks.

Where does this leave me? I don't know. I've given this cipher all it can handle, but it continues to hold tight to it's secret.

I may finally start looking into the 28x7 or 7x28 shape and repeat some of the work I've done on the 14x14 square. Someday I'll win, but for now I will rest.

D'Agapeyeff Cipher - ADFGX Postscript

I left my blog in limbo while my solver was running for approximately 14 or 15 months.  Sure, it seems crazy, but I wasn't willing to give up on the idea that the D'Agapeyeff cipher was a 98 character Polybius square encryption with a 14 column transposition key.  To fully check the likely keyspace took a lot of computer cycles.

Once I had checked all the phi values from the max (600) down to 502, I had a decision to make. I could either let the program run, or I could re-evaluate the hypothesis and possibly concede there might be another path. Each phi value below 502 has somewhere in the neighborhood of 4,000 to 8,000 key variants (plus the 5,040 column pairing permutations to consider). I deemed it extremely unlikely that D'Agapeyeff's plaintext was written with some many distinct digraphs that the phi value would drop that low - even for 98 characters of plaintext.

I believe in another blog post I talked about 75% of all 98 character plaintexts have a phi value between 540 and 660. I took this fact, and combined it with the facts that:

• His other sample ciphers had plaintexts with phi/IC values greater than that of the expected value for texts of those lengths.
• Most plaintexts with phi values in the expected range (540-660) will most likely have a max phi value greater than 600.

It's for both these reasons I ended my standard ADFGX attack and went back to the drawing board.

To fully beat the dead horse, I still believe the 6, 7, 8, 9, and 0 digits are nulls added after the message was enciphered to thwart cryptanalysis  What I've now decided to consider is that D'Agapeyeff may have still used a 14x14 square, but did not use columnar transposition.

He certainly could have inscribed the 196 digits from the polybius square in a 14x14 matrix, either row-wise, column-wise, or in some other pattern such as left to right alternating directions, or in a clockwise/counterclockwise circular pattern. He then could have taken these digits out of the 14x14 matrix either row-wise, column-wise of by some other pattern. This is the path I'm going down next.

Until next time.