Got a YouTube account?

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

English subtitles

← 01-13 One Time Pad

Get Embed Code
3 Languages

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

  1. So let's define that a little more precisely.
  2. So we're going to find our set of messages--
  3. is strings of 0s and 1s--so we'll use bits and some fixed length.
  4. So n is number that gives us the maximum length of a message.
  5. Our message is selected from all binary strings of length n.
  6. Our key is also selected from the set of all binary strings of length n.
  7. And then to do encryption--our encryption function--
  8. we're going to think of the message as being this sequence of bits
  9. and the key is also a sequence of bits.
  10. The result of our encryption is the ciphertext,
  11. which is a sequence of bits.
  12. So, length n, where the value of each ciphertext bit
  13. is equal to the XOR of the corresponding message bit
  14. and the corresponding key bit.
  15. So let's try an example.
  16. And for this example, I'm going to give you the ciphertext
  17. and the key and the message.
  18. So suppose our message is the string 'CS,'
  19. but our message space is in bits.
  20. Well, the first thing we need to do is to convert those strings to bits
  21. and we can do that in Python by using ord,
  22. that takes a one character string and turns it into
  23. a decimal number.
  24. And then we need to convert that decimal number into bits.
  25. Into a binary number.
  26. And we need to do this for each character in the string.
  27. We're going to convert it to a character, convert that to bits,
  28. and I'll show you the code for doing that,
  29. we'll leave the more interesting code for you to write.
  30. Here we're converting to bits.
  31. This is a fairly straightforward, but not the shortest way to do this.
  32. We're going to make an array of bits as our result for any decimal number
  33. if it's divisible by 2, we want to have a 0 at the beginning of a result.
  34. If it's not divisible by 2, that's going to be a 1.
  35. And then we divide the number by 2 as we go forward.
  36. So that's going to fill up all the places.
  37. We want our bits to be particular lengths,
  38. so we have a padding,
  39. and for all the characters, we'll use 7 bits.
  40. So we're going to pad the result with leading zeros
  41. until we get to that size.
  42. We can see this--so if we do ord we see that
  43. the number corresponding to the letter C is 67.
  44. If we convert that to bits--and we'll use 7 as our padding--
  45. that gives us enough for 128 different values
  46. which is enough for the ASCII character values
  47. that we get back from ord.
  48. We can see those bits as a list,
  49. and we can see that a little more easily as a string
  50. using the display bits procedure that just turned that into a string.
  51. So now we want to convert more than one character.
  52. To do that, we have a string to bits procedure
  53. that goes through all the characters in the string,
  54. converting each one to bits using convert to bits,
  55. and concatenating those all together to the result.
  56. So now we can do string to bits.
  57. For our two-letter string, and now we get 14 bits as a result.
  58. So if that's our message, then the value of M is what we got there.
  59. So this is our message.
  60. There are 14 bits, n is 14.
  61. That means--to encrypt this using a One-Time Pad,
  62. we need a key that also has 14 bits.
  63. So let's pick our key,
  64. and--we're just going to make up a random key now.
  65. Actually finding random values is very important in cryptography,
  66. and we'll talk about that in a later unit,
  67. but for now let's just make one up.
  68. So suppose this is our key.
  69. Then the ciphertext is just the result of XOR
  70. in each message bit with the corresponding key bit.
  71. So that's our ciphertext.
  72. So the question is, as an interceptor,
  73. you saw just this ciphertext, you don't know anything
  74. about the message or the key, and you're going to guess
  75. possible key values to try to figure out what the message is.
  76. And what key value would you guess
  77. that would mislead you to think that the message
  78. was actually BS instead of CS?