﻿[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.