[12541] in cryptography@c2.net mail archive
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Tue Feb 18 20:17:46 2003
X-Original-To: cryptography@wasabisystems.com
X-Original-To: cryptography@wasabisystems.com
In-Reply-To: <200302182345.h1INjFG18103@gungnir.fnal.gov>
Date: Tue, 18 Feb 2003 19:42:18 -0500
To: Matt Crawford <crawdad@fnal.gov>
From: "Arnold G. Reinhold" <reinhold@world.std.com>
Cc: Greg Rose <ggr@qualcomm.com>,
Ralf-Philipp Weinmann <ralf@fimaluka.org>,
cryptography@wasabisystems.com
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 majordomo@wasabisystems.com
