And Waiting . . .

Status Update:  925 key variants checked.  4,662,000 total keys checked.  20.5% complete.

3584 remaining key variants.  18,063,360 total keys remaining.  79.5% remaining.

Still Waiting for D'Agapeyeff

Today I calculated the percent of the likely key space I've checked to date.  I have checked:

564 Key Variants
2,842,560 Transposition Keys

The likely keyspace, as I've defined it, is any permutation of column pairings with a phi value over 500.

4509 Total Key Variants
22,725,360 Total Transposition Keys

Thus far I've checked only 12.51% of the likely key space.  It's slow going, but I hope to be rewarded for my patience.

Waiting for D'Agapeyeff

Waiting for a solution to present itself is both exciting and challenging.  I've never been accused of being patient, but in this endeavor it's my only choice.

This entire process reminds me quite a bit of the play Waiting for Godot.

D'Agapeyeff will not be here today, but . . .
he will surely be here tomorrow . . . right?

Another Short Update

Over the past month I've spent some time ensuring that I'll be able to see this theory through to completion.

That means two things.  The first is that I now I have a completely automated program that solves ADFGX ciphers and has been tested on known ciphertexts.  This program now only needs a list of key variants to check, which I've automated with another process.  For the D'Agapeyeff cipher I've chosen the top 4,509 key variants for testing which represent phi values 498 through 600.  As previously stated I've eliminated all keys from 538 through 600 and feel confident that those do not contain a solution for this cipher.

Testing now continues on phi values 536 down to 498.  This process will take several months.

Quick Update

I see that quite a few people stumble across this space on a given week, so I figured I'd give an update since it's been nearly a month since my last post.

As noted earlier, when treating the D'Agapeyeff cipher as a numerical version of ADFGX (treating the 6-0 digits as nulls) the max attainable phi value is 600 which is associated with an IC of 1.64 (6.3%).

From tests I've run, the fact that the IC tops somewhere below the value expected for English leads me to believe that if the D'Agapeyeff cipher is in ADFGX form, the plaintext has a lower IC much like the cipher D'Agapeyeff decoded from his friend in the cryptanalysis section of his book.

Thus far I've eliminated all key variants from 600 down to 538.  This represents 215 key variants and 1,083,600 total keys.  The program I'm working with allows me to input one key variant, and it then checks the 5,040 permutations of the 7 column pairings and scores the potential plaintext with log tetragraphs.  It's a slick program, but does require me to input keys.  If I make it down to a phi value of 520 with no plaintext the key distinct variants do get tougher to distinguish.  And by tougher I just mean time consuming.  I've not come up with a great programmatic way to sort through all the keys that fall into a given phi/IC and pick out just the unique column pairings.

That's all for now.

Dispatching The D'Agapeyeff Cipher

If the D'Agapeyeff Cipher is indeed a numerical version of the ADFGX cipher, then I now possess the ability to check the entire likely keyspace . . . and in under a lifetime . . . with help from a fellow crypto-enthusiast.

