Turing's Enigma Problem (Part 1) - Computerphile

a movie has just come out called the imitation game starring Benedict Cumberbatch as Alan Turing and Keira Knightley as one of the team that work with cheering her name was Joan Clarke 5 minutes and 34 seconds you said to do it in under six and I'm sure many of you know Alan Turing worked at the government code and cypher center at Bletchley Park throughout the war right from when it broke out in 1939 right through until the end of war 1945 Alan Turing was at Princeton doing research with another very famous mathematical logician called Alonzo Church he returned from Princeton in 1938 but even in that year from 3839 is very clear that he was contacted by G C and C s even though he wasn't employed by them and became a sort of consultant became acquainted with all of the difficulties that were gonna hit the Allies when war broke out as seemed inevitable in deciphering German ciphers that have been done on this enigma machine now an awful lot of the material that I am going to be using today really uses as a reference book this one by Andrew Hodges it's called Alan Turing the Enigma this has been reprinted republished I think in a slightly new edition because the imitation game is based on this account of cheering's life now a back a long way prior to is used by the German armed forces it was just a simple commercial cipher machine and it was a pretty reasonable system but I suppose you could say that the number of possibilities the the degree to which it scrambled up the message was considerable but not ultra ultra safe I think it was a machine that as they say in the Crypt illogical trade was designed to discourage casual snooping rather than to withstand serious attention from experts in the field and what I want to do is to go through with you in this video the components of the system then in a later one summarize and say that's the pearl the problem they were up against how do you make a machine that could help you decipher that code if you didn't know the settings of the machine that you created it in the first place I mentally cross refer you to some footage on our sister channel numberphile James grime has done a couple of videos on numberphile which actually use a real live in nygma machine that belongs to Simon Singh the lucky James gets to use the real thing and I would strongly recommend if you're puzzled by all of this go and watch those two videos one of them is just a generalized introduction to the enigma the other one that explains precisely why the enigma machines big flaw was that it could never earn cipher a letter as itself believe it or not that is a big big security flaw and just provide a way in for people who want to crack that particular code the enigma itself looks at first sites a bit like an ordinary typewriter it's got a typewriter board layout this typewriter keys but you then notice that if you switch it on and it is battery powered in the area just above the keys it's going 26 further keys you'll have 26 places where a lamp can light up a letter see my presser t and it will light up as a G what else is there inside this machine how does the key press get through to illuminating a lamp well in the most amazing and convoluted way there's a set of rotors here these rotors have 26 alphabetic letters engraved around the circumference sometimes you don't get a letter you get numbers 0 1 3 2 26 but it comes down to the same thing in the end when the lid is closed on top of them the letter as it were pointing upwards on the rotor anywhere between eh-2-zed shows up in three identical looking windows perhaps the easiest way to think of it in for those of you viewing who were relatively young can you remember back to your family's first ever car where it had an old and odometer you know a mileage indicator on the dashboard which wasn't all done in electronics it was actually driven off the engine and you actually had little wheels moving in front of you and on the right-hand side would be the tenths of a mile or tenths of a kilometer and every time that I got up to 9 it would nudge the dial to the left of it to move on one place and so on the principle is exactly the same on the Enigma the right-hand rotor moves the fastest and at a certain stage you will nudge the next one into moving on a knotch the left-hand rotor is the slowest moving of all and once the lid is closed on the Enigma all you see is the letter on the rotor that's uppermost showing through the windows at the top now complication upon complication within each rotor there is if you like on the two sides an input stud and an output stud and they are cross wired if you could break open as is shown here the rotor mechanism you would see a whole bunch of 26 wires in there which are cross wiring an input stud to an output stud so you might get a cross wide 2j b cross wire to q-see croft white W something like that when enigma first came out there were three sorts of rotor wheel numbered 1 2 and 3 in Roman numerals typically in the German instruction manuals a rotor of type 2 would not be cross wired in the same way as a rotor of Taiwan and similarly a rotor of type 3 will be a completely different cross wiring I think many of you will know the number of ways you can arrange three things on a spindle like that is three factorial which is six six possible orderings of the rotors on the spindle so you can begin to see the multiplication of the number of combinations about how this thing could be set up in the first place you've got different orderings on the spindle you've got different cross wirings within different sorts of rotors so the very basic machine there that was just about it you fed the signal through the rightmost rotor through the middle rotor with a different cross wiring and mapping through the left-hand rotor and then there was what the Germans called a reverse er sometimes English called a reflector what he would do was to return the signal bad fire a different stud on the left-hand rotor so it would take a different journey back through the machine to the way it came in now here is the secret of why it never mapped a letter to itself it couldn't because to make that effect happen you'd have had in the reflector drum here to say ah it's coming out of the a Schloss I'm going to return it back through the a slot it wasn't electrically set up to enable you to do that you effectively had to decide to cross wire in that reflector to something different and I think here if you look carefully a is actually cross Y just thing like W now in the early three rotor enigma that reflector had fixed cross wirings which was the same on all Enigma machines so your current goes back through a different route and then finally lights up a lamp on the lamp array just ahead of the keyboard over here so that's the way it was up until about the mid 30s but then as the German armed forces were taking more and more interest in these things and say always we could beef them up these could be made into military-grade security devices they did two things first thing they said we're not just going to have three rotors in six combinations we're going to do the following we're going to invent two more rotors called four and five amazingly here's what you now do we will choose any three out of those five rotors well the ways of picking 3 from 5 is 5 times 4 over 1 times 2 5 factorial over 3 factorial ounces 10 but for though each of those 10 ways you can still jumble them up in sick weighs on the spindle 10 times 6 is 60 so classic army airforce enigma use this pretty well throughout the war you chose 3 from 5 and the 3 gyros could be put in the spindle in a certain way now comes the real killer if that wasn't bad enough the Armed Forces decided that on the input to the machine on the output they would have another cross wiring board called the plug board now this one's simple to understand it's basically got sockets numbered from A to Z and you're given chunks of wire if the instructions say cross link a to J that's what you did cross link B to are you did that as well usual operating practice 10 out of 13 of those plugs would be Crosswhite and wired up you could wire up in pairs but you didn't absolutely have to wire up everything if you left something unwired or unstick it as they would say in german then that's fine I mean a letter Q might have no plug in it going absolutely nowhere fine so Q maps to Q is not altered to anything else at all but like I said typically 10 out of 13 will be wired up so this is getting to be a pretty complex machine now and you would think by golly surely this is enough security for anybody well what's good enough for the Army in the Air Force in almost any Armed Forces in the world is never good enough for the Navy I think it's that case in the UK certainly that way in the US and it certainly was that way in Germany Admiral Karl dönitz who was the head of the German it was a very smart guy some people theorize and maybe they're right that he strongly suspected as a war went on that maybe Army and Air Force enigma was being decrypted successfully sometimes by the Allies he was determined to make the the German Navy version of ending my far harder so first thing he did was say alright we'll stick with three rotors for the moment but it doesn't choose three from five its choose three from eight and by the time you would set out how many ways to pick three from eight and then multiply by six for the number of ways you can arrange the three of chosen on the spin ball the answer is 336 and as daunting one of the things that I think does need a bit of careful explanation it's not very well done in the various books about Bletchley Park and enigma and how it worked is to explain what these so called a ring setting as well now the straightforward internal cross wiring is simple you just look at the top row and for every letter you follow vertically downwards and you say okay in a tight one rotor a on one side gets mapped to e on the opposite side B gets mapped to K C gets mapped to M all the way through to Z gets mapped to J but to complicate matters just a little bit further every one of these rotor rings add a little blob of paint associated with it showing which was the proper setting with a at the top and a against the dot of paint but it had the ability to be able to turn the thing in such a way that you still have a beam against the canonical blob something else was so you could set a little notch that held it in position but in the place that actually was not the standard position if you put your button your ring setting button against the letter B it had the effect of making a map across to what B would normally have turned into B would normally have turned into K B goes to M C goes to F D goes to L and so on it's just an offsetting mechanism it's just moving as it were the bunch of wires inside the so that is what a ring setting is it's basically an initial offset that changes the mapping a versus up Li makes things even more complicated final bit of complication now just so that we're completely mind blown and thinking how on earth could this ever be decrypted by anybody that you might think that just as a car's odometer would go all the way up to nine on the right-hand side and the moment it turns over at nine it would nudge the next one on on the left some bright spark had the idea that it might give more security if you made different wheel types have different turnover points and a donut is extra rotors six seven and eight even worse they turn over twice once it's said and once a dam in the middle of the alphabet actually it's not a good idea if you think about it and I'll tell you why imagine you know because you've done a lot of work on this you're pretty sure that's at the moment the machine has got a type one rotor at the right and you're also pretty sure from the Crypt analytical work you've done that it's currently on the letter n you then type in three more of the receive to ciphertext letters and you certainly see you've so many fine things going completely weird this isn't just the same wheel turning something's happening it shouldn't have come out looking like this this sequence oh it's turned over the middle rotor so if I think it was on N and it's turned over the middle rotor on a cue then it follows that that right-hand rotor must have be of type 1 and I wanted to know that all along so these turnover points because they weren't all at said to a which would have made it all look uniform you know whenever anything turns over it that's way it does it has this little signature that if you're very careful new cryptanalysis gives the game away how is it all gathered together if you were very lucky in the very early days the war you didn't even have to try and crypt analyze this incoming ciphertext traffic either by hand or by machine if you could do what Bletchley Park called a pinch you could actually get a secret agent or an army officer to just accidentally be able to get hold of the code tables issued to the German armed forces kitchens have to do any cryptanalysis at all either by a hand or by using this very expensive machinery that we'll be talking about next time this electromechanical bomb you didn't have to use those it's all here but as James makes very clear in his videos if you did get that bit of luck it never lasted long you maybe got a month's worth and then it ran out or somebody back at headquarters said I'm not happy one of our code books seems to be stolen and disappeared tell you what even though the six months to go on it we're throwing it away and we're issuing another one just to be on the safe side we've assumed and it's quite right that the good thing about in enigma from the Crypt analysis point of view it started off life as a commercially available totally open machine so you might think well the wiring inside those routers then three of the routers at least one two and three will be known yes but of course the moment the luftwaffe and the arm is starting introducing two more routers you then got the problem of can we steal these things or do we have to work out from first principles and with rather a lot of advanced group theory in mathematics and a lot of known ciphertext and plaintext from all sorts can we work out what the wiring is in those routers without actually having them and the answer is eventually yes but it's very very nice if somebody helps you on this front what did you need to know in order to decrypt a cipher stream done with enigma that your listening stations had picked up it was transmitted in Morse as single letters sent to Bletchley Park what do you need to know to make any sense of this number one which rotor wheels are in use number two what is the ordering left-to-right of those rotor wheels number three for each of those rotor wheels where has that stud been allocated that does the ring setting against which letter forth thing which we haven't mentioned very much but which in the next video will say a lot about the operator himself usually himself not herself had to also do what was called a message setting for this particular message every separate message had to have a different message setting it wouldn't have been safe just to keep using the ring settings alone without any alteration to those so that's has to be worked out as well and finally last but not least the plugboard cross connections had to be worked out now that's a lot of stuff in the very early days of simple enigmas whether early three rotors not chosen from anything else just three we'll find out next time that the Polish cipher Bureau had a lot of success by hand and with a very simple machine in getting things decrypted but the moment you start adding more rotors plugboard and all the complications you rapidly find that you just don't have enough time in the day to decrypt all that you'd like to do the sheer weight of cypher traffic takes over you have to mechanize the wires of the circuit are inside the rotors so when the wires turn the battery will connect to a different bulb let's try and see that happen six options are wrong that means your rotor position is wrong and what you do is you go click you check the next rotor position and you go through all that again

Channel: Computerphile

Views: 1,285,711

Keywords: computers, computerphile, Alan Turing (Computer Scientist), Enigma Machine, Mathematics (Field Of Study), computer science, university of nottingham, professor david brailsford

Id: d2NWPG2gB_A

Length: 19min 0sec (1140 seconds)

Published: Fri Nov 28 2014

Reddit Comments

[u/[deleted]]

Well there goes my plan to do homework!

[u/b4ux1t3]

One of my all-time favorite Computerphile series.