The one-time pad | Journey into cryptography | Computer Science | Khan Academy


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.

Leave a Reply

Your email address will not be published. Required fields are marked *