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

Perfect secrecy

Claude Shannon's idea of perfect secrecy: no amount of computational power can help improve your ability to break the one-time pad. Created by Brit Cruise.

Want to join the conversation?

  • piceratops ultimate style avatar for user bennette1916
    Wouldn't it be better to choose his card, and put a decoy card inside the box?
    (192 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user Chapman Caddell
    What exactly is the difference between the key space and the other two? I guess I just do not really understand the definitions of all the spaces.
    (18 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Suppose Alice wants to send a letter to Bob.
      We call the contents of the original letter the Message or Plain Text

      If Alice wants to prevent someone from being able to understand the message while it is being sent to Bob, Alice will want to turn the original Message into text that others can not understand. The text that others can't understand is called Cipher Text . The process of turning a Message into Cipher Text is called encryption.
      Bob will then need to turn the cipher text back into plain text. The process Bob uses is called decryption.


      When you encrypt a message you choose a key to use. The Cipher Text that you get after encrypting a Message depends on what key you use
      i.e. if we have a message and encrypt one copy using key1 to get a cipher text 1
      and we encrypt another copy using a different key, key2, to get a cipher text 2
      cipher text 1 and cipher text 2 will usually be different

      Message Space- all of the possible messages Alice could send to Bob
      Key Space- all of the possible keys Alice could use to encrypt a message
      Cipher Text Space- all of the possible cipher texts that Alice could generate by encrypting messages

      Example:
      Alice wants to send a message to Bob.
      The only messages that Alice wants to send are "Yes","No" answers to 2 questions
      The Message Space = { (Yes,Yes),(Yes,No), (No,Yes), (No,No) } it has a size of 4

      Suppose Alice uses a method that only allows her to choose from the following keys to encrypt her message:
      key 1: results in the following encryptions (Yes,Yes)-> (W,W) ,(Yes,No)->(X,Z), (No,Yes)->(W,X), (No,No)->(X,X)
      key 2: results in the following encryptions (Yes,Yes)-> (Z,W) ,(Yes,No)->(W,W), (No,Yes)->(Z,X), (No,No)->(W,X)

      Alice and Bob need to have agreed on which key they are going to use.

      The Key Space = {key1,key2} it has a size of 2

      The only possible CipherTexts that Alice could generate are (W,W),(X,Z),(W,X),(X,X),(Z,W),(Z,X)

      The Cipher Text Space = { (W,W),(X,Z),(W,X),(X,X),(Z,W),(Z,X)} it has a size of 6

      Note: This example does not show perfect secrecy.
      e.g. A cipher text of (X,Z) reveals that the message must have been (Yes,No).
      e.g. A cipher text of (W,W) reveal that the 1st answer was Yes (Message was either (Yes,Yes) or (Yes,No) )


      Hope this makes sense.
      (54 votes)
  • mr pants teal style avatar for user Keaton Blazer
    Couldn't you test all the possible combinations using a computer and then search for a common, almost always used word like "the"? That would limit the number of possibilities drastically, and by running all of those messages through a spell/grammar check program, you could limit those possibilities further. Lastly, if you included spaces in the number of letters, you could search first for the message that had the nearest average number of letters per word; for example, ten letter words are rather rare, so you could generally eliminate those. Lastly, you could find the message that makes the most sense given the identity of the sender as well as the situation. Although this would not entirely eliminate "junk" messages, it would give you a much better idea of what they are messaging each other about.
    (8 votes)
    Default Khan Academy avatar avatar for user
  • starky tree style avatar for user Taylor
    But Eve could figure out his card, if she randomly guesses. I mean, if you randomly pick a number between one and ten and your friend guesses which number you picked, he could guess right. Is there some way to make SURE that Eve CANNOT guess the card?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Aaron Fink
      No, there will never be any way to make sure that Eve cannot guess correctly because there always is some correct answer and guessing can alway work. Even so, if the only way to find the answer is to guess randomly, this is considered "perfect secrecy."
      The problem is that there are only 10 possible choices in this example so guessing isn't difficult but imagine instead I pick a number between one and a sextillion (1,000,000,000,000,000,000,000). Now the chance of Eve guessing correctly is mind-bogglingly low. If Eve could guess 60 numbers a second for as long as it takes, it would take her on average 264,248,266,531 years to guess the correct number, or about 19 times longer than the universe has existed. And that's only a message of about 15 letters. Yeah.
      (7 votes)
  • male robot donald style avatar for user Isaac Mansfield
    I disagree with Brit. There's still a chance of her guessing the card, even if it is a small one.
    (0 votes)
    Default Khan Academy avatar avatar for user
    • piceratops ultimate style avatar for user Jasper
      The key point is that Eve has no way of knowing if she has the right card. Among the cards are all possible messages, not just a lot of noise surrounding one sensible message. If the message is "My name is Alice", then Eve may very well guess that. But the message could just as well be "My name is Bob". Eve cannot tell which is the right message, and therefore has no information about the content of the message. Eve has the same amount of information about the content of the message as she did before the message was sent.
      (16 votes)
  • piceratops ultimate style avatar for user raegan.walter
    I disagree that given a cyphertext, every messagetext is equally likely. Assuming the message is a message, and not just a string of letters, there are messagetexts that can be eliminated as the right answer.

    If you receive the cyphertext "gcy" and you know the messagetext is a single English word, you can throw out any solution that does not return at least one vowel.
    (3 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Kevin Connors
      "and you know the message text is a single English word"

      Why do you know that? What if someone was applying a one-time pad to a Caeser cipher? The Caeser cipher would provide unreadable text and then you encrypt that with a one-time pad. Besides "Attack the East" would still be indistinguishable from "Attack at night" since they have the same length so which do you defend against?
      (3 votes)
  • male robot johnny style avatar for user thomas worthen

    How do shannons proofs pertain to information theory?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user math_turtle
    I actually have an idea for a cipher that is pretty hard to break. I call it the fifth power cipher. This is the cipher:
    A=A
    B=F
    C=I
    D=J
    E=E
    F=B
    G=K
    H=H
    I=C
    J=D
    K=G
    L=L
    M=M
    N=N
    O=S
    P=V
    Q=W
    R=R
    S=O
    T=X
    U=U
    V=P
    W=Q
    X=T
    Y=Y
    Z=Z
    I know that some of the letters are the same after encryption, but consider an example. Say I want to encrypt the phrase "The world is round." Plugging it into my cipher gives "Xhe qsrlj co rsunj." And if you apply a Caesar cipher of 13 and another fifth power cipher, it gives "Gur jbeyq vo ebhaq." Pretty hard, right?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • starky ultimate style avatar for user Astro
    what if he doesn't lock the correct card
    (2 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user Kavach
    Do we use the one time pad still?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      It's still used for super secure applications, but very rarely.

      However, the idea is still used.
      1) First we start with a master key of some size.
      2) Then our messages will be broken up into small chunks of bits e.g. 64 bits.
      3) Then for each chunk we generate a pseudorandom key, based on our master key. The pseudorandom key will be the same size as the chunk.
      4) Then for each chunk it's pseudorandom key will be XOR'd with the chunk to encrypt it. So, it's the same as using the one time pad except the pseudorandom key is not truly random. Since the key is not truly random, it can still be broken (but it may be nearly impossible to break it).

      This method sacrifices a little bit of security, but allows us to use a short key for long messages.

      Hope this makes sense
      (2 votes)

