Dimensiunea aproximativă a imaginii lui SHA512

Acest lucru este necunoscut, dar se suspectează că este cazul. Dacă modelăm SHA-512 ca o funcție pseudoaleatoare care este distribuită uniform pe codomeniul său, un coș de ieșire fix rămâne gol dacă toate bilele îl ratează.

Aici aruncăm $k$ bile în $n$ pubele de gunoi. Un recipient de ieșire rămâne gol dacă toate bilele o ratează, ceea ce se întâmplă cu o probabilitate $$ (1-1/n)^k = \left[(1-1/n)^n\right]^{k/n}<e^{-k/n} $$ Unde $n=2^{512}$ și $k>n$. Dacă dorim ca această probabilitate să fie strict mai mică decât $1/n^2$ trebuie să rezolvăm

$$ e^{-k/n}<\frac{1}{n^2}=e^{- 2 \ln n} $$ care dă $k>2 n \ln n.$

Acum putem aplica legat de sindicat (ceea ce este slab, dar întrebarea este despre dimensiunea infinită a domeniului, deci este bine) pe complementul acestui eveniment și rețineți că din moment ce există $n$ bins probabilitatea ca orice bin este gol este strict mai mic decât $n(1/n^2)=1/n.$

Asta da $$ k>2^{513+\log_2 \ln 512} $$ dacă nu am făcut o eroare de calcul.