碰撞的數學：從生日悖論到雜湊安全性

「碰撞」的概念在機率論和電腦科學中都至關重要。無論是小房間內有兩個人共享同一個生日，還是安全系統中兩個不同的輸入產生了相同的雜湊值，其底層數學原理都是一樣的。理解這些機率往往違背直覺，進而導致了通常所說的「生日悖論」。

本文探討了生日問題的數學基礎、由 Richard von Mises 引入的從特定機率到一般機率的轉變，以及這些概念如何應用於現代網路安全和雜湊表（hash table）的效率。

生日悖論：為什麼 23 是神奇數字

乍看之下，認為房間裡只需要 23 個人就有 50% 的機會讓兩個人共享同一個生日，這聽起來似乎不合理。直覺往往會出錯，因為我們通常在思考某人共享「我們」特定生日的機率。然而，當我們尋找的是「任何」兩個人共享「任何」生日時，悖論就產生了。

為了計算這個，尋找反向機率會更容易：即該群體中沒有人共享生日的機率。對於一個 $n$ 個人的群體：

• 第一個人可以有任何生日 (365/365)。
• 第二個人必須有不同的生日 (364/365)。
• 第三個人必須與前兩個人不同 (363/365)。

對於 $n=23$，所有生日都唯一的機率大約是 49.3%，這意味著至少發生一次碰撞的機率為 50.7%。正如一位社群成員所指出的，「驚訝」之處在於主題從「你」本身轉向了群體中的「任何兩個人」。

擴展範圍：佔用機率

雖然計算配對是直接的，但要確定更複雜的碰撞機率——例如在 60 個人的群體中，有三個人共享同一個生日——則更為困難。1930 年代保險數學局的早期嘗試通常會得到極低的機率（僅幾千分之一），因為他們關注的是三個人共享一個「特定、預先選定之日」的機率。

1939 年，數學家 Richard von Mises 將視角轉向了「佔用機率」（occupancy probability）。他不再詢問某個特定箱子（日期）是否包含三個球（人），而是建議觀察所有的箱子，並計算有多少個箱子包含三個或更多的球。

透過將其視為期望值 $E(x_s)$，數學計算發生了顯著變化。對於一個 60 個人的群體，三重複合的期望機率大約是 0.22。這意味著在每 4 到 5 個 60 人的群體中，大約會發生一次三重複合的生日匹配，這比之前的計算結果顯示的事件要常見得多。

電腦科學中的實際應用

這個數學框架不僅僅是一個有趣的現象；它是我們在電腦科學中處理數據的方式之基礎。

雜湊表碰撞

在雜湊表中，「日期」變成了表格欄位，而「人」變成了雜湊值。生日問題允許開發者根據所選的表格大小和輸入項目的數量，來估算會發生碰撞的次數。這對於維持表格的性能至關重要，因為過多的碰撞會降低查詢速度。

網路安全中的生日攻擊

在安全領域，「生日攻擊」（Birthday Attack）是一種用於尋找加密雜湊函數碰撞的暴力破解法。攻擊者不會等待特定的雜湊值出現；他們只是不斷生成隨機輸入，直到「任何」兩個輸入產生了相同的輸出。

由於生日問題的平方根特性，碰撞可以在大約 $\sqrt{n}$ 次嘗試中被找到。例如，使用 SHA-256，其具有 $2^{256}$ 種可能的輸出，攻擊者大約需要 $2^{128}$ 次嘗試來找到碰撞。雖然這仍然是一個巨大的數字，但它比尋找特定雜湊值所需的 $2^{256}$ 次嘗試要小得多。

檢測 RNG 缺陷

除了安全，這些原理也被用於測試隨機數生成器（RNGs）。一個週期為 $2^{32}$ 且分佈完全均勻的 RNG 應該在最初的 $2^{32}$ 次輸出中發生零次碰撞。然而，一個真正的隨機序列在僅 200,000 次輸出後，預期會顯示大約 100 次碰撞。這種差異允許工程師檢測出一個 RNG 是否只是在返回其狀態的 1 對 1 置換，而不是表現得像隨機行為。

結論

生日問題告訴我們，碰撞的發生機率遠比我們的直覺所暗示的要高。透過從特定目標轉向一般佔用，我們可以更好地預測複雜系統的行為，從房間內的人口統計學到世界上最敏感數據的安全。