Sunday 11 July 2010

Crypt Kicking

Having returned from the recent adventures in HB-Land, I was keen to have a play with the "Challenges" in the Appendix of Pincock and Frary's book "Code Breaker"...



There are some websites which give the solutions, but I'll show enough of my working to prove that I've actually cracked the codes!

Challenge 1

We are told that the first Challenge is enciphered using a simple Ceasar shift.

Here's the ciphertext...

AXQTGINUGTTSDBINGPCCNXHSTPSGJCWTCRTEGDRAPXBRGNXIP
QDJIIWTHIGTTIHHDBTIDIWTRDBBDCEJAEXIHPCSRGNDJIAXQTGIN
UGTTS DB PCSTCUGPCRWXHTBTCI ETDEATPCS HTCPI DG HQTCDIPUU
GXVWITSUANCDIHIPCS[HXUUPBQXIXDCHSTQIXHEPXSIWTLDGSH
DURPTH PGQTUDGTWTUTAALXAADETCIWTCTMISDDG


I wrote a function in MATLAB to perform Frequency Analysis on the ciphertext and here's the result...

There is the strong set of peaks which would be expected from a mono-alphabetic substitution (such as a Caesar shift). What's more, the modal peak at "T" in the ciphertext is likely to correspond to the plaintext character "E", suggesting a 15 (or 11) character shift. If we make such a shift, the following plaintext emerges...

LIBERTYFREEDOMTYRANNYISDEADRUNHENCEPROCLAIMCRYITABOUTTHESTREETSSOMETOTHECOMMONPULPITSANDCRYOUTLIBERTYFREEDOMANDENFRANCHISEMENTPEOPLEANDSENATORSBENOTAFFRIGHTEDFLYNOTSTANDSTIFFAMBITIONSDEBTISPAIDTHEWORDSOFCAESARBEFOREHEFELLWILLOPENTHENEXTDOOR

Here's the Frequency Analysis of the plaintext...

... which follows that expected in English (see, e.g., the distribution on page 38 of Code Breaker or on the Wiki page)

We can break up words and phrases by adding spaces and carriage return/line feeds "by inspection"...

LIBERTY FREEDOM TYRANNY IS DEAD
RUN HENCE PROCLAIM CRY IT ABOUT THE STREETS

SOME TO THE COMMON PULPITS AND CRY OUT
LIBERTY FREEDOM AND ENFRANCHISEMENT

PEOPLE AND SENATORS BE NOT AFFRIGHTED
FLY NOT STAND STIFF AMBITIONS DEBT IS PAID

THE WORDS OF CAESAR BEFORE HE FELL WILL OPEN THE NEXT DOOR


It doesn't take too much effort (e.g. cutting and pasting into Google) to track the first six lines to Shakespear's Julius Caesar, Act 3, Scene 1.

The seventh line, above, suggests that we find the words of Caesar "before he fell" - these last words are uttered immediately before the extract above: "et tu Brute".

Challenge 2

The second challenge is tougher - we are told it is cast in a Vigenère cipher.

Here's the ciphertext...

HXLNSFSXHMGMQPQYKSRBGYTRWDIHBGHJEYMLVXXZPLLTRHTGHFOY
WFCYKUOTYBRIBZBUVYGDIKHZJMYMLMLIISKWBXCPAITVJTXVHGMBZH
MMWLMDPYHMLIUTJUZMMMWTM
ZPLLMCJHNLUNYGXCYBPFEYBKLMYC
GKSLMBXTHEZMMLIUBLUYJEEGXHZERNHWJKBYOUQASWXYUN
ZFRREFXSPLHXIHMHJSFWXIH


I wrote another MATLAB function to find repeats of 2,3 and 4 letter sequences within the ciphertext and the spacing between such repeats. The results are as follows...

Two-Character repeat spacings...
213 216 174 97 106 208 91 40 142 9 21 46 189 198 18 188 146 117 45 45 47 81 135 90 90 171 90 90 85 90 39 72 108 77 2 36 90 29 52 73 80 34 88 34 88 74 54 59 9 111 17 18 62 18 23 44 51 102 54 54 54 45 1 45 44 81 21 28 36 62 38 5 7 24 9 9

Three-Character repeat spacings...
45 90 90 34 88 18 54 54 45 9

Four-Character repeat spacings...
90 54

For clarity, I've highlighted the first pair of four-character repeats "ZPLL" in the ciphertext above. The second four character repeat involves the sequence 'MLIU'.

If we look at the repeat spacings above, we can see a lot of repeats separated by multiples of 9 places, suggesting a 9 character key for the Vigenère cipher.

This is emphasized if we look at the distribution of the (two character) repeat spacings divided by nine in modulo-9 division...

OK - so we suspect a 9-character key. But what is it?

If we look back to the first challenge and remember we were told that Caesar's last words "will open the door", we note that "et tu Brute" has nine characters, so we'll try that as the key...

Here's a plain alphabet (first row) and 9 shifted alphabets associated with the "ettubrute" key (you can see "et tu brute" in the first column)...

ABCDEFGHIJKLMNOPQRSTUVWXYZ
EFGHIJKLMNOPQRSTUVWXYZABCD
TUVWXYZABCDEFGHIJKLMNOPQRS
TUVWXYZABCDEFGHIJKLMNOPQRS
UVWXYZABCDEFGHIJKLMNOPQRST
BCDEFGHIJKLMNOPQRSTUVWXYZA
RSTUVWXYZABCDEFGHIJKLMNOPQ
UVWXYZABCDEFGHIJKLMNOPQRST
TUVWXYZABCDEFGHIJKLMNOPQRS
EFGHIJKLMNOPQRSTUVWXYZABCD

Decoding the ciphertext according to this scheme was achieved by another simple MATLAB function I wrote ("viginere.m" - nothing pretty, but saves the ball-ache of doing it "by hand")...


Sending the (uppercase) ciphertext and key strings to the function returns the following plaintext...

DESTROYEDINTWOZERONINESACKEDINNINETHREEFOURANDANNEXEDBYFRANCEINEIGHTEENZEROFIVETHISPORTCITYWHOSEPATRONSAINTISSTJOHNTHEBAPTISTISATFOURTYFOURTWENTYFIVENEIGHTFIFTYSIXEANDISTHEBIRTHPLACEOFDATOSFRIENDWHOSEFAMILYNAMEYOUNEEDTOPROCEED

... which again is "punctuated" by inspection...

DESTROYED IN 209 SACKED IN 934 AND ANNEXED BY FRANCE IN 1805
THIS PORT CITY WHOSE PATRON SAINT IS ST JOHN THE BAPTIST
IS AT 44 25 N 8 56 E
AND IS THE BIRTHPLACE OF DATOS FRIEND
WHOSE FAMILY NAME YOU NEED TO PROCEED


Entering the coordinates into Google Maps will reveal the city as Genoa (Genova), whilst the historical dates of destruction, sacking and annexation, as well as the Patron saint, are confirmed in (e.g.) this Wiki page.

As yet, I haven't had time to figure out who "Dato" or his(/her) friend is - so this remains a work-in-progress!

...-.- de m0xpd

Update:-

OK - Leonardo Dato, secretary to the Pope, was friend of Leon Battista Alberti. I found this by poking about on the internet - but I'm ashamed to say it is in the book! Pages 41-42!

Guess I'm ready to move to the next challenge...

2 comments:

  1. Cool stuff. Just picked up this book the other day and thought it was pretty interesting, though nowhere near as thorough as Simon Singh's. But, I did find the challenges at the end intriguing and figured I'd give them a go. Got stuck at Challenge 4 (ADFGX) and found your site while searching for a clue... Based on my search results, it's obvious there as some sites out there with solutions, but I'm trying to work through it (mostly) by myself.

    I realize this post is old now, but just curious if you finished the other challenges?

    ~Keith

    ReplyDelete
  2. Thanks for the tip on who Dato was. Didn't find much online andy never thought of looking in the book glossary! Sneaky Pincock!

    ReplyDelete