Question 1

Wouldn't it be better to choose his card, and put a decoy card inside the box?

Accepted Answer

I agree, a decoy would have been a good idea, but if they knew a "decoy" existed, then the odds of her picking the right card just got better.

Question 2

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.

Accepted Answer

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.

Question 3

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.

Accepted Answer

Great question, the answer is no - and it's important to see why (see other questions on this). If **every** outcome is equally likely how would you eliminate anything? Remember, the encrypted text will be indistinguishable from a random string.

Question 4

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?

Accepted Answer

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.

Question 5

If rolling dice is a generator of psuedo-randomness, then couldn't you make a computer that rolls a pair of dice then uses a camera to read it? Wouldn't that be true randomness?

Accepted Answer

no because it would not be random. because computers only do what people do for them

Question 6

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.

Accepted Answer

"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?

Question 7

2:28
How do shannons proofs pertain to information theory?

Accepted Answer

Great question! The Information Theory lesson will explain this eventually. (hint. randomness is difficult if not impossible to compress)

Question 8

what if he doesn't lock the correct card

Accepted Answer

I would put the card back in the deck and then lock the empty box

Question 9

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?

Accepted Answer

This cipher can be easily broken by looking at the letter frequency fingerprint. Any method that directly maps letters to other letters will have this vulnerability.

Question 10

I disagree with Brit. There's still a chance of her guessing the card, even if it is a small one.

Accepted Answer

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.

Course: Computer science theory > Unit 2

Perfect secrecy

Want to join the conversation?

Video transcript