The One-Time Pad

Applied math

Ancient Cryptography

What is Cryptography?
Probability Space
Probability space
The Caesar Cipher
Caesar Cipher Exploration
Frequency Fingerprint Exploration
Polyalphabetic Cipher
Polyalphabetic Exploration
The One-Time Pad
Perfect Secrecy Exploration
Frequency Stability
Coin flip sequences
Frequency Stability Exploration
The Enigma Encryption Machine (case study)
Perfect Secrecy
Pseudorandom Number Generators

The One-Time Pad The perfect cipher

Back

The One-Time Pad

⇐ Use this menu to view and help create subtitles for this video in many different languages. You'll probably want to hide YouTube's captions if using these subtitles.

For over four hundred 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-dice
to generate a long list of random shifts,
and share this with Bob, instead of a code word.
Now, to encrypt her message,
Alice uses the list of random shifts instead.
It's important that this list of shift is 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'd 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's no frequency differential,
and therefore no leak,
it's now impossible for Eve to break the encryption.
This is the strongest possible method of encryption,
and it emerges toward the end of the 19th century,
it's 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 1 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 5 times,
which is almost 12 millions.
Sometimes it's hard to visualize.
So imagine she wrote her name on a single page,
and on top of it, stack 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's the same as picking one of these pages at random,
from the perspective of Eve, the codebreaker,
every five letter encrypted word she has
is equally likely to be any word in this stack.
So, this is perfect secrecy in action.

Questions
Tips & Feedback

Be specific, and indicate a time in the video:

At 5:31, how is the moon large enough to block the sun? Isn't the sun way larger?

Have something that's not a question about this content?

Post a tip or feedback
General discussion about the site
Report a technical problem with the site
Request a video or feature

This discussion area is not meant for answering homework questions.

Formatting tips

Cancel or

( total)

Share a tip

When naming a variable, it is okay to use most letters, but some are reserved, like 'e', which represents the value 2.7831...

Suggest a fix

At 2:33, Sal says "double bonds" but should say "single bonds."

Have something that's not a tip or feedback about this content?

Ask a question
General discussion about the site
Report a technical problem with the site
Request a video or feature

This discussion area is not meant for answering homework questions.

Formatting tips

Cancel or

Discuss the site

For general discussions about Khan Academy, visit our Reddit discussion page.

Flag inappropriate posts

Here are posts to avoid making. If you do encounter them, flag them for attention from our Guardians.

abuse

disrespectful or offensive
an advertisement

not helpful

low quality
not about the video topic
soliciting votes or seeking badges
a homework question
a duplicate answer
repeatedly making the same post

wrong category

a tip or feedback in Questions
a question in Tips & Feedback
an answer that should be its own question

about the site

a question about Khan Academy
(Visit our FAQ)
a post about badges
a technical problem with the site
(Report a problem)
a request for videos or features