CRC32碰撞概率

Question

我已經完成了很多其他問題的檢查，並且我仍然不確定這個問題。

這裏是我的用例：

我有一個在線購物車。偶爾，某些客戶發現訂購流程太繁瑣，或者有些客戶在線訂單不會削減訂單，並且他們需要實際的PDF估算（報價）才能購買產品。

因此，我編寫了一個採購購物車內容的模塊，並將其整齊排列爲PDF估算值。

現在，因爲這個過程只使用購物車的內容，並沒有使用任何其他的東西，甚至沒有數據庫，我不得不創建一個唯一的估計文件編號，所以如果客戶支付報價，他們有一個參考用於他們的付款指示。

購物車目前會生成一個5位數的購物車ID，每位顧客根據他們的會話都是唯一的。我已經拿到了這個5位數的購物車ID，然後我給它添加了UNIX時間，這給了我一個很好的長號碼作爲估算文件號碼。

所以我最終是這樣的：363821482812537 [36382是車ID和1482812537是UNIX時間在生成的PDF估計時間]

這裏的問題是，它是太長了，由於銀行付款參考資料有限，將成爲一個問題。理想情況下，我想保留10個字符或更少。

我決定看看CRC32以縮短生成的估計數，並且它似乎能夠將估計數縮短爲可接受的字符數。

但是，誰能說明我可能會遇到什麼樣的碰撞？

幾件事情要考慮：

1. 車ID將永遠是5個位數。

2. Unix時間永遠是10位，直到今年2286

[那麼我們將永遠結束了15位需要被編碼，並沒有更多]

有一個安全措施，如果有機會發生重複，則會引發錯誤，並提供選項以重試並生成估計。這是通過將估計值保存到與估計值相匹配的文件名（或者在這種情況下，估計值的CRC32哈希）來完成的 - 然後首先檢查是否存在帶有哈希的文件名。

由於我的問題並不重要，客戶暫時不可以自行生成估算值。所以它只會是可以產生估計值的管理員。

我關心的是簡單的，我會發現自己遇到了碰撞經常與我的15位到CRC32散列編碼，或者它會是相當難得碰上的衝突？

Answer 1

爲什麼不只是維護一個估算數字，你每次需要一個新的時候就增加一個？您已經有效地維護了使用的號碼列表以檢查是否存在衝突，因此請將您的櫃檯放在那裏。那麼你只需要看一件事情，而不是n的東西。通過採用CRC，您可以放棄您可能試圖從估算編號中提取的信息，因此，首先從該信息中提取ID是毫無意義的。你的方法似乎方式比它需要更復雜。

單個碰撞的概率爲2 ^-32。數據內容並不重要，只要它超過32位，就是在這種情況下，因爲CRC在混合位方面做得非常好。然而，如果您以前產生了n估計值，那麼您在碰撞時有n的機會。因此，當n增長時，碰撞的機會相應增加。 （見生日問題。）結果，在77,164次估計之後，其中兩個哈希相互碰撞的概率爲50％。