[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 505
  • Last Modified:

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..
0
younoeme
Asked:
younoeme
  • 4
  • 2
  • 2
  • +1
1 Solution
 
ozoCommented:
a) (N-1)/N
0
 
meaculpa1113Commented:
thank you.. but would u pls mind elaborating and the reasoning behind the answer?

cheers,
0
 
ozoCommented:
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
meaculpa1113Commented:
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?
0
 
ozoCommented:
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).

cheers,

0
 
younoemeAuthor Commented:
any suggestions..??

thankis,
0
 
ozoCommented:
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
http://www.experts-exchange.com/memberAgreement.jsp
you should not have more than one account.
0
 
ibrahim7887Commented:
i think it is not enough answer
if there are more details
will be good
0
 
ibrahim7887Commented:
the valid answer for a is 1/(N-t)!
if any one has mathematical details please write it
0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

  • 4
  • 2
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now