Video transcript

(tranquil music) - [Voiceover] Consider the following game. Eve instructs Bob to go into a room. (door creaks shut) Bob finds the room empty, except for some locks, an empty box, and a single deck of cards. Eve tells Bob to select a card from the deck and hide it as best he can. The rules are simple. Bob cannot leave the room with anything, cards and keys all stay in the room, and he can put, at most, one card in the box. Eve agrees that she has never seen the locks. He wins the game if Eve is unable to determine his card. So what is his best strategy? Well, Bob selected a card, six of diamonds, and threw it in the box. (box clicks shut) First he considered the different types of locks. Maybe he should lock the card in the box with the key. Though, she could pick locks, so he considers the combination lock. The key is on the back, so if he locks it and scratches it off, it seems like the best choice. But suddenly he realizes the problem. The remaining cards on the table leak information about his choice, since it's now missing from the deck. The locks are a decoy. (metal jangles) He shouldn't separate his card from the deck. He returns his card to the deck but can't remember the position of his card. So he shuffles the deck to randomize it. Shuffling is the best lock, because it leaves no information about his choice. His card is now equally likely to be any card in the deck. He can now leave the cards openly, in confidence. Bob wins the game, because the best Eve can do is simply guess, as he has left no information about his choice. Most importantly, even if we give Eve unlimited computational power, she can't do any better than a guess. This defines what we call "perfect secrecy." On September first, 1945, 29-year-old Claude Shannon published a classified paper on this idea. Shannon gave the first mathematical proof for how and why the one time pad is perfectly secret. Shannon thinks about encryption schemes in the following way. Imagine Alice writes a message to Bob, 20 letters long. (paper ruffling) This is equivalent to picking one specific page from the message space. The message space can be thought of as a complete collection of all possible 20 letter messages. (paper ruffling) Anything you can think of that's 20 letters long is a page in this stack. Next, Alice applies a shared key, which is a list of 20 randomly generated shifts between one and 26. The key space is the complete collection of all possible outcomes, so generating a key is equivalent to selecting a page from this stack at random. When she applies the shift to encrypt the message, she ends up with a cipher text. The cipher text space represents all possible results of an encryption. When she applies the key, it maps to a unique page in this stack. Notice that the size of the message space equals the size of the key space equals the size of the cipher text space. This defines what we call "perfect secrecy," for if someone has access to a page of cipher text only, the only thing that they know is that every message is equally likely. So no amount of computational power could ever help improve a blind guess. Now the big problem, you're wondering, with the time pad, is we have to share these long keys in advance. To solve this problem, we need to relax our definition of secrecy by developing a definition of pseudo-randomness. (white noise)