younoeme
asked on
Block-cipher encryption, probability question
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.
Thank you..
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.
Thank you..
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.
only one of which where K=K'
so ((N-1)!-1)/(N-1)! of them are different mappings.
any suggestions on the the 2nd question?
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?
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?
Are we fixing t and then summing over all t` <= N-t?
And who's asking this question? younoeme or meaculpa1113?
And who's asking this question? younoeme or meaculpa1113?
ASKER
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).
cheers,
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).
cheers,
ASKER
any suggestions..??
thankis,
thankis,
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?
According to
https://www.experts-exchange.com/memberAgreement.jsp
you should not have more than one account.
Were the t test pairs chosen in advance?
According to
https://www.experts-exchange.com/memberAgreement.jsp
you should not have more than one account.
i think it is not enough answer
if there are more details
will be good
if there are more details
will be good
the valid answer for a is 1/(N-t)!
if any one has mathematical details please write it
if any one has mathematical details please write it
cheers,