As I outlined in my last post, the beauty of a fractionated cipher like the ADFGX is that each permutation of the columns will produce a unique phi value (or IC if you'd rather talk in terms of a ratio).

As I pointed out in my last post, for any even length transposition key there are only:

N! / ((N/2)! + (N/2)!) unique ways to create a phi value.


14! / (7! + 7!) = 8.7 million ways to create a phi value for the D'Agapeyeff cipher when treated as a fractionated transposition.  I refer to each of these 8.7 million permutations as "key variants".  From each key variant I can obtain all 7! = 5040 permutations of the column pairings.

For instance, let's say this is the correct key: 4, 5, 9, 11, 0, 1, 7, 13, 8, 3, 2, 12, 6, 10 and generates a phi value of 574.

I don't need to find this exact key to find the solution, I just need to find one of the 5,040 variations of the same column pairings, say:  9, 11, 4, 5, 7, 13, 0, 1, 6, 10, 2, 12, 8, 3.  This also generates the same phi value because all the columns are pairing up the same to create the same "letters".  If I were to check all 5,040 permutations of this key, I'd eventually come across 4, 5, 9, 11, 0, 1, 7, 13, 8, 3, 2, 12, 6, 10 and through log tetragraph scoring arrive at the correct plaintext after hill-climbing the substitution key.

Of course, I don't know the phi value of the plaintext in question, but I do know that it should fall into some acceptable range for English.  While 634 is expected for English, the range actually spans from 480 to 780.  I took a random sample of many different books from Project Gutenberg and randomly pulled different 98 characters of text and tested their phi values.  As you can imagine, 75% of all the phi values fall between 540 and 660.

For the D'Agapeyeff cipher, only 0.001% of the 8.7 million key variants fall within the 540 to 660 range.  This represents 74 key variants.  If the D'Agapeyeff Cipher has a solution in this keyspace, I'll need only to check 74 * 5040 = 372,960 total keys to find the solution.  This is much better than 87,178,291,200.

And what if the D'Agapeyeff cipher has a phi value closer to 500?  There are 3,744 key variants with a phi value greater than or equal to 500.  This represents 18,869,760 total keys to be checked.  While this would take approximately 100 days to check each key in the solver, that's much better than 800 years.

Digging For D'Agapeyeff DNA

What is the biggest obstacle to solving a 14 column fractionated transposition with an underlying substitution?

The solution space.  It's not feasible to check and score the entire space.  Or is it?

Let's start with a smaller example before leaping into the ADFGX cipher.

There is a dance tonight, and you have to form dance partners from a group of 4 people.  Two men:  Bob and Tom.  Two women:  Jenny and Sara.

There are N! ways to make dance partners, or in this case 4! = 24.  However there are only (N! / ( (N/2)! + (N/2)!) ) = 6 ways to make unique pairs where the order matters.  Bob & Jenny, Tom & Sara.  If you flip the men and women:  Jenny & Bob, Sara & Tom.  If you change the dance partners:  Tom & Jenny, Bob & Sara.  And if you flip the men and women:  Jenny & Tom, Sara & Bob.  The other two unique pairs are pairing the men together and the women together, and flipping their order.

How does this apply to the ADFGX cipher and my theory surrounding the D'Agapeyeff cipher?  For that we'll need one more statistic.  Phi value.  With the ADFGX cipher, each permutation of the column order produces unique pairs of columns that come together to make one "letter".  Even when you don't know the underlying substitution, you can still calculate the Phi value for the ciphertext.

Consider a 14x14 completed filled transposition grid.  There are 196 characters total which will eventually pair together to form 98 plaintext alphabetic characters.  As I've stated previously here, the expected Phi value for 98 letters from English text is 634 (98 * 97 * 0.0667).

Although there are 14! ways to arrange the columns, there are only 14! / ( (14/2)! + (14/2)! ) = 8,648,640 unique ways to calculate a Phi value.  Going back to a smaller example:

1,2 and 3,4 = unique phi value, and will result in the correct plaintext in the substitution phase.
2,1 and 4,3 = same phi value and will in fact produce the same plaintext in the substitution phase.  All you've done is flip all the row and column coordinates from the polybius square.

3,4 and 1,2 = same phi value, but will not result in the correct plaintext during the substitution phase because the letters are not in the correct order.
4,3 and 2,1 = same phi value, but will also not result in the correct plaintext during the substitution phase because the letters are not in the correct order.

So you might be asking, what does this accomplish?  One, for an even numbered transposition key, completely filled rectangle the ADFGX cipher has two correct keys.  Secondly, if you have any permutation of the correct key, you need only try (N/2)! permutations in the substitution solving phase to yield the correct plaintext.  For the 4 column example, I need only try (4/2)! = 2 permutations of the best potential keys to find the solution and correct plaintext.

Back to identifying the best potential keys.  Here is where the Phi value is key.  It's basically like the DNA fingerprint for the correct plaintext.  If 634 is the Phi value you'd expect to see for a 98 character plaintext you'd need only check potential solutions within a certain proximity to that value.

Let's go back to the 14 column example and it's 8,648,640 unique Phi values.  If I generated 8,648,640 random permutations of the 14 columns and had perfect distribution, within that pile of Phi values, one would contain some permutation of the correct transposition key.  It would have all the correct column pairings but be in the wrong order.  I'd need to try all (N/2)! or 7! or 5,040 permutations of that key in a substitution solver to yield the correct plaintext.

Think of it this way, you are looking for a toothpick in a large pile of toothpicks, however there are 5,040 variations of each of the 8,648,640 toothpicks.  Randomly drawing, let's say 20,000,000 toothpicks of the pile should give you at least 1 or 2 of the 5,040 variations of the toothpick you are looking for.  And on top of it, only 0.002% of the toothpicks look like yours.

What I found on trial runs with a known plaintext is that only about 40 high phi values show up in those 8,648,640 phi values.  Thus far, in limited testing with different plaintexts and polybius squares the correct phi value for my plaintext has always shown up in the top 40 unqiue phi values.  Meaning I'd need only check 40 * 5040 = 201,600 possible transposition keys for mono-alphabetic substitution.

In my view this is far superior to starting with a hill-climber and trying to maximize a scoring function on 99.99998% of potential keys that never have a chance to yield a correct plaintext.

Since I've Got The Time

Genetic search algorithms and hill-climbers are all very serious business, so I thought I'd try out a couple of educated guesses on the transposition key for the D'Agapeyeff Cipher for fun.   Why?  Why not?  I've definitely got the time.  Sure it's a 1 : 87 billion guess, but it's EDUCATED! :)

I started with a few of my usual assumptions:

1.  Strip out the odd digits from the ciphertext (all the 5, 6, 7, 8, 9, and 0 digits)
2.  Write the ciphertext vertically into 14 columns (14x14 grid)
3.  Assume that "04" near the middle of the cipher text marks the last character in the cryptogram

That leaves us looking for a 14 character transposition key, where the last column of the original matrix is what I like to call C7 (Column 7 after transposition).

What do we know about Alexander D'Agapeyeff?  We know he was a cartographer, born in Russia, and lived (and died) in England.  We also know that he showed us an example of substitution + fractionated transposition in his Codes and Ciphers book:

A cartographer living in the UK you say?  I believe it.  Mr. D'Agapeyeff used MANCHEST(E)R as the keyword in his example.  As you can see, he removed the 2nd instance of "E" to give a resulting 9 columns for the transposition key width.

Let's assume for a moment that he's playing by the same rules with his challenge cipher.

We're looking for a key phrase with 14 unique letters.  Not exactly a simple task.

NOT EXACTLY A SIMPLE TASK.  There are 21 characters in that sentence, but only 14 unique.  But let's revisit the mind of a cartographer.  A man who made maps for a living.  No doubt his mind is littered with names of places.  Towns, villages, cities, countries, etc.

Let's also revisit one of the first assumptions:

"That leaves us looking for a 14 character transposition key, where the last column of the original matrix is what I like to call C7 (Column 7 after transposition)."

 Okay, so we need a key phrase where the last unique character is somewhere near the middle of the alphabet.  Why is that?

Remember when a key is finished being transposed, essentially what you have is:

MANCHESTR to ACEHMNRST

If we "know" (and I use that term loosely, remember this is just for fun) the last letter of the keyword alphabetizes to the 7th position there needs to be 6 letters preceding it and 7 following it in the alphabet.

ABCDEF     GHIJKLMNOPQRS     TUVWXYZ

We can rule out A-F being the last unique letter in the key phrase, as well as T-Z.  That leaves us with G-S as the possibilities.  But let's be realistic.  I highly doubt all of ABCDEF or TUVWXYZ are all used in the keyphrase.  We are likely looking for a key phrase where the last unique letter is IJKLMNOPQ.

So back to D'Agapeyeff's keyword of choice in his book.  MANCHEST(E)R.

MANCHESTER UNITED KINGDOM.  15 unique characters.  Probably not it (I tried)

But hey, there are a ton of cities in the UK for a map maker to draw from, and there are 8 unique letters just in "UNITED K(IN)G(D)OM".  Added bonus that M and O are the last unique letters provided that they both don't show up in the city name you choose.  Take for instance Liverpool.

LIVERPOOL, UNITED KINGDOM

LIVERPO(OL)UN(I)T(E)DK(IN)G(DO)M.  14 unique characters.  When alphabetized:

DEGIKLMNOPRTUV.  M is the last unique character and falls into the 7th spot when reordered for transposition.  Beautiful.  Cipher Solved!  Re-arrange the columns, pair up the digits to form the 2 digit numbers from the polybius square used for substitution and plug into my mono-alphabetic substitution solver
, and . . . . nope, garbage.  Coventry fit the bill as well, but no dice there either.

But hey, it wasn't hard to try with a spreadsheet setup to do all the leg work.  Realistically I checked the phi-test value (380 something) and it told me it wasn't English.

D'Agapeyeff Cipher: Searching For A Solution

It's been almost  two months since my last post on the D'Agapeyeff Cipher, and I guess you could say that I've moved from "interested in this cipher" to "actively looking for a solution". As far as I can tell, there aren't many in this category, but I am interested in discussing this cipher with other interested parties, so please feel free to contact me.

In my last post from November 24, 2010 I attempted to identify the "row-columns" and "column-columns" that exist from using a polybius square for the substitution phase of the encryption.

I did do some due diligence and check the frequency counts for each digit of a 7x28 matrix, but saw no compelling evidence to suggest this shape was used.

My focus then remains on the 14x14 transposition matrix. Once the columns are paired (un-fractionated?) there will be a 7x14 (98 character) simple substitution cipher remaining. The trick is first solving the the transposition encryption independently of the substitution.

Tiago Rodrigues does a great job summarizing this strategy on his D'Agapeyeff.com website.


Back to the 14 columns, and the transposition space:

C1	C2	C3	C4	C5	C6	C7	C8	C9	C10	C11	C12	C13	C14
5	4	4	3	5	4	3	4	2	5	5	3	2	2
2	4	5	5	4	5	5	1	2	3	2	3	3	4
2	4	3	5	3	5	2	1	5	2	4	5	2	2
5	2	2	1	2	3	1	1	1	4	4	2	2	2
1	4	4	3	5	2	4	4	5	4	4	3	2	3
2	3	1	1	4	2	3	3	1	1	1	4	2	5
1	1	5	5	3	2	3	5	4	2	3	2	3	1
4	3	4	5	1	3	2	4	1	4	5	2	2	4
1	1	5	5	5	2	5	5	2	2	4	2	5	5
4	1	3	5	1	1	1	4	5	2	1	5	4	4
1	4	5	4	4	1	3	5	4	4	1	2	5	5
4	4	5	2	5	2	3	5	5	1	5	3	2	1
5	2	5	2	4	1	3	2	5	1	2	5	1	2
4	2	3	2	5	4	4	4	1	3	4	2	3	2

I surmised that columns C3, C7, C12, and C13 were likely to be "row-columns" while C1, C8, C11, and C14 were likely to be "column-columns" based on differing frequency counts for each of the 5 ciphertext characters.  The remaining six columns were sorted into row-columns or column-columns based on their frequency distribution.

Another member of the D'Agapeyeff cipher Yahoo! forum continued with some analysis of his own based on my assumptions to date.  That analysis is located here.  The outcome is similar to my findings with the caveat that C4 and C10 don't seem to favor being a row or a column.

Additionally this analysis output the largest Phi values possible - where 584 is the maximum value and is attained when the pairs are:

C1 - C6
C2 - C12
C5 - C7
C8 - C14
C9 - C13
C10 - C4
C11 - C3

If you recall, 634 is the expected Phi value for English text where N=98.  584, as well as several other sets of column pairings fall within an acceptable range, however no value of Phi(o) exceeds 634.

Assume for a moment that these are the correct column pairings, what remains is a 7! transposition which when in the correct order will leave a very simple substitution cipher.

Perhaps we're making headway against this as yet unsolved cipher.

Identifying Odd & Even Numbered Columns: D'Agapeyeff Cipher

In the last post I identified the mostly likely columns to have occupied even numbered positions in the original matrix:  C3, C7, C12, and C13.  I'm going to isolate these columns for purposes of this post.

As I referenced in a previous post, Friedman outlined a general solution for solving the ADFG(V)X cipher that relied on extrapolating data from cryptograms in the same key.  I'm going to use that same technique/assumption to try and tease out which three columns also belong in the same family.

If all four of these columns were even numbered in the original matrix, they should begin to show us a pattern of what the other even numbered columns look like by way of frequency counts.

  
If our assumption is correct, we can see a pattern emerging here.  The other even numbered columns should show few instances of 1 or 4.  Let's check the original matrix.  I've added counts for the other cipher numbers.

I want to first check the columns that have the next highest amounts of 3s.  C2, C4, C5, C6 and C10.

Of those five columns, one seems to fit the profile exactly:  C4.  It has only three instances of ciphertext 1 and ciphertext 4, while at the same time has six instances of ciphertext 2 and five instances of ciphertext 5.

The next most likely suspects are C6 and C14.  Not only do they have the fewest ciphertext 1s and ciphertext 4s (five each), they both have the next highest counts of ciphertext 2s (five each).

At this point, I feel comfortable moving forward to try and reconstruct the original pairs of columns.  But I'm a realist, I've only taken the possible transpositions from 14! or 87,178,291,200 down to 7! * 7! or 25,401,600.  So don't worry, I'm still daunted.

Back At It: D'Agapeyeff Cipher

To recap my assumptions before we dive in:

1.  The D'Agapeyeff Cipher consists of numbers 1-5 derived from a polybius square, numbers 6-9 which are nulls to disguise the ciphertext, and the number zero used as a termination point and to pad out the cipher.

 "The cipher is of course easily made out, but if every third, fourth, or fifth letter, as may be previously arranged, is a dummy inserted after a message has been put into cipher, it is then extremely difficult to decipher unless you are in the secret."

2.  The D'Agapeyeff Cipher can be written into a 14 x 14 square matrix.

3.  Phi tests on the cipher text as pairs of numbers running column-wise, row-wise, or pairing digits before and after the zero near the middle fail for mono-alphabetic substitution.  Therefore, columnar-transposition must be in play.

4.  Once removing the nulls from the ciphertext, the remaining digits should be placed into columns of 14 digits:

5.  What remains is a substitution followed by fractionated transposition.


There are the assumptions, and now for a little preliminary analysis on the digits to set the table:

Count of 1s     33
Count of 2s     46
Count of 3s     29
Count of 4s     43
Count of 5s     45

One more assumption we'll need to make is that the polybius square was keyed with a keyword and that the most infrequently used letters fell into a row together (example below):

In this case, "VWXYZ" fall into a row together and their frequencies in the English language would mean two things for our impending analysis.  First of which is that 5, in this example above, would be the least represented number in the ciphertext.  Second, 5 would be more likely to appear as an even numbered column rather than an odd numbered column before the columnar transposition occurred.

Using this information and applying it to our cipher text, it would appear that ciphertext 3 represents this row coordinate of these infrequently used letters as it only appears 29 times.  Based on the frequency count for each digit, we may be looking at a polybius square that looks something like this:

It's helpful to disassociate the numerical order that these figures represent normally.

Let's take a look again at our ciphertext.  I've added column headers for referencing the columns and shaded all instances of 3.

Since it's likely that 3 was used more often than not as a second number in a pair rather than a first we should be able to identify which columns were likely odd numbered columns in the original matrix (the first number in a pair) and which columns were likely even numbered columns in the original matrix (the second number in the pair).


There are four columns that contain more instances of 3 than most:  C7, C12, C3, and C13.  Interestingly enough the column containing the digit 4 that was previous attached to zero (04) seems to slot in as an even numbered column from the original matrix.  My hypothesis is that "04" was used to signify the last column in the original matrix.

There are five columns that contain zero or one instances of 3.  These columns are the most probable to be odd numbered columns from the original matrix.

To be continued . . . .

Is The D'Agapeyeff Cipher The ADFGX Cipher?

As a continuation of my previous post, I decided to break the D'Agapeyeff cipher into two smaller 7x7 squares.

To achieve this meant pairing up the digits in some fashion.  In one test used the "04" spot in the original ciphertext to mark the break point for the first 49 pairs and second 49 pairs.

In the second test, I used the "04" as the stopping point for the first digit in the pairs and all the numbers after the "04" as the second digit.

As mentioned in that post, I did remove all the 6-9 digits and the zeros before pairing up the remaining 196 digits.

My assumption was that if it was enciphered in this manner the same polybius square would have been used as there would be no need to complete two squares.  When comparing the frequencies of the pairs of numbers I didn't see enough commonalities between the two sets of 49 pairs to continue pursuing this method.

One example would be that in one group of 49 pairs the most frequent number was 22, but 22 wasn't represented at all in the other 49 pairs.

This brought me back to the drawing board, and I went back to review D'Agapeyeff's section on substitution plus transposition and my corresponding notes, which read:

I wonder if he understood how complex this concept is when introducing fractionated letters during the transposition step?

Look again at his example from the book:

This brings me back to one of my original hypotheses, although I was hoping it not to be this complex.  A completed filled 14x14 square with fractionated substitution.  To put it very simply, we'd be looking at the ADFGX cipher or as it became after the polybius square was expanded to accommodate numeric characters, the ADFGVX cipher.  This cipher was employed by the German military during World War I.

If you've read Friedman's Military Cryptanalysis, Part IV, Transposition and Fractionating Systems then you may recall there a couple different ways to solve the ADFGX cipher.  During the war they relied on high volumes of traffic and special circumstances such as messages with the same beginning, same ending, or completely filled rectangles.  One thing remains constant with all those special circumstance solutions:   high volume.

We have only one cryptogram, but we do have a couple things working for us.

1. There is a completely filled rectangle.  196 factors into 4x49, 7x28, or 14x14
2. If we assume the 14x14 square was used, we have an even number of columns which also reduces the cryptanalytic work

Let's consider the steps.  The 98 character plaintext was converted to digits via a polybius square resulting in pairs of numbers for each letter.  Consider the plaintext:

The bridge is out on the southeast road.  Use the bridge on the road north of the city for attack.  Hold position two day more.

The intermediate text was then inscribed into a 14x14 square horizontally as shown in D'Agapeyeff's example above.  A keyword/phrase is inscribed in the column headers for transposition.

Transposition is then completed via alphabetizing the columns:

The final ciphertext can be written out be reading column-wise (vertically) starting with the first column.  Nulls may be inserted every other character to re-create the appearance of the D'Agapeyeff cipher.

What does this mean in terms of attack strategies for the D'Agapeyeff cipher?  If we can assume the cipher was written on a 14x14 square we can assume there are 7 columns which represent the row coordinates from the polybius square and 7 columns which represent the column coordinates from the polybius square.

Unfortunately, we don't have additional ciphers to draw upon, so if this is the method by which the cipher was constructed it will be tough to crack.  Furthermore, if D'Agapeyeff's polybius square didn't have the low frequency letters "VWXYZ" in a row together as in my example the cipher becomes impervious to attack fairly quickly.

I've done some initial calculations assuming a 14x14 transposition rectangle (square) and there is evidence to suggest that VWXYZ or some combination of low frequency letters may have ended up in the third row, or D'Agapyeff may have changed the order of the row/column coordinates from the traditional 12345 to something like 34512.  I'll go into more details after further testing.

D'Agapeyeff Cipher As Two 7x7 Squares

Picking up where I left off last time, I want to continue testing the D'Agapeyeff cipher as a combination substitution-transposition cipher with nulls added to the final ciphertext.


As stated in the previous post, removing all the 6s, 7s, 8s, 9s and the zeros would leave 196 numbers or 98 number pairs.

Before:

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

After:

    52 251 21 414 14 544 44 243 13 114
    42 245 32 415 45 355 53 355 13 155
    55 422 25 432 54 315 14 545 45 532
    22 321 12 143 52 143 32 513 33 441
    11 435 45 455 24 225 15 141 25 455
    15 324 41 242 24 113 52 444 13 541
    15 243 35 234 22 252 35 223 22 223
    25 452 13 242 23 514 54 512 2

The question now becomes, how were these numbers written prior becoming the final ciphertext?  And why was there a zero near the middle?

Some ideas:

1. The numbers are paired moving left to right, top to bottom (first pair 52).  The zero would mark the 49th pair, splitting the ciphertext into two sets of 49 pairs.  Or possibly two 7x7 squares.
2. The numbers are paired using the first number (5) and the first number after the middle zero, the 99th overall number (4).  This would yield 98 total number pairs.
3. The numbers were no longer paired when placed into 14x14 transposition table or two 7x14 tables.  They were fractionated much like the example on pg. 124-125 of the original D'Agapeyeff book.  Shown below.

The thing that steers me away from the use of a 14x14 table in both the conventional setup (no nulls used) and the setup I'm proposing is D'Agapeyeff's use of a keyword to reorder the columns.  Choosing a 14+ letter keyword doesn't seem as plausible, nor did D'Agapeyeff use a longer key phrase in any of his examples in the book.  You can't rule it out completely, but it seems less plausible.  It would seem to make sense that he was building off his own examples since this was included at the end of the book, asking the reader to test the skills they had just learned.

In the next post I'll post results from the phi tests I ran on the 7x7 squares of pairs of numbers.

The D'Agapeyeff Cipher

As I stated in my introductory post, I've taken an interest in this challenge cipher from the 1939 book "Codes and Ciphers" by Alexander D'Agapeyeff.

This cipher was included on the last page of the book and you can read more about it on Wikipedia.  Not a lot of other information exists about this cipher even though it appears on lists of the most famous unsolved codes.

Tiago Rodrigues' site does a nice job of analyzing the cipher text.

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

Before acquiring and reading D'Agapeyeff's book, I took a look at the cipher for the first time and just noted down what I saw that was interesting.

1. The first thing that catches my eye about this cipher is the sheer number of 8s that appear.
2. Zeros occur only twice.  Once to pad out the end of the cipher, and one other time near the middle of the cipher.
3. The pattern of the numbers.  The first digit is a 6, 7, 8, or 9 and the second number in the pair is a 1, 2, 3, 4, 5.

As I said before, not much information regarding analysis or attempts to solve this cipher exists.  What little information I have seen normally suggests that this cipher should be analyzed in the 196 number pairs that exist when you remove the three zeros from the end (000).

That same school of thought then suggests a polybius square was used to encode the plaintext letters into 2 digit numbers.  This theory is statistically sound:

N = 196
Phi(r) = 1472
Phi(e) = 2549
Phi(o) = 2664
IC = 0.069

For those 196 number pairs the expected phi value is 1472 for random text, 2549 for English, and the observed phi value for the counts of these pairs of numbers is 2664.  This yields an IC of 0.069.  Perfectly in line with what you'd expect for English text that's undergone a substitution.

Here's the problem I have with this method of attack.  The setup for this allows the zero near the middle of the cipher to remain.  Why?  If "000" is removed from the tail-end of the ciphertext, shouldn't we assume the other zero was also performing the same function?

Let's go back to my first and third observations.  Plethora of 8s.  Number pattern.

D'Agapeyeff makes mention of several ideas in his book to make cryptanalysis more difficult.  One such idea is the insertion of nulls into the ciphertext.  If the pattern of 9/8/7/6 and 1/2/3/4/5 is man-made through the use of null values, perhaps the ciphertext is actually just made of up pairs of 1-5 from another sort of polybius square:

Removing all the 6s, 7s, 8s, 9s and the zeros would leave 196 numbers or 98 number pairs.

After removing the nulls

Number Pair Counts

This would suggest a 7x14 or 14x7 rectangle (less probable are 4x28 and 28x4).

However, when performing the phi test for mono-alphabeticity on the resulting 98 number pairs yields:


N = 98
Phi(r) =366
Phi(e) =634
Phi(o) = 402

According to the test, these frequencies more resemble random letters than readable text.  Perhaps the numbers are paired in another manner or the cipher is broken into smaller pieces.

This brings me back to my second observation, the zero near the middle.  It must indicate a break or something similar, otherwise why not just keep using 6s, 7s, 8s, and 9s and save the three zeros to pad out the end of the cipher.  To be continued next post . . .