On Sat, Mar 10, 2012 at 7:28 PM, Jon Callas <[email protected]> wrote:
>>
>> 2) Is it known if every (valid) digest has always more than one
>> preimage? To state it otherwise: Does a collision exist for every
>> message? (i.e., is the set h^{-1}(x) larger than 1 for every x in the
>> image of h?).
>>
>
> Sure, by the pigeonhole principle. Consider a hash with 256-bit (32-byte)
> output. For messages larger than 32 bytes, by the pigeonhole principle, there
> must be collisions. For messages smaller than 32 bytes, they might collide on
> themselves but don't have to, but there will be some large message that
> collides with it.
I think you are misunderstanding the question (or at the very least I
am). The pigeonhole principle only shows that there exist collisions
not that collisions exist for every element in the codomain.
Think about the function over the natural numbers:
f(x) = {
1, if x = 0
2, if x > 0
3, if x < 0
}
While there exist collisions within N it isn't true that every element
in the co-domain has a collision.
--
Eitan Adler
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
