
Title:
0142 Guessing Keys Solution

Description:

[Evans] The answer is 0.55.
¶

The key is 0. We can cancel that out.

So we're left with delta M XORed with delta S.

That could be 0 either if delta M is equal to 0 and delta S is equal to 0,

then the XOR of 0 and 0 would be 0.

The probability that delta M is 0well, we know that.

That's 0.61, and we're going to multiply that by the probability of delta S is 0,

which we know is 0.73.

But that's not the only way delta Z could be 0.

The other way delta Z could be 0 is if both of these are 1.

So it's the probability they're both 0 plus the probability they're both 1,

and these probabilities are 1 minus the probabilities that we have before us,

so it's (1  0.61) * (1  0.73).

And if you calculate all that, you get 0.5506.

That's probably a little more precise than it should be,

especially because this value is just a guess.

We'd have to do a much more detailed analysis of German

to know whether that probability is really 0.61,

and we'd have to know more about the particular messages that might be encrypted.

But this value is pretty far away from a half.

Any advantage that's that large, if we have a lot of text

we're going to see that pretty clearly.

So if we have enough text, we can count the number of positions

where delta Z is equal to 0.

If it's close to half of them, then it was a wrong guess.

If it's close to 0.55 of them, then we have a good likelihood that that was the right guess.

So now all we have to do is feed in the intercepted messages.

Our guesses for the starting position of the 2 keys,

we need to compute a big summation of these values,

of the delta Z values, with those keys.

And if it's close to the length of the message divided by 2,

that means it was a bad guess. We weren't able to cancel out the key.

If it's close to 0.55 times the size of Z, then it's a good key.

It's likely that that's a good guess.

And then we should be able to use those key guesses

to find out what the actual message was, to decrypt the cipher text.

So this is exactly the problem that what is arguably the first electronic digital computer

was built to solve.

So with this advantage there's a good likelihood

that you would be able to know when you guess the right key.

You need to try all the configurations of K0 and K1,

and for each one of those configurations you have to compute this double delta.

What we're computing for each configuration is this double delta,

the XOR of 2 deltas,

and that involves computing all these XORs.

We need the XORs of the keys XORed with the messages and the S wheels.

But remember what we're doing is guessing that this is 0.

We don't have any way to predict those S values.

We're producing the key values, and we're XORing those key values

with the intercepted cipher text.

So we need to do these XORs, XORing out the key

and XORing the key with the value of the cipher text.

So for each character we're doing 7 XORs

and we're counting the number of times that's equal to 0.

So multiplying all those together, we know the total number of XORs we need to do,

and we get about 44.5 million.

That's the maximum number that we might need to do.

If we're lucky, we might guess the right configuration right away,

and we could know that that's the right configuration

by getting the high number of 0s out.

If we're unlucky, we might need all 1271.

Normally, we should expect to need about half of that.

So maybe on average we would need about 25 million XORs to find the configuration,

the correct value of X K1 and K0 for 1 cipher text.

Once we've got K1 and K0, we can do similar things to find K2, K3, and K4,

and then we can decrypt the whole message.

So today, a modern processor runs at 2 gigahertz,

so you're doing 2 billion operations per second,

and 1 operation could include many XORs, possibly 64 XORs or 32 XORs

depending on your processor.

So to do that on a modern processor would take a fraction of a millisecond.

To do that in 1941 was a major technical challenge.

Computers didn't exist yet, but this was the main impetus

for building what was arguably the first electronic programmable digital computer.