The Alan Turing
Cryptography Competition.
edition 2018
You are reading the website of the 2018 edition of the competition, which ended on Saturday 28th April at 11:59 pm.

Mike and Ellie will return for a new adventure next year!

The website for that new edition, to start in January 2019, appears in December here. If you would like to receive a reminder around that time by email please look here. For any particular enquiries you can contact us on cryptography_competition@manchester.ac.uk.
The Tale of the

Morphogenesis

Mystery

Is released!
Is released!
Is released!
Is released!
Is released!
Is released!
Is released!
Announcing

The Alan Turing

Cryptography Day

2018!

Want to come over to Manchester for a bit of live crypto stuff, the prize ceremony and an opportunity to meet the organisers?

# Solutions.

## Chapter 1

Truman Cuddeny presents Barquith with a piece of paper, onto which are glued letters cut out of a newspaper.

You might guess that the code used is not going to be very complicated. If you try all the 26 possible Caesar ciphers then you will quickly discount all those. Another straightforward cipher is Atbash, where the alphabet is reversed:

 cipher alphabet plaintext alphabet 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 Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

The plaintext is

Leave the moor or face Old Schuck

How could you have worked out that the message is enciphered using Atbash? The message is too short for frequency analysis to be useful, but one might still guess that one of the most common letters (V, L, X) represents E. The two letter word LI is unlikely to start with an E. The word NLLI contains a repeated L. Common two letter words include to, or, of, be, etc, and only O commonly occurs as a repeated letter in the middle of a four letter word. Hence L is likely to represent O.

LI is likely to be 'or' or 'of', so I probably represents either R or F. We guessed above that V or X probably represents E. The word GSV is then likely to be THE. At this point, it starts becoming clear that Atbash is being used.

As mentioned in the story, Turing was a very keen long-distance runner. His best marathon time was 2hrs 46mins 3secs, only 11 minutes slower than the winning time in the 1948 London Olympics. In fact, Turing was due to compete in the 1948 Olympics but, due to illness, he had to pull out. Turing also competed in cross-country races (once finishing ahead of Tom Richards who went on to win silver in the marathon at the Olympics).

During the Second World War, Turing worked as a code-breaker at Bletchley Park (near what is now Milton Keynes). When he had meetings to attend in London, he would on occasion reject the official car and instead run the approx. 60 miles along the Grand Union Canal.

The story of this year's competition is, quite obviously, heavily based on the Sherlock Holmes story 'The Hound of the Baskervilles' by Arthur Conan Doyle, available on Project Gutenberg here. There are several examples of codes appearing in Sherlock Holmes (see the Epilogue below). Spectral hounds have a long history in English folklore. Old Schuck is based on Black Shuck, see Wikipedia. Finally, Garamond is the name of a font (look for it on MS Word), as is Baskerville...

## Chapter 2

A mysterious taxi driver throws a piece of paper at Mike and Ellie. The paper contains letters arranged in a pyramid shape and a post-it note is attached, hinting that there is "something odd about Pascal's triangle...

 D O N O R T L E T T H D N I E T R S A U T H E W T I A N O U T S Y D R M

Writing out the entries in Pascal's triangle corresponding to the triangular grid of letters gives

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1

If we now select the letters that correspond to the odd numbers in the triangle, we obtain

 D O N O T L E T T H E T R U T H W I N O U T

which reveals the message when read from top to bottom and right to left:

Do not let the truth win out

The number of the Uber is 1729, and it is an interesting number! It's the first taxicab number: a number expressible as the sum of two cubes in (at least) two different ways. You can read about taxicab numbers on Wikipedia here.

## Chapter 3

In the middle of the night, Ellie sees a mysterious sequence of flashing lights on the moor. The message resembles Morse code, but every dot has been replaced by a dash, and every dash has been replaced by a dot. The Wikipedia page on Morse code is here.

The plain text is:

You must leave the moor. No good can come of your plans. Old Schuck can be fickle.

## Chapter 4

Izzy gives Mike and Ellie a letter to pass on to Hope Maliphant. The code is a polyalphabetic substitution, with each group of 4 letters representing either a letter, space, or punctuation symbol.

Frequency analysis quickly shows that TTTT is the most common quadruple of letters, which suggests that this might be an 'E'. However, the distribution of TTTTs throughout the message suggests otherwise (in a message that long, one might expect at least one word to have two repeated Es in it). Instead, maybe TTTT represents a space.

Assuming that TTTT is a space, then you'll notice that there are several occurrences of ATAG GTTT at the start of a word. The most common pair of letters that start a word in English is TH. This suggests that ATAG is T and GTTT is H. You can then start guessing which quadruple of symbols represents E (identifying words you think might be 'THE") and R (identifying words you think might be 'THERE'). It then becomes a process of elimination.

For each letter of the alphabet, there are three possible ways of enciphering it: one for the uppercase alphabet and two for the lowercase (plus punctuation). The cipher is described in the table below (although not every symbol was used):

Plaintext  Uppercase  Lowercase  Lowercase
A CTCA AACT GGAC
B CTAG AACC GGAA
C CTAT AGAA GTGG
D CTAC AGAG GTGT
E CTAA AGAT GTGC
F CCTG AGAC GTGA
G CCTT AGGA GTTG
H CCTC AGGG GTTT
I CCTA AGGT GTTC
J CCGG AGGC GTTA
K CCGT AGTA GTCG
L CCGC AGTG GTCT
M CCGA AGTT GTCC
N CCCG AGTC GTCA
O CCCT AGCA GTAG
P CCCC AGCG GTAT
Q CCCA AGCT GTAC
R CCAG AGCC GTAA
S CCAT ATAA GCGG
T CCAC ATAG GCGT
U CCAA ATAT GCGC
V CATG ATAC GCGA
W CATT ATGA GCTG
X CATC ATGG GCTT
Y CATA ATGT GCTC
Z CAGG ATGC GCTA
In addition, TTTT represents a space and TAAA represents a full-stop.

(There is some logic as to how each letter is enciphered: the first symbol determines which cipher alphabet is being used (C for uppercase, A and G for lowercase, and T for punctuation). For the upper- and lowercase alphabets, the next three letters are related to the base 4 representation of the letter in the plaintext alphabet. We'll leave it to you to work out exactly how this works!)

Meet me at the Rocking Chair stones tomorrow at dusk. We need to enact our plan. I have done what was asked of me at the Institute but I can no longer be part of it. There have been too many strange incidents recently and I fear being discovered. Remember that no matter what happens you can never put your trust in the truth.

ACGT refer to the nucleotides found in (human) DNA. You can read more on Wikipedia here.

## Chapter 5

Mike and Ellie are at the mysterious stranger's camp and find a note addressed to themselves. The note contains a code which appears to be a list of grid references.

The grid references refer to Ordnance Survey grid references (as hinted at in the story: Mike and Ellie notice a pile of Ordnance Survey maps at the camp). You can find an explanation of how the Ordnance Survey grid references work on Wikipedia here.

There are several websites that take grid references and give you the corresponding Ordnance Survey maps; for example Street Map. There are also several different scales that Ordnance Survey maps use: from 1:2,500 to 1:1,000,000. The correct scale is 1:50,000; one of the most commonly used for outdoor activities.

The grid references point to certain words on the 1:50,000 Ordnance Survey maps. Specifically:

Correcting the grammar we have the plaintext

## Chapter 6

Ellie has a photograph of Cuddeny's laptop, on which he was writing a message in code. Frequency analysis is of no help, so the message is likely to be a polyalphabetic cipher.

Various documents appear on the desktop. Some are references to Sherlock Holmes stories (and are Easter eggs). but two stand out. 'Liber Abaci' is a book written by the 13th century mathematician Leonardo of Pisa, better known as Fibonacci. Fibonacci is most famous for the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,...
where each number is the sum of the preceding two numbers. The Fibonacci sequence arose from one of the most famous problems in Liber Abaci: Suppose a pair (one male and one female) of rabbits are in a field surrounded on all sides by a wall. Rabbits can reproduce from the age of one month and produce a new pair (again, one male and one female) from the second month onwards. How many pairs of rabbits will there be after one year? The number of pairs of rabbits at the end of the nth month is the nth Fibonacci number (so there will be 144 pairs of rabbits at the end of the year).

Another document on Cuddeny's desktop refers to the 'Dynamics of Leporine Populations'. Leporine refers to hares or rabbits and dynamics refers to constructing mathematical models. This suggests the Fibonacci sequence is important to Cuddeny!

We're going to think of letters as numbers, with A=1, B=2, C=3, etc. Take the nth letter of the ciphertext and subtract the n+1st Fibonacci number, which avoids the repeated 1 at the start of the sequence. Now convert this back to a letter by taking the remainder on division by 26 (mathematically, we are working 'mod 26'). This gives the plaintext

My position as Director is now secure. The staff will soon be locked in the institute to finish the work. The locals are too scared of old schuck to come anywhere near us. We can complete the weaponisation of morphogenesis. I am sure your government will pay me better for it than the british government. Glory to Genesia!

There is some interesting maths at work here. The sequence of Fibonacci numbers taken mod 26 eventually repeats; after 84 Fibonacci numbers, the sequence of Fibonacci numbers, when calculated mod 26, goes back to the beginning. Thus the code is, essentially, a Vigerère cipher where the key is a 84-character 'word' generated by the Fibonacci numbers. See Wikipedia for a discussion on the Vigerère cipher. The periods of the Fibonacci numbers taken mod n form what is called the Pisano sequence; again see Wikipedia for more details.

Genesia is a (fictional) rogue state. We named it after the planet Genesia in Star Wars, a planet riddled with crime and corruption!

## Epilogue

Old Schuck—now revealed to be a labrador covered in paint and glitter—delivers a code to Mike and Ellie. The code is a series of 'dancing men,' as seen in the Sherlock Holmes story `The Adventure of the Dancing Men'. The code reads

Some codes are elementary, my dear Mike and Ellie.

How would you decipher the message if you weren't familiar with Sherlock Holmes stories? An inspection of the code quickly suggests that the figures holding flags denote either punctuation or the end of a word. Frequency analysis quickly identifies that a figure holding both hands in the air is an 'E' from which the decipherment quickly follows. Alternatively, note that the final word appears to have the same first and last letters and the same second and third letters; in the context of the story, this is likely to be 'Ellie'.

(There are other Sherlock Holmes stories in which codes play a crucial plot point; 'The Valley of Fear' contains a book code and Holmes' explanation of how he solved it. Elements of code-breaking also appear in 'The Adventure of the Gloria Scott' and 'The Adventure of the Musgrave Ritual'.)

Organiser: