[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.00,Default,,0000,0000,0000,,[Evans] The answer is 0.55.
Dialogue: 0,0:00:03.00,0:00:06.00,Default,,0000,0000,0000,,The key is 0. We can cancel that out.
Dialogue: 0,0:00:06.00,0:00:10.00,Default,,0000,0000,0000,,So we're left with delta M XORed with delta S.
Dialogue: 0,0:00:10.00,0:00:17.00,Default,,0000,0000,0000,,That could be 0 either if delta M is equal to 0 and delta S is equal to 0,
Dialogue: 0,0:00:17.00,0:00:20.00,Default,,0000,0000,0000,,then the XOR of 0 and 0 would be 0.
Dialogue: 0,0:00:20.00,0:00:23.00,Default,,0000,0000,0000,,The probability that delta M is 0--well, we know that.
Dialogue: 0,0:00:23.00,0:00:28.00,Default,,0000,0000,0000,,That's 0.61, and we're going to multiply that by the probability of delta S is 0,
Dialogue: 0,0:00:28.00,0:00:31.00,Default,,0000,0000,0000,,which we know is 0.73.
Dialogue: 0,0:00:31.00,0:00:34.00,Default,,0000,0000,0000,,But that's not the only way delta Z could be 0.
Dialogue: 0,0:00:34.00,0:00:38.00,Default,,0000,0000,0000,,The other way delta Z could be 0 is if both of these are 1.
Dialogue: 0,0:00:38.00,0:00:43.00,Default,,0000,0000,0000,,So it's the probability they're both 0 plus the probability they're both 1,
Dialogue: 0,0:00:43.00,0:00:49.00,Default,,0000,0000,0000,,and these probabilities are 1 minus the probabilities that we have before us,
Dialogue: 0,0:00:49.00,0:00:58.00,Default,,0000,0000,0000,,so it's (1 - 0.61) * (1 - 0.73).
Dialogue: 0,0:00:58.00,0:01:03.00,Default,,0000,0000,0000,,And if you calculate all that, you get 0.5506.
Dialogue: 0,0:01:03.00,0:01:05.00,Default,,0000,0000,0000,,That's probably a little more precise than it should be,
Dialogue: 0,0:01:05.00,0:01:08.00,Default,,0000,0000,0000,,especially because this value is just a guess.
Dialogue: 0,0:01:08.00,0:01:11.00,Default,,0000,0000,0000,,We'd have to do a much more detailed analysis of German
Dialogue: 0,0:01:11.00,0:01:15.00,Default,,0000,0000,0000,,to know whether that probability is really 0.61,
Dialogue: 0,0:01:15.00,0:01:19.00,Default,,0000,0000,0000,,and we'd have to know more about the particular messages that might be encrypted.
Dialogue: 0,0:01:19.00,0:01:23.00,Default,,0000,0000,0000,,But this value is pretty far away from a half.
Dialogue: 0,0:01:23.00,0:01:27.00,Default,,0000,0000,0000,,Any advantage that's that large, if we have a lot of text
Dialogue: 0,0:01:27.00,0:01:29.00,Default,,0000,0000,0000,,we're going to see that pretty clearly.
Dialogue: 0,0:01:29.00,0:01:32.00,Default,,0000,0000,0000,,So if we have enough text, we can count the number of positions
Dialogue: 0,0:01:32.00,0:01:35.00,Default,,0000,0000,0000,,where delta Z is equal to 0.
Dialogue: 0,0:01:35.00,0:01:38.00,Default,,0000,0000,0000,,If it's close to half of them, then it was a wrong guess.
Dialogue: 0,0:01:38.00,0:01:42.00,Default,,0000,0000,0000,,If it's close to 0.55 of them, then we have a good likelihood that that was the right guess.
Dialogue: 0,0:01:42.00,0:01:46.00,Default,,0000,0000,0000,,So now all we have to do is feed in the intercepted messages.
Dialogue: 0,0:01:46.00,0:01:51.00,Default,,0000,0000,0000,,Our guesses for the starting position of the 2 keys,
Dialogue: 0,0:01:51.00,0:01:55.00,Default,,0000,0000,0000,,we need to compute a big summation of these values,
Dialogue: 0,0:01:55.00,0:01:59.00,Default,,0000,0000,0000,,of the delta Z values, with those keys.
Dialogue: 0,0:01:59.00,0:02:04.00,Default,,0000,0000,0000,,And if it's close to the length of the message divided by 2,
Dialogue: 0,0:02:04.00,0:02:08.00,Default,,0000,0000,0000,,that means it was a bad guess. We weren't able to cancel out the key.
Dialogue: 0,0:02:08.00,0:02:13.00,Default,,0000,0000,0000,,If it's close to 0.55 times the size of Z, then it's a good key.
Dialogue: 0,0:02:13.00,0:02:16.00,Default,,0000,0000,0000,,It's likely that that's a good guess.
Dialogue: 0,0:02:16.00,0:02:19.00,Default,,0000,0000,0000,,And then we should be able to use those key guesses
Dialogue: 0,0:02:19.00,0:02:22.00,Default,,0000,0000,0000,,to find out what the actual message was, to decrypt the cipher text.
Dialogue: 0,0:02:22.00,0:02:28.00,Default,,0000,0000,0000,,So this is exactly the problem that what is arguably the first electronic digital computer
Dialogue: 0,0:02:28.00,0:02:30.00,Default,,0000,0000,0000,,was built to solve.
Dialogue: 0,0:02:30.00,0:02:33.00,Default,,0000,0000,0000,,So with this advantage there's a good likelihood
Dialogue: 0,0:02:33.00,0:02:36.00,Default,,0000,0000,0000,,that you would be able to know when you guess the right key.
Dialogue: 0,0:02:36.00,0:02:41.00,Default,,0000,0000,0000,,You need to try all the configurations of K0 and K1,
Dialogue: 0,0:02:41.00,0:02:45.00,Default,,0000,0000,0000,,and for each one of those configurations you have to compute this double delta.
Dialogue: 0,0:02:45.00,0:02:50.00,Default,,0000,0000,0000,,What we're computing for each configuration is this double delta,
Dialogue: 0,0:02:50.00,0:02:52.00,Default,,0000,0000,0000,,the XOR of 2 deltas,
Dialogue: 0,0:02:52.00,0:02:55.00,Default,,0000,0000,0000,,and that involves computing all these XORs.
Dialogue: 0,0:02:55.00,0:03:01.00,Default,,0000,0000,0000,,We need the XORs of the keys XORed with the messages and the S wheels.
Dialogue: 0,0:03:01.00,0:03:04.00,Default,,0000,0000,0000,,But remember what we're doing is guessing that this is 0.
Dialogue: 0,0:03:04.00,0:03:07.00,Default,,0000,0000,0000,,We don't have any way to predict those S values.
Dialogue: 0,0:03:07.00,0:03:12.00,Default,,0000,0000,0000,,We're producing the key values, and we're XORing those key values
Dialogue: 0,0:03:12.00,0:03:14.00,Default,,0000,0000,0000,,with the intercepted cipher text.
Dialogue: 0,0:03:14.00,0:03:17.00,Default,,0000,0000,0000,,So we need to do these XORs, XORing out the key
Dialogue: 0,0:03:17.00,0:03:21.00,Default,,0000,0000,0000,,and XORing the key with the value of the cipher text.
Dialogue: 0,0:03:21.00,0:03:26.00,Default,,0000,0000,0000,,So for each character we're doing 7 XORs
Dialogue: 0,0:03:26.00,0:03:29.00,Default,,0000,0000,0000,,and we're counting the number of times that's equal to 0.
Dialogue: 0,0:03:29.00,0:03:33.00,Default,,0000,0000,0000,,So multiplying all those together, we know the total number of XORs we need to do,
Dialogue: 0,0:03:33.00,0:03:37.00,Default,,0000,0000,0000,,and we get about 44.5 million.
Dialogue: 0,0:03:37.00,0:03:40.00,Default,,0000,0000,0000,,That's the maximum number that we might need to do.
Dialogue: 0,0:03:40.00,0:03:44.00,Default,,0000,0000,0000,,If we're lucky, we might guess the right configuration right away,
Dialogue: 0,0:03:44.00,0:03:46.00,Default,,0000,0000,0000,,and we could know that that's the right configuration
Dialogue: 0,0:03:46.00,0:03:49.00,Default,,0000,0000,0000,,by getting the high number of 0s out.
Dialogue: 0,0:03:49.00,0:03:52.00,Default,,0000,0000,0000,,If we're unlucky, we might need all 1271.
Dialogue: 0,0:03:52.00,0:03:54.00,Default,,0000,0000,0000,,Normally, we should expect to need about half of that.
Dialogue: 0,0:03:54.00,0:04:00.00,Default,,0000,0000,0000,,So maybe on average we would need about 25 million XORs to find the configuration,
Dialogue: 0,0:04:00.00,0:04:06.00,Default,,0000,0000,0000,,the correct value of X K1 and K0 for 1 cipher text.
Dialogue: 0,0:04:06.00,0:04:13.00,Default,,0000,0000,0000,,Once we've got K1 and K0, we can do similar things to find K2, K3, and K4,
Dialogue: 0,0:04:13.00,0:04:15.00,Default,,0000,0000,0000,,and then we can decrypt the whole message.
Dialogue: 0,0:04:15.00,0:04:18.00,Default,,0000,0000,0000,,So today, a modern processor runs at 2 gigahertz,
Dialogue: 0,0:04:18.00,0:04:21.00,Default,,0000,0000,0000,,so you're doing 2 billion operations per second,
Dialogue: 0,0:04:21.00,0:04:28.00,Default,,0000,0000,0000,,and 1 operation could include many XORs, possibly 64 XORs or 32 XORs
Dialogue: 0,0:04:28.00,0:04:30.00,Default,,0000,0000,0000,,depending on your processor.
Dialogue: 0,0:04:30.00,0:04:34.00,Default,,0000,0000,0000,,So to do that on a modern processor would take a fraction of a millisecond.
Dialogue: 0,0:04:34.00,0:04:38.00,Default,,0000,0000,0000,,To do that in 1941 was a major technical challenge.
Dialogue: 0,0:04:38.00,0:04:41.00,Default,,0000,0000,0000,,Computers didn't exist yet, but this was the main impetus
Dialogue: 0,0:04:41.00,9:59:59.99,Default,,0000,0000,0000,,for building what was arguably the first electronic programmable digital computer.