Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

The Birthday Paradox

Demonstrates that, in a hash function, the probability of finding two different inputs that produce the same hash is surprisingly high, impacting security assumptions.
📜

The statement of the theorem

Let MM be the size of the hash output space (the number of possible hash values). Consider a sequence of NN randomly chosen inputs x1,x2,…,xNx_1, x_2, \dots, x_N mapping to H(xi)∈{0,1}kH(x_i) \in \{0, 1\}^k, where M=2kM = 2^k. The probability P(N)P(N) of finding at least one collision (i.e., H(xi)=H(xj)H(x_i) = H(x_j) for i≠ji \ne j) is given by:\nP(N)=1−∏i=1N−1(1−iM)P(N) = 1 - \prod_{i=1}^{N-1} \left(1 - \frac{i}{M}\right) \nFor N≪MN \ll M, the probability of collision approaches 1/21/2 when NN reaches approximately πM/2\sqrt{\pi M / 2}. Specifically, N≈1.2MN \approx 1.2 \sqrt{M} ensures P(N)≥0.5P(N) \ge 0.5.
Source: Wikipedia