YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 01-42 Guessing Keys Solution

Get Embed Code
1 Language

Showing Revision 1 created 04/24/2012 by Amara Bot.

  1. [Evans] The answer is 0.55.
  2. The key is 0. We can cancel that out.
  3. So we're left with delta M XORed with delta S.
  4. That could be 0 either if delta M is equal to 0 and delta S is equal to 0,
  5. then the XOR of 0 and 0 would be 0.
  6. The probability that delta M is 0--well, we know that.
  7. That's 0.61, and we're going to multiply that by the probability of delta S is 0,
  8. which we know is 0.73.
  9. But that's not the only way delta Z could be 0.
  10. The other way delta Z could be 0 is if both of these are 1.
  11. So it's the probability they're both 0 plus the probability they're both 1,
  12. and these probabilities are 1 minus the probabilities that we have before us,
  13. so it's (1 - 0.61) * (1 - 0.73).
  14. And if you calculate all that, you get 0.5506.
  15. That's probably a little more precise than it should be,
  16. especially because this value is just a guess.
  17. We'd have to do a much more detailed analysis of German
  18. to know whether that probability is really 0.61,
  19. and we'd have to know more about the particular messages that might be encrypted.
  20. But this value is pretty far away from a half.
  21. Any advantage that's that large, if we have a lot of text
  22. we're going to see that pretty clearly.
  23. So if we have enough text, we can count the number of positions
  24. where delta Z is equal to 0.
  25. If it's close to half of them, then it was a wrong guess.
  26. If it's close to 0.55 of them, then we have a good likelihood that that was the right guess.
  27. So now all we have to do is feed in the intercepted messages.
  28. Our guesses for the starting position of the 2 keys,
  29. we need to compute a big summation of these values,
  30. of the delta Z values, with those keys.
  31. And if it's close to the length of the message divided by 2,
  32. that means it was a bad guess. We weren't able to cancel out the key.
  33. If it's close to 0.55 times the size of Z, then it's a good key.
  34. It's likely that that's a good guess.
  35. And then we should be able to use those key guesses
  36. to find out what the actual message was, to decrypt the cipher text.
  37. So this is exactly the problem that what is arguably the first electronic digital computer
  38. was built to solve.
  39. So with this advantage there's a good likelihood
  40. that you would be able to know when you guess the right key.
  41. You need to try all the configurations of K0 and K1,
  42. and for each one of those configurations you have to compute this double delta.
  43. What we're computing for each configuration is this double delta,
  44. the XOR of 2 deltas,
  45. and that involves computing all these XORs.
  46. We need the XORs of the keys XORed with the messages and the S wheels.
  47. But remember what we're doing is guessing that this is 0.
  48. We don't have any way to predict those S values.
  49. We're producing the key values, and we're XORing those key values
  50. with the intercepted cipher text.
  51. So we need to do these XORs, XORing out the key
  52. and XORing the key with the value of the cipher text.
  53. So for each character we're doing 7 XORs
  54. and we're counting the number of times that's equal to 0.
  55. So multiplying all those together, we know the total number of XORs we need to do,
  56. and we get about 44.5 million.
  57. That's the maximum number that we might need to do.
  58. If we're lucky, we might guess the right configuration right away,
  59. and we could know that that's the right configuration
  60. by getting the high number of 0s out.
  61. If we're unlucky, we might need all 1271.
  62. Normally, we should expect to need about half of that.
  63. So maybe on average we would need about 25 million XORs to find the configuration,
  64. the correct value of X K1 and K0 for 1 cipher text.
  65. Once we've got K1 and K0, we can do similar things to find K2, K3, and K4,
  66. and then we can decrypt the whole message.
  67. So today, a modern processor runs at 2 gigahertz,
  68. so you're doing 2 billion operations per second,
  69. and 1 operation could include many XORs, possibly 64 XORs or 32 XORs
  70. depending on your processor.
  71. So to do that on a modern processor would take a fraction of a millisecond.
  72. To do that in 1941 was a major technical challenge.
  73. Computers didn't exist yet, but this was the main impetus
  74. for building what was arguably the first electronic programmable digital computer.