Hash Functions and Probabilty

147 Views Asked by At

We are considering bit strings of length 160. Let there be some input x, and hash function $H(x) \rightarrow \left \{ 0,1 \right \}^{160}$. How many turns at least it takes to make collision: $H(x_{1})=H(x_{2})$?

I've heard that it may have something common with Birthday Paradox or some probability inequality.

1

There are 1 best solutions below

2
On

You might look at the generalized birthday problem. What is the appropriate number for $d$, the equivalent of the number of days in a year? This presumes that your question is inputting many different inputs $x_i$ and looking for the first collision of any pair.