About this video
The answer to the leaky fingerprint problem is randomness: Alice and Bob share a long list of random shifts, as long as the message, so the shifts never repeat and the ciphertext has a uniform frequency distribution. This is the one-time pad, the strongest possible encryption, and the video shows its strength through the combinatorial explosion of possible encryptions.
You'll be able to
- explain how Alice and Bob use a list of random shifts to encrypt and decrypt a message.
- state the two properties that make the one-time pad impossible to break.
- compare the number of possible encryptions for a Caesar cipher and a one-time pad.
- explain why every possible plaintext looks equally likely to Eve.
Key words
- one-time pad
- A cipher that shifts each letter by its own random amount, using a list of shifts as long as the message.
- randomness
- Having no pattern, so each outcome is unpredictable, like rolling a fair die.
- uniform frequency distribution
- Every letter appears about equally often, so there is no fingerprint.
- brute force search
- Breaking a code by checking every possible key one by one.
- combinatorial explosion
- The huge, fast growth in the number of possibilities as you add more choices.
- perfect secrecy
- When the ciphertext gives Eve no information, so every message is equally likely.
Transcript
For over 400 years, the problem remained. How could Alice design a cipher that hides her fingerprint, thus stopping the leak of information? The answer is randomness. Imagine Alice rolled a 26 sided die to generate a long list of random shifts, and shared this with Bob instead of a code word.
Now, to encrypt her message, Alice uses the list of random shifts instead. It is important that this list of shifts be as long as the message, as to avoid any repetition. Then she sends it to Bob, who decrypts the message using the same list of random shifts she had given him.
Now Eve will have a problem, because the resulting encrypted message will have two powerful properties. One, the shifts never fall into a repetitive pattern. And two, the encrypted message will have a uniform frequency distribution. Because there is no frequency differential and therefore no leak, it is now impossible for Eve to break the encryption.
This is the strongest possible method of encryption, and it emerged towards the end of the 19th century. It is now known as the one-time pad. In order to visualize the strength of the one-time pad, we must understand the combinatorial explosion which takes place.
For example, the Caesar Cipher shifted every letter by the same shift, which was some number between 1 and 26. So if Alice was to encrypt her name, it would result in one of 26 possible encryptions. A small number of possibilities, easy to check them all, known as brute force search.
Compare this to the one-time pad, where each letter would be shifted by a different number between 1 and 26. Now think about the number of possible encryptions. It's going to be 26 multiplied by itself five times, which is almost 12 million. Sometimes it's hard to visualize, so imagine she wrote her name on a single page, and on top of it stacked every possible encryption.
How high do you think this would be? With almost 12 million possible five-letter sequences, this stack of paper would be enormous, over one kilometer high. When Alice encrypts her name using the one-time pad, it is the same as picking one of these pages at random.
From the perspective of Eve, the code breaker, every five letter encrypted word she has is equally likely to be any word in this stack. So this is perfect secrecy in action.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.