According to the books that i have read, it says that S.H.A(Secure Hash Algorithm) is collision resistant.But if the input space is a 1024 bit number and the output space is a 512 bit message digest then shouldn't it be colliding for (2^1024)/(2^512) times? As the range is lesser than the domain being mapped there should have been collisions. please explain where i am going wrong.
9
votes
Related: Pigeonhole principle and Collision resistance
– Artjom B.
I'm voting to close this question as off-topic because this is purely about cryptography without involving programming.
– Maarten Bodewes
Yes, it will collide by definition. However, it should be impossible to calculate or guess which value collide. You cannot just iterate over possible values until you find a collision of course, you'd have run out of time (any time - pick your period) before you'd find a collision.
– Maarten Bodewes
(2^1024)/(2^512) = 2^512 which is close to 10^155 (which is bigger than a googol but less than a googolplex).
– zaph
What does "the input space is a 1024 bit number" mean? The only thing that counts is the number of unique inputs and in turn the number of unique outputs. Perhaps see Hash collision probability calculator.
– zaph
2 Answers
13
votes
The chance for a collision does not depend on the input size. The chance to a 512-bit hash collision is 1.4×10^77, see Probability table
9
votes
Maybe your book has also mentioned the definition of collision resistance? It does not mean that no collisions are created (which is clearly not the case), but that given a hash you are not able to create a message easily that produces this hash.
a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b
From Wikipedia
