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.

Are we fixing t and then summing over all t` <= N-t?
And who's asking this question? younoeme or meaculpa1113?

0

younoemeAuthor Commented:

i m not sure wat u mean by 'fixing' t'.. the way i understand it (and i dont mean to patronize) is if there are 10 given plaintext-ciphertext pairs for N = 121 what is the probability that K' = K for the remaining 120 of those..

meaculpa1113 = younoeme.. i had asked another questioin under meaculpa1113, and was checking that so just posted a reply to this one w/the same acct.. (have distributed points, so was balancing it out using 2 diff accts).

Are you asking if there are t matches, what's the probability that none of the other N-t plaintext-ciphertext pairs match?
Were the t test pairs chosen in advance?