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
With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work 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?