任意兩個使用者生成相同的 128、256、2048 位密鑰的機率是多少？
有一些協議要求使用者在本地（客戶端）生成一些隨機密鑰，而沒有伺服器權限來“批准”或“拒絕”他們的密鑰，並且基於這樣的假設，即兩個使用者極不可能想出同一把鑰匙。比特幣就是其中之一。
兩個不同的使用者想出的機率是多少：
- 相同的隨機生成的 128 位字元串。
- 相同的隨機生成的 256 位字元串。
- 相同的隨機生成的 2048 位 RSA 密鑰。
- 由於散列衝突，兩個使用者擁有相同的 128/256 位公鑰散列的機率是多少？
與比特幣相比如何？
如果有 $ n $ 一個房間裡的人，他們的生日是獨立均勻分佈的 $ k = 365 $ 可能性，他們中至少有兩個生日相同的機率是多少？ 稱這個機率 $ P(C; n, k) $ , 之間的碰撞機率 $ n $ 有的人 $ k $ 可能的生日。這是機率的補 $ P(D; n, k) = 1 - P(C; n, k) $ 他們的生日都是不同的，這更容易直接計算：
- 如果只有一個人，他們的生日總是不同的，因為有 365 種可能性，每種可能性都有機率 $ 1/365 $ ，一個人所有不同生日的機率是 $ \frac{365}{365} = 1 $ 正如我們所希望的那樣。
- 如果有兩個人，不管第一個人的生日是什麼，第二個人的生日只有364種可能性，每個人都有機率 $ 1/365 $ , 所以兩個人生日不同的機率是 $ \frac{365}{365} \cdot \frac{364}{365} $ .
- 對於三個人，第三個人只有 363 種與前兩個不同的可能性，所以三個人生日不同的機率是 $ \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} $ 等*。*
一般來說，如果有 $ n $ 人和 $ k $ 可能的生日，所有生日都不同的機率是$$ P(D; n, k) = \frac{k}{k} \cdot \frac{k - 1}{k} \cdot \frac{k - 2}{k} \cdots \frac{k - n}{k}. $$ 自從 $ \frac{k - \ell}{k} = 1 - \frac \ell k $ ，我們可以將其重寫為
$$ \begin{equation} P(D; n, k) = \biggl(1 - \frac 1 k\biggr) \biggl(1 - \frac 2 k\biggr) \cdots \biggl(1 - \frac n k\biggr). \end{equation} $$
使用方便的花花公子屬性 $ e^{-2x} \leq 1 - x \leq e^{-x} $ 對於任何 $ 0 \leq x \leq 1/2 $ （證明），我們可以為所有生日不同的機率設置一個下限，只要 $ n \leq k/2 $ :
$$ \begin{multline} P(D; n, k) \geq e^{-2/k} e^{-4/k} e^{-6/k} \cdots e^{-2n/k} = e^{-2(1 + 2 + 3 + \cdots + n)/k} \ = e^{-n(n - 1)/k} \geq 1 - \frac{n (n - 1)}{k} \geq 1 - \frac{n^2}{k}. \end{multline} $$
這設置了存在任何生日碰撞的機率的上限：
$$ \begin{equation} P(C; n, k) = 1 - P(D; n, k) \leq \frac{n^2}{k}. \end{equation} $$
顯然，我們真正感興趣的不是生日，而是密碼系統中的密鑰。那裡有很多人，超過七十億。讓我們四捨五入 $ n = 2^{40} $ ，這是一個很大的數字，但如果這個星球上的每個人平均有數百個鑰匙，那麼這個數字似乎是合理的，或者 $ n = 2^{64} $ ，這是一個非常大但並非難以想像的鍵數量。
$$ \begin{equation} \begin{array}{cccc} & \text{#keys, $k$} & P(C; n = 2^{40}, k) & P(C; n = 2^{64}, k) \ \hline \text{AES-128 key} & 2^{128} & 2^{-48} & 1(?) \ \text{secp256k1 key} & \approx2^{256} & 2^{-176} & 2^{-128} \\ \text{RSA-2048 key}^* & \approx2^{1013} & 2^{-933} & 2^{-885} \end{array} \end{equation} $$
對於 RSA-2048 密鑰，真正的問題不僅僅是模數*衝突，而是任何主要因素的衝突。此處的條目假設具有 1024 位因子的兩個素數 RSA，並使用近似值 $ \pi(n) \approx n/\log n $ 對於素數計數函式 $ \pi(2^{1024}) - \pi(2^{1023}) \approx 2^{1014} - 2^{1013} = 2^{1013} $ . 擴展到多質 RSA 留給讀者作為練習。
好奇的入口 $ 1(?) $ 在 AES-128 的行中並不意味著發生碰撞的機率為 1——顯然直到 $ n = k $ ; 它只是意味著上面計算的界限不是很緊 $ n \approx \sqrt{k} $ . 更嚴格的界限是可能的，但隨著使用者數量的增長 $ \sqrt{k} $ ，碰撞的機率迅速增加並收斂到 $ 1 $ . 因此，除了 AES-128，如果您想要 128 位安全級別，無論如何都不應該使用它，兩個使用者碰巧選擇相同密鑰的可能性微乎其微——當然，除非他們的隨機數字生成器被破壞了，這比我們希望的要經常發生。
鍵的雜湊值衝突怎麼辦？ 對於像 SHA-256 這樣的任何固定散列函式，這很難準確知道，但我們可以通過統一隨機函式對其進行建模 $ f $ ， 在哪裡 $ f(x) $ 是每個不同的獨立均勻隨機散列值 $ x $ . 如果使用者生成的密鑰是 $ x_1, x_2, \dots, x_n $ , 並假設可能的鍵數與可能的雜湊值相同，那麼雜湊值之間發生衝突的機率是多少 $ f(x_1), f(x_2), \dots, f(x_n) $ ? 考慮兩個互斥事件：
- 鍵之間有衝突 $ x_1, x_2, \dots, x_n $ , 這發生在機率上 $ P(C; n, k) $ . 在此條件下，雜湊之間發生衝突的機率 $ f(x_1), f(x_2), \dots, f(x_n) $ 顯然是1。
- 按鍵 $ x_1, x_2, \dots, x_n $ 都是不同的，這很有可能發生 $ P(D; n, k) = 1 - P(C; n, k) $ . 在此條件下，雜湊 $ f(x_1), f(x_2), \dots, f(x_n) $ 是 $ n $ 獨立的均勻隨機變數 $ k $ 可能的值，因此它們之間發生衝突的機率為 $ P(C; n, k) $ .
因此，密鑰雜湊之間發生衝突的機率為 $$ P(C; n, k) + (1 - P(C; n, k)) \cdot P(C; n, k) \ = 2 P(C; n, k) - P(C; n, k)^2 \leq 2 \frac{k^2}{n}, $$ 如果密鑰之間發生衝突的機率是，這也可以忽略不計。
（將分析擴展到比散列更大的鍵，例如使用 SHA-256 散列 RSA-2048 鍵，留給讀者練習。）
如果您使用BLAKE2使用SHA-256（或其他位值）或（其他雜湊算法的範例）生成雜湊值，您可以保持冷靜，因為碰撞問題幾乎是不可能的。
如果X 輸入只有一位與 Y 輸入****不同，則生成的雜湊將完全不同。
*如果我正確理解了這個問題。