Birthday-Attack
生日攻擊機率為 1
根據維基百科，
$ n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}} $
設 n(p;H) 是我們必須選擇的最小數量的值，這樣發現碰撞的機率至少為 p。如果我希望我的機率為 1 怎麼辦？在這種情況下， $ p = 1 $ 和 $ \frac{1}{1-1} $ 未定義。我可以知道如何使用上面的公式找到與機率為 1 的碰撞所需的最小值嗎？
要獲得機率為 1 的碰撞，您需要散列 $ H+1 $ 不同的價值觀。你可以看到，因為如果你只散列 $ H $ 值，每個值都可能碰巧散列到唯一的散列輸出；如果有任何合理大小的散列函式，這是極不可能的，但它確實有一個非零機率發生。另一方面，如果我們散列 $ H+1 $ 不同的值，我們知道（根據鴿子洞原理（因為只有 $ H $ 散列輸出），兩個輸入必須散列到相同的輸出。
Wikipedia 上的表達式是機率近似值，無論如何請查看早期的近似值
$$ p\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^2/(2H)} $$ 這表明您可以實現機率 $ 1-\varepsilon $ 對於任何 $ \varepsilon>0 $ 如果你讓 $$ e^{-n^2/(2H)}=\varepsilon $$或者$$ n=\sqrt{2 H \ln (1/\varepsilon)}. $$ 為了保證碰撞，您需要 $ 1+H $ 鴿巢原則的不同價值觀。接近機率一比保證它快得多。