Tuesday 13 July 2010

Biting off more than you can chew - almost

I finished Challenge Three of Pincock and Frary’s “Code Breaker” hoping that the next Challenge would have more meat on the bone – indeed it did turn out to offer a more substantial meal!

Challenge Four is a series of three messages encrypted in “ADFGX” cipher.

Cracking this cipher requires knowledge of two things; the randomized Polybius grid (by which each of the letters of the alphabet in the message are represented by a pair of the codes [A,D,F,G,X]) and the key (used to transpose the resulting sequence of codes, making decryption (by e.g. frequency analysis) more difficult).

As the book presents an insufficient sample of ciphertext messages to hope to crack the ADFGX cipher of challenge 4 from scratch, I made the assumption that:

  • we probably know the key word already
  • we must have access to the distribution of letters in the Polybius grid
I started by working on a program which took the ciphertext sequences and arranged them into a grid, assuming a certain key word…

Here's the raw ciphertext for the first part of the challenge…

XAGAXDFAFGFAXGDDFFDDADXGGDFAFFDFFAGAXXDAAXFFXGAXFDFAF
GFGDAAFADADAXAAGXAADFDFFGFFAGADXDDDGAAAAFAAAFXAAAAG
AAAGAAFAFFGGFDAFDDFFFDFDAFFFAXFADFDFFDFFAXXDDFFGAFADFG
DXDADAAGAAFDGFGFAA

It has 176 characters suggesting (since characters of the plaintext are represented by a PAIR of ciphertext codes) a plaintext message of 88 characters. The 176 characters have to be arranged into a grid, according to a key word. The grid will have the same number of columns as the number of characters in the key and, given the ciphertext length, will have a certain number of rows, INCLUDING SOME POTENTIALLY INCOMPLETE ROWS. The number of columns, number of complete rows and number of complete columns all can be calculated from the key length and the ciphertext length ("l")…


Given that we know the number, n, of complete columns, those particular columns which are complete are the first n columns of the un-transposed sequence and these columns can be tracked through the transposition with reference to an alphabetical sorting of the key. We know the ciphertext, we have an algorithm to arrange it and undo the transposition – but WHAT’S THE KEY?

Well, having coded the algorithm (in MATLAB) I decided to use the 5 * 5 arrangement of letters of the alphabet (with single square for i/j) in the Polybius grid on page 94 of the book…

F N W C L
Y R H I V
T A O U D
S G B M Z
E X K P Q

This allowed me to test for a correct key word, just by seeing if the program produced meaningful plaintext output.

After a few experiments with random key words (like “KAISER” from the example on pp 94 – 95, “ALBERTI” from the solution of Challenge 2 and simple sequences like “ABCDEF”, to test if there actually hadn’t been any transposition) I tried “STAGER”, the solution of Challenge 3.

Here’s the resulting transposed sequence…


AEGRST
------
XFADFX
ADFGDD
GFAAAD
AFDAFF
XAAADF
DGDADG
FAAFFA
AXXAFF
FXAAFA
GDAADD
FAGFFF
AAXXDG
XXAAAD
GFAAFX
DFDAFD
DXFAFA
FGDGAD
FAFAXA
DXFAFA
DFGAAG
ADFGDA
DFFAFA
XAAADF
GFGFFD
GGAAFG
DFDFDF
FGXFFG
ADDGFF
FADGAA
....XA

And here’s the result of “undoing” the transposition by sorting the columns according to the correct spelling of the key on the first row…

STAGER
------
FXXAFD
DDAFDG
ADGAFA
FFADFA
DFXAAA
DGDDGA
FAFAAF
FFAXXA
FAFAXA
DDGADA
FFFGAF
DGAXAX
ADXAXA
FXGAFA
FDDDFA
FADFXA
ADFDGG
XAFFAA
FADFXA
AGDGFA
DAAFDG
FADFFA
DFXAAA
FDGGFF
FGGAGA
DFDDFF
FGFXGF
FFADDG
AAFDAG
XA....

Obtaining the plaintext is then simply a matter of reading off the rows and columns from the Polybius grid – for example, the first pair, “FX” refers to row 4, column 5, which returns the letter ‘D’...

The entire plaintext of the first part of the challenge is…

Dearwinstonthefirsttwolettersyouwillneedstartthenameofthecitywiththefamousshroudboniface

Which we can easily “punctuate”, to reveal the fictional “Letter”, as follows…

Dear Winston
The first two letters you will need start the name of the city with the famous shroud
Boniface



The remaining two “letters” are decrypted in the same manner (they used the same key etc)…

Dear Winston
The next two letters stand for the us state where you will find the naval undersea warfare center
Boniface

Dear Winston
Nazi Germany initially.
Boniface


Solution doesn’t require the skills of a crossword puzzle addict (just as well, for I'm not into puzzles at all - in fact all this code breaking stuff is fast turning into a bit of a chore). Turin is famous for its shroud, a quick search on the ‘net reveals that NUWC is headquartered in Newport, Rhode Island and the initals of Nazi Germany are there for all to see.

We conclude that the answer is “TURING” – entirely fitting as it is the family name of the tortured English genius, for whom a street in Manchester is named!

Initial looks at Challenge 5 reveal much more of a problem and a mistake in the book - more on that later.

...-.- de m0xpd

3 comments:

  1. Nice. You can obviously ignore my comment on your other post since I found this. Following your example, I saw where I was making an error during the transposition (using columns instead of rows). I don't know MATLAB and am working either by "hand" or bash scripting.

    THANKS!

    ReplyDelete
  2. Can i get copy for MATLAB ADFGVX? Because i running of time to do my thesis.. :)

    ReplyDelete
  3. Sorry - I searched and don't have a copy any longer - must be on a hard drive on an old computer on a land fill site now. Sorry!

    ReplyDelete