Welcome guest.
The ALAN TURING
Cryptography Competition.
(edition 2013: #2).
You are reading the website of the 2013 edition of the competition, which ended on Wednesday 1st May at 12:00 am. We are planning to run a new edition next year, to start in January. The website for the current edition can be found here. For any particular enquiries you can contact us on cryptography_competition@manchester.ac.uk.
The Tale of the
Egyptian Enigma
Is released!
Is released!
Is released!
Is released!
Is released!
Is released!
Is released!
Is released!

# Solutions.

## Chapter 1

Having been handed back Turing's leather satchel, Ellie finds some old pieces of paper.

This is, essentially, a jigsaw. The original message is

I am fed up with that Barquith and his games. I am ready to give up on this Egyptian Enigma problem and get back to my real work for a while... On the other hand, I think the Old Colossus knows more than he's letting on. A.M.T.

The 40th word is Colossus.

A.M.T. is, of course, Alan Mathison Turing. Perhaps best known for his work in breaking the Enigma machine during World War II, Turing moved to the University of Manchester in 1948. Whilst at Manchester, he wrote some of the first ever computer programs, including one for the Baby (the world's first stored-program computer, a replica can be seen at the Museum of Science and Industry in Manchester) that performed long division - a significant challenge at the time! He died in 1954 aged 41, most likely committing suicide as a result of a conviction for homosexuality.

## Chapter 2

Having realised that the `Old Colossus' probably refers to Max Newman, Mike and Ellie head over to the School of Mathematics where they meet the lecturer Jo Smyth. She directs them to a display of Newman's research papers.

This is an example of steganography. In steganography, a message is hidden or disguised within another message or image. Some of the letters in the image are in bold and italicised:

noosteemdetcurtsnocereceiplanifmotaythgim
Mighty atom. Final piece reconstructed. Meet soon.

The 7th word is soon.

Although Jo Smyth is fictional, Max Newman is a real person. He was a lecturer at the University of Cambridge, and in 1935 gave a series of lectures which were attended by Turing and inspired Turing to work in mathematical logic. He worked at Bletchley Park during World War II, and together with Tommy Flowers built the `Colossus' - the first digital programmable computer - that was used to crack the Lorenz cipher. (The Nazis used several different codes during the war, not just the Enigma machine, and they all needed different techniques to crack.) In 1945, he moved to the University of Manchester as the Fielden Chair (=professor) of Mathematics and was instrumental in recruiting Turing to Manchester. He later worked in an area of pure mathematics called combinatorial topology (you can read a quick explanation of what topology is about here).

## Chapter 3

Mike and Ellie think that `the Mighty Atom' might refer to Ernest Rutherford and head back to the Museum to investigate. Mr B shows them to Rutherford's old laboratory, where Mike kicks Rutherford's old desk to discover a secret hiding place. Inside is the following telegram.

This is a substitution cipher, where each letter in the ciphertext is replaced throughout by another letter in the plaintext. The first thing to do with a cipher like this is to try frequency analysis on the letters. Counting each letter you'll see that

 letter: frequency: 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 36 13 2 73 23 32 14 29 1 37 32 18 2 8 14 58 63 12 8 27 40 22 0 9 1 9

In English, the most commonly occurring letters are ETAOINSHRDLUCMFWYPVBGKQJXZ (in that order). This suggests that `D' - 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.

However, it's possible to be much smarter and not rely on counting letters. First note that `PJD' occurs quite frequently either on its own or at the beginning of another word. This suggests that `PJD' is probably `THE'. The letters `U' and `Q' appear on their own, and so are probably `A' or `I' (or the other way round). The final word of the telegram looks like a signature. So far, it reads `H?***TH' where the `?' is either an `A' or `I'. The only character in the story that fits this is `HAWORTH' (who appeared briefly in Chapter 1), and this tells us that `JQSKFPJ' = `HAWORTH'. We can then start reconstructing the message, and - after some trial and error - decode it as follows:

I trust you are well. As you know, the latest shipment of Egyptian antiquities arrived last week. Everything arrived safely at the museum, but the jade Cleopatra - probably the most valuable artefact of them all - was missing. I have just received a letter from that dreadful scoundrel Barquith. Apparently he has the statue and has put it into, in his words, safe-keeping. He has even told me where he has hidden it but, as usual, there is a catch. he has sent the location to me in code, using that infernal Egyptian Enigma device i told you about. He knows my machine is broken, and has asked me to pay him to mend it for me - the despicable rogue! You are a practical man Rutherford, perhaps as a favour you could fix it instead? Haworth

The encryption used is

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

The 27th word is Cleopatra.

Ernest Rutherford was a hugely influential physicist, best known for his work on determining the structure of the atom. He worked at the University of Manchester from 1907 to 1919. His most famous experiment was to fire alpha particles (two protons and two neutrons) at thin gold foil. Most alpha particles passed straight through, but some were deflected backwards. Rutherford used this experiment to determine the now-widely accepted model of the atom as a small positively-charged nucleus surrounded by a cloud of electrons. He received the Nobel prize for Chemistry in 1908 for earlier work on radioactive half-lives, and how one element can decay into another.

## Chapter 4

Having escaped from the Museum basement, Mike and Ellie go to the Schuster Building. They spot Mr B leaving a piece of paper on a table outside the Moseley Lecture Theatre.

The clue is that the code was left on Moseley's table. Moseley was a physicist at the University of Manchester who did pioneering work on the periodic table. The numbers refer to the atomic numbers of chemical elements:

 Atomic number Element 34 18 6 1 24 89 19 4 1 53 60 35 8 90 68 16 16 18 27 15 1 47 92 16 Se Ar C H Cr Ac K Be H I Nd Br O Th Er S S Ar Co P H Ag U S

Search crack behind brothers sarcophagus

The 5th word is Sarcophagus.

Henry Moseley was a physicist at the University of Manchester between 1910 and 1913. Before Moseley's work, elements in the periodic table were listed in order of atomic weight (now known to be the number of protons plus the number of neutrons in the nucleus), but with some elements swapped around so that elements with similar chemical properties appeared in the same vertical column of the periodic table. Moseley discovered how to use X-ray diffraction to calculate the atomic number (the number of protons in the nucleus) of elements; ordering elements by atomic number, rather than weight, removes the need for swapping around elements in the periodic table. In 1914, Moseley volunteered to serve in the British Army during World War I. He was killed by a sniper in 1915, aged just 27. Had he lived, it is believed that he would have been awarded a Nobel prize.

## Chapter 5

After deciphering the message left by Mr B., Ellie and Mike find an old manuscript in The Manchester Museum.

The code is based on Egyptian hieroglyphics and each hieroglyph represents a different letter of the alphabet. In fact, all hieroglyphs in the message appear on Gardiner's Sign List, a standard reference for hieroglyphics. The code uses more than one symbol for each letter, which makes frequency analysis more difficult, but it does use several well-known features of hieroglyphics which can provide the means to crack the code.

The cartouche, the oval symbol, indicates that the word within is a name (technically a royal name). The name is eight letters long and is likely to be one of the characters in the story ... how about Barquith?

Hieroglyphs can be written in different directions (left to right or right to left), but the direction in which the characters face tells you which way to read them. If the faces are turned to the left, then you read from the left; if the faces are turned to the right, then you read from the right. Within the cartouche the animals are all facing to the right, so should be read from the right, which gives the symbols for the letters B, A, R, Q, U, I, T, H.

It is now possible to proceed by filling in these letters in the rest of the message and using educated guesswork to deduce the meaning of the other symbols. For example, you can look at the two and three letter words trying the obvious possibilities: of, to, by, and, the, ... That said, there is a shortcut in this code: the letter represented by each symbol is the first letter of the standard name of the symbol. For example, in the name Barquith (bier = B), (arm = A), (ram = R), (quail = Q), (vulture = V/U), (intestine = I), (turtle = T), (hair = H). The complete table of symbols that were included in the code is below (although not all symbols were actually used in the end):

The decoded message is

machine appears to be primitive means of encoding messages moving disk surrounded by fixed ring and large handle disk and ring both have twenty-three characters of classical latin alphabet arranged in order central spindle connects disk to cog with twenty-three teeth that meshes with smaller cog connected to control disk with three stops irregularly spaced around circumference when lever turned control disk rotates until next stop reached, so that alphabets move relative to one another blasted control disk broken no idea how to decipher barquiths code.

The thirty-fourth word is Spindle .

Jesse Haworth was textile merchant and businessman in Manchester who funded and supported Egyptology in the late 19th century. Although the incidents related in the story are fictional, Haworth did fund a number of archaeological expeditions to Egypt and was a collector of Egyptian artefacts. He also put forward money to fund the building of The Manchester Museum and donated money and his private collection of Egyptian antiquities to the museum in his will.

## Chapter 6

Mike and Ellie have to decipher Barquith's clue to the location of Haworth's stolen goods. The clue was encoded by a working Egyptian Enigma device, but there is only a sketch of a broken version of the machine.

The decoded text from chapter 5 gives a description of how the machine works and the all-important control wheel is the "logo" that appeared in chapters 1, 2 and 4.

The code is a polyalphabetic cipher, which means that different substitution alphabets are used. In this case, the alphabet is changed for every letter of the message by moving the disk on the machine. The fictional machine uses a cipher disk, a method that was actually developed much later, in the 15th century. In the machine, the central disk is connected to a cog with 23 teeth that meshes with a smaller cog with 13 teeth. Advancing each gear one tooth corresponds to moving the alphabet on the disk along by one letter relative to the fixed alphabet on the outer disk. The control disk has only three lugs separated by 3, 4 and 6 teeth on the cog below (3 + 4 + 6 = 13) so the alphabets can move by 3, 4 or 6 places relative to each other between each letter of the code.

Each complete revolution of the control disk advances the alphabet by 13 letters and because 13 and 23 are coprime (have no common prime factors), the control disk must be turned 23 times before the system returns to its initial position. Assuming that the machine starts when a lug of the control disk is at the stop (if it isn't, just turn the handle until it is), then there are 3 possible positions for the control disk and 23 possible positions for the central disk, which gives 69 different starting positions! An important point is that every possible starting position can be reached before the sequence repeats.

In order to decode the message, try every possible starting position and see whether the message decodes. The direction in which the disk rotates is also unknown, but we can consider both possibilities at once by decoding from the disk to the ring and also from the ring to the disk. Although there are 69 cases to try, as soon as it is obvious that the message doesn't make sense, that case can be discounted. It is possible to write a computer program to do this, but the fastest way is actually to print out the machine, cut out the ring and do it "by hand". The first letter is a Y, which gives the starting position of the disk and the control disk is set so that the alphabet on the central disk is advanced by 4, 3 and then 6 places repeatedly.

The decoded message (after replacing v's for u's where appropriate) is

Your property is guarded by a sacred bird.

The eighth word is Bird .

The most well-known polyalphabetic cipher is probably the Vigenère cipher and, in fact, this code can be thought of as a Vigenère cipher with a non-standard alphabet and a very long (69 letter) keyword.

## The Epilogue

The bonus cipher is a mixture of the 6 ciphers used during the competition. The message reads `Mike and Ellie will be back in a new adventure next year'. Once you decipher the first 9 words, you can probably guess the remainder of the plaintext. In particular, you can guess that the Egyptian Enigma machine in Chapter 6 must decipher LSOERCKLB to `adventure' - and from this it is easy to work out the initial settings of the machine. It is then straightforward to decipher Chapter 6 (assuming, of course, that the same initial settings are used in both Chapter 6 and the Epilogue). There is an important cryptographic principle here: you should never encode two messages with the same key - this makes it significantly easier for the cryptanalyst to decipher either or both messages. (This is one reason why the way in which the (real) Enigma machine was actually used during World War II so complicated - to prevent messages being sent using the same key.)

 This competition is organised by and sponsored by