現(xiàn)在，為了使事情變得更糟，我們說它不可能發(fā)現(xiàn)碰撞。然而，有些方法可以保證發(fā)現(xiàn)碰撞?？紤]以下簡單的方法來查找具有256位輸出大小的哈希函數(shù)的碰撞：挑選2的256次方加1個不同的值，計算它們中每一個的hash值，并檢查是否有兩個一樣的輸出。由于我們選擇了比可能輸出更多的輸入，所以當應(yīng)用哈希函數(shù)時，它們中的一些必須發(fā)生碰撞。

上面的方法保證會找到碰撞。但是，如果我們選擇隨機輸入并計算哈希值，那么在檢查2的256次方加1個輸入之前，我們會高概率的發(fā)現(xiàn)碰撞。事實上，如果我們隨機選擇2的130次方加1個輸入，結(jié)果會有99.8％的概率至少有兩個會碰撞。事實上，我們可以通過只是粗略地檢查可能的輸出數(shù)量的平方根來找到?jīng)_突，這現(xiàn)象在概率上被稱為第二天悖論。在本章末尾家庭作業(yè)的問題中，我們將對此進行更詳細的研究。

這種碰撞檢測算法適用于每個哈希函數(shù)。但是，問題在于這需要很長很長的時間。對于具有256位輸出的哈希函數(shù)，在最壞的情況下，您必須計算哈希函數(shù)2的256次方加1次，平均大約2的128次方次。這當然是一個天文數(shù)字——如果一臺計算機每秒計算10,000次hash值，那么需要超過一千萬（10的27次方）年的時間來計算2的128次方個hash值！以另一方式來思考這個問題，我們可以這樣說，如果人類制造的每一臺計算機從宇宙誕生以來都開始計算，到目前為止，他們發(fā)現(xiàn)沖突的幾率仍然是非常渺小的。如此之小，比地球在接下來的兩秒鐘內(nèi)被一顆巨大的流星摧毀的幾率都要小得多。

熱點：usdt 收Usdt 泰達幣