• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 535
  • 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
What Kind of Coding Program is Right for You?

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.

 
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

What Kind of Coding Program is Right for You?

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.

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