The ALAN TURING
Cryptography Competition.
(edition 2015: #4).
You are reading the website of the 2015 edition of the competition, which ended on Wednesday 13th May 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 2016, 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

Carbon

Conundrum

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

The Alan Turing

Cryptography Day

2015!

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

# Solutions.

## The National Graphene Institute

We're very grateful to the National Graphene Institute at The University of Manchester for allowing us to use it as a setting for large parts of this year's story. The National Graphene Institute was officially opened on 20th March . You can read more about the University of Manchester's connection with graphene here.

## Chapter 1

The quantum computer has just been stolen. Ellie discovers a crumpled piece of paper on which a code has been written. To read the message, read the letters down each column starting from the left and working to the right.
Get the computer to me straight after the lecture today

The code word is the 9th word of the plaintext and the answer is `lecture'.

This is a transposition cipher: the letters of the plaintext are permuted (moved around), but, unlike a substitution cipher, the letters themselves do not change. The letters are arranged in a hexagonal grid that has been reflected and rotated from its original position. In fact all possible symmetries of the hexagon can be generated by composing reflection about a line connecting the midpoints of two opposite sides of the hexagon and rotation by 60 degrees. Can you work out the exact sequence of transformations used to obtain the coded message? Graphene is a two-dimensional, hexagonal lattice of carbon atoms and you may have noticed that hexagons are a recurring theme in this year's competition.

## Chapter 1.5

Mike writes a quick note, in code, to Ellie. This is another transposition cipher: each word is split in half and then the two halves are written backwards (and any punctuation is left in place). The plaintext is:
When the competition website
For chapter one's code
We're trying to put it all right

The code word is the 10th word of the plaintext and the answer is `struggled'.

## Chapter 2

Barquith appears to have been shot. As Mike and Ellie tend to their friend, Mike notices a piece of paper in Barquith's pocket containing a hexagonal array of letters together with the phrase `I've always been fond of the mnemonic Richard Of York Gave Battle Vainly'. A mnemonic is a technique, often using the initial letters of a phrase, that allows one to remember information. The order of the colours of a rainbow are given by the mnemonic `Richard Of York Gave Battle In Vain'. We amended this by dropping `In' (Indigo) to obtain six colours, rather than seven, which fitted more neatly into the hexagon theme.

The message is read by starting at an appropriate red coloured letter, tracing out a path of letters coloured, in sequence, red-orange-yellow-green-blue-violet and then repeating. The correct place to start requires some trial and error, but is the `M' in the bottom right corner.

The plaintext is
Mike, Ellie. Those who perform evil work must be stopped. Trust no man. Barquith.

The code word is the 11th word of the plaintext and the answer is `trust'.

As explained in the Epilogue, `Trust no man' is actually a reference to Professor Niemand (Niemand being German -- and, much to Kees' amusement, Dutch -- for `nobody'). `Evil Work' is a reference to MaliOpus; `Mali' and `Opus' mean `Evil' and `Work', respectively, in Latin.

## Chapter 3

Mike and Ellie watch a statement by Lord Porterfield in which he talks about his apparent narrow escape from death and uses it to promote his company's forthcoming products. As Lord Porterfield reads his statement, he makes (obvious) hand gestures on certain words. The indicated words spell out a secret message to his accomplices.

The plaintext is
You have done well. I will be at the National Graphene Institute in three days time. Be there to hand the quantum computer over to me.

The code word is the 22nd word of the plaintext and the answer is `quantum'.

This code was partly inspired by the (real-life) story of Jeremiah Denton. Denton was an American airman who served in the Vietnam war. In 1965 his plane was shot down over North Vietnam and he was taken prisoner. In 1966, his captors forced him to take part in a press conference. During this conference he repeatedly blinked out the word `T-O-R-T-U-R-E' in Morse code, confirming to the American government that American POWs were being tortured by the North Vietnamese (click here to see part of the press conference). You can read the full story of Denton's life here.

All of the uses of graphene mentioned by Lord Porterfield are genuine current or future applications of graphene.

The role of Lord Porterfield is played by Professor Oliver Jensen, a member of the academic staff in the School of Mathematics. Professor Jensen is an applied mathematician who works in continuum mechanics and mathematical modelling with applications to medicine and biology. We are very grateful to Professor Jensen for his time in making the video, which took a number of takes to get right!

## Chapter 4

Mike accidentally switches Niemand's computer on and sees an unsent email. The email is written in code and contains a mixture of upper and lower case letters. Frequency analysis (ignoring case) does not help: the most common letters are i,c,y,b,d (with 52-57 occurrences). Instead, perhaps the upper and lower case letters should be considered separately. If you perform frequency analysis just on the lower case letters then you notice that the letters i and y are the most common (54 and 51 occurrences, respectively) and that the pair of letters `iu' appear 14 times. This strongly suggests that `i' represents `t', `u' represents `h' (as `th' is the most commonly occuring pair of letters in English) and `y' represents `e'. Trial and error then allows you to recognise that the lower case letters are a substitution cipher. The substitution is given by the following table.

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

(There is no significance to this choice of substitution; it was a random choice.) The plaintext is

I know what we are trying to achieve is important but I am not too happy about having to do your dirty work. However I will continue to do as you have instructed me. I hope you appreciate the risk that I took during the speech given by our adversary and that the shooting has its desired effect. It is imperative that research into graphene is kept away from those who will exploit it for their own ends. I also agree that we continue to put those two children to good use. Personally I find them slightly annoying but I will do my best to look after them. I am and remain your faithful servant. Niemand

Looking at the upper case letters it then becomes clear that these are nulls (letters or symbols inserted into the ciphertext that are not used as part of the cipher). Indeed, the upper case letters are there purely to ensure that naive frequency analysis does not work.

The code word is the 22nd word of the plaintext and the answer is `dirty'.

## Chapter 5

Mike and Ellie retrieve a singed piece of paper carelessly discarded from Lord Porterfield's car window. The paper contains chemical structural formulae for twenty-two different molecules. Handwritten in the bottom right corner are the words: "Remember: Each molecule is a ... Each element is ...", where the missing words are obscured by the charred paper. Anybody with even a basic knowledge of chemistry will know that most of the molecules are impossible to make, although a few of them including hydrogen cyanide and carbon dioxide are real.

Looking carefully, you can guess that the complete handwritten text should be "Each molecule is a word. Each element is a letter." This gives the hint that the message is a strange sort of substitution cipher. If each molecule is a word then the number of elements in each molecule gives the number of letters in each word. Looking at the only single letter word reveals that Cl (chlorine) must be I or A. Frequency analysis of the elements suggests that Ca is E and gives likely candidates for the other letters. The difficulty is that the order of the letters in the words is not immediately obvious, but there is a system. The order is from left to right on linear molecules and starting from the bottom left and proceeding anticlockwise on the ring molecules. This is the standard ordering in ChemFig the package used to typeset the chemical formulae. Even without knowing the letter order, the message can be deciphered by trial and error, playing with anagrams and looking for words that you expect to appear, such as quantum, computer and institute.

The letter substitution is given by the following table.

 Plaintext: Cipher text: 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 Cl Ti Co K Ca Si Rb I H Br Sr S Fe Mg O Zn B P N C Na Cu Ba F Pb Sn

The message is written in conventional order, starting from the top left and reading across each row and the plaintext is

cannot recover quantum computer from its hiding place institute very crowded too dangerous for a handover here meet inside maliopus headquarters tomorrow.

The code word is the 11th word of the plaintext and the answer is `crowded'.

## Chapter 6

Mike and Ellie receive simultaneous e-mails containing 46 rows of three sets of five digits taking the values 0 or 1, separated by dashes. As signposted in Chapter 3, this is a binary code and is certainly the hardest code that we have set in any of the competitions ... so far!

Mike and Ellie have different messages and they should be combined to form the final binary code. If you look carefully at Mike's code (tilt your head to the left and read up), you can just make out the hidden letters XOR formed by the 1's. Exclusive OR (XOR) is a binary operation that takes two binary numbers as input and returns 0 if the inputs are both the same and 1 if they are different. Thus, if you XOR together the binary numbers 01010 and 11011, the answer is 10001. You can read more about XOR here.

XORing the two messages together gives the result in the first column of the table below, which is then converted into decimal (standard base 10) in the next column.

Binary Decimal
00011-00110-0111003-6-14
00010-00011-0100002-3-08
00011-00101-0111103-5-15
00111-00101-1001007-5-18
00111-00100-0010107-4-05
01001-00011-0110109-3-13
01001-00101-1010109-5-21
00011-00010-0001103-2-03
01001-00100-0111109-4-15
00101-00011-1010105-3-21
00111-00011-0010107-3-05
00110-00010-0010106-2-05
00010-00100-1010002-4-20
00110-00111-0011006-7-06
00100-00111-1010004-7-20
01000-00010-1010008-2-20
01000-00100-1010008-4-20
00001-00100-0100101-4-09
00110-00011-1001106-3-19
00111-00010-0000107-2-01
00100-00110-0010004-6-04
00100-00100-0001104-4-03
00110-00110-0100006-6-08
00100-00101-1010004-5-20
00110-00101-0000106-5-01
00100-00001-0111004-1-14
01010-00100-1010010-4-20
00101-00110-1011105-6-23
00111-00001-0111007-1-14
00110-00001-0111106-1-15
00100-00011-0110104-3-13
00101-00010-0011005-2-06
00101-00101-0001005-5-02
00100-00010-0000104-2-01
00111-00111-0100107-7-09
01000-00101-1000108-5-17
00011-00011-0010103-3-05
00101-00001-0111105-1-15
01000-00110-1001108-6-19
00101-00100-0111105-4-15
00111-00110-0111107-6-15
00110-00100-0110106-4-13
00011-00100-0100003-4-08
01000-00011-1010108-3-21
00101-00111-0111105-7-15
00010-00101-0100002-5-08

Only the final column has numbers higher than ten, so we could guess that it represents the letters of the alphabet with standard numerical susbtitituion: 1 = A, 2 = B, etc. The first two columns contain numbers between one and ten and they represent Cartesian (x,y) coordinates indicating where to put the corresponding letter. Putting all the letters in place in a standard Cartesian grid gives the hexagonal pattern of letters below.

7 6 5 4 3 2 1 1 2 3 . . . T O F I . . . . . N D W H O S . . . H O T B A R Q U . I T H C O M E T O T . H E M U S E U M . . . C A F E A T . . . . . N O O N . . .

The final plaintext is obtained by reading across the rows from the top:

To find who shot Barquith come to the museum cafe at noon

The code word is the 9th word of the plaintext and the answer is `museum'.

## The Epilogue

A pair of young ladies (the twins?) ask a barrista to pass on a piece of paper to Mike and Ellie. The paper has a large number of hexagons printed on it. Some of the sides of the hexagons are solid and some are dashed. Each hexagon represents a letter and you can crack the code using frequency analysis; however it is possible to be smarter. Each side of the hexagon represents either 0 (a solid line) or a 1 (a dashed line). Starting from the bottom side and working anticlockwise around each hexagon, you can convert the sides of the hexagon into binary. The hexagon represents the letter with the corresponding number (so 000001 represents A, 000010 represents B, 000011 represents C, etc).

The plaintext is
Mike and Ellie. This is only a temporary setback. We had enough time to study the quantum computer and will open our own research labs to develop it. TwinTech will soon be in every electronic device. We are and will remain far smarter than you. DD.

The code word is the 24th word of the plaintext and the answer is `research'.

Organiser: