Main content
Course: Computer science theory > Unit 2
Lesson 1: Ancient cryptography- What is cryptography?
- The Caesar cipher
- Caesar Cipher Exploration
- Frequency Fingerprint Exploration
- Polyalphabetic cipher
- Polyalphabetic Exploration
- The one-time pad
- Perfect Secrecy Exploration
- Frequency stability property short film
- How uniform are you?
- The Enigma encryption machine
- Perfect secrecy
- Pseudorandom number generators
- Random Walk Exploration
© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice
The one-time pad
The perfect cipher. Created by Brit Cruise.
Want to join the conversation?
Did the German Enigma machine use polyalphabetic cypher or something even more advanced? I'm looking forward to seeing more of these videos!(162 votes)
From the author:(it was a very long polyalphabetic cipher) Video on this coming up next(148 votes)
Wouldn't a computer be able to test all the possibilities very fast(65 votes)
If you had 100 letters of code then even if a computer tests all possibilities immediately it would just give you all possible sequences of 100 letters. There is no way it can work out which sequence of 100 letters is most likely to be the real text because each is equally likely.(17 votes)
Doesn't this shift the problem to finding out how to transmit the one time pad key? How do you do something like this if you can't meet the person you're trying to communicate with securely before sending your message?(57 votes)
Yes, which is why it's not used very often. It can only be used if you can meet the other person and transfer the pad to them securely. It was used during the Cold War when Moscow and Washington set up a "Hotline" to allow the leaders to communicate securely.
Another problem is that it is actually quite difficult to generate large quantities of truly random numbers. Generally to generate many numbers you use a computer, but computer's aren't very good at generating randomness.(35 votes)
What really is "perfectly secret"?
Is that really possible, because you can guess and check forever until you get the right key?(13 votes)- Watch the Perfect Secrecy video. You can guess and check forever, but you don't know which of your guess and checked results is the correct one. The intended message could be anything in the Message Space. A four letter word could be guess and checked into oops, east, west, down, side, left, bird, or any four letter word. Just to make your life a little bit harder, in some versions of the One Time Pad, the spaces are coded as well, so you really will never know what the message is. Unless you have the key, or the enemy's method of automated encryption or transfer is flawed and not a true 1TP.(28 votes)
- What is the difficulty of using the one-time pad? If it is so secret and hard to break due to the randomly selected numbers, why wouldn't everyone use the method?(13 votes)
- The biggest problem with the one time pad (OTP) is the key:
-you can only use the key once
-the key must be randomly chosen, and the same size of the message
So it tends to beg the question, that if Alice and Bob could meet to securely exchange a key the same size as the message, why wouldn't they just exchange the message ?
In practice, to make the OTP useful Alice and Bob need to exchange a list of keys that they will agree to use in the future when they send messages to each other. Every time they use a key they need to scratch it off their list and use the next key. When they run out of keys, they will need to meet again to exchange a new list.
In practice, this could be a big problem. Here's a scenario that illustrated why:
Suppose Alice and Bob are at war with Eve and they need to exchange battle plans. Unfortunately they can't cross the battlefield to meet each other.
Before they got separated Alice and Bob, exchanged a 1000 page book full of keys, with 10 keys per page, for a total of 10,000 keys. Suppose each key is 1000 bytes.
Each day Alice sends Bob 1 picture showing her battle plans. The size of the picture is 1 MB (Where we mean 1 MB=1,000,000 bytes). This means every day she needs to use (1 MB/1000 bytes) =1000 keys to send the one picture. In just 10 days Alice will have used 10,000 keys, and Alice and Bob will no longer be able to send messages securely using the OTP unless they can exchange a brand new list of keys.
If instead of the OTP, Alice and Bob decided to use a cipher like AES-256, they could share a 256 bit key once, and reuse the same key over and over, while still remaining very confident that their messages are secure. While AES-256 isn't perfectly secure it is secure enough.
Hope this makes sense(25 votes)
- Why doesn't Eve steal the random shift too? Why does she just steal the message?(4 votes)
Ideally, the key is not sent unencrypted. Perhaps Alice and Bob met in person to set up the key.(5 votes)
why would a computer not be able to use an algorithm to solve this? what was that algorithm called where it sorted different length collums and only moved them over one space at a time or something like that.(2 votes)
You could. But an algorithm, given enough time, will find every possible combination of letters of that length, with no way to tell which one is the right message. Without knowing the pad, "ATTACKEAST", "ATTACKWEST", and "RETREATNOW" are all equally plausible messages.
Sorting algorithms have very little to do with this. Either you're talking about bubble sort or insertion sort.(5 votes)
If the key is longer than the message, will it be more or less secure?(2 votes)
If the key is longer than the message, no changes to the security of the cipher will be made. It will still be a One-Time Pad and only the part of the key at the beginning that is as long as the message will be used. The rest is simply unnecessary.(4 votes)
- But how does Bob know how to decrypt it?
If the key is sent to him, it would be possible for Eve to "share" it and then intercept the message.(3 votes)
That's the problem of the one-time pad.
You see, perfect secrecy depends on the scenario that Eve cannot intercept the key.(2 votes)
- I've read somewhere that reusing the same key in OTP is very bad. Why?(2 votes)
- The more you reuse it, the easier it is to find and thus crack.(3 votes)
Video 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.