WEBVTT
00:00:00.000 --> 00:00:03.000
[Evans] The answer is 0.55.
00:00:03.000 --> 00:00:06.000
The key is 0. We can cancel that out.
00:00:06.000 --> 00:00:10.000
So we're left with delta M XORed with delta S.
00:00:10.000 --> 00:00:17.000
That could be 0 either if delta M is equal to 0 and delta S is equal to 0,
00:00:17.000 --> 00:00:20.000
then the XOR of 0 and 0 would be 0.
00:00:20.000 --> 00:00:23.000
The probability that delta M is 0--well, we know that.
00:00:23.000 --> 00:00:28.000
That's 0.61, and we're going to multiply that by the probability of delta S is 0,
00:00:28.000 --> 00:00:31.000
which we know is 0.73.
00:00:31.000 --> 00:00:34.000
But that's not the only way delta Z could be 0.
00:00:34.000 --> 00:00:38.000
The other way delta Z could be 0 is if both of these are 1.
00:00:38.000 --> 00:00:43.000
So it's the probability they're both 0 plus the probability they're both 1,
00:00:43.000 --> 00:00:49.000
and these probabilities are 1 minus the probabilities that we have before us,
00:00:49.000 --> 00:00:58.000
so it's (1 - 0.61) * (1 - 0.73).
00:00:58.000 --> 00:01:03.000
And if you calculate all that, you get 0.5506.
00:01:03.000 --> 00:01:05.000
That's probably a little more precise than it should be,
00:01:05.000 --> 00:01:08.000
especially because this value is just a guess.
00:01:08.000 --> 00:01:11.000
We'd have to do a much more detailed analysis of German
00:01:11.000 --> 00:01:15.000
to know whether that probability is really 0.61,
00:01:15.000 --> 00:01:19.000
and we'd have to know more about the particular messages that might be encrypted.
00:01:19.000 --> 00:01:23.000
But this value is pretty far away from a half.
00:01:23.000 --> 00:01:27.000
Any advantage that's that large, if we have a lot of text
00:01:27.000 --> 00:01:29.000
we're going to see that pretty clearly.
00:01:29.000 --> 00:01:32.000
So if we have enough text, we can count the number of positions
00:01:32.000 --> 00:01:35.000
where delta Z is equal to 0.
00:01:35.000 --> 00:01:38.000
If it's close to half of them, then it was a wrong guess.
00:01:38.000 --> 00:01:42.000
If it's close to 0.55 of them, then we have a good likelihood that that was the right guess.
00:01:42.000 --> 00:01:46.000
So now all we have to do is feed in the intercepted messages.
00:01:46.000 --> 00:01:51.000
Our guesses for the starting position of the 2 keys,
00:01:51.000 --> 00:01:55.000
we need to compute a big summation of these values,
00:01:55.000 --> 00:01:59.000
of the delta Z values, with those keys.
00:01:59.000 --> 00:02:04.000
And if it's close to the length of the message divided by 2,
00:02:04.000 --> 00:02:08.000
that means it was a bad guess. We weren't able to cancel out the key.
00:02:08.000 --> 00:02:13.000
If it's close to 0.55 times the size of Z, then it's a good key.
00:02:13.000 --> 00:02:16.000
It's likely that that's a good guess.
00:02:16.000 --> 00:02:19.000
And then we should be able to use those key guesses
00:02:19.000 --> 00:02:22.000
to find out what the actual message was, to decrypt the cipher text.
00:02:22.000 --> 00:02:28.000
So this is exactly the problem that what is arguably the first electronic digital computer
00:02:28.000 --> 00:02:30.000
was built to solve.
00:02:30.000 --> 00:02:33.000
So with this advantage there's a good likelihood
00:02:33.000 --> 00:02:36.000
that you would be able to know when you guess the right key.
00:02:36.000 --> 00:02:41.000
You need to try all the configurations of K0 and K1,
00:02:41.000 --> 00:02:45.000
and for each one of those configurations you have to compute this double delta.
00:02:45.000 --> 00:02:50.000
What we're computing for each configuration is this double delta,
00:02:50.000 --> 00:02:52.000
the XOR of 2 deltas,
00:02:52.000 --> 00:02:55.000
and that involves computing all these XORs.
00:02:55.000 --> 00:03:01.000
We need the XORs of the keys XORed with the messages and the S wheels.
00:03:01.000 --> 00:03:04.000
But remember what we're doing is guessing that this is 0.
00:03:04.000 --> 00:03:07.000
We don't have any way to predict those S values.
00:03:07.000 --> 00:03:12.000
We're producing the key values, and we're XORing those key values
00:03:12.000 --> 00:03:14.000
with the intercepted cipher text.
00:03:14.000 --> 00:03:17.000
So we need to do these XORs, XORing out the key
00:03:17.000 --> 00:03:21.000
and XORing the key with the value of the cipher text.
00:03:21.000 --> 00:03:26.000
So for each character we're doing 7 XORs
00:03:26.000 --> 00:03:29.000
and we're counting the number of times that's equal to 0.
00:03:29.000 --> 00:03:33.000
So multiplying all those together, we know the total number of XORs we need to do,
00:03:33.000 --> 00:03:37.000
and we get about 44.5 million.
00:03:37.000 --> 00:03:40.000
That's the maximum number that we might need to do.
00:03:40.000 --> 00:03:44.000
If we're lucky, we might guess the right configuration right away,
00:03:44.000 --> 00:03:46.000
and we could know that that's the right configuration
00:03:46.000 --> 00:03:49.000
by getting the high number of 0s out.
00:03:49.000 --> 00:03:52.000
If we're unlucky, we might need all 1271.
00:03:52.000 --> 00:03:54.000
Normally, we should expect to need about half of that.
00:03:54.000 --> 00:04:00.000
So maybe on average we would need about 25 million XORs to find the configuration,
00:04:00.000 --> 00:04:06.000
the correct value of X K1 and K0 for 1 cipher text.
00:04:06.000 --> 00:04:13.000
Once we've got K1 and K0, we can do similar things to find K2, K3, and K4,
00:04:13.000 --> 00:04:15.000
and then we can decrypt the whole message.
00:04:15.000 --> 00:04:18.000
So today, a modern processor runs at 2 gigahertz,
00:04:18.000 --> 00:04:21.000
so you're doing 2 billion operations per second,
00:04:21.000 --> 00:04:28.000
and 1 operation could include many XORs, possibly 64 XORs or 32 XORs
00:04:28.000 --> 00:04:30.000
depending on your processor.
00:04:30.000 --> 00:04:34.000
So to do that on a modern processor would take a fraction of a millisecond.
00:04:34.000 --> 00:04:38.000
To do that in 1941 was a major technical challenge.
00:04:38.000 --> 00:04:41.000
Computers didn't exist yet, but this was the main impetus
00:04:41.000 --> 99:59:59.999
for building what was arguably the first electronic programmable digital computer.