ALAN TURING CENTENARY CRYPTOGRAPHY COMPETITION

Chapter 1
(Is released!)

Chapter 2
(Is released!)

Chapter 3
(Is released!)

Chapter 4
(Is released!)

Chapter 5
(Is released!)

Chapter 6
(Is released!)

Epilogue
(Is released!)

Solutions
(Is released!)

# Solutions

#### Chapter 1

Mike, playing around with the replica of The Baby at the Museum of Science and Industry, discovers the following code:

The message is written backwards, starting from the bottom and working up, and with spaces inserted every 4 characters. It reads:

The silver will be found at the end of line. For the next clue you must delve deep in Gorton Monastery.

#### Chapter 2

Mike and Ellie discover a broken mobile phone displaying the following:

This is a text message, but with predictive texting turned off. Thus `A' (button 2 on a phone) could stand for `A', `B' or `C'. Indeed:

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

In terms of cryptography, this is what is called a `non-injective' or `non one-to-one' cipher, meaning that the same character in the cipher text could encipher different characters in the plaintext. For example, `GMMD' could be `home' or could be `good' (if you use predictive texting then you'll be familiar with this, and many other, examples).

The plaintext is

Get the clue from Gorton Monastery. Bring it to the Imperial War Museum tomorrow.

#### Chapter 3

Mike and Ellie discover the following note:

The first thing to do when presented with a cipher like this is to try frequency analysis on the letters. Counting each letter you'll see that

 letter: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z frequency: 0 11 1 11 10 5 11 2 0 10 8 18 31 19 6 22 6 3 15 8 3 1 1 2 3 8

In English, the most commonly occurring letters are ETAOINSHRDLUCMFWYPVBGKQJXZ (in that order). This suggests that `M' - the most common letter in the ciphertext - is `E' in the plaintext, and `P' - the second most common letter in the ciphertext - is `T' in the plaintext. Looking at the ciphertext, we see that `PLM' occurs many times. Hence `L' in the ciphertext is probably an `H' in the plaintext and PLM means THE. This gives:

 ciphertext: L M S E K N Z P L O N J P L M plaintext: H E ? ? ? ? ? T H ? ? ? T H E

 ciphertext: D M W P T B Z M F N P N plaintext: ? E ? T ? ? ? E ? ? T ?

 ciphertext: S B E M J B M X M E F M Q S B C Z R plaintext: ? ? ? E ? ? E ? E ? ? E ? ? ? ? ? ?

 ciphertext: P N P L M Q G V S J E G D D S D E plaintext: T ? T H E ? ? ? ? ? ? ? ? ? ? ? ?

 ciphertext: O N B B N Q P L M R S P L P L J N Z F L| plaintext: ? ? ? ? ? ? T H E ? ? T H T H ? ? ? ? H

 ciphertext: P L M Q N N E K P L M T B Z M G K plaintext: T H E ? ? ? ? ? T H E ? ? ? E ? ?

 ciphertext: Y Z J G M E G D P L M T S U M plaintext: ? ? ? ? E ? ? ? T H E ? ? ? E

 ciphertext: Y M L G D E P L M H Z S J J X S P plaintext: ? E H ? ? ? T H E ? ? ? ? ? ? ? T

 ciphertext: P L M E M U G B K F S P M plaintext: T H E ? E ? ? ? ? ? ? T E

 ciphertext: O N B B N Q S O G Y N D S T T G plaintext: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

 ciphertext: K M H Z M D T M N O R S T M K G D plaintext: ? E ? ? E ? ? E ? ? ? ? ? E ? ? ?

 ciphertext: P L M T S U M O N J Q S J E P L M D plaintext: T H E ? ? ? E ? ? ? ? ? ? ? T H E ?

 ciphertext: J G F L P P N P L M B N N K M plaintext: ? ? ? H T T ? T H E ? ? ? ? ?

 ciphertext: K P N D M plaintext: ? T ? ? E

PN in the ciphertext is the word T?; thus N probably stands for O. The five most frequent letters in English are ETAOI and the five most frequent letters in the ciphertext are MPNSL. As M, P and N are already accounted for, this suggests that S in the ciphertext is A in the plaintext. The first line then becomes

 ciphertext: L M S E K N Z P L O N J P L M plaintext: H E A ? ? O ? T H ? O ? T H E

You might then guess that the message starts either `Hear' or `Head'. Continuing in this way, making educated guesses as to what each letter stands for, you eventually obtain the plaintext:

Head south for the next clue. Go to Alderley Edge, walk up to the Wizard Inn and follow the path through the woods. The clue is buried in the cave behind the quarry at the Devil's Gate. Follow a Fibonacci sequence of paces in the cave, forward then right, to the loose stone.

The substitution used is

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

(This is derived from the title of Turing's PhD thesis: Systems of logics based on ordinals.)

#### Chapter 4

This is a book cipher. Here the key is a specific book, and the numbers refer to the locations of words in that book. Obviously there are millions (billions?) of books that could have been used, so there has to be a clue in the code to indicate the correct book.

In a book cipher, the numbers refer to the location of a word in a give book. The first thing to do is to try to work out which book it might be. Barbara says that it's a `wizard book cipher' - `wizard' here could be (rather old-fashioned!) slang for `excellent', or it could be a clue that it's a cipher using a book about wizards. The most popular books about wizards are probably the Harry Potter books, so this deserves further investigation.

The first number is 11.12 - this could refer to the 12th word on the 11th line, or the 12th word on the 11th page, or the 12th word of the 11th chapter, etc. The first possibility is ruled out by (for example) the number 21.96 - it's highly unlikely that one line has 96 words on it. The second possibility is ruled out by (for example) the number 1.9 - page 1 of most books is the title or contents page. Let's try the 3rd option with `Harry Potter and the Prisoner of Azkaban'. Here

• 11.12 - the 12th word of Chapter 11 is `Managed'
• 6.6 - the 6th word of Chapter 6 is `Entered'
• 3.19 - the 19th word of Chapter 3 is `Effort'
• 16.6 - the 6th word of Chapter 16 is `The'.
Looking at the words doesn't look too promising. But if you look at the initial letters, then you get `MEET' - this looks like we're on the right track!

If you try to decipher the rest of the message in this way then you get:

Meet me in the Northern Quarter.

#### Chapter 5

The following cipher was discovered by Mike and Ellie in the caves on Alderley Edge.

The cipher uses the numbers 0-9 and letters C,D,E,F,W,X,Y,Z. Looking at individual characters in the cipher text doesn't suggest any immediate patterns. However, if you look at pairs of letters then you can see that certain pairs frequently occur: 20, 69, 6E, 61, 00, amongst others. This suggests that pairs of characters in the ciphertext are being used to denote individual characters in the plaintext. You can also see that many pairs start with a 6 or a 7. However, some pairs starting with a 6 or 7 have an W,X,Y or Z between them (6CY75, 74X72, etc). This suggests that W,X,Y,Z are `nulls' (meaningless characters that have been inserted to confuse the cryptanalyst!) and should be ignored.

You could then solve the code by stripping out all of the W,X,Y,Zs and performing a frequency analysis on pairs, as in Chapter 3. (For example, one of the most commonly occurring pairs 20, 61, 65 is likely to be `e'.) You'll soon discover that there are more pairs than there are letters in the alphabet, so it seems likely that a given character in the plaintext is being encoded by one than more pair (there is also the possibility that punctuation is also being encoded).

However, it's possible to be a bit smarter. Once the supposed nulls have been stripped out, the cipher uses the characters 0-9 and C,D,E,F. This looks like hexadecimal (base 16), and there is a well-known way - known as ASCII - of encoding text with each character represented by a two-digit number in hexadecimal. You can find a table of ASCII codes here: http://www.asciitable.com.

You are so close, don't run out of steam. The treasure is located near the East Lancashire Railway. The final clue is in Bury Bolton Street Station.

#### Chapter 6

Here's Ellie's sketch of Turing's last clue.

Here frequency analysis doesn't suggest anything, so we can deduce that the cipher isn't a simple substitution.

A Vigenère cipher is a generalisation of a substitution cipher - and it's much harder to crack! (In fact, another name for it is the `le chiffre indéchiffrable' - the undecipherable code.) First remember how a Caeser cipher, described in the Introduction, works. In a Caeser cipher with shift 5, all the letters in the plaintext are rotated 5 places to the left to form the ciphertext; so A is encoded as F, B is encoded as G, etc. A Vigenère cipher uses a repeating sequence of different Caeser ciphers. One chooses a keyword, and each letter of this keyword determines a Caeser cipher: the letter A in the keyword corresponds to a Ceaser cipher with shift 0, the letter B in the keyword corresponds to a Caeser cipher with shift 1. One can easily encode messages using a Vigenère cipher using the following table.

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

For example, we would encode the plaintext `To be or not to be that is question' using the keyword `Hamlet' as follows:

 plaintext: T O B E O R N O T T O B E T H A T I S T H E Q U E S T I O N keyword: H A M L E T H A M L E T H A M L E T H A M L E T H A M L E T ciphertext: A O N P S K U O F E S U L T T L X B Z T T P U N L S F T S G

Here, the first `T' is shifted by the Caeser cipher determined by the letter `H', so we look up the entry in row T and column H in the table and get `A'. `O' is shifted by the Caeser cipher determined by the letter `A', and the entry in row O and column A is `O'. `B' is shifted by the Caeser cipher determined by `M', i.e. to N, and so on.

There are many ways to crack a Vigenère cipher. For (reasonably) long messages, cracking the cipher can be done by a generalisation of frequency analysis. In the above example, the pair `TT' occurs twice with a gap of 6 letters between. This suggests that the keyword is of length 6 and that, in the plaintext, `TT' is a commonly occurring pair of letters. Just as one can perform frequency analysis on letters, one can also perform frequency analysis on pairs of letters (also known as digraphs); the most commonly occurring digraphs in English are th, he, in, er, an, re, on, en, at, es, ed, te, ti, or, st, ar, nd, to, nt, is, of, it, al, as, ha, ng, co, se, me, de. (In this case, the keyword does have 6 letters, and `TT' in the ciphertext is `TH' in the plaintext.) Assuming the keyword is 6 letters long, you could then break the ciphertext into 6 separate Caeser ciphers and use frequency analysis on each of these to break the code.

However, the message Ellie discovered is too short for this method to work. Instead, you can crack it by guessing words that might be in the message and using this to determine what the keyword must be.

Starting at the top left, the cipher is:

 ciphertext: F Y R L B C F C C T M B V A V R O Y I K N T U Y W W H T W C E B U K H F U W N Q M L V M O E

Common words that you might expect to be in the message include `and' and `the'. The picture in the cipher also provides a hint: there's a tree and what might be an old mill. Let's assume that the plaintext contains the word `mill' somewhere, and work out the keyword that would encode the plaintext to give that result.

 plaintext: M I L L ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? keyword: T Q G A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ciphertext: F Y R L B C F C C T M B V A V R O Y I K N T U Y W W H T W C E B U K H F U W N Q M L V M O E

 plaintext: ? M I L L ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? keyword: ? M J A Q ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ciphertext: F Y R L B C F C C T M B V A V R O Y I K N T U Y W W H T W C E B U K H F U W N Q M L V M O E

etc. Here, none of the keywords look like they are proper English words. However, when we get to

 plaintext: ? ? ? ? ? ? M I L L ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? keyword: ? ? ? ? ? ? T U R I ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ciphertext: F Y R L B C F C C T M B V A V R O Y I K N T U Y W W H T W C E B U K H F U W N Q M L V M O E

we have what looks like the start of the word `Turing', so we can try this is as a keyword.

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

`Meadow Mill' suggests that we're on the right lines, but the remainder of the message is still gibberish. If one tries starting the message not at the `F' in the top left, but at the `M' on the top row, we have

 ciphertext: M B V A V R O Y I K N T U Y W W H T W C E B U K H F U W N Q M L V M O E F Y R L B C F C C T keyword: T U R I N G T U R I N G T U R I N G T U R I N G T U R I N G T U R I N G T U R I N G T U R I plaintext: T H E S I L V E R C A N B E F O U N D I N T H E O L D O A K T R E E B Y M E A D O W M I L L

and we get the plaintext:

The silver can be found in the old oak tree by Meadow Mill

#### The Epilogue

Mike and Ellie wonder if there's a connection between the places they've visited. The clues were found at

• Museum of Science and Industry
• Gorton Monastery
• Imperial War Museum
• Alderley Edge
• Northern Quarter
• East Lancashire Railway
There are several possible answers: here's one of Cryptoteam's solutions...

Taking the initial letters of these locations you have MGIANE, which can be re-arranged to form `ENIGMA'. Alan Turing is, perhaps, most famous for being part of the team that successfully cracked the Enigma machine during World War II. You can read more about the life of Alan Turing and his contributions to cryptoanalysis, computer science and mathematics at Wikipedia or in Andrew Hodges' biography Alan Turing: The Enigma (Amazon).

 The cartoon of Alan Turing is (c) 2011 ...is organised ...is sponsored and is organised in honour Charles F Cooper, coopertoons.com. by the University by of the Centenary of Alan Turing's Furthermore this competition... of Manchester www.skyscanner.net birth in London on June 23, 2012