Solved

Block-cipher encryption, probability question

Posted on 2004-09-26
10
451 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
 

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
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 

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

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Suggested Solutions

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…
Dependencies in Software Design In software development, the idea of dependencies (http://en.wikipedia.org/wiki/Coupling_%28computer_programming%29) is an issue of some importance. This article seeks to explain what dependencies are and where they …
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

760 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now