Continued Struggles Against the D'Agapeyeff Cipher

The end of 2013 brought with it yet another excursion into the depths of the D'Agapeyeff cipher for me.

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

Or, as I like to think of it:

52251 21414 14544 44243 13114
42245 32415 45355 53355 13155
55422 25432 54315 14545 45532
22321 12143 52143 32513 33441
11435 45455 24225 15141 25455
15324 41242 24113 52444 13541
15243 35234 22252 35223 22223
25452 13242 23514 54512 2

It's interesting to reflect back to my first look at the D'Agapeyeff Cipher, and even though it's been over three years, I still feel the same about the potential ciphertext.

My main pieces of rationale have not withered over time:

1. This book was published in 1939. Enciphering an approximately 200 character message by hand was still an arduous task. All example ciphers in his book were approximately 100 characters or less. Including an 89 character polybius square cipher produced by "a friend" which he solves in the Cryptanalysis section. Even this cipher contained 3 typos and one omitted letter.
2. If I set aside the first piece of rationale, the distribution is far too flat for a message 200 characters in length.
3. A 14x14 transposition square makes more sense with 196 digits, not 392. D'Agapeyeff himself suggested adding characters as nulls at regular intervals to thwart cryptanalysis. He also suggested looking for square shapes when transposition was in play.

If you are considering the original ciphertext, we can also pretty much rule out that fractionation was used. Think about it this way, what are the chances that the 9s only paired with 1s until the last column/row (depending how you write it out).

75 62 82 85 91 62 91 64 81 64 91 74 85 84
64 74 74 82 84 83 81 63 81 81 74 74 82 62
64 75 83 82 84 91 75 74 65 83 75 75 75 93
63 65 65 81 63 81 75 85 75 75 64 62 82 92
85 74 63 82 75 74 83 81 65 81 84 85 64 85
64 85 85 63 82 72 62 83 62 81 81 72 81 64
63 75 82 81 64 83 63 82 85 81 63 63 63 04
74 81 91 91 84 63 85 84 65 64 85 65 62 94
62 62 85 91 85 91 74 91 72 75 64 65 75 71
65 83 62 64 74 81 82 84 62 82 64 91 81 93
65 62 64 84 84 91 83 85 74 91 81 65 72 74
83 83 85 82 83 64 62 72 62 65 62 83 75 92
72 63 82 82 72 72 83 82 85 84 75 82 81 83
72 84 62 82 83 75 81 64 75 74 85 81 62 92

All this brings me back to the ciphertext I consider the working ciphertext:

52251 21414 14544 44243 13114 42245 32415 45355 53355 13155
55422 25432 54315 14545 45532 22321 12143 52143 32513 33441
11435 45455 24225 15141 25455 15324 41242 24113 52444 13541
15243 35234 22252 35223 22223 25452 13242 23514 54512 2

Around Christmas I did some more trials with all the variations of writing 196 characters into a 14x14 square and exactracting it. I ran these 48 x 47 = 2,256 ways of transposing the plaintext digits through a solver taking into consideration all possible shifts of the ciphertext. The idea came to me when contemplating whether or not the zero in the middle of the original ciphertext marked the true beginning of the cipher. I had done something similar in my last post on just the non-shifted ciphertext.

When nothing came of those "simple" transpositions  I went back to the columnar transposition idea in the 14x14 square (ADFGX) and ran that to get the max phi value for each of the possible 195 shifted ciphertexts.

The best phi values (~670) came when the ciphertext was shifted four positions from the starting point, or from the starting point of any of the 14 columns.

This collided with one of my other hypotheses to check, which is "what if the ciphertext got out of phase while he was copying it from the square to the final copy for the book?". Since it was a 14x14 square I couldn't imagine it wouldn't correct itself after one column or row. Perhaps a solution lies in that shifted ciphertext. I just haven't had time to pursue it yet.

One other hypothesis I've generated is to consider two rectangles were used for columnar transposition - one for the first coordinate in the pair and another for the second. In this hypothesis I would have either two 7x14s or two 14x7s to solve. It doesn't feel very simple and thus I don't want to touch it quite yet :)

I will say that I'm still intrigued by the prologue to this ciphertext:

Here Is A Cryptogram Upon Which The Reader Is Invited To Test His Skill

If I could pick only one key for 14 columns, I would use that one as a place to explore.

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.

Kryptos: A Potential K4 Algorithm

Before I begin -  Thank you for reading, and comments are welcome and appreciated.  Also, please be as forgiving as possible with my use of terminology.  I do my best not to misuse jargon.


The facts as stated by the men who designed Kryptos and it's encryption methods:

• K4 uses an unknown algorithm (at least at the time it was created)
• The English in K4 is masked
• The cryptographer gave the artist ways to modify existing systems for use in Kryptos
• Each step forward in Kryptos represents a more challenging cipher than the previous one
• The biggest clue is in plain view 

For quite some time I've been concentrating on these facts.  Masking English can be done in many ways using modern crypto techniques, but one easy way to accomplish this in classical cryptography is to use fractionated substitution.  This can be accomplished using a Polybius square or a straddling checkerboard.  Examples are the bifid, trifid, CM Bifid, ADFGX, and other monome-dinome type ciphers based on the straddling checkerboard.

Fractionated substitution is good as a precursor to a transposition step.  Being able to diffuse the pieces that make up a plaintext letter, in a systematic format, is an algorithm.

The algorithms for ciphers such as the bifid are well known, with their weaknesses well documented and their general solutions published.  They no longer represent a challenge to the cryptographic community given enough ciphertext.

