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.

There are (N-1)! mappings where C[i] = E[K'](P[i])
only one of which where K=K'
so ((N-1)!-1)/(N-1)! of them are different mappings.

0

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

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?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.