The Enigma Code

hi can you hear me if I you hear how this is better I'm just gonna hold up my tie for the next 50 minutes that was actually my first radio interview like ever and this is the first time I've talked to more than seven people in my life so bear with me yes as Monica said my name is David Perry I am a Cryptologic mathematician at the at the NSA and during the summer I teach three week course and cryptology how many of you have heard of CTU I maybe even have done cty excellent yeah I just finished a class a week and a half ago in Lancaster Pennsylvania at the Franklin Marshall campus and a lot of this material comes from that class and I enjoy giving this this lecture in particular because a lot of people nowadays seem to know about the Enigma machine you've heard about it it's been kind of popular in in books and in movies in the last ten years the story itself has only been really known to the public for about 30 or 35 years how many of you have heard of the Enigma before Wow yeah have you seen this movie enigma Kate Winslet's anyone any other movies uh that involve the Enigma just call them out when I ask questions just call answers out u-571 how many people have seen that Matthew McConaughey anyone see dude where's my u-boat it's the worst movie ever yeah so the enigma machine is is is kind of well unknown it was a crypto device used by the Germans during World War two but I think most people don't really know how it worked they just know it was used for encryption a lot of people have understood that the Germans thought it was unbreakable and they had very good reason to believe it was unbreakable but in fact it really wasn't unbreakable I guess that makes it breakable it was first broken by the poles in the 30s and that's not so well known but then it was exploited repeatedly in England at Bletchley Park and a lot of people know more that story and Alan Turing's story than the Polish story what I'm going to talk about in this lecture is how the Enigma actually worked how it encrypted messages and what I want you to understand by the end of this talk is why the machine was designed to work the way it worked why did they think that this was unbreakable encryption so what we're going to do is actually go through 2,000 years of Cryptologic history in a very short span of time and I want to hit the high points and and look at why the machine was designed the way it was and you all should understand that by the end of this talk and know exactly how the Enigma worked okay so first of all not only have most of you heard of the Enigma but I think a lot of you know something about cryptology already okay I this puzzle I took this cryptogram was taken from a Lancaster newspaper a few years ago and it's clear what is intended it's an encrypted message the method of encryption is that every ciphertext letter here represents a plaintext letter consistently throughout the message so maybe the M stands for and R and every M in this message stands for an R in plaintext what we have to do is try to figure out which letters represent which other letters and usually people in the audience can tell me at least how to start this particular puzzle because there's there's something kind of obvious and just call it out yeah well just going to point vaguely and sea of voices arises ah someone got the very first word I think they said it was there okay certainly there's there something that stands out there's a three-letter block that really stands out ABC okay it appears twice as a word in this cryptogram and it appears at the beginning of the very first word it might not be the word there what's another possibility these but certainly th e is very common not just as a word but as a trigraph so that would certainly be a good place to start okay and once you guess at part of the message you can fill in your hypothesis you can fill in the other t's HS and E's and then try to go further okay and I think everyone in this room could probably solve this puzzle in less than five minutes okay ah before I reveal the answer to this puzzle I should tell you this is actually an example from the newspaper these puzzles are horrible the answer is always some kind of pun it's some kind of horrible joke but it's not funny and I'm telling you a complete honesty I did this again this year I use these as punishment if my students don't don't quiet down during study hall you know they get distracted I threatened to give them a cryptogram and the first time they're like ooh puzzle sure we'll do that but they're quiet the second time I threatened to give them a cryptogram the solutions are horrible and I do not take responsibility for it this is the answer to the puzzle they're just pawns are stupid they're not rewarding it's like an ice-cream cone without the ice-cream and without the cone it's horrible okay so there is no limit to the heights every man can attain by remaining on the level okay now I'm telling you this technique of encryption this letter for letter substitution consistently throughout the message was actually considered to be unbreakable for over 1,000 years okay if you can believe that why is it that we can look at this puzzle and solve it in less than five minutes any ideas what's one thing that's kind of obvious about about this puzzle that makes it easier to solve what's that patterns there's something even more obvious that we see that helps us spaces why on earth would we give spaces if we were actually using this technique to encrypt things what happens if I remove the spaces okay is this now harder to crack is it impossible to crack okay no because you've already told me patterns is it not the case that you can still see a VC repeated three times in this short message and might you still think that represents t-h-e yes okay so why exactly why exactly do we intuitively know this nowadays this uncrackable cipher why do we kind of understand how to crack it well before I get into that let me give the the technical name for this cipher okay we call this a monoalphabetic substitution cipher there's a single ciphertext alphabet or key alphabet rule that allows you to encrypt or decrypt okay and any scrambling of the alphabet would be a key you could use for encryption okay there's one up there the mathematical term for as scrambling of the alphabet is a permutation okay any permutation of the alphabet gets you a key for this kind of cipher and now at the bottom I wrote down a really large number I claim there's this many permutations of the alphabet okay where does that number come from I heard 26 Mack toriel yeah factorial okay uh 26 factorial that is to say 26 times 25 times 24 all the way down to 1 how do you obtain that answer well that would be too long perhaps for seven of you to call out the answer you know there are 26 choices for what a encrypts to but once you know what a encrypts do there are 25 choices for B and so forth yes the answer is 26 factorial okay would you agree that's a very large number yeah it's about 4 times 10 to the 26th power why do we care that there are this many permutations or this many keys for this cipher system well because there's something a Code Breaker can always do and we want to keep this in mind for the future slides a Code Breaker can always try something called brute force to decrypt something okay what that means is that as a Code Breaker I can just try a random key okay and I decrypt the message with my randomly chosen key oh the first one didn't work I'll try a second key okay try that oh it didn't decrypt try a third key how long do you think it would take in this scenario to use brute force too long too long even with computers too long as a code maker you want to always make sure that you guard against brute force and the way you do that is to make sure that your system has a lot of possible keys that you and your intended recipient can share to exchange secret messages okay before we go on let me actually take a step back and talk about a very specific kind of monoalphabetic substitution cipher I think I mentioned this on the radio program there's something called a Caesar shift it's a very simple monoalphabetic substitution cipher you encrypt just by sliding every letter over a certain number of fixed spaces to the right okay and there are 26 ways you can do this okay and just as some notation if we're using the method of encryption where a and khrysta D and B becomes E and C becomes F let's refer to this as a Caesar D cipher okay now are there really 26 different shifts of the alphabet or what would Cesar a encryption be kind of lousy where a becomes a and B becomes B and C becomes C ok there's really only 25 then again why do I care about that number well because how would you crack a Caesar shifted cipher you just try the 25 different possibilities and you'll eventually find the correct one ok and this is named as the Caesar cipher after Julius Caesar who talked about cryptology and in one of his books on the Gallic Wars I'd like to think he didn't actually use this type of cipher that he was just talking about a kind of cipher you could use because it is very vulnerable to brute force ok now intuitively even when you take out the spaces everyone in the audience seemed to understand that you could look for patterns you could look for bias in the ciphertext and that would still be a way to crack this kind of encryption ok that's called frequency analysis ok why is it something that we understand so readily but took a thousand years for the world to sort of understand that well I guess if this were a smaller audience I might solicit some actual opinions but it's not the reason for that is well how many of you play Scrabble ok how many E's do you get in Scrabble twelve and why do you get 12 yeah we are in general a very literate society we almost universally we have a high illiteracy rate we know that some letters are more frequent than others the Qs and Z's and J's hardly ever come up in words but in history many cultures were not as as literate in fact literacy rates were very low historically it was the Arab culture that that first had enough people who worked as secretaries transcribing things encrypting things for their bosses and if you're writing a lot of stuff down if you're always using this kind of encryption you cannot help but see bias in letters that this letter appears the most frequently in the language and it wasn't long after they they noticed that that they were able to crack these kinds of codes okay well once you're able to crack a particular kind of code the ball goes back into the court of the code maker okay the code breakers can break can break something well the code makers have to come up with something better okay and they tried a few things like Oh what if you misspelled words or what if you introduce what are called null characters that don't really mean anything but throw off frequencies this worked as spackling for a few centuries but eventually crypt analysts were they knew all the tricks and they were able to crack anything that the code makers tried they really needed to have a conceptual leap forward okay and the conceptual leap forward was the notion of a polyalphabetic substitution cipher the idea that well maybe you don't use the same rule to encrypt every single letter so that the bias in plaintext is seen in the cipher text maybe you have to use a different rule for each letter as you encrypt and the easiest way to do this the first way that was adopted kind of universally was something called the Visionaire cipher okay and here's how it worked maybe you've already read this slide you have to choose a keyword or phrase you agree upon that with your intended recipient for example the word climb and then you write that keyword over and over above your message until you get to the end of the message and above every plaintext letter to encrypt it you just use that particular Caesar shift okay so let's let's take a look at that more more more carefully so if we wanted to take that awful pun sentence there is no limit dot dot and encrypt it with the keyword climb you just keep writing the word climb above the sentence and to encrypt the T I use a Caesar C cipher where a goes to C B goes to D and so forth and the T encrypts to V to encrypt the H I use a Caesar l cipher and if a goes to L H will go to s and so forth and you ask does this really defeat frequency analysis and the answer is well sure it looks like it because a T can become a V but oh look at the end I see a T becomes an F and sometimes a T becomes our V comes from T but V can also be the encrypted version of n so if I count how many bees there are on the cypher it doesn't automatically give me something meaningful okay so the Visionnaire cypher is excellent and in fact was referred to as Lu Chiffre and a chief Rob Lowe anyone speak French pas moi aussi okay so Lucia freh and a chief Rob Lowe is just the cipher in the in decipherable cipher or the uncrackable cipher okay it turns out however and I want to cut to the chase so we can get to the enigma it was very sheaf Rob Lowe it was not an DC problem so we're already going to talk about how to crack the Visionaire okay to do so let me first let me go back to the original sentence and now encrypt it both with the mono elf that we know we can defeat with frequency analysis and the Visionaire method of encryption which we don't yet know how to crack okay why is mono elf bad well because th e always becomes AVC and that's bias that's repetition I can exploit as a code breaker but the Visionaire is great because sometimes th e becomes V SM but o over here th e becomes something different it becomes e PQ but then down there th e becomes something different it becomes e PQ wait a minute wait a minute that looks like a repetition to me I thought the visionary idea was going to sort of eliminate repetition or eliminate bias well it looks like it doesn't eliminate repetition it's reduced it because th e can become V SM but it looks like it twice became the same thing okay is that something we could potentially exploit well let's take a much longer message okay Kenny one crack this I've got all night okay perhaps it's the case that looking for repetitions in the cypher might give us some information i've actually hidden a three-letter word it actually comes up in this ciphertext many times can you find it use yes okay the trigraph us e comes up five times in the cipher okay now that may be entirely coincidental or it may be that USC represents the same tre trigraph in plaintext how do we know well let me add something to the picture that might explain how to proceed okay what I've done here is I've added the distances that occur between these repetitions it takes exactly 16 characters before you go from the first instance of use to the second then 40 characters then eight and then finally there's 240 letters between the fourth and fifth instances of use is there anything at all that you might strike you yes okay we have a hypothesis that the keyword has four letters in it okay does anyone understand why that's a good hypothesis yeah I heard someone else shouts something it could also be eight okay is that what you were going to say sort of okay ah yeah it's possible that the keyword is four letters long or it's eight letters long if in fact these instances of ciphertext really do come from the same plaintext trigraphs that means the key word has to cycle a certain number of times and get back to the same key letters above these ciphertext appearances of use and if the site if the key word is eight letters long that will give us the same key letters over these same ciphertext letters resulting in the same plaintext letters okay now if there are coincidences that's something we can't really address right now but if it's not a coincidence this gives us information about the key word it's potentially eight letters long is that helpful does that tell us what the keyword is okay how about brute force in this case we didn't even really talk about that brute force in the Visionaire that's rough because you don't even know how long the keyword is even now that we think we know it's 8 letters long what about brute force how many different keywords are 8 letters long a lot they don't have to be intelligible words they could just be random letters okay so brute force is still not what we want to do what we do want to do is I'm going to put some random symbols up to represent the eight unknown letters that we are seeing here okay why is this helpful well it's helpful if we try to do a divide and conquer strategy I want to try to get one letter at a time so let's first look at the letters there that are encrypted with the spiderweb okay that is the first letter the 9th letter the 17th letter every 8th letter after that and those are the letters that I've highlighted in red okay so I know that all those letters were encrypted with the same Caesar shift okay how can I use that information to figure out what Caesar shift well what I'm going to do is I'm going to take these red letters and I'm going to put them into a histogram and let me show you what results okay you might have noticed I think every time I see this slide I notice there seem to be a lot of use aren't there so you seems to be a very common ciphertext letter B also is common there's a histogram on the right-hand side on the left-hand side what I've done is I've taken the frequencies with which letters appear in English like e's appear about 12% of the time and I divided those numbers by 2 to get the same scale ah the question that we have to face or the question we're asking is what Caesar shift gets us from this picture to that picture ok now there's not going to be an exact answer because I have a very small sample size so I want to use what I know about the letters of the alphabet can anyone think of let's say three letters in English that are ver a common that all appear in a row what's that sorry one over here sorry three letters that appear that are right next to each other in the alphabet that are all common rst yeah I mean we can see that sort of here rst all have kind of high spikes how about letters that aren't very frequent there's six in a row that are not very frequent and that happens right after rst uvwxyz are all uncommon letters so this histogram I can see you know three tall columns followed by six very small columns and then there's a spike at the a and then four letters after that I get the spike at E so look at the right-hand side and try to figure out where does the rst slide 2 and the uvwxyz slide 2 how far over does it seem to be 1 and so what kind of Caesar cipher would that be it's easier be site for a slides to be B to C and in point of fact you are correct okay what about the third letter and every 8th letter after that so I've highlighted them in red and now here the two histograms ok can we use the same kind of logic to try to figure out what Caesar shift got us from the left-hand side to the right-hand side it's a Caesar a shift in fact I heard someone call it out okay there's no shift at all and I I've forgotten this I made this slide maybe five years ago or so I believe the key word I used was blankets but the point is it's not always easy to do this you do have a small sample size but if you can get a few of the key letters then what you can do is decrypt part of the message and then try to fill in the parts you don't know and then use that to get more of the key you can use a bootstrap method as part of the strategy this technique was called the Babbage Kiski technique and it did make leshiy freh and a sheath problem it made a daisy problem it cracked the Visionaire wide open okay so the question I want to ask them before we get into the Enigma which is where we're going next clearly uh what lesson do you learn from this Babbage consis key does this attack what would you recommend what what must a code maker do with their key words to make that attack harder and let's just take a look at a picture like this what can you do to the key word that would make it much harder to do this yes yeah the longer the key word is the fewer of these red letters you're going to see and the much lousy er that histogram on the right hand side is going to be it'll be much harder to do that attack if you use a longer key word in fact could you use a key word as long as the message itself and then you'd have one red letter over there that'd be kind of hard to to do yeah doesn't work okay so the longer it takes for you to recycle your ciphertext alphabets the longer it takes before your rule of encryption starts over again as it does with the Visionaire the better okay so that's a design principle we want to sort of put into our pocket and consider when we look at the Enigma machine okay so the Enigma machine as I said was used by the Germans in a decade before World War two and during World War two it was actually invented in 1918 by a German inventor named Arthur scherbius okay arthur scherbius was just one of many people in the world who had the idea at the same time that we should try to mechanize encryption okay encrypting things by hand you saw how long that Visionnaire message was can you imagine if it was your task as a secretary to to decrypt it even if you had the key one letter at a time decrypting it by hand that sounds like a fun way to spend a Sunday afternoon on a Sunday evening and then the Monday morning and then Monday afternoon manual encryption is tedious it's it's slow it's prone to error so certainly everyone had the same idea about the same time oh we need machines to do encryption that would be much better it would go faster less tedious less error-prone the Enigma is only one such device that was invented okay now scherbius invented this in 1918 in germany and he marketed it marketed it to the german government and the german military okay it was an expensive machine do you think he was easily able to sell the machine in Germany in 1918 why not murderers remember that's correct okay what I think some of you said was a combination of the following uh world war one it just happened okay Germany did not win World War one they lost it and they had to cede land away by treaty they had to forcibly cut their military I was part of the treaty they started to suffer from hyperinflation the economy was in the tank Germany was not doing so well at the time and arthur scherbius is enigma machine you know when he explained the principles to the people he tried to sell it to of course it was a great machine of course it seemed to be uncrackable encryption but it was very expensive to produce okay and not just expensive back then but I think in an Enigma machine went on eBay in May and went under just one hundred thousand dollars to buy an enigma if you want to have your own they're kind of expensive now they were certainly expensive back then okay so they said thanks but no thanks we can't really afford it besides they already had crypto I mean the German military they were encrypting all their messages at the time and it must have worked out well in World War one because of course Germany won that war right No okay so something happens in history that's kind of mind-boggling to consider that something is the publication of a few books in England only about five years after the war and in those books basically the author's discussed why England and their allies had won World War one and they said well we were cracking German encryption the ADF gvx cipher other methods of encryption he could read them this was news to Germany ah it was like really uh-huh ah one of the authors of this so one of those books was called the world crisis and the author was Winston Churchill okay why is that ironic well because well Winston Churchill went on to become the Prime Minister and face the Germans again in World War two okay so when the Germans learned that their crypto was vulnerable they had no position no recourse but to adopt something better and they felt they could not afford the Enigma but they couldn't afford not to adopt something the best that they knew of and the Enigma was was that machine ok the person who made that decision was a man named Rudolf Teela Schmitt remember that name Rudolf Teela Schmitt he was the head of the German cipher Bureau he was not cut from the military after World War one he rose through the ranks and he made the decision to adopt the Enigma ok Winston Churchill was then quoted as saying oh snap why because one day are actually probably not just in one day but over the course of several weeks in the 20s all encryption all communications went dark for France for England for Poland all the countries that were intercepting messages and reading them easily all of a sudden they could no longer read messages the Enigma had arrived and that was a very bad thing I will leave I will leave that as a cliffhanger and just ignore that let's actually take a look at the Enigma machine let's talk about how the Enigma worked ok so on the left hand side that's the Enigma machine as you would have seen it as an enigma operator on the right hand side I've taken an important portion of the machine out of the machine ok let's see there are three things that affect encryption ok you see on the left hand side clearly you want to type stuff in when you type in letters it looks like there's there are things that are going to light up and that's true you have a keyboard you have what's called a light board but there are three components between the keyboard and light board that in fact how a letter is encrypted ok the front of the machine is called the plugboard eye you can see 26 different holes into which you can plug cables the Enigma operators were given six cables initially and every day they were told connect this letter with this letter with your first cable then this letter with this letter with the second cable and so forth ok the effect of having a cable between letters was that anytime you pass through the plugboard in either direction you would either swap with another letter or you wouldn't if you were unplugged okay so that's the plugboard in the back you can see what what appear to be three rotors that's in fact what they are they don't just appear to be rotors they are rotors here are the rotors taken out of the machine and when the lid is closed you can sort of tell you can dial the rotors individually to have whatever three letters you want or their numerical equivalence on top of the machine okay now these rotors were were numbered one two and three and every Enigma operator had a machine that had a set of those all rotors number one had the same wiring inside and all rotor rotors number two had the same wiring and rotors number three were all the same but the each of the three rotors were different from the others okay ah the rotors actually come out of that rotor assembly and you can put them in a different order and that was part of what you were told every day as part of the key put the rotors in order to three one or one two three and so forth okay and then you were also told the final component of the day key is what to dial on top of the rotors at the start of every message okay the third thing that affects encryption is something called the reflector it's on the left-hand side of the three rotors okay so far so good we've got a plugboard rotors and a reflector okay how does encryption work okay well let's take a walk through the machine okay when you press a key what you're actually doing is completing a circuit the path of the circuit is as follows you start at the keyboard and you come forward to the plugboard if there's a cable there you will swap with another letter otherwise you won't okay from the plugboard you then go to the back of the machine to the right-hand side of the rotor assembly okay now what the rotors were there are 26 contact points on the left and 26 contact points on the right and there's some permutation that takes you from left hand side to right hand that's the wiring I refer to that's on the inside okay so you come to the plugboard go to the back you enter the rightmost rotor at some point and then you come out at some other point entering the middle rotor going in at some point coming out somewhere else entering the leftmost rotor in out somewhere else and then you come to the reflector okay the reflector was hardwired it simply swapped the 26 letters in pairs so if you enter the reflector you will exit as some other letter okay and now you get back to the rotors oh this sounds like fun let's go through the rotors in Reverse now coming in going out somewhere coming in going out somewhere coming in going up somewhere okay surely that's it no sadly it's not you have to go back then to the front to the plugboard you either swap with a letter or you don't again this direction finally you emerge at the light board and something lights okay that's clear right I don't have to really explain that any further I think pretty obvious how encryption works well let's actually look at it a little bit more closely okay now this schematic where I scale down the alphabet to just have six letters rather than 26 I've completely stolen this idea from Simon Singh who wrote a book called the codebook which I'd highly recommend you read we use it as the textbook for the Cty cryptology class so his idea is to okay let's just first look at the rotor and the reflector let's forget about the plugboard for a second ah and let's just trace through the machine let's talk let's talk about what happens when I press the letter A for example okay what you have to understand about the rotors is that they're two dimensional on this slide but they're actually three dimensional and reality if you leave the top they sort of wrap around those wires that go at the top will emerge from the bottom and so forth and vice versa okay I've currently dialed AAA on top of the rotors so who can tell me what happens when I press the letter A well what do I already have an answer see how many people think see who have traced through the path okay so if you go in to the four Roeder you're in that yellow path you come to the reflector on the brown thing you come back on the pink yes the C will light up okay what happens if you press a B what will light up f does anyone else can occur with F yeah it is in fact at what happens when you press a see a okay did you kind of know it had to be a already well why did you know that because if I press a and trace the path to the C then when I trait when I press a C I trace the path and it comes back out at the a okay so if B becomes F what happens when I press F it becomes B why do you think the machine is designed to work that way decrypt okay as long as the other person has their machine set up exactly the same way I do when I encrypt the a and I get a C they're going to press the C button and come back with the a right okay the reason why that happens is entirely due to the reflector the reflector is what basically takes the paths from the six letters and it matches them up into pairs okay why the reflector exists in this machine is so the decryption is exactly the same as encryption as long as the device on the other side of the communication is in exactly the same state as mine the same rotor order the same rotor settings on top okay so there's the entire permutation that we get for this setting okay let's now add the plugboard okay it is there on the machine it's important so recall that I said when you plug two letters together it will swap the letters in either direction so if you had a cable that connects the a to the D that's represented by that like dark gray X where a goes to D or D goes to a a second cable maybe swaps a and F okay now can anyone tell me you hit the plugboard going both in and out what happens if i press an A I hear F I hear e so let's see if we trace through the path yeah at the very end it's almost e but then the cable switches the e 2 and F so in point of fact if you press a or get F if you press B you get e if you press C you get D and vice versa ok now if this is all the machine did if this is all the machine did this isn't very good cryptography because every single time I press an e I'm going to get a a B and so that sounds just like a monoalphabetic substitution cipher right the the frequencies of ease and plaintext will show up as B's in cipher text ok so do you think this is all the machine does no and the fact that we have something we call rotors means well clearly they rotor 8 they rotate what actually happens when you press a key is you're going to trigger that first rotor to move it so you press an a and the F lights up and if you look at the closest rotor it moves one click up and instead of a a on top you now have BA a on top okay not only that but if you notice the positions of the wirings have completely changed this is now an entirely different permutation of the alphabet what happens now when you press an a and this is a little trickier because it's now not is nicely color-coded what happens if I press an a C is any one second that all in favor say C see yes okay and again you press a and get a C kachunk that rotor moves another time and now see a a is on top okay now the rotors of the Enigma machine works like an odometer of your car you know the odometer every time the zero goes to a nine and the ones digit it triggers the tens digit to move from a zero to a one uh and every time the tens digit moves a certain number of times that's what triggers the 100's digit to move it's the same thing with the rotors okay so as you type letters in merrily each letter you type is going to move that first rotor until you get a point where you have FAA on top and you're about to get the a on top again in the rotor number one and now when I press a D and get a see the first two rotors are going to move F bat to a but now the second rotor has moved from A to B hey how long does it take if you understand what I'm talking about with the odometer analogy how long does it take before you will finally see AAA on top how many letters do I have to press eight though how many six cubed how many people said six cubed yeah 216 times takes six rotations of the first rotor to trigger the second rotor once it'll take 36 times before you finally get a a on top of the first two rotors again triggering the third rotor once and so forth six cubed you'll finally see a a a on top and you will have your initial permutation again so that's great but the real enigma did not have six letters but rather 26 how long does it take for the real enigma yes 26 cubed which is 17,576 okay that's the Visionaire idea it takes you that long before you finally start recycling your permutation alphabets that long before you start recycling your alphabets there aren't going to be messages longer than 17,576 characters okay this now explains why the rotors are in the machine okay we understand why the reflector so decryption works we understand why the rotors are there so that you take as long as possible to recycle alphabets what do we not understand why is the plugboard there okay well let's see before before we talk about the plugboard let's just remind ourselves what it means to have a setting of the machine there are three things that I'm told every day to set up for that day the rotor order I take the rotors out I put them in in a particular order i dial up the same thing to be on top of the message for every so for example jxt and finally i have six plug word cables to use okay these three things give me a day key and we want to ask as always for any cryptosystem how many keys do we actually have then well how many ways can I put the three or rotors into order how many orderings are there are three rotors six it's three factorial how many things can I how many ways can I dial a tri graph on top so I have 26 possibilities for the first 26 for the second 26 for the third how many ways can I take six cables and plug them into 26 openings that's actually a non-trivial combinatoric sexercise how many of you have heard the word common it works before some of you may be very recently have heard of combinatorics it's the mathematics of counting things and it's a non-trivial calculation and I take great delight in making my cty students actually do that calculation every summer and Simon sings the code book the magic number just appears out of nowhere but I make the students earn it that number turns out to be just over 100 billion 100 billion three hundred ninety-one million seven or ninety one thousand five hundred okay ah and the total is then you have ten quadrillion different keys okay and finally we understand why the plugboard if you did not have a plug board on the machine if it was just the reflectors and the rotor you would only have about 100 thousand possible keys and brute force you could certainly use brute force then it's the addition of the plugboard and suddenly getting a factor on the order of 100 billion thrown into the mix you suddenly have just too many keys to brute force okay why did the Germans think their machine was unbreakable it uses every design principle they knew up to that point it certainly does seem unbreakable okay but before I go on uh it really would have been unbreakable if the polar Polish cipher Bureau and the French and the English if they knew nothing about the innards of the machine they really would have been in a very bad place how for example would they have known what the wirings of the rotors were okay you could physically capture a machine but in point of fact that's not how they deduced the wirings of the rotors what really happened is that some espionage was involved okay I told you to remember a name earlier there was someone named Rudolf Tilos Schmidt okay he was the person who adopted the Enigma machine he had a younger brother named Hans okay let me tell you about Hans all right now Rudolph was a golden boy he was not let go from the military because he was you know a good soldier and he worked his way up to the head of the cipher Bureau Hans was let go not happy about that he had a family to support and in an economy of hyperinflation he tried several things several businesses nothing seemed to really work out he eventually ended up in Berlin and had to beg his golden boy older brother Rudolf for a job at the cipher Bureau and even with that job he had a hard time making ends meet okay so Hans felt betrayed by his country he had been let go from the military he resented his older brother he was working in the cipher Bureau with access to lots of interesting documents and so forth it's kind of inevitable perhaps what happened Hans tila Schmidt turned traitor and he he sold out his country he he met with a French spy named Rex it's hard to make up a codename like rats but it's true Rex was not his real name uh he met with a he met with Rex in in Belgium and he said I have some very interesting documents perhaps you'd like to photograph them and give me some money and they offered a Hans Teela Schmidt enough money that Hans came to an agreement okay there were two documents they photographed one of the documents allowed the Polish cipher Bureau to deduce the wirings of the rotors using mathematics in an extremely clever way it was not a photograph of the wirings but it allowed the Polish cipher Bureau to determine the wire rings okay now this is kind of interesting because wait a minute it was a French spy who actually came across this information why is it the Polish cipher Bureau that ends up utilizing the information well we're all very fortunate that Poland and France had a reciprocity agreement okay France and England had tried to crack the Enigma cipher they knew roughly how it worked but without the wirings they really had no way to proceed okay once they had the wirings it still is a very difficult problem it seems intractable it seems unbreakable okay why is it Poland that feels the motivation to crack my not the French or the English okay well Germany was looking to the east at Poland and saying oh that land we gave up we'd sort of like it back and what's happening to the east of Poland in the 1920s it's after the Russian Revolution and they're looking West we're trying to spread communism Poland is feeling trapped in device Poland is feeling extreme motivation fear is a great motivator and they were the ones who expended the energy and they deduce the wirings and they not only deduced the wirings but they figured out a way to crack the Enigma okay we're not going to talk about that but there's one final piece of information I am going to talk about okay and that is ah what the instructions for Enigma encryption were okay it turns out that this machine I've said is uncrackable it's uncrackable in part because it uses different cipher text alphabets to encrypt every character because the rotor keeps moving uh but nonetheless there's a vulnerability if every single message on a particular day starts out with the same setting of the machine because it maybe you have different permutations as you go along encrypting letters but it's the same set of permutations for every message and frequency analysis will still apply because if you look at the distribution of the first ciphertext letter of every message and 12 percent of the time it's our you might say oh I wonder if that's an E and so forth this protocol is designed to get you around that problem okay what is the protocol this is what you were told to do as an enigma operator so des keys were given out in monthly code books so you look up okay on today here's my day key setting you put the rotors into the right order you dial the right thing on top to start encrypting a message and the plug boards have to be set correctly and now for every single message you are going to decide on a random try graph and that's going to be your message key and every message you send will have a different message fee okay what you're told to do then is to take the message key and repeat it twice r zu r zu in this example and now you encrypt and so in the day key setting the are encrypts to J the first rotor goes kachunk and then the Z encrypts to I first rotor goes kachunk and so forth and for example perhaps the ciphertext looks like j io w QP now as an enigma operator encrypting you take the message key you decided upon and you put that on top of the machine wherever the rotors ended up forget about it you you dialed the RZ you and now you encrypt the actual message ok kachunk kachunk kachunk kachunk ok now you send the message across the wire the other side receives it how on earth are they going to decrypt the message when they don't know what message key you selected ok how to decrypt how does it work again I guess if there are 12 people in the audience I might solicit that from from a member of the audience but let me just tell you it works because the other side of the communication will have the same day key to start and they will have received the message jio wqp the first 6 kachunk sub the machine will recover rzu rzu now as the Decrypter do you now know the message key yeah it's rzu you dial RZ you to be on top of the machine and now you can decrypt the rest of the message just as what it was encrypted okay so this protocol definitely works ok why it was done again is that if you actually choose random trigraphs now if i take every message and i look at the frequencies of the first ciphertext letter 126th of the time it'll be a 126th of the time it will be B and so forth this idea of frequency analysis goes away entirely this protocol does wonders for that and by the time you get to the seventh letter of every message the machines all over the field are set up differently their message key dependent at that point so this protocol works wonderfully ok but is there anything about this protocol that looks kind of stupid or silly that you're asked to do here ok again it starts out by saying write down the message key twice and encrypt that ok is there anything about that that seems a little bit odd yes why twice that's the question I would ask repetition is bad bias is bad that's what the codebreaker loves why on earth are they told to repeat the message key twice because if you think about it this protocol would work just as well if you only encrypt the message key once you would still as you decrypted expose the message key change your machine and decrypt the rest of the message just fine why in this protocol do you think are you told to encrypt the message key twice to make sure you get it right okay this notion of redundancy is something we call error correction it's the exact kind of thing that applies to your CDs when you have CD players in cars and you drive over a bump you don't always have the music skip on you because there's redundant information that allows the CD player to like sort of fill in the gap when you go over a bump okay it's because if there's a garble at the start of the message and wireless communications with bad weather over a distance believe me there will be garbles in the message if it happens at the beginning and you only have the message key there once then you try to decrypt the rest of the message and you'll just get garbage you'll have no idea what the message was and you have to ask the other side to resend the message and maybe they don't get that so they say oh could you resend what could you resend could you resend it's bad but if you repeat the message key and there's a garble and you decrypt on the other side and you see rzu RZ h you're like okay i don't know what the message key is because it should have been the same thing but it's either RZ u or RZ h you do not have to resend the message it was done for practical reasons nonetheless that is precisely the vulnerability of the way the Enigma machine was used and the Polish cipher Bureau was able to crack the Enigma okay this cracking was done by a Polish mathematician named marian rejewski there were some grad students who actually saw me speak earlier today and i went through the mathematics and we actually talked about how the Enigma was cracked using the mathematics of permutations which you would learn in abstract algebra in college it was stupendous because it had never been the case that mathematics was applied in this manner to crack it was eye-opening and Poland was able to actually get this information to France and Britain just before they were overrun by Germany and France and in Great Britain they were they're flummoxed they had given up on the Enigma and they were like are you kidding it's crackable really and the psychological effect of that was so great that even when the Germans stopped repeating the message key ah a man named Alan Turing and the cryptologists at Bletchley Park were still able to come up with a way of cracking the Enigma and they might never have even tried if it hadn't been for the pols who had demonstrated it could be done by using mathematics okay and there are a lot of stories one can tell about the Enigma but I'm out of time so I'll stop here I guess there's going to be time for a Q&A the question is how long would it take to crack a message with a supercomputer and I believe probably the question means by brute force yeah and I honestly don't I don't know that I'm not a big computer junkie I don't know what the fastest processor currently is the best supercomputer so the roadrunner I honestly don't know how long it would take to brute-force but it you know interesting problems arise for example how do you know how does a computer know when it's found the right answer like how do you automate that we recognize you know when something makes sense oh it must be decrypted because there is no limit bla bla bla do you have an answer to the question up there okay um yeah so the answer is I don't know yes another question yo I'm glad you asked because the answer is yes uh they actually have a few at work they're kind of cool to be able to play with but the hold that the American public can play with an Enigma machine that's that's always functioning there's a National Cryptologic Museum that's just outside of the NSA just outside of Fort Meade Maryland and they keep an Enigma machine always working they replace the light bulbs religiously and the museum is free of charge I would highly recommend if you ever get to DC or Baltimore in that area this is a really cool museum and it's free unlike the spy museum in DC which is like $20 I've never been to it might be a good museum but it's expensive yes okay so the real story is a lot more complex there was the initial enigma and the initial use of the enigma but what happened when what happened was kind of unfortunate Germany introduced a rotor number four and a rotor number five sometime in the 30s and everything that the Polish had done to crack the Enigma suddenly became impossible or much harder and they were no longer able to read messages daily uh and in fact didn't know what rotor for and what rotor 5 looked like initially uh and it was things that happened like that like periodically the Navy went from a three rotor enigma to a four-rotor enigma not because they thought the enigma had been broken which apparently the Germans never knew the Enigma had been broken during the war they just added security just kind of as well we may as well you know because who knows what they're doing on every time they made a change to the machine like usually something would have to be captured for us to understand what the wirings were now and things like that yes I see you with the black shirt yes so daya so the monthly code books were usually the ones that were carried by the u-boats they had a special ink that was like water-soluble and you know u-boat operators were instructed like take the rotors and throw them into the water so they sink to the bottom and take the code books and make sure they're wet so that they go away but of course when a you boat is sinking you know you're going to forget what your instructions are so occasionally code books were captured before they were being dissolved and sometimes code books were obtained by espionage hans tila schmidt provided a few code books to Rex for some money yeah see other questions you with the five fingers Wow well I mean there are a lot of different career fields like mathematician engineer computer scientist linguist as a mathematician they actually hire at all degree levels they tend to say you don't have to specialize in one particular area of mathematics but it is helpful to have some background in number theory it's helpful to have abstract algebra it's helpful if you know some computer science and if you can program certainly it makes your application stronger but but really a lot of different mathematics different kinds of mathematics are used statistics abstract algebra it's hard to go wrong but yeah we we could talk more specifically if you had a more specific question like I am a math person what do I need to do something like that you with the five fingers behind the other guy who had five fingers yes other branches of the military usually had a nygma's that were different they had some rotors in common so the different branches of the military could communicate but the naval enigma for example was was different and eventually had four rotors I think I've seen an airforce enigma that had seven rotors sometimes these were vulnerable and sometimes they they couldn't really crack they couldn't crack every message they came across but yeah that was a problem they were there there's not just one enigma there's lots yes Oh what is that story I don't know offhand I do know there are certainly so he's referring to the Battle of Coventry uh okay it should be clear from the story of World War one when you are able to break a crypto system you really do not want to advertise that fact even if the war is over certainly not during the war ah now if you're intercepting enigma messages and you always know where their planes are going to be do you always want to go after their planes precisely where they're going because well you know you don't germany is eventually going to say wait a minute how do they always know where our tanks are what could it be what could it be oh maybe they crack the Enigma and they're going to adopt something uh stronger okay so I mean it's a very interesting thing to ponder I mean it's not an easy question or a question to answer what do you do then you can't always know exactly what's going to happen or seem to know or the adversary is going to get information and change things there were actually a lot of different tactics that were interesting like so I don't know specifically about that particular story but I know we did clever things like we would send out patrol debts and an accidentally spot you know something that we weren't supposed to know about then the patrol jets would go back and then the real jets would come and Germany honestly in many cases thought we have the worst luck ever those dang Patrol jazz they were there again uh and yeah I mean we really we know now the Germany never found out that the Enigma was cracked like all our techniques of deception were effective amazingly amazingly yes I'm sorry apology today well it's no longer machine based it's you know computer based it's digital and because it's digital it tends to be mathematical I really don't wanna get into too many specifics because it's too broad of a subject were you here for a cosmos or a similar program okay uh so a lot of mathematics now number theory goes into cryptology the RSA crypto you've probably heard of diffie-hellman key exchange it's all different it would take too long for me to talk about butBut do the research go to Wikipedia read about what's that yeah I'm gonna borrow his tie um the math cluster for cosmos has a great demonstration with for laptops when you go outside and they'll demonstrate to you some principles of cryptography and code breaking okay yes you with the green shirt okay I think the question was how did you come up with 100 billion three hundred ninety-one million 790 1500 okay so the problem is you have 26 holes and you have six cables there there's more than one way to do the problem you can start by saying first of all how many ways are there to select twelve holes with which I'm going to plug from the 26 so 26 2 12 have you had combinatorics yeah okay so 26 to 12 is the start now that you have the twelve holes you're going to pair off you have to select the first pair so that's 12 choose 2 and then times 10 choose to then times eight choose 2 all the way down to 2 choose 2 then you're almost done you're not done because the order in which you select the pair's doesn't matter so if you do a B first and then C D it's still the same hole still the same set of pairs if you do C D first and then a B so you have to divide by 6 factorial because the six pairs can come in any order and that will give you the 100 million result sorry for the rest of you if that whoa what huh good grief yes you I'm sorry ah the same techniques you know modern-day techniques or you know that's a great question actually um I would love to know more about how you know they encrypted things in ancient China or middle-aged China or Japan where character sets are much broader yeah I really don't know and so the question is I don't even know how to encrypt let alone how to try to crack such systems but I'm sure the systems existed because we've always wanted secrecy every culture yes same guy with the same hand still five fingers I'm sorry I didn't catch that ah Japan had their own set of codes on some of them work all of their code names red and purple they had an Enigma machine so that they could talk to the Germans we actually had a lot of success against the purple machine in fact this is one of the cool things about the National Cryptologic Museum I believe we were intercepting purple messages from Japan and we figured out how the machine must have worked and built a replica of the machine and it turned out to look remarkably similar to an actual purple machine once the war had ended and we we found that out so I think the purple machine replica is in the museum to see yes I would imagine so if if the techniques are more like manual or machine encryption nowadays with everything digital it doesn't matter if it's Mandarin or Navajo or whatever everything goes to zeros and ones and then the encryption happens after that point so it's kind of a neat nowadays digital encryption is a bit equalizing in terms of languages did you have a one more question around top people but then move about there's refreshments and the yeah vana takes zero more questions you you

Channel: UC Davis

Views: 408,162

Rating: 4.8839216 out of 5

Keywords: cryptography, applied, mathematics, Enigma, Code, David, Perry

Id: ncL2Fl6prH8

Length: 65min 16sec (3916 seconds)

Published: Mon Feb 01 2010

Reddit Comments

[u/essentialatom]

Wasn't sure of the flair, I suppose mathematics, history and technology could each apply to some degree. It's not an overly mathematical talk.

David Perry from the NSA explains the increasing complexity of ciphers, including the Caesar cipher and Vigenère cipher, how they can be broken, and how they informed the design of the Enigma machine.

[u/[deleted]]

Isn't smart enough to move the mic up his tie

[u/JoBone69]

Any other lectures by this speaker? He's very entertaining and clearly explains everything.