However, the concept for some of these ciphers fit all the criteria for K4 should they be modified in some way:

• They mask the English by breaking the relationships between the ciphertext characters and plaintext letters.
• This type of cipher, substitution plus transposition, fits the criteria of being more challenging than the previous layers of the Kryptos puzzle (Morse Code, Vignere, Double Row-Column Transposition)

That leaves only one problem . . . what is the algorithm?  If it's unknown, we can't solve for it, right?

For that I look to the last fact in our list.  It's in plain view.

Could it be that the algorithm isn't a secret, but instead placed in front of us in the familiar dYAhR out of alignment letters?  I believe so.  Let me explain.

As noted, the traditional algorithms for bifids are known.  One such method includes placing the row coordinates (from the Polybius square substitution) for each plaintext letter on a top line, while placing all the column coordinates a line below. An example of a period 7 bifid encipherment is included here (Polybius square not shown):

S	H	A	R	P	E	N
1	2	1	5	3	2	3
1	1	5	4	1	5	3

Pairing up the numbers on the top row, followed by the bottom row yields the following number pairs and corresponding ciphertext characters:

1	2	1	5	3	2	3	1	1	5	4	1	5	3
Z		A		J		P		A		M		B

When deciphering a bifid by hand  you  use the known algorithm to place half-letters in a particular order, and use those half-letters to attempt decryption.  Since this is not a reflective cipher, we don't have access to the coordinate numbers from the polybius square.  A letter followed by a 1 represents a row coordinate from the polybius square and a 2 represents a column coordinate:

Z1	Z2	A1	A2	J1	J2	P1
P2	A1	A2	M1	M2	B1	B2

As you can see, in the third position, what is called a "natural" appears in the reconstructed ciphertext.  Reading vertically, A1 A2 results in a plaintext "A" revealing itself.  The bifid leaks information in the form of naturals throughout the course of decryption.  This is possible in all the odd numbered locations where it reads 1,2 vertically.

Now, let's consider a bifid with a different algorithm.  Take the pattern from the dYAhR pattern.  Down, Up, Up, Down, Up.  Let's encode 5 letters at a time (10 numbers) from our plaintext "SHARPEN":

S		H		A		R		P
1	1	2	1	1	5	5	4	3	1
	1	2		1		5	4		1
1			1		5			3
1	2	1	5	4	1	1	1	5	3
Z		A		M		S		B

Now let's consider the potential decryption, since we now know the algorithm, we can work backwards:

	Z1	Z2		A1		A2	M1		M2
S1			S2		B1			B2

The first plaintext letter is made up of S1 Z1.  The second letter Z2 S2.  The third A1 B1.  The fourth A2 M1.  The fifth B2 M2.

This bifid doesn't leak.  No possibilities of naturals - ever.  Previously, not only did our bifid have a chance to leak plaintext letters, it only had two patterns available to the cryptanalyst.  12 and 21.  This bifid has three patterns:  11, 22, and 21.

What this means to the cryptanalyst is that there are 75 ways each plaintext letter could be enciphered.  Essentially, what results for a 97 character cipher is a homophonic representation of the plaintext.

This system also presents a bigger challenge than the known bifid due to two of the patterns potentially only helping place letters in the same row, or in the same column, but never giving the full link to row and column.

When solving bifids, such as the ones that appear in the Cryptogram, you are generally given a crib to get started.  Consider our previous example "SHARPEN" with only 5 letters given as a crib:

		A	R	P	E	N
Z1	Z2	A1	A2	J1	J2	P1
P2	A1	A2	M1	M2	B1	B2

What we are able to glean from this crib is that J & P share a row, M & P share a column, N & P share a row, and N & B share a column.

Given the same type of crib for the dYAhR bifid, we are only able to take a fraction of that information:

				A		R		P
	Z1	Z2		A1		A2	M1		M2
S1			S2		B1			B2

A shares a row with A, nothing to glean from the "21" pattern, and P shares a column with M.

As you can see, this modified bifid cipher is slightly more cryptographically secure than the traditional bifid algorithm and uses an algorithm previously not documented.

It combines what's best about the bifid - digraphic substitution -  and improves it's strength.  While at the same time it improving its known weakness - naturals.

In the end what's left is a new algorithm to cryptanalyze and create a general solution for - just like Friedman and Callimahos presented in their Military Cryptanalytics series.

Some concluding remarks:

• On all 26 letters are present in K4.  If I/J or U/V (or any other two letters) share a square, it would be very easy for the cryptographer to alternate which letter he chose to put in the final ciphertext.  In the end, the letters themselves don't matter anyway, just the underlying relationships.

• On the statistical phenomenon seen in K4 - using only 5 characters to encipher the plaintext typically yields between 3 to 8 instances of double letters in the final ciphertext.  On many occasions these can fall on the same intervals, but overall they are random.

• By flattening the distribution of 1s, 2s, 3s, 4s, and 5s in the intermediate ciphertext you will have a higher probability of lowering the final Index of Coincidence (IC).  It is all dependent on the Polybius square chosen and the plaintext.  A well mixed Polybius square with some low, medium, and high frequency letters in each row will accomplish this.

• Lastly, it should be noted that without a crib this cipher is very tough to crack by hand.  I would imagine that perhaps the morse code contains a crib, much like VIRTUALLY INVISIBLE for K2.  Or perhaps LAYERTWO was meant to be a crib for K4 prior to the "BERLIN" release.

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.