Solved

Block-cipher encryption, probability question

Posted on 2004-09-26
10
476 Views
Last Modified: 2013-11-13
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
Comment
Question by:younoeme
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 2
  • 2
  • +1
10 Comments
 
LVL 84

Accepted Solution

by:
ozo earned 350 total points
ID: 12157388
a) (N-1)/N
0
 

Expert Comment

by:meaculpa1113
ID: 12157397
thank you.. but would u pls mind elaborating and the reasoning behind the answer?

cheers,
0
 
LVL 84

Expert Comment

by:ozo
ID: 12157752
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
Independent Software Vendors: 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!

 

Expert Comment

by:meaculpa1113
ID: 12157940
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
 
LVL 84

Expert Comment

by:ozo
ID: 12157993
Are we fixing t and then summing over all t` <= N-t?
And who's asking this question?  younoeme  or  meaculpa1113?
0
 

Author Comment

by:younoeme
ID: 12161532
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
 

Author Comment

by:younoeme
ID: 12164477
any suggestions..??

thankis,
0
 
LVL 84

Expert Comment

by:ozo
ID: 12165498
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
 

Expert Comment

by:ibrahim7887
ID: 38908561
i think it is not enough answer
if there are more details
will be good
0
 

Expert Comment

by:ibrahim7887
ID: 38908590
the valid answer for a is 1/(N-t)!
if any one has mathematical details please write it
0

Featured Post

Independent Software Vendors: 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!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article explores the design of a cache system that can improve the performance of a web site or web application.  The assumption is that the web site has many more “read” operations than “write” operations (this is commonly the ca…
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

729 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question