Block-cipher encryption, probability question
Posted on 2004-09-26
I was looking at this question in a book that I am reading, and it seemed intriguing. I am an algorithms person, not too strongly inclined towards math, but though an answer to this would be curious enough.
Question: consider a block encryption algorithm that encrypts blocks on lenght n, and let N = 2^n. Say we have t plaintext-ciphertext pairts P[i], C[i] = E[K](P[i]) where we assume that the key K selects one of the N! possible mappings. Imagine that we wish to find K by exhaustive search. We could generate key K' and test whether C[i] = E[K'](P[i]) for 1 <= i <= t. If K' encrypts each P[i] to its proper C[i] then we have evidence that K = K'. However, it may be the case that the mappings E[K](X) and E[K'](X) exactly agree on the t plaintext-ciphertext pairs P[i], C[i] and agree on no other pairs.
a) What is the probability that E[K](X) and E[K'](X) are in fact distinct mappings?
b) What is the probability that E[K](X) and E[K'](X) agree on anohter t' plaintext-ciphertext pairs where 0 <= t' <= N - t?
Seems a little complicated, but actually really isn't. I understand the question and the point behind it, but just dont have the mathematical skills to compute it. Any help is much appreciated.