SHA512 圖像的近似大小

讓 $ s: {0,1}^* \to {0,1}^{512} $ 是 SHA512 雜湊（其中 $ {0,1}^* $ 是所有有限的可數集 $ {0,1} $ 字元串。

是否知道 $ |\text{im}(s)|/2^{512} \geq 0.5 $ ?

如果是，最大的是什麼 $ n\in\mathbb{N} $ 這樣 $ |\text{im}(s)|/2^{512} \geq 1 - (1/2)^n $ ?

這是未知的，但懷疑是這種情況。如果我們將 SHA-512 建模為在其 codomain 上均勻分佈的偽隨機函式，則如果所有球都未命中，則固定輸出箱將保持為空。

我們在這里扔 $ k $ 球進 $ n $ 垃圾箱。如果所有球都錯過了輸出箱，則輸出箱仍然是空的，這是有可能發生的 $$ (1-1/n)^k = \left[(1-1/n)^n\right]^{k/n}<e^{-k/n} $$ 在哪裡 $ n=2^{512} $ 和 $ k>n $ . 如果我們希望這個機率嚴格小於 $ 1/n^2 $ 我們需要解決

$$ e^{-k/n}<\frac{1}{n^2}=e^{- 2 \ln n} $$ 這使 $ k>2 n \ln n. $

我們現在可以在這個事件的補集上應用聯合界限（它很弱，但問題是關於無限域大小，所以這很好）並註意，因為有 $ n $ bins任何bin 為空的機率嚴格小於 $ n(1/n^2)=1/n. $

這給 $$ k>2^{513+\log_2 \ln 512} $$ 如果我沒有犯計算錯誤。

引用自：https://crypto.stackexchange.com/questions/99795