在部分雜湊中發現衝突是否經常不是一個壞問題？
我的情況：我已經在自己獨特的雜湊函式上工作了幾個月，我已經更改了很多次並且有兩個主要版本，但我不會讓任何人對我的工作細節感到厭煩；至少不在這裡。我來這裡是想問一個對任何試圖設計加密雜湊的人都有幫助的具體問題。（我希望）
現在我很清楚，僅僅作為一個通常不受信任的隨機函式，並不能產生密碼安全的 hash。
然而，我的問題是： 如果發現碰撞的頻率低於隨機函式預測的頻率，這是否是一個警鐘，我們可能有一些經驗上的弱點？
請允許我詳細說明：
在我的測試中，我發現來自不相關輸入（或相關輸入但不同輸出）散列函式數組的任何給定的 32 位集合（來自散列中的某個位置）確實看起來是隨機的，直到我注意到：發現碰撞：平均而言，一個人必須經歷大約 89000 次不同的嘗試（儘管顯然數字大幅波動）。由於生日界限只有 65536（或 ~77000），所以似乎有些不對勁。由於我的測試涉及使用不同 PRNGS 的電池來創建輸入以及非隨機的有條理的輸入，並且我執行了這些測試數億次，這意味著我已經進行了數十億次雜湊……我不認為這是我的測試有缺陷或我的樣本量太小。
我幾乎可以 100% 的自信地說，發現碰撞所花費的嘗試比真正隨機（理想）輸出所期望的要多。
旁注：我嘗試了 16 位、40 位樣本等，但總是得出相同的結果：衝突不太頻繁。
第二個旁注：當將散列描述為 PRNG 或使用散列的 PRNG 時，它通過了死硬套件上的生日間距測試就好了（我覺得這有點令人困惑）。
如果有人可以解釋這種奇怪的現象（頑固地通過但在我自己的測試中失敗），那麼加分但我想知道的是：
因此，鑑於我們在給定的散列中確實有“期望的隨機碰撞機率”（從邏輯上講，該散列中的任何較小的單詞），那麼當在給定的單詞（並且可能是一般的散列）中發現碰撞時會發生什麼預期的？我們獲得了哪些關於可能的原像攻擊的資訊？實際上是非理想分佈或任何其他資訊？
我知道這可能是一個很難回答的問題，但也許不是。
當我們繪製獨立的均勻隨機整數時有不同的生日界限 $ d $ （對於一些大 $ d $ ， 包含 $ d=2^{32} $ 問題）並註意碰撞：
- 在加密貨幣中，我們經常考慮 $ \sqrt d $ ( $ 65536 $ 為了 $ d=2^{32} $ ) 繪製，在該處有相當大的碰撞機率： $ p\approx1-1/\sqrt e\approx39.3% $ . 這也與最有可能發生第一次沖突的抽籤次數有關。
- 開始可能的抽籤次數（ $ p\ge1/2 $ ) 至少有一次碰撞；那是關於 $ \sqrt{\log4}\sqrt d $ ( $ \approx1.17741\sqrt d $ , $ \approx77163 $ 為了 $ d=2^{32} $ ); 更精確的公式在這裡。
- 第一次碰撞出現的平均（等效：預期）抽籤次數；那是關於 $ \sqrt{\pi/2}\sqrt d $ ( $ \approx1.25331\sqrt d $ , $ \approx82137 $ 為了 $ d=2^{32} $ ); 更精確的公式在這裡。
三者之間的區別是因為離散機率分佈的眾數、中位數和均值不是一回事（有點：我們以前很少發生碰撞 $ 77163 $ ，並且通常在此之後具有第一次碰撞方式，因此均值明顯更大）。混亂可能是導致問題差異的原因。
如果對於某些可能的雜湊函式，對於可能的隨機輸入（限制在仍然比輸出域大得多的域），我們始終觀察到衝突的頻率遠低於這些邊界所預測的頻率，那麼
- 我們可能的隨機輸入（或其域）是有偏差的
- 並且我們的雜湊函式在隨機預言模型中是不安全的，其方式與我們的隨機輸入中的偏差有關。
