雜湊碰撞機率計算機
輸入
| 雜湊大小 | 128 |
|---|---|
| 項目數量 | 1,000,000 |
雜湊碰撞機率計算機
估算一組雜湊值中發生生日碰撞的機率，並計算在特定雜湊大小下達到 50% 碰撞機率所需的項目數量。
輸入
雜湊參數
結果
輸入數值即可顯示計算結果。
碰撞機率
雜湊碰撞機率
雜湊函式將任意長度的輸入映射為固定長度的輸出（稱為摘要）。理想情況下，不存在兩個不同輸入產生相同摘要的情況，此特性稱為碰撞抵抗性。實際上，由於輸出空間有限，碰撞必然存在；問題在於：需要雜湊多少個輸入，才有可能發生碰撞？本計算機使用生日近似法量化此機率，其名稱源自生日悖論。
生日悖論
在一群均勻隨機分佈於 365 天生日的 23 人中，任意兩人同天生日的機率已超過 50%。這個機率之所以遠高於直覺預期，是因為它計算的是群體中任意一對的匹配，而非與特定目標的匹配。相同的不對稱性也適用於雜湊碰撞：找到任意兩個輸入產生相同雜湊值（碰撞），遠比找到特定目標雜湊值的輸入（原像）容易得多。
計算公式
對於 位元輸出的雜湊函式，搜尋空間共有 個等可能的值。給定 個隨機雜湊項目，碰撞機率的精確公式為所有 個輸出均不同的機率的補集：
p=1−k=0∏n−1(1−2bk)當 較大且 適中時，生日近似法提供更簡潔的封閉形式：
p≈1−e−n2/(2⋅2b)求解碰撞機率達到 50% 時所需的項目數量：
n50%=2⋅2b⋅ln2計算範例
以 32 位元雜湊（如校驗碼中使用的 CRC32）為例：
n50%=2×232×ln2=2×4,294,967,296×0.6931≈5,954,124,768≈77,163在儲存庫中只要有 77,163 個檔案，就有約 50% 的機率出現兩個具有相同 32 位元 CRC 的檔案。以近似公式驗證：
p=1−e−771632/(2×232)≈1−e−0.693≈0.50這正是 CRC32 不適合作為大型資料集唯一識別碼的原因，儘管它是針對小型資料串流的出色錯誤偵測碼。
資安意涵
生日界限確立了一個原則： 位元的雜湊函式僅提供 位元的碰撞抵抗性。攻擊者大約需要 次雜湊計算即可找到碰撞，而非 次。這正是密碼雜湊函式的輸出位元數設計為目標安全等級兩倍的原因：
| 雜湊函式 | 輸出長度 | 碰撞抵抗性 |
|---|---|---|
| MD5 | 128 位元 | 約 （實際已被破解） |
| SHA-1 | 160 位元 | 約 （實際已被破解） |
| SHA-256 | 256 位元 | 約 （目前標準） |
| SHA-3-512 | 512 位元 | 約 （高安全性） |
MD5 和 SHA-1 被標記為「已被破解」，不僅是因為生日界限，更是因為研究人員發現了演算法弱點，能以遠低於 次運算找到碰撞。MD5 碰撞現在在一般電腦上只需數分鐘即可計算出來。
如需分析密碼搜尋空間的相關計算，請參閱 密碼強度（熵值）計算機。
常見問題（FAQ）
密碼學中的生日悖論是什麼？
生日悖論是一個反直覺的結論：在僅 23 人的群體中，就有超過 50% 的機率有兩人同一天生日——儘管一年共有 365 天。
同樣的數學原理適用於雜湊函式：攻擊者只需雜湊約 √(2^b) = 2^(b/2) 個項目，就有 50% 的機率找到兩個輸出相同的輸入，這就是生日攻擊。對於 128 位元的 MD5，此門檻約為 2^64 ≈ 1.8 × 10¹⁹ 個項目，遠少於原像攻擊所需的完整 2^128 次組合。
為何生日攻擊只需一半位元數即可破解？
原像攻擊必須找到特定的雜湊輸出，因此需要搜尋完整的 2^b 空間。生日攻擊只需找到任意兩個輸入碰撞，由生日界限可知，在約 2^(b/2) 個樣本後，找到此類配對的機率即超過 50%。這正是密碼雜湊函式通常設計為比目標安全等級多一倍輸出位元的原因：256 位元的雜湊函式提供 128 位元的碰撞抵抗性。
為何 MD5 和 SHA-1 被認為不安全？
MD5（128 位元）和 SHA-1（160 位元）已遭到實際碰撞攻擊破解，而非僅是生日界限的機率攻擊，而是利用演算法弱點，以遠比生日界限更高效的方式找到碰撞。2004 年，研究人員展示了 MD5 碰撞；2017 年，Google 的 SHAttered 計畫產生了首個公開已知的 SHA-1 碰撞。
這兩個函式在非密碼學用途（如校驗和與內容定址）上仍然安全，但不應用於需要碰撞抵抗性的場合，例如數位簽章或憑證機構。
碰撞和原像有何差異？
碰撞指找到任意兩個相異輸入 x 和 y，使得 hash(x) = hash(y)。原像指找到一個輸入 x，使其雜湊值等於特定目標值 h——難度更高，因為無法自由選擇兩個輸入。第二原像指找到與已知輸入 x 具有相同雜湊值的另一輸入 y。
以上三者按難度由低到高排列：碰撞抵抗性是最弱的屬性，第二原像抵抗性是最強的。用於數位簽章的雜湊函式必須抵抗第二原像攻擊；用於雜湊表或布隆過濾器的函式則只需具備較弱的碰撞抵抗性。