Old German homophonic cipher solved

[doranchak Profile Website]

Nick posted about a fascinating story about researchers who solved an old German homophonic cipher:

http://www.ciphermysteries.com/2011/09/30/german-cipher-mystery-found-and-solved

The referenced paper shows their interesting approaches to cryptanalysis. I wonder what the 408 and 340 ciphers would look like if we applied the same clustering analysis that they used for the German cipher.

Now we need to convince those researchers to attack the 340 with us. :)

[traveller1st Profile]

Thanks Nick and Doranchak for respective postings. Looks really interesting and I've only just glanced at the researchers page - gonna need to make time to read.

some zynchronisity right off the bat in the first para.

Apart from what is obviously an owner's mark (“Philipp 1866”)

Trav

[doranchak Profile Website]

I just realized Kevin Knight is the same researcher who wrote "Bayesian Inference for Zodiac and Other Homophonic Ciphers":

http://www.isi.edu/natural-language/people/zodiac-11.pdf

[Aud8us Profile]

There was an Israeli guy who solved Edgar Allen Poe's cypher a few years back using a computer, can't remember what his name is. I actually made contact with him and tried to direct him to the Zodiac codes but he seemed to be preoccupied with something else....

[glurk Profile Website]

Without even having to look it up, I remember that guy's name was Gil Broza (sp?) and it was a fascinating story.

-glurk

EDIT: Quickly found a link:

http://bokler.com/eapoe_challengesolution.html

[doranchak Profile Website]

I whipped up a "cosine similarity" calculator, which is how Knight et. al. compared symbol pairs. Here are the top results for the 408:

Code: Select all


Symbols: [EW] Cosine similarity: [0.7058823529411765] Actual homophone? [Yes]
Symbols: [!M] Cosine similarity: [0.6708203932499369] Actual homophone? [No]
Symbols: [E_] Cosine similarity: [0.6507913734559685] Actual homophone? [No]
Symbols: [)M] Cosine similarity: [0.649519052838329] Actual homophone? [Yes]
Symbols: [#%] Cosine similarity: [0.6172133998483678] Actual homophone? [Yes]
Symbols: [Ep] Cosine similarity: [0.5940885257860046] Actual homophone? [Yes]
Symbols: [#z] Cosine similarity: [0.5892556509887896] Actual homophone? [No]
Symbols: [EG] Cosine similarity: [0.5850179393017045] Actual homophone? [No]
Symbols: [Nl] Cosine similarity: [0.5477225575051661] Actual homophone? [No]
Symbols: [O^] Cosine similarity: [0.5443310539518174] Actual homophone? [Yes]
Symbols: [G_] Cosine similarity: [0.5393598899705937] Actual homophone? [No]
Symbols: [+p] Cosine similarity: [0.5163977794943223] Actual homophone? [Yes]
Symbols: [Ul] Cosine similarity: [0.5163977794943222] Actual homophone? [No]
Symbols: [!)] Cosine similarity: [0.5163977794943222] Actual homophone? [No]
Symbols: [PV] Cosine similarity: [0.5090278103806222] Actual homophone? [No]
Symbols: [(c] Cosine similarity: [0.5000000000000001] Actual homophone? [No]
Symbols: [F^] Cosine similarity: [0.5000000000000001] Actual homophone? [No]
Symbols: [+Z] Cosine similarity: [0.4999999999999999] Actual homophone? [Yes]
Symbols: [Qt] Cosine similarity: [0.49613893835683387] Actual homophone? [No]
Symbols: [Wp] Cosine similarity: [0.4950737714883372] Actual homophone? [Yes]
Symbols: [TW] Cosine similarity: [0.485071250072666] Actual homophone? [No]
Symbols: [#D] Cosine similarity: [0.4811252243246882] Actual homophone? [No]
Symbols: [GX] Cosine similarity: [0.45454545454545453] Actual homophone? [No]
Symbols: [Yt] Cosine similarity: [0.44474958999666075] Actual homophone? [No]
Symbols: [6B] Cosine similarity: [0.43643578047198467] Actual homophone? [No]
Symbols: [!E] Cosine similarity: [0.4338609156373123] Actual homophone? [No]
Symbols: [W_] Cosine similarity: [0.4338609156373123] Actual homophone? [No]
Symbols: [AF] Cosine similarity: [0.43301270189221935] Actual homophone? [No]
Symbols: [8J] Cosine similarity: [0.43301270189221935] Actual homophone? [No]
Symbols: [9P] Cosine similarity: [0.4305283859114459] Actual homophone? [Yes]
Symbols: [HK] Cosine similarity: [0.42426406871192845] Actual homophone? [No]
Symbols: [5Y] Cosine similarity: [0.4225771273642583] Actual homophone? [No]
Symbols: [Vq] Cosine similarity: [0.4139186771923578] Actual homophone? [No]
Symbols: [Dz] Cosine similarity: [0.4082482904638631] Actual homophone? [No]
Symbols: [Td] Cosine similarity: [0.4082482904638631] Actual homophone? [Yes]
Symbols: [@j] Cosine similarity: [0.4082482904638631] Actual homophone? [No]
Symbols: [Md] Cosine similarity: [0.4082482904638631] Actual homophone? [No]
Symbols: [Ie] Cosine similarity: [0.40824829046386296] Actual homophone? [No]
Symbols: [LP] Cosine similarity: [0.40555355282690625] Actual homophone? [No]
Symbols: [KX] Cosine similarity: [0.40451991747794525] Actual homophone? [No]
Symbols: [!k] Cosine similarity: [0.40451991747794525] Actual homophone? [No]
Symbols: [X_] Cosine similarity: [0.40451991747794525] Actual homophone? [No]
Symbols: [eq] Cosine similarity: [0.4045199174779452] Actual homophone? [No]
Symbols: [ET] Cosine similarity: [0.40422604172722165] Actual homophone? [No]
Symbols: [qr] Cosine similarity: [0.4029114820126901] Actual homophone? [No]
Symbols: [=S] Cosine similarity: [0.40089186286863654] Actual homophone? [No]
Symbols: [%P] Cosine similarity: [0.40050093945740706] Actual homophone? [No]
Symbols: [!_] Cosine similarity: [0.3999999999999999] Actual homophone? [No]
Symbols: [9\] Cosine similarity: [0.39405520311955033] Actual homophone? [No]
Symbols: [#O] Cosine similarity: [0.3928371006591931] Actual homophone? [No]
Symbols: [I\] Cosine similarity: [0.3903600291794132] Actual homophone? [No]
Symbols: [Fe] Cosine similarity: [0.3872983346207417] Actual homophone? [No]
Symbols: [/e] Cosine similarity: [0.3872983346207417] Actual homophone? [No]
Symbols: [5c] Cosine similarity: [0.3872983346207417] Actual homophone? [No]
Symbols: [Zp] Cosine similarity: [0.3872983346207417] Actual homophone? [Yes]
Symbols: [@e] Cosine similarity: [0.3872983346207417] Actual homophone? [No]
Symbols: [^e] Cosine similarity: [0.3872983346207417] Actual homophone? [No]
Symbols: [%L] Cosine similarity: [0.38575837490522974] Actual homophone? [No]
Symbols: [Of] Cosine similarity: [0.3849001794597505] Actual homophone? [No]
Symbols: [8B] Cosine similarity: [0.38188130791298663] Actual homophone? [No]
Symbols: [jr] Cosine similarity: [0.3779644730092272] Actual homophone? [No]
Symbols: [6S] Cosine similarity: [0.37499999999999994] Actual homophone? [No]
Symbols: [@P] Cosine similarity: [0.3746343246326776] Actual homophone? [No]
Symbols: [Gp] Cosine similarity: [0.36927447293799825] Actual homophone? [No]
Symbols: [JK] Cosine similarity: [0.3651483716701107] Actual homophone? [No]
Symbols: [/K] Cosine similarity: [0.3651483716701107] Actual homophone? [No]
Symbols: [@K] Cosine similarity: [0.3651483716701107] Actual homophone? [Yes]
Symbols: [DK] Cosine similarity: [0.3651483716701107] Actual homophone? [No]
Symbols: [_p] Cosine similarity: [0.3651483716701107] Actual homophone? [No]
Symbols: [#B] Cosine similarity: [0.36369648372665403] Actual homophone? [Yes]


There are a lot of "false positives" among the top-scoring results. I'm not sure a strict greedy merge of the top scoring results would be the best approach. Perhaps there is a way to be more selective of the merges, such that they maximize some desirable characteristics of the resulting merged cipher text (for instance, maximizing n-gram counts or improving the remaining homophone sequence scores, etc)

[doranchak Profile Website]

And here are the results for the 340:

Code: Select all

Symbols: [&@] Cosine similarity: [1]
Symbols: [Xy] Cosine similarity: [0.8017837257372731]
Symbols: [>l] Cosine similarity: [0.6666666666666666]
Symbols: [_y] Cosine similarity: [0.6546536707079772]
Symbols: [-:] Cosine similarity: [0.6324555320336759]
Symbols: [@R] Cosine similarity: [0.5773502691896258]
Symbols: [&_] Cosine similarity: [0.5773502691896258]
Symbols: [@b] Cosine similarity: [0.5773502691896258]
Symbols: [&b] Cosine similarity: [0.5773502691896258]
Symbols: [&R] Cosine similarity: [0.5773502691896258]
Symbols: [@_] Cosine similarity: [0.5773502691896258]
Symbols: [>P] Cosine similarity: [0.5773502691896258]
Symbols: [Pl] Cosine similarity: [0.5773502691896257]
Symbols: [#)] Cosine similarity: [0.5714285714285714]
Symbols: [Bl] Cosine similarity: [0.5499719409228703]
Symbols: [(X] Cosine similarity: [0.5345224838248487]
Symbols: [7b] Cosine similarity: [0.5163977794943222]
Symbols: [RU] Cosine similarity: [0.5163977794943222]
Symbols: [U_] Cosine similarity: [0.5163977794943222]
Symbols: [bk] Cosine similarity: [0.5163977794943222]
Symbols: [F_] Cosine similarity: [0.5000000000000001]
Symbols: [R_] Cosine similarity: [0.5000000000000001]
Symbols: [:A] Cosine similarity: [0.4999999999999999]
Symbols: [+@] Cosine similarity: [0.48666426339228763]
Symbols: [&+] Cosine similarity: [0.48666426339228763]
Symbols: [^b] Cosine similarity: [0.47140452079103173]
Symbols: [HW] Cosine similarity: [0.47140452079103173]
Symbols: [*c] Cosine similarity: [0.47140452079103173]
Symbols: [.P] Cosine similarity: [0.47140452079103173]
Symbols: [@N] Cosine similarity: [0.4472135954999579]
Symbols: [&U] Cosine similarity: [0.4472135954999579]
Symbols: [@U] Cosine similarity: [0.4472135954999579]
Symbols: [Sd] Cosine similarity: [0.4472135954999579]
Symbols: [&N] Cosine similarity: [0.4472135954999579]
Symbols: [kl] Cosine similarity: [0.4472135954999579]
Symbols: [78] Cosine similarity: [0.4472135954999579]
Symbols: [(c] Cosine similarity: [0.4364357804719848]
Symbols: [#;] Cosine similarity: [0.4364357804719848]
Symbols: [Kb] Cosine similarity: [0.4364357804719848]
Symbols: [cy] Cosine similarity: [0.4364357804719848]
Symbols: [);] Cosine similarity: [0.4364357804719848]
Symbols: [Kc] Cosine similarity: [0.4364357804719848]
Symbols: [K_] Cosine similarity: [0.4364357804719848]
Symbols: [LW] Cosine similarity: [0.43301270189221935]
Symbols: [(y] Cosine similarity: [0.4285714285714285]
Symbols: [Ky] Cosine similarity: [0.4285714285714285]
Symbols: [2V] Cosine similarity: [0.4216370213557839]
Symbols: [BN] Cosine similarity: [0.4216370213557839]
Symbols: [8^] Cosine similarity: [0.4082482904638631]
Symbols: [@^] Cosine similarity: [0.4082482904638631]
Symbols: [@Z] Cosine similarity: [0.4082482904638631]
Symbols: [&Z] Cosine similarity: [0.4082482904638631]
Symbols: [&^] Cosine similarity: [0.4082482904638631]
Symbols: [BP] Cosine similarity: [0.4082482904638631]
Symbols: [Xc] Cosine similarity: [0.40824829046386296]
Symbols: [Ej] Cosine similarity: [0.40824829046386296]
Symbols: [3P] Cosine similarity: [0.40824829046386296]
Symbols: [AR] Cosine similarity: [0.40824829046386296]
Symbols: [PX] Cosine similarity: [0.40824829046386296]
Symbols: [X_] Cosine similarity: [0.40824829046386296]
Symbols: [;q] Cosine similarity: [0.40824829046386296]
Symbols: [6L] Cosine similarity: [0.40824829046386296]
Symbols: [7k] Cosine similarity: [0.3999999999999999]
Symbols: [+Z] Cosine similarity: [0.3973597071195132]
Symbols: [Bz] Cosine similarity: [0.3928371006591931]
Symbols: [^|] Cosine similarity: [0.3872983346207417]
Symbols: [8p] Cosine similarity: [0.3872983346207417]
Symbols: [Oz] Cosine similarity: [0.3849001794597505]
Symbols: [15] Cosine similarity: [0.3849001794597505]
Symbols: [(Y] Cosine similarity: [0.3779644730092272]
Symbols: [@K] Cosine similarity: [0.3779644730092272]
Symbols: [&K] Cosine similarity: [0.3779644730092272]
Symbols: [DK] Cosine similarity: [0.3779644730092272]
Symbols: [5K] Cosine similarity: [0.3779644730092272]
Symbols: [)5] Cosine similarity: [0.3779644730092272]
Symbols: [)@] Cosine similarity: [0.3779644730092272]
Symbols: [&y] Cosine similarity: [0.3779644730092272]
Symbols: [&)] Cosine similarity: [0.3779644730092272]
Symbols: [@y] Cosine similarity: [0.3779644730092272]
Symbols: [(5] Cosine similarity: [0.3779644730092272]
Symbols: [+b] Cosine similarity: [0.37463432463267765]
Symbols: [2F] Cosine similarity: [0.372677996249965]
Symbols: [+K] Cosine similarity: [0.3678836036909795]
Symbols: [U^] Cosine similarity: [0.3651483716701107]
Symbols: [.T] Cosine similarity: [0.3651483716701107]
Symbols: [_|] Cosine similarity: [0.3651483716701107]
Symbols: [<C] Cosine similarity: [0.3651483716701107]
Symbols: [b|] Cosine similarity: [0.3651483716701107]
Symbols: [7^] Cosine similarity: [0.3651483716701107]
Symbols: [4U] Cosine similarity: [0.3651483716701107]
Symbols: [%p] Cosine similarity: [0.36514837167011066]
Symbols: [+U] Cosine similarity: [0.36273812505500586]


Seems to be easier to find highly similar pairs of symbols when the symbols don't occur frequently. For example, "&" and "@" are highly similar because they don't occur frequently, and they are always preceded by "+".

"X" and "y" have high cosine similarity because one "X" is preceded by "c" and another "X" is preceded by "B", while one "y" is preceded by "c" and two "y"s are preceded by "B".

I wonder if the distribution of cosine similarities could be used to test transpositions. For example, would a correctly unravelled transposition yield the "ideal" distribution of cosine similarities?

[smithy Profile]

D. - which transpositions...... columnar? Row?
I'm just thinking about the size of the numbers.

[doranchak Profile Website]

Well, I guess I'm speaking very generally, because I don't know that we can limit transpositions to columnar and row, since there are other possibilities such as writing the plaintext in multiple directions within the same block.

Because there are so many possibilities, we have to devise some sort of metric that we can use as part of a heuristic to help explore the huge space. Perhaps some combination of n-gram counts, homophone sequences, and cosine distances will "peak" when we get close to the correct transpositions.

[doranchak Profile Website]

The New York Times finally caught up to the noteworthy story Nick recognized long ago:

http://www.nytimes.com/2011/10/25/science/25code.html

But when that approach failed, they figured that the code was what cryptographers call a homophonic cipher — a substitution code that does not have a straightforward correspondence between the original and encoded information. And they decided the original language was probably German.

Eventually they concluded that the Roman letters were so-called nulls, meant to mislead the code breaker, and that the letters represented spaces between words made up of elaborate symbols. Another crucial discovery was that a colon indicated the doubling of the previous consonant.

The researchers used language-translation techniques like expected word frequency to guess what a symbol might equal in German.

“It turned out that we can apply a lot those techniques to code breaking,” Dr. Knight said.

Cool stuff!