計算 50% 的衝突機率散列的消息的最小數量（生日悖論）

我在解決加密難題時遇到了這個問題。這就是謎題。

You have a hash which gives a 11-bit output. How many minimum messages do we have to hash to have a 50% probability of getting a collision.

通常我們會看到通過使用近似值來解決的問題 $ 2^{n/2} $ 或者 $ \sqrt {2^n} $

因此，對於 11 位散列，要散列的消息數量有 50% 的衝突機會將是

$ \sqrt {2^{11}} = 45.255 \approx 46 $ 消息

然而，這個謎題的解決方案使用

$ log_{\frac {2^{11} - 1} {2^{11}}}{(0.5)} = log_{\frac{2047}{2048}}{(0.5)} = 1419.22 \approx 1420 $ 消息

因此，您必須對大約 1420 條消息進行雜湊處理才能獲得 50% 的發生衝突機率。

該解決方案沒有解釋他們是如何做到這一點的。那麼哪個是正確的解決方案？

您大致正確；他們錯了。他們的答案計算了匹配特定值的機會，即雜湊反轉。看到這個 $ k $ 嘗試有一個 $ (2047/2048)^k $ 找不到匹配的，所以你想要 $ k>\log(0.5)/\log(2047/2048) $ .

對於小數字，我們可以通過找到最小的來計算生日界限的確切值 $ k $ 這樣 $$ \prod_{0\le i\le k}\frac{n-i}n=\frac {n!}{(n-k)!n^k}<0.5 $$ 在這種情況下是 $ k=54 $ .

引用自：https://crypto.stackexchange.com/questions/88748