How to make (and break) a code

是时候看数学的代码。在studio with Chris Smith and Adam Murphy is mathematician James Grime. They're discussing the World War II Enigma machine and the fact that the Poles cracked Enigma, and even built a replica machine to decode it, without ever having seen the real thing...

James - I know and people don't know that. And people should know this.

Chris - Have you seen one, because you know you work on this?

James - Yes. Yeah. So the Polish Double, which is where they reconstructed what an enigma machine must be. They had one at the Polish Institute and I did do some work with the Polish Institute a few years ago, where I did a talk at the Polish embassy about the Polish mathematicians.

Chris - How did they do what they did at Bletchley Park, then? How did that Bombe technique that she mentions work in order to crack that code? And what was the nature of the code that made it so hard to actually grapple with?

James - Okay so there's two things that make enigma difficult. First of all, there are lots of combinations. So I think we talked about, there's lots of combinations; too many to check. But the other thing that makes it very difficult is the moving wheels.

Chris - Because the simplest level is just substituting one letter for another isn't it?

James - It is.

Chris - But you're saying is moving wheels, is that because the substitution isn't the same every time. It's not - today A is E and tomorrow A is Z, it’s actually, right now A is Z but next turn of the wheel it's going to be D or something.

James - You’ve got it exactly right. So when the wheels turn, each letter of the message, it's been sent with a different code essentially, which makes traditional code breaking techniques impossible.

Chris - So how did the Bletchley Park team attack that?

James - Yeah. So what they were doing when they built these large BOMBE machines, what it was doing it was a process of elimination. So actually was trying to work out the plugboard, if I can tell you the truth. That’s the little wiring at the front and it was trying to work that out, if it found it was impossible, it would move on to another position and if it's impossible, it would reject, and it would reject, and it would reject. And this process of elimination was actually faster. So whatever you can't reject must therefore be the correct answer.

Chris - So in other words what they're doing is basically, a brute force attack on this thing, you take what you've stolen as the encrypted message, try what you think might be the solution, and see if you can decode it.

James - Just one step cleverer than brute force, because once you reject one answer, there's a whole family of answers you can reject at a stroke.

Chris - Oh, so you narrow down the opportunities and so that speeds it up. So how long was it taking them to do the average, to get the code for that day.

James - So on a good day you could check all your positions and find the correct setting in 20 minutes.

Chris - Right. But then obviously the work began, because then you got to feed all of the messages you have intercepted in, using that code and break them for that day.

James - Yeah. And what the codebreakers at Bletchley could do is, they could be reading these messages, these secret messages from the German army before the Germans had a chance to decode what they said. It’s amazing you can do that.

Chris - And how does everyone know what the settings will be for each day? Was that published somewhere so the German army knew what settings to use for what date?

James - Yes, so the Germans were given a key sheet, a large sheet of paper, and for each day of the month it told you how to set the machine for that day. Nice little story: The Navy would write those on blotting paper. So if your ship gets torpedoed and wet, that would wash away. That's how you keep the secrets of those codebooks.

Chris - Now people thought this was unbreakable. Obviously, it wasn't because the clever people in Poland, and also at Bletchley Park did suss it out and they got to the bottom of it. Is it possible mathematically though James, to make codes that are not breakable?

James - Yeah. There is such a thing as an unbreakable code. So that is called a one time pad cipher. And it's not that difficult to explain. I could explain it now. So you might have tried as a child, a shift code where you shift the alphabet across. You might shift it three across, or four across.

Chris - Do you mean that every time I should write A, I write C or D or something?

James - Exactly. Yeah. So if we shift it one, A would become B and a B would become a C. Now there are 26 possible ways we could shift the alphabet. Now a one time pad, does the same idea but it uses a different shift for each letter of the message.

能源部克里斯——这就是一个谜s, isn’t it?

James - Exactly that's what it has in common with enigma. Now if you do that, me and my friend, we have to share that sequence of shifts. Then my friend can just reverse it and get the message back.

Chris - But the vulnerability is that I could find out what that series of shifts is because someone else knows it?

James - Yeah. If you can steal that key. Absolutely. That's one of the problems. But if you steal the code and don't know the key, you'd have to try every possible shift on each letter of the message. What you get is every possible decryption. What you're doing is taking each letter for the message and you're allowed to shift it as many places as you want. Now if you don't know and you just try every possibility, you could make it say any possible message

Chris - Oh. Oh that would be nasty wouldn't it? Is anyone actually using that? Is that in industrial use.

James - I have heard that it is something that is used between the president of Russia and the president of America. I can't believe Trump and Putin are sat there doing their one time pad ciphers. But that is something I've heard, but it is slightly impractical as a code. The closer we can get to that idea in principle, though, the closer we are to an unbreakable code.

Chris - And did you have a code as a kid? Because I mean people like Samuel Pepys wrote his diary in code. Julius Caesar wrote in code, did you have a secret James Grime code as a kid.

James - I did. I used to write my words backwards and put a Z at the end. And I thought, Ah, no one will ever be able to break my secret code.

Chris - And?

James - Of course no one did. No one cared!