Tip:
Highlight text to annotate it
X
The answer is this one.
It's the probability that the message is M divided by the number of keys.
To see why let's think about our probability space.
We have all the possible messages being ordered.
We have message 0, message 1, all the possible messages.
There is some message that we've selected that's message M8.
We don't want to assume that the messages are uniformly distributed.
The probability that the message is M is not necessarily
1 divided by the number of messages.
If the messages were uniformly distributed, then this answer would also be correct.
But they're not. We don't want to assume that.
Maybe the attacker has some prior knowledge about the distribution of the messages.
That's normally the case.
Even if we don't know anything about the particular messages,
maybe we know it's a message in English.
Most random strings of text are not messages in English.
The other dimension in our probability space is the choice of the key.
There are K possible keys.
What we want to know is what is the intersection of these two events.
The M even is this line in our probability space.
Each one of these keys maps exactly one message to C.
We saw that before, that there is one key that maps each message to C.
We can think of that as being a diagonal line through our probability space.
This is the line where the encryption of Ki and Mi is equal to C.
Depending on what C is, it might not be a diagonal line.
But we can think of it that way, that there's one key
that maps each message to each cipher text.
That means there's exactly one point here where those two intersect.
If the distributions were normal, that would indeed by the correct answer.
It's one point and our space is the size of M times the size of K.
But the distribution isn't normal.
We don't want to make any assumption about the distribution of M.
For the keys we do want to assume that the distribution is normal,
that each key is equally likely. The keys are chosen perfectly at random.
We have the probability of picking M,
and we're multiplying that by the probability of picking this intersecting key.
We'll call that K.
But because the keys are uniformly distributed, we know that this probability is 1/K--
1 over the size of K.
We don't know that about the messages.
We leave that probability as it is.
That's why this is the answer to the probability that the message M intersected
with the encryption of the message is C.
Now let's go back to our definition.