Solved

Block-cipher encryption, probability question

Posted on 2004-09-26
10
466 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
  • 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
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 

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

Active Directory Webinar

We all know we need to protect and secure our privileges, but where to start? Join Experts Exchange and ManageEngine on Tuesday, April 11, 2017 10:00 AM PDT to learn how to track and secure privileged users in Active Directory.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Word Problem 4 88
Windows Batch File - Count Down 4 88
How to install SVN Command Line Client? 5 78
What is CANH and CANL voltage when CAN Trasceiver is in sleep mode ? 2 19
Introduction This article discusses the Chain of Responsibility pattern, explaining What it is;Why it is; andHow it is At the end of this article, I hope you will be able to describe the use and benefits of Chain of Responsibility.  Backgrou…
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…
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.
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…

828 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