Re: AES-128 keys unique for fixed plaintext/ciphertext pair?

[Arnold G. Reinhold]

At 5:45 PM -0600 2/18/03, Matt Crawford wrote:

 > ... We can ask what is the

 probability of a collision between f and g, i.e. that there exists
 some value, x, in S such that f(x) = g(x)?

But then you didn't answer your own question.  You gave the expected
number of collisions, but not the probability that at least one
exists.

That probability the sum over k from 1 to 2^128 of (-1)^(k+1)/k!,
or about as close to 1-1/e as makes no difference.

But here's the more interesting question. If S = Z/2^128 and F is the
set of all bijections S->S, what is the probability that a set G of
2^128 randomly chosen members of F contains no two functions f1, f2
such that there exists x in S such that f1(x) = f2(x)?

In general, if G has n randomly chosen members of F, isn't the answer just 1/e**(n**2)? There are n**2 pairs of functions in G (ok n*(n-1)) and the probability of no collision for each pair is 1/e as you point out above.

G is a relatively miniscule subset of F

Just plain minuscule:  |G| = 2**128,  |F| = (2**128)!  ~= 2**(2**135)

but I'm thinking that the
fact that |G| = |S| makes the probability very, very small.

Even if |G| << |F| that is true. If G contains 5 functions, there are 20 pairs and 1/e**20 ~= 2.06E-9.


Arnold Reinhold



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]