Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Block-cipher encryption, probability question

Posted on 2004-09-26
Medium Priority
499 Views
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
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
• 4
• 2
• 2
• +1

LVL 84

Accepted Solution

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

Expert Comment

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

cheers,
0

LVL 84

Expert Comment

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

Expert Comment

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

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

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

ID: 12164477
any suggestions..??

thankis,
0

LVL 84

Expert Comment

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

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

Expert Comment

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

## Featured Post

Question has a verified solution.

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

This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
Introduction A frequently used term in Object-Oriented design is "SOLID" which is a mnemonic acronym that covers five principles of OO design.Â  These principles do not stand alone; there is interplay among them.Â  And they are not laws, merely princâ€¦
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201â€¦
###### Suggested Courses
Course of the Month11 days, 3 hours left to enroll