Welcome guest.   Log in
The ALAN TURING
Cryptography Competition.
(edition 2016: #5).
You are reading the website of the 2016 edition of the competition, which ended on Saturday 30th 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 2017, 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.
Home
About
Cryptography
Register
FAQ
Rules
For
Teachers
News
Leaderboard
Forum
Map
Archive
The Tale of the

Artificial

Adventure

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

The Alan Turing

Cryptography Day

2016!

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

Then sign up!

Solutions.

Chapter 1

Alice has shown Ellie a text message on her phone, thinking that Ellie is a spy. Ellie could only read the first half of it before escaping from Alice and Kenneth. The code is a simple substitution cipher: each letter of the alphabet has been replaced by its place value in the alphabet expressed in Roman numerals (so A=I, B=II, C=III, D=IV,..., Z=XXVI). The translated message reads

Mike here. Barquith and I convinced not all well at lab. Meet tomorrov at...
Mike was clearly in a rush when he typed this because his message contained a spelling mistake. The 13th word in plaintext (i.e. standard English) is 'tomorrow'.

The character's names in the story are not accidental. Eliza, Parry and ALICE are chatbots. A chatbot is a computer program designed to mimic intelligent conversation. Eliza is an early example of a chatbot and was created by Joseph Weizenbaum at MIT in 1964-66. Kenneth Colby created Parry in 1972. Eliza was designed to mimic a psychiatrist whereas Parry was designed to mimic a person suffering from schizophrenia. You can find a conversation conducted between Eliza and Parry over Arpanet (the predecessor of the internet) in 1973 here. Hugh Loebner created the Loebner prize, a variant of the Turing test for chatbots.

In 2016 Manchester is the European City of Science and there are events throughout the year to celebrate this, see here for details. CoSAIM, the event in which EKA-labs are competing, is fictional, as is EKA-labs itself.

Geshtu is named after the ancient Sumerian god of intelligence.

The specifications of Geshtu that Barquith reads out are all an order or two of magnitude larger than the current most powerful supercomputers, and it was probably this that raised his suspicions.

Chapter 2

Ellie has seen a chess board on which it appeared that Alice and Kenneth had been playing some kind of game. Next to the chessboard was a hand-written note saying `Another late knight tonight, we must take a tour around the building'. This hints at a knight's tour around the chessboard. (A knight's tour is a sequence of moves on a chessboard such that the knight visits each square once and once only.) The only word starting with a capital is `We' in the bottom left corner, and so this is the most likely place to start. Using this corner as a starting point, there is only one way to travel around the board using a sequence of knight's moves so that the words spell out a coherent message.

The plaintext is

We will need to be very careful. She is much smarter than she looks
and the 14th word is 'looks'.

The authors of the books in Alice's office are not accidental. Donald Knuth is a famous computer scientist, best known for his series of books `The Art of Computer Programming' and also for inventing the mathematical typesetting language TeX. Lofti Zadeh is a mathematician and computer scientist who invented an area of mathematical logic known as fuzzy logic. Wolfgang von Kempelen invented the Mechanical Turk, a fake chess-playing computer from the late 18th century. The Mechanical Turk inspired Geshtu's final form in Chapters 5 and 6 and the Epilogue of the story.

This kind of puzzle, where letters or (in this case) words on a chessboard are to be visited in order by following a knights tour is called a cryptotour. Cryptotours were popular in the late 19th century; see here for details.

Chapter 3

Mike has recovered a flight itinerary from Eliza's purse. Ellie thinks that Eliza has been doing a lot of travelling, trying to raise funds for EKA-labs, but Barquith isn't so sure.

Each airport is allocated a 3-letter IATA (International Air Transport Code) code. For example, Heathrow is LHR and Manchester is MAN; you will often see IATA codes on the airport luggage labels. You can find a complete list of IATA codes here.

Replacing each airport with its IATA code spells out the following message:

Geshtu will never function. A new mechanical solution is to be found.
The 12th word is 'found'.

The webpage mimics that of SkyScanner. SkyScanner is a flight comparison website that was founded by two graduates from the University of Manchester. SkyScanner have very close connections with the Alan Turing Cryptography Competition: they sponsor the competition and the Alan Turing Cryptography Day. Rachel Evatt from SkyScanner will be awarding the prizes at the Cryptography Day in April.

Chapter 4

Mike and Ellie leave coded messages for Kenneth and Alice to get them out of the way.

The message is a mixture of letters and numbers, but careful analysis reveals that only the letters A, C, D, E, F, H, L, M, O, P, R, T, U and the digits 0 to 9 are used. Thus, there are 23 symbols, which means it could be a simple susbtitution with three unused letters, but there do appear to be several recurring patterns. What is going on? Looking more closely there are a couple of hidden English words: "HOME" and "ARC", could they be commands or instructions?

In fact the message is written in Logo, a programming language that also has roots in artificial intelligence. Logo was also used to teach children to program (although it has now been replaced by alternatives such as Scratch ). Logo is best known for being a control language for the turtle, a robot that held a pen and could be moved to create drawings. The letters in the message are the turtle commands PD (pen down), PU (pen up), FD (forward), LT (left turn), RT (right turn), HOME (return to the start), ARC (draw an arc of a circle). The numbers are arguments to the commands: for example RT 135 means "make a right turn of 135 degrees". A list of common Logo commands is given here. Following the instructions will write out the message. You can do this by hand or using a logo interpreter; there are several available online, for example this one. It's a good discipline to type in code (it means that you have to time to think about what you are doing), but if you just want to see the answer, you can copy and paste the below text.

PD FD 10 RT 135 FD 7 LT 90 FD 7 RT 135 FD 10 LT 90 PU FD 5 PD LT 90 FD 10 RT 90 FD 10 PU RT 180 FD 10 LT 90 FD 5 LT 90 PD FD 5 PU RT 180 FD 5 LT 90 FD 5 PD LT 90 FD 10 PU FD 5 PD LT 90 FD 10 RT 90 FD 10 PU RT 180 FD 10 LT 90 FD 5 LT 90 PD FD 5 PU RT 180 FD 5 LT 90 FD 5 PD LT 90 FD 10 PU FD 10 PD LT 90 FD 10 LT 90 FD 5 RT 180 FD 10 PU RT 90 FD 10 LT 90 FD 20 PD LT 90 FD 10 PU RT 90 FD 5 RT 90 FD 10 RT 180 PD FD 10 RT 135 FD 14 LT 135 FD 10 RT 90 PU FD 20 RT 90 FD 10 LT 90 PD FD 10 LT 90 FD 5 LT 90 FD 10 RT 90 FD 5 RT 90 FD 10 PU FD 5 PD FD 10 RT 180 FD 5 LT 90 FD 10 PU LT 90 FD 15 LT 90 FD 5 PD ARC 360 5 PU RT 90 FD 10 PD FD 10 LT 90 FD 5 LT 90 FD 10 LT 90 FD 10 LT 180 FD 5 RT 90 FD 10 RT 90 FD 5 LT 90 PU FD 5 LT 90 PD FD 10 RT 90 FD 10 RT 180 FD 10 LT 90 FD 5 LT 90 FD 5 RT 180 FD 5 LT 90 FD 5 LT 90 FD 10 PU HOME RT 180 FD 20 LT 90 FD 15 PD LT 90 FD 10 RT 90 FD 10 RT 90 FD 5 RT 90 FD 10 RT 180 FD 10 RT 90 FD 5 LT 90 PU FD 10 LT 90 PD FD 10 LT 90 FD 5 LT 180 FD 10 PU FD 20 PD RT 90 FD 10 LT 180 FD 10 RT 135 FD 14 LT 135 FD 10 PU RT 90 FD 10 RT 90 FD 5 PD ARC 360 5 LT 90 PU FD 15 PD ARC 360 5 PU FD 10 RT 90 FD 5 RT 180 PD FD 10 RT 135 FD 14 LT 135 FD 10

The plaintext is

MEET IN STORE AT NOON
and the 5th word is 'noon'.

If you are interested in learning more about Logo there are plenty of online tutorials available, like this one. The UCBLogo language was used to create the code. You may be interested to know that higher-level programming concepts such as loops and variables were used to develop the code, which saved typing the same instructions out again and again.

Chapter 5

Mike and Ellie send a coded e-mail to Barquith to let him know what they have found out.

The message consists of emoji, all of which are available in the Unicode standard. The message is a substitution cipher, but with multiple symbols for the most common letters 'E', 'T', 'I', 'O' and 'N'. The spacing between words is largely preserved, which makes it easier to crack than codes with the spaces removed. The message is quite short, which means that if the spaces are removed it becomes significantly more difficult to decipher.

Using frequency analysis combined with analysis of the short words eventually leads to the following plaintext:

You were right to be suspicious. We have discovered that the conspiracy is bigger than Kenneth and Alice. Eliza is also involved! Geshtu will still be demonstrated at ESOC CoSAIM event later tonight. We will try to meet you there. E and M.
The 12th word of the plaintext is 'conspiracy'.

The UTF-8 character encoding (famously designed on a diner placemat) allows a representation of all possible symbols defined by Unicode. It is widely used to handle extended character sets and includes emoji. The code in this chapter was created by replacing the letters in the plaintext by the appropriate UTF-8 symbols. The final look of the characters depends on the software (web browsers, phones) and the fonts available; it took a while to find a font with symbols that we liked.

Chapter 6

Barquith is at CoSAIM, the event at which Geshtu will attempt to pass the Turing Test. As he looks for Mike and Ellie, the demonstration of Geshtu begins but it doesn't go to plan. Geshtu appears to break down and reads out the following sequence of letters:

BAARCGNQSUTEESEUAHUEEHLHSNSTSOEIDRETDPAUEGDWIERISENIX.

Frequency analysis doesn't help: the distribution of letters is as one would expect in English. This suggests that it's a transposition cipher: the letters have remained unaltered, but their positions in the message have been permuted.

Suspecting that the message is for Barquith, one can look for his name in the message. Note that 'B', 'A', 'R', 'Q' occur in the following places:

B 1
A 2, 3, 17, 39
R 4, 34, 47
Q 8
Note that BARQ appears at places 1,2,4,8. This suggests that the next letter of the message can be found by taking the place number of the previous letter and multiplying by 2. Thus we should expect to see a 'U' in place 2*8 = 16 and an 'I' in place 2*16=32, as indeed is the case.

Continuing this, we should expect a T in place 2*32=64; unfortunately there are only 53 letters. However, when we get to the end of the message we can continue to count from the start: so we count out 64 letters by first counting out 53 letters, returning to the start of the message, and then counting out the remaining 11 letters. As predicted, there is a 'T' in place 11.

The next letter is in place 2*11=22 and is a 'H'. We then continue this process, looking at letters in places 2*22=44, 2*44=88 (which,as we are wrapping around, means place 88-53=35, 'E'), etc. Continuing this process until we return to the start of the message gives the plaintext

Barquith we are on stage hidden inside Geshtu please rescue us
and the 10th word is 'rescue'.

There is some detailed mathematics at work here. We are really using modular arithmetic. Modular arithmetic is also known as 'clock arithmetic' and deals with arithmetic when numbers are allowed to 'wrap around'. More precisely, modular arithmetic mod n can be thought of as normal arithmetic, except that we only look at the remainders after division by n. Clock arithmetic is modular arithmetic mod 12: for example if it is 9 o'clock now, then in 5 hours time it will be 9+5=14=2 o'clock (as 14 has remainder 2 after division by 12).

In this cipher, the letter in the nth place of the plaintext occurs in place 2n mod 53 of the ciphertext. (We are working mod 53 as we need to wrap around after the length of the message.) We don't need to calculate 2n: instead all we need to do to find the place of the next letter is to multiply the current place by 2 and then take the remainder after division by 53. Can you prove why this is the case?

Modular arithmetic is hugely important in many areas of mathematics and particularly so in number theory. It has many applications to cryptography. Indeed, several currently used forms of cryptography owe their security to the fact that the discrete logarithm problem is difficult to solve. The discrete logarithm problem is (essentially): given a (very large) prime number p, find the smallest positive number n for which 2n = 1 mod p. (Can you see from the message in this chapter what the smallest number n is for which 2n = 1 mod 53?)

The voice of Eliza in the audio code was performed by Professor Daniele George. Professor George is Professor of Radio Frequency Engineering in the School of Electrical and Electonic Engineering at the University of Manchester. She gave the Royal Institution Christmas Lectures in 2014 and regularly appears in the media discussing science, technology and engineering. We are very grateful to Professor George for her involvement in the competition.

Epilogue

Eliza and her conspiracy have been unmasked. Mike kicks Geshtu, who displays a final message.

The code is a straightforward substitution cipher and can be cracked by using frequency analysis. Be careful though: different sizes of the same symbols represent different letters. The plaintext is

This has been an interesting game. I think Eliza has learned that in her circumstances the only winning move was not to play. I have enjoyed my little adventure with Mike and Ellie and I look forward to meeting you again. Hasta la vista baby. Geshtu
and the 15th word is 'circumstances'.