If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

The one-time pad

The perfect cipher. Created by Brit Cruise.

Want to join the conversation?

  • piceratops ultimate style avatar for user ∫∫ Greg Boyle  dG dB
    Did the German Enigma machine use polyalphabetic cypher or something even more advanced? I'm looking forward to seeing more of these videos!
    (165 votes)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user samuel.c.18287
    Wouldn't a computer be able to test all the possibilities very fast
    (64 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user Daryl
    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)
    Default Khan Academy avatar avatar for user
    • leafers sapling style avatar for user Peter Collingridge
      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)
  • old spice man green style avatar for user Jungwoo Sheen
    What really is "perfectly secret"?
    Is that really possible, because you can guess and check forever until you get the right key?
    (14 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user Varun
      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.
      (27 votes)
  • leaf green style avatar for user TL
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • piceratops ultimate style avatar for user Dicky Wira Senjaya
    Why doesn't Eve steal the random shift too? Why does she just steal the message?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • hopper happy style avatar for user Cody R.
    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)
    Default Khan Academy avatar avatar for user
    • leaf grey style avatar for user Alex
      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)
  • aqualine ultimate style avatar for user Ziming Lan
    If the key is longer than the message, will it be more or less secure?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user Sen
    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)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user Sammy
    Wasn't the One-Time Pad the one cipher that when you had a letter you roll dice and the letter couldn't repeat which created a leak?Wasn't the One-Time Pad also used in the Enigma and had the Allies confused until they found out this leak and the Enigma workers didn't use dice to start the Enigma?That helped created the bomb in which the key setting could be found in the key space.
    (3 votes)
    Default Khan Academy avatar avatar for user

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.