Tip:
Highlight text to annotate it
X
The answer is there is always exactly 1.
For any message ciphertext pair, there is one key that maps that message to that ciphertext.
We can see that thinking about the nature of the one-time pad.
Suppose we just have 1-bit messages.
We have messages 0 and 1.
Then the key 0 will map 0 to 0.
The key 1 will map 1 to 0. The key 0 will map 1 to 1.
This works for any length message and any length key.
Note that the length of the key and the length of the message scale the same way.
If we had 2-bit messages there would be four different keys
that would map each message to each different ciphertext.
If we had 2-bit messages, there would also be one key
that maps each message to each different ciphertext.
For example, the key that maps 00 to 10 would be the key 11.
That means we can compute this probability,
summing over all the messages summing over all the keys
where we've got the probability that that key encrypts that message to the given ciphertext.
We need to divide this by the space, which is the size of the messages
times the size of the keys.
Now whats the value of the summation?
We know for a given message there is exactly one key that maps it to that ciphertext.
This is one, and we're summing over all the messages,
summing the value of 1.
That means we're going to get the number of messages divided by
the number of messages times the number of keys.
That's equal to 1 over the number of keys.
That's the probability of event B, which is probability
that some message encrypts to some key.
Notice this is computed over all the messages.
That's over the distribution.