Tackling Enigma (Turing's Enigma Problem Part 2) - Computerphile
ฝัง
- เผยแพร่เมื่อ 8 ธ.ค. 2014
- Just how did the team at Bletchley Park tackle the problem of decoding Enigma? In Part Two of our series on "The Real" Imitation Game, Professor Brailsford explains how they did it.
Part One of this series:
Turing's Enigma Problem: • Turing's Enigma Proble...
Professor Brailsford's notes: bit.ly/enigmapart2
Numberphile on Enigma: • 158,962,555,217,826,36...
History of Undecidability: • The History of Undecid...
Mainframes and the Unix Revolution: • Mainframes and the Uni...
Turing Machines Explained: • Turing Machines Explai...
EXTRA BITS - Banburismus Secret: • EXTRA BITS - Secret Ba...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels
Sending out the RAF to bomb specific targets in the hope of generating a message which contained specific coordinates they could then decrypt, was called "gardening".
And the weird thing about that is that the aircrew themselves referred to it as "gardening", although the majority probably thought of it in relation to the sowing of magnetic mines. Not that "gardening" was without its dangers as the aircraft frequently with new "sprog" crews, could often be intercepted and shot down.
What specific targets was the "RAF" capable of being sent out to "bomb" in 1939? How many "bombing" missions did the "RAF" fly during the "Phoney War"?
Are you implying that the first world war did not happen?
Mark Fryer nn
Kinda reminds me of Joe Rochford sending out the clear text about the water purifier on Midway.
I could listen to this man speak on any subject for hours
His gift is that he can take something extrodinarily complex, and not only explain it in layman's terms but with respect to his audiences intelligence, with a little wit mixed in. Very hard to do.
Extremely charming. Makes working from home difficult :)
You're easily impressed.
He has the priceless gift of distilling information down without dumbing it down.
The "German spy" was actually an agent -- Hans Thilo-Schmidt, who handed over the operating manual for the Heer version of Enigma, the Enigma 1, to French intelligence in 1931. He didn't defect, but continued to work as an agent until his arrest and execution by the Gestapo in 1943. He never handed over the actual device, which would have been quickly missed.
The operating manual is a description of the procedures for using the device. It didn't describe the internals, particularly the rotor wirings (ie, the permutations) necessary as the first stage in breaking its code. French intelligence shared the information with the Poles and the English. Only the poles, in their three-man cipher bureau, were able to reconstruct the wirings using permutation algebra, with the reconstruction method also suggesting the Polish technique of breaking it.
Great info!
Thank you
Also worth noting: Hans was sort of the black sheep of the family, and his more successful brother got him the job
that it took the Gestapo until 1943 to find the spy is testament to their ineffectiveness.
The Polish did amazingly well in decrypting some of the Enigma code with only one machine.
Professor Brailsford Is a fantastic narrator. I love his enthusiasm!
Definitely knows his stuff on computer technology, in fact I know few people that know as much as I do. I often use his video's to explain stuff to people. Very handy.
I'm really glad that Professor Brailsford mentioned about Poles
The Poles had their own codes and cipher bureau. Biuro Szyfrow (Cipher Bureau) or BS for short. BS was based in Warsaw Poland. Last chapter of the1978 Brian Johnson book "The Secret War" is devoted to breaking the Enigma codes. Copy of the original Polish bomba sketched by Marian Rejewski is included. Jerzy Rozicki and Henryk Zygalski are also mentioned in the chapter.
love listening to this guy speak
This video is about 1 hour too short, i love this professor
This 2 part set is the very best scientific rundown of the enigma saga I've ever seen anywhere. Much more informative than the history channel program on the subject! Also, very good digital diagrams and charts showing the physical reality...
More long two part episodes, please. I love these 15+ minute videos.
A few relatives and I at a family reunion were talking about our experiences, and one fellow in his early nineties told us something unexpected - during WWII he was stationed in Washington DC in a group working on decrypting the Enigma machine. For secrecy reasons he couldn't and didn't divulge anything, but it was interesting to learn he had worked on such an important project. He's gone now, nevertheless I will never forget that little bit of exposure.
Wonderful description, fascinating style of delivery, fantastic video. More pls!
Absolutely fabulous videos. While understanding the math, you pull it all together in a fabulous presentation that is completely captivating. Well done!
Fantastic telling of a great story. Can't wait for part 3.
Andrew Gleeson part 3: Trial over homosexuality, Chemical castration and self- ‘topping’ of Alan Turing. Handover of Bletchley and the computer industry to the USA and jubilation of the codebreakers with obscure awards and sworn secrecy until 1970s.
Superb presentation of the facts. Such an impressive effort and rich history. Thank you.
Thank you for this series on "Enigma" professor Brailsford! :)
Thank you very much for the correct explanation of the history of Enigma.
Professor Brailsford is the David Attenborough of computing what an amazing gentleman!
To find a man that can explain this in such detail and order .... This guy is a genius and such a great guy ! TY
*****, whatever you've done in your shooting with Prof.B. looks really good; props!
That clumsiness, combined with the fact that he was experimenting with gold-plating spoons (a process which requires potassium cyanide) when he died, means that many people now believe Turing’s death was an accident rather than suicide. The apple that he supposedly laced with cyanide was never actually tested, and his symptoms were apparently more consistent with cyanide inhalation rather than ingestion.
wonderful video...I could listen to Professor Brailsford all day.
I live 15 minutes from Building 26 at NCR where Joseph Desch worked at NCR in conjunction with US Office of Intelligence to build Bombes and decode Enigma ciphers. He also developed some new techniques to speed up the process of decoding the messages by using his expertise in electronics development to add electronic systems in place of some mechanical components. Smart guy. The building was razed about 10 years ago. The building was purchased by Univ. Dayton and as the campus sits across the street from the building they used it to expand campus footprint. Desch also graduated from there. Despite the enigma eventually being cracked, its still a marvel of ingenuity and engineering for late 1930s technology. In many ways so complex, yet in other ways so simple by merely using the leverage of multipliers to increase "possible combinations". What does the military use now? Is it all sophisticated digital encryption such as a military grade version of SSL or PGP?
I think you'll find that Enigma IS a digital encryption system.
Being from the USA and from growing up almost right next to the NCR facility that is referenced I would like to thank him for mentioning that. In sooo many of the videos and talk about the bombe, there is little to no comment about the USA's input into this effort. I am glad to see that the efforts here in the States and specifically in the NCR facility have not been totally forgotten.
where was the NCR facility???
@@josephbrady6760 Dayton, Ohio
It’s amazing that some of this information was still declassified until 2010!
Excellent stuff, found out several things I didn't know!
Thank you for posting this - such important history.
At the first minutes, I thought that he ridiculed Enigma, but a few minutes later I acknowledged that „military enigma“, esp. Navy enigma, was a tough target to break. Only by gathering code books from weather ships etc. it could be solved sometimes, while many messages remained encrpyted. I like that he gives credit to the Poles and Paul Alexander, who really deserve it for embracing on this quest.
Beautifully presented, and reasonably intelligible to non mathematicians like me...thankyou!
I could listen to this guy all day, everyday
Can't wait for the Colossus video(s)!
Felt like listening to your old granpa talking about "My time". Very interesting series!
Very interesing dicussion. My thanks to those who developed the video.
RESPECT to Simon Singh who told me about these things years ago also. Love the book.
Listening to this man speak is a delight
I love these videos, thank you very much.
Appreciate the details, that you gave the graphics enigma a German keyboard.
Excellent video
Who on this earth would 'thumbs down' this video?! Aliens?! Brady, your work is top notch and Professor Brailsford is just awesome.
Sorry, Sean Riley! Actually your work!
Great episode!
I could listen to him talk all day.
wow. amazing. thank you for sharing this history.
Truly Fascinating stuff.
The last few minutes describe what's basically distributed computing, decades before arpanet was in anyone's dreams
the national museum of computing an Bletchley is an amazing place to visit, seeing colossus in action is mind blowing
The rebuilt Bombe machine is also at The National Museum of Computing NOT at the Bletchley Park museum. The two are next to each other but are different organisations.
Alan Turing is my hero! Big fan of computation theory too
Utterly mind blowing.
Wow, Alan Turing is truly a hero! I bet he was rewarded well for his very important role in the war! :/
Well, they did About the opposite of that :/
I would not recommend betting on that.
He was prosecuted as a homosexual after the war. The whole enigma story was secret until the 1970's.
Mark Mayonnaise he topped himself, after being prosecuted.
@@StephenButlerOne and chemically castrated.
This is fascinating history trivia, goodness
Thank you for this video
I can't find any information about the underwater cable mentioned at the end of the video and used to "submit" jobs to other machines running in the USA. It sounds really interesting.
Nice film great story
Thank you i want more!!!
@1:45--If you didn't catch it, Polish intelligence was very much responsible for the success and later notoriety of Bletchley Park.
That's overstating the case. The techniques used at Bletchley Park were invented at Bletchley Park. The techniques the Poles used became useless as the Germans changed the Enigma machine and procedures. The British bombe was a British design that operated on different principles than the bomba designed and used by the Poles, even though the name of the former was based on the name of the latter. The British had to continually reinvent the wheel. If they had only had the Polish techniques, no messages would have been decrypted during the war period. The four rotor uboat Enigma didn't even exist at the time that Poland was overrun. Breaking that machine was what saved Britain from being starved out of the war by having all their supply ships sunk. By getting into that code, they were able to keep their convoys much safer and get the vital supplies they needed. The Poles made no direct contribution to accomplishing that task.
What the Poles did supply was the basic hardware design, the early techniques for the simpler machines and procedures and, possibly most importantly, the idea that spending resources trying to decrypt Enigma traffic was far from a colossal waste of time*. You've got to be in it to win it and the Poles proved that getting in it could pay off.
* Apparently the Germans came to the conclusion that trying to break the British encryption would be a colossal waste of time and so never made a serious effort.
I love the Raspberry Pi bear in the both Computerphile Enigma videos!
This yank thanks you. I now know what I can tell my dad about my great, great grandfather. He never understood why he was told that gg grandad said he helped build bombs and to tell no one. Thank you for deciphering this.
Just to note, what kinda blows my mind.. is that the techniques even developed because of the machine was literally only gained because, before the war, a traitor betrayed the machine & handed it over.
(which makes it all the more tragic honestly.. given why the war itself was sparked, and that the only success was gained from a turncoat. Giving the grounds of starting and a very solid direction to go with the encryption)
One wonders what would have been made of the war if this exceptionally vital start wasn't gained so early.
Do i have ocd ?? I just kept looking at his shirt collar out of the sweater and thinking about putting it in ..
I call it CDO, it must be in alphabetical order or I get a twitch.
Spoiler alert sßs
I was hoping he would fix that collar......
18:53 The Americans had their work cut out for them. They also had to work on deciphering Axis codes for the Pacific Theater of the War, which used the JN machines. Bletchley held that work at Hut 7. The reason the Americans also had to work on deciphering codes produced with those machines is because it was the Pacific Theater that got them into the war on December 7, 1941, “a date which will live in infamy,” i.e. the attack on Pearl Harbor.
The professor is very interesting!
He must be from the same area as the actor who plays Dr. Mallard on NCIS!
I always thought The Bombe was named that way for the same reason the first tank was named to sound like a water tank, so that if any eavesdroppers or spies overheard that there was work being done on a new "Bomb", they wouldn't think much of it. Its nonetheless interesting that it was actually named as a nod to the polish Bomba which itself has a lot of speculation about its name's origin.
Much of what went on was clouded, deliberately, by disinformation in order to hide the techniques used to decrypt messages. Even Turing's involvement was subject to this, apparently. It was only recently (turn of the millennium?) that the 'truth' of what they actually did was released. Even then, much was omitted or redacted. It is all fascinating stuff, especially as you never know which bits are true and which bits are skins of the onion.
What I read about the Polish Bomba was, that the name came from the sound that it made when it would stop on a configuration and drop something on the ground as a result
I haven't quite watched the entire video yet, but I really want to hear from the German side at the time in this whole mess of cryptography and with what was going on to decrypt it by Allied forces.
Yeah, that would be an interesting video.
They somewhat covered a few aspects from the German side at the time in previous videos, notably how the Navy didn't trust _anyone_, even their other military divisions like the army and airforce, and demanded more secure Enigma machines.
GothAlice, I want to go beyond that and into detail on what their suspicions where, why, and how they came to be for example :)
I'm sure they would have been more paranoid than that? Maybe not naval, but definitely air-force and army.
mPky1, good point ;) But to be fair, I'm only going by what he has spoken of in the videos. I do not know him as an individual.
"The Secret in Building 26" is a great book on NCR's Bombe program!
All these enigma videos are making me wonder just what the computational complexity of enigma actually is...
Was it merely difficult for the time, or would you still struggle to decrypt it even with modern computer technology?
It would be child play nowadays
I think the key was as mentioned in the video, Letters will not represent themselves. Knowing that these days would be easy on a computer. Without knowing that it would take a lot more work.
The Enigma, in it´s best naval configuration without all the mistakes made by the german army, could still occupay a modern computer for a while. The keyspace was between 77 bit to 88 bit. The last few thousend enigma massages are still in the process of being decrypted. Btw. the german wikipedia article is gigantic if you speak german by chance :)
Well there's 2 different questions there. The computational complexity hasn't changed, and if you didn't have any ideas about heuristics (ie. this letter has % chance of appearing here) you would have to take some sort of brute force approach even today.
The difference is that we can try it so frequent that it wouldn't take long on today's HW.
"Write a program to break Enigma" is a pretty normal exercise for an undergraduate cryptography course these days.
Insanely smart.
How the world would seem like a weird place for people like Alan Turing.
What a team.
hmmm it almost feels like they were doing some sort of quantum cryptanalysis with those perforated sheets.. by sliding them over each other, checking every combination simultaneously
Amazing
At 5:20 the professor says "Alan" instead of Andrew (Hodges)
I had a little trouble understanding how the BOMBE machine works. From my understanding the BOMBE is comprised of Enigma machines that each create the permutations of possible cypher text to match the cypher text input and that this machine is made more efficient by eliminating permutations that include letters routing to themselves. Is this far off?
That sounds about right I think
the approach from the staff of bletchley park, regarding the cracking of the enigma, was brilliant indeed . which were the cryptographic methods that the allies were using to transfer their messages ???? were the germans trying to break them ???
The British made a machine called "Typex", which was also based on the pre-wartime commercial Enigma. It was more secure, and easier to use because it printed the encoded message directly onto tape, instead of having to copy it down.
The Germans made some attempts at cracking it, but apparently gave up, thinking it was too complicated.
***** How about doing another video on the "Geheimfernschreiber" (Siemens & Halske T52) which was an even more complex crypto machine used by the Germans and cracked by Swedish mathematician and cryptographer Arne Beurling in 2 weeks using pen and paper? The story of the Enigma is well known but I think the story of "G-skrivaren" deserves a bit more recognition than it currently receives. =)
I think this is the machine that Bletchley Park referred to as "Sturgeon" ? I think BP spent some time on it but concluded that there was a much bigger quantity of useful intelligence from regular Lorenz machine traffic. Sean and I have got Lorenz and Colossus firmly on our "to do" list.
ProfDaveB Yes apparently most of the information the allies could intercept that was sent using this machine was also sent via the enigma so not worth the effort. The information sent to Norway via lines through Sweden was useful for Sweden and Finland (and Russia due to a leak). The fact that Beurling cracked it in two weeks without having any information other than the encrypted messages to go on is rather amazing. It is also a rather interesting encryption technique and apparently the most complex used by the Germans if the article on Wikipedia is to be believed.
is there a video you can point to anywhere?
@@profdaveb6384 - Thank you so much for producing these videos.
Very interesting talk. Is there a book that talks about the French, Polish hand over of the machine codes etc
Fascinating. The Japanese codes were also cracked, what coding method did they use? And what codes did the allies use and did the German's try to crack them? Or did the allies just use carrier pigeons?
Everyone used rotor machines at that time for their high level codes. They were the state of the art in cryptography.
This is AAAAAWESOOOOOOME. 👏👏👏👏👏👏👏👏👏👏👏👏👏👏👏👏👏
Fantastic. Sadly can’t get ‘extra bits ‘ to open.
Could someone tell about the code inside the BOMBE controlling the system itself, if there was one and based on what the Bombe stops indicating the code was broken? I’m assuming the words were in German, am I right?
Forgive my naive question: Is that machine essentially doing the same thing as mining for Bitcoin on SHA-256?
Alpharius Omegon No, hashes are a different kind of cryptography compared to the cyphertext generated via DES or AES. Unlike cyphertext, hash generation cannot be reversed back into plaintext. The process of hashing causes pieces of the plaintext data to be truncated (lost) and pieces are added to the resultant text to ensure that all hashes generated are of equal length. Hashes are a little more complicated, and because of the rules that are changed, hashes have different purpose, strengths, and weaknesses.
Fascinating stuff! Can't wait for the video on breaking the Lorenz cypher :-)
I see...said the blind man.
Subscribed!
I got confused about the rotor count - last video it was said that the naval enigma eventually had eight rotors to choose three from. Now the prof says there were three and four rotor "huts". So the naval version had four rotors inside it? Or to choose from? The method that Turing (working in the "four rotor hut") came up with helped to see what the first two rotors were, and the third could be left to the bomb to solve. But shouln't they have been working on that four rotor version?
German Navy Enigma used 3 rotors chosen from 8 for general cipher traffic. The 4-rotor version was introduced for U-boats . The 4th rotor was different from the rest
and consisted of a thin rotor combined with a modified version of the reflector block. If you use your search engine to find "Wikipedia Cryptanalysis of Enigma" you'll find all the details in section 5.10 of that article.
ProfDaveB
Ah, so the 4th rotor was not like the others. Thanks for the answer prof!
@@luppa79 For one thing, it didn't rotate.
"so we would send the menu to the Americans and they would load menu on their bombe and give us the result.
I guess you would call them programs now."
Computers running programs before we had words for them.
Correct me if I am wrong but it doesn't actually seem to me that the plug board would add that much security. It seems that it would be susceptible to simple frequency analysis.
MrGoatflakes [Edited]
If you know the rotor settings then adding the plug board does nothing that can't be cracked in a few seconds by frequency analysis. But the very point of the rotors is that by constantly moving they prevent frequency analysis - the length of the swap cipher is effectively longer than the message.
But the rotors are a known design and are mechanically limited, so if you combined looking for key words, or some other trick, with the known rotor constructions, then you could conceivably lock onto the correct rotor settings without using frequency analysis.
What the plug board does is simply multiply up the number of outputs that any one rotor setting can produce, thus making it hugely harder to deduce which rotors and settings have been used. So it has the rotors preventing frequency analysis and the plug board providing big number permutations.
chrisofnottingham right, so in theory all you have to do is try a rotor setting and then subject it to frequency analysis and see if it matches the frequency analysis of normal traffic, then you know you have the right or near right rotor setting, but in practice you have to do this after you have tried each setting, so it isn't practical. Or at least that's how I interpreted that :p
MrGoatflakes I think that's right (tho I'm no expert). Bearing in mind the computing power available at the time, it meant that you couldn't just try rotor settings until German text came out, you needed to do another layer of processing every time.
The lightbuoy pinch was "Erloschen ist Leuchttonne".
Hugh Alexander went on, after the war, to be head of section 'H' at GCHQ. Those were the Russian-code breakers. He was their top cryptanalyst. Read Peter Wrights 'Spycatcher'. It's fascinating. (Although, take his suspicions about Roger Hollis with a pinch of salt. He got it wrong there.)
By watching this, I've started being more interested in what the Allies, or in this case the British, were using to cipher their messages. All the captured german messages had to come back to the Bletchley park eventually. How?
Was there a parallel Allied enigma machine?
Primarily they used dispatch riders between the y stations (radio intercept stations) and station x (Bletchley). This cut down on the risk of anyone noticing "strange" communications between the locations.
Thomas, that perhaps is correct for that particular case, but my question was more in global terms.
How did the Alias communicate with their forces? They could not dispatch riders to talk to their submarines ;)
They had to have some kind of cipher on their own...
***** Sorry I misunderstood. There were various machines used by the different allied powers the British used a "super enigma" (though it differed substantially) that was able to encode a number as its self called i think the x machine. What was used depended on the "level" of the communication, at the bottom end they used simple substitution ciphers, code books etc. There is some good stuff on Wikipedia that links from the enigma/bletchley pages.
Thomas Newberry Sorry, make that the "Type X" machine
MichaelKingsfordGray
The book he is talking about is most certainly "The code book", by Simon Singh. I do recommend it, it explains the history of cryptography in a very divulgative manner.
#TakeThat!
Inputting "salt" and already coded messages (attack=foo, retreat=boo) could screw the encoding business...
id imagine they did.
I think primitive salting came along much later in the war. Since they didn't know their code was being read they didn't have the incentive/data to figure out how to make it stronger in that way. If they knew the British techniques, that would have given them a big boost in protecting against it.
The Japanese did from the start. They enciphered codes... that was part of the problem in that you had to crack the cypher and then the codes.
"bomba" in Polish is just "a bomb" in English ;) Just saying. Great material. Thanks!
It was named after an Italian ice cream. However, there was some concern that using the "bombe" name might lead to the Germans assuming they were producing the A-bomb at Bletchley.
So what did the British use for encryption?
He used proper Polish pluralization, too!
This guy's pretty cool.
Actually he didn't. One bomba, two bomby, six bomb, sixty bomb. "Bomby" is only for 2-4.
before ww2 French, Brits and Soviets tried to break enigma code. Without any success. Poles cracked enigma and they laid down blueprints to Turing's invention.
“I don’t know allow the details,”
Great! Then logically I’ll know even less!
How about the Lorenz Cipher?
Love these videos, but the colour correction on this one is *greeeeeeen*!
He's probably in the Matrix.
John von Horn At least that's where you _think_ you're from ;)
It ain't easy being green!
Fascinating. I never knew America was involved in decrypting enigma messages. And what a shame Enigma was kept a secret for so long, the participants couldn't be interviewed and their work recognized. Because winning WW2 where 70 million died and made what the world it is today, is a big deal.
The reason for keeping it top secret for the next 40-50 years was that many of the techniques developed at Bletchley were just as important during the cold war. The need for secrecy didn't just end in 1945.
Today, speaking of building the deenigma machine; could a program and a computer do the whole work?
*Enigma, and yeah it was basically an early computer, so we could probably do it today
Yeah a simple piece of software would probably take very few seconds to crack any Enigma code.
Looping through 3 rotors of n, m, p size for example is an O(n*m*p) problem but the permutations of the original Enigma don't blow up to anything that your most basic CPU can take care of instantly.
A computer does millions of instructions per second at the very least. Modeling any sort of early mechanical computer is a pretty trivial task.
@@stapler942 I THINK HE DIDINT MEAN "BRUTE FORCE"
"Bomba" - a bomb in Slavic languages. I imagine someone asked a guy what he caries and to be secretive and keep inquisitive guy away he said "bomba".
@5:21 Its Andrew Hodges not Alan
uh! thanks for reminding me about the movie, forgot all about it, gonna watch it right now!
Excellent video, well explained. The mind boggles how a group of people can think up of a mchine like that that can work out the codes without computers, internet or calculators. There weren't half some clever folk back then
The worlds first digital programmable computer, a British invention
The Jet engine, a British invention
The world wide web, a British invention.
That's not really as weird as it seems. Circa 1930 the UK was one of the main global powers ie it had a lot of resources and a lot of people. The statistical probability that either the UK or the US would be first was always higher than say Portugal. It makes perfect sense considering the resources available.
What the documentary does not say is that the british raided a weather ship and took a enigma machine.
There were a number of planned pinches like that weather reporting ship, another was during a Commando raid in Norway I think. Plus the occasional pinch from a sinking U-Boat. The ships and U-Boats would carry books with the rotor settings for two months so if they could be captured early then it could give a way into the settings for up to about a month and a half.
Yes, they already had working copies of the machines. What was most valuable were the code books.