3 ms·
You are correct: by the pigeonhole principle, if the sum of the lengths of all the hashes/checksums is less than the length of the checksummed data, then collis
by versteegen 10y ago
You are correct: by the pigeonhole principle, if the sum of the lengths of all the hashes/checksums is less than the length of the checksummed data, then collisions exist.
(A detail: If checksums are included into the input of other checksums, their length doesn't count towards the amount of checksummed data, because they are not free to vary.)
- jeeceebees 10y agoWouldn't this imply that all hash functions (other than one-to-one mappings) must have collisions? Why does the pigeonhole principle hold?
- glitch003 10y agoYes, this is correct. It's a really simple principle, and I think an explanation can help you understand :) Suppose you have 3 holes, and 4 pigeons, and you stuff the pigeons into holes. There must be 1 hole with at least 2 pigeons, right? The same is true with hash functions. If you're hashing data down to a fixed length, like say 256-bits with sha-256, and the data is longer than 256 bits, there must be a collision somewhere.
- userbinator 10y agoWouldn't this imply that all hash functions (other than one-to-one mappings) must have collisions? Yes, they do. Finding them is the hard part.
- clarkcox3 10y agoYes; by definition using something with X possible values to represent something with Y possible values will always have collisions if X < Y.