COMP2048 Theory of Computation S. S. Chandra 1 Codebreaking Lab Dr S. S. Chandra The deciphering of secret messages in World War II was one of the main drivers of the computational age we currently live in. Cipher machines developed around this time were sophisticated enough that breaking the coding system by hand was no longer feasible. This lab was designed to allow you to follow in Alan Turing’s footsteps as he tackled such problems, helping building one of the world’s first computational machines, the Bombe machine used to crack the code generated by the German Enigma Machine and later the more general-purpose electronic computer called the Colossus. In the first part of the lab, we study the much simpler Caesar cipher used during Roman times that can be broken by hand, though we shall use computers instead. In the second part, we will use a pre-built simulator of an Enigma code machine in Python to crack Enigma coded messages just as the Allies would have done in World War II. Lastly, we will cover general code breaking tasks for those looking for a challenge. Part I – Caesar Cipher (5 Marks) The Caesar cipher is a simple plain text substitution cipher, where you replace your message alphabets to the same alphabet but shifted by a constant offset. ——————————- [See the starting code provided in test_caesar.py and test_caesar_break.py] a) Use Python dictionaries to create a shifted directory of letters that will allow you to map your letters to shifted ones, so that you can use the encrypt and decrypt code provided in test_caesar.py to encode and decode Caesar cipher messages. Demonstrate that your code works for your own custom message by running the encrypt and decrypt methods within the script provided. (2 Marks) b) This type of cipher is easily broken by observing that some letters in the English language occur more often than others, such as the letter ‘e’. Use the initial code provided in test_caesar_break.py to write an algorithm to break the code and decrypt the message provided. (1 Mark) c) Extend your script to break any Caesar cipher message of an arbitrary shift if you haven’t already done so. Test out your code with your neighbour or mate by exchanging ciphered messages of unknown shifts between yourselves. (2 Marks) Part II – Enigma Cipher (8 Marks) The Enigma machine was a commercial electro-mechanical cipher device introduced to the public before World War II for encrypting communication. It was adopted by the German military with various enhancements to make it more secure before the war broke out. It can be seen as the ultimate plain text cipher system that not only incorporates shifts but also permutations that change for every letter encrypted by using a combination of rotors. You can find a detailed description of the machine COMP2048 Theory of Computation S. S. Chandra 2 and its internal workings in (Copeland, 2004) [Enigma, Section 2]. We may also find the Enigma videos in the Computation YouTube Playlist helpful. For our purposes however, all we need to know is that the machine maps a letter to another letter in our alphabet using two main mechanisms. Firstly, there are three rotors that can be chosen from a set of 5 or 7 distinct rotors. Each rotor maps an input letter to another output letter with a shift determined by its rotation rate. All available rotors have different rotation rates and any combination of three can be chosen to be used within the machine for ciphering. The result is that the input letter passes through all three rotors to thoroughly jumble up the shifts to produce the output letter. The starting positions of the three rotors dictates the rotational offsets of the cipher and is called the window positions or key. The window positions change as the cipher is used, so that the initial window positions are required to decrypt messages. Lastly, there is an override mapping mechanism especially outfitted for the Germany military called the plugboard. The board allows one to add additional mappings of individual letters to other letters even before the rotors are applied. ——————————- [See the starting code provided in test_enigma_simple.py and test_enigma_break.py] Shakes the Horrible has decided to purchase a set of Enigma machines to ensure communication with his armed forces (consisting mainly of Spider Monkeys) is secure as possible. a) Demonstrate a working Enigma machine with the given simple example script. (1 Mark) In his arrogance however, he has decided to force his military to always use the window positions SSC as those are the initials of his name. He is also a cheapskate! He hasn’t even bothered to purchase the plug board or any additional rotors, meaning he only has access to rotors I, II and II. b) Decipher Shakes’ message to his military given in the example script using the Enigma machine simulator. (1 Mark) After realising that his military forces are taking heavy losses, he decides to take the advice of his generals and allows a different fixed, but hidden window positions for all further communications. He however still refuses to buy the plugboard. He does decree though that all messages are to end with the phrase “Hail Shakes!”. c) Using the known end phrase, phrases like which are called cribs, write an algorithm to break Shakes’ new code into the provided script and decrypt the message provided. (3 Marks) d) Add a counter to your script to keep track of the number of tries. How many attempts does it take to crack the code? How long did it take on your computer? How long do you think it would’ve taken for a computer in the 1940s?! (1 Mark) e) If Shakes the Horrible wasn’t so ignorant and worried about money, he would have purchased both the extra 2 rotors and the plugboard. How much longer would have the cracking his code taken on your computer? An estimate as a number of tries or minutes/hours is sufficient. (2 Marks) COMP2048 Theory of Computation S. S. Chandra 3 Part III – Code Breaking (2 Marks) A number of sophisticated encryption schemes can be broken with some simple prior knowledge of the context in which the message was composed, but without knowing anything about the encryption scheme or device. Crack the following message intercepted by the United States navy that was addressed to a Japanese naval officer in 1941 to reveal its contents. It is actually doable by hand, but you may use Python as well. ——————————- 19 17 17 19 14 20 23 18 19 8 12 16 19 8 3 21 8 25 18 14 18 6 3 18 8 15 18 22 18 11 References Copeland, B.J., 2004. Essential Turing: Classic Writings on Minds and Computers. Oxford University Press, Oxford, UK.
