Funcții hash, bijectivitate și entropie

Acest lucru este deja răspuns Aici pentru 1 iterație și Aici pentru multe iterații, dar deoarece ultimul răspuns prezintă un argument euristic, voi lăsa aici Lema 4 din Grafice funcționale și aplicațiile lor în atacurile generice asupra construcțiilor hash iterate care oferă o bună aproximare bazată pe teorema 2 a Statistici de cartografiere aleatorie, și (3.10) din Pe înălțimea copacilor:

Lema 4. Lăsa $f$ fi o mapare aleatorie în $\mathcal{F}_N$. Denota $N = 2^n$. Pentru $k \le 2^{n/2}$, așteptarea numărului de noduri de imagine k-a iterate în graficul funcțional al $f$ este $$ (1 - \tau_k)\cdot N \aprox \left(\frac{2}{k} - \frac{2}{3}\frac{\log k}{k^2} - \frac{c}{ k^2} - \dots \right) \cdot N\,. $$ sugerează că $\lim_{k \to \infty} k\cdot (1 - \tau_k) = 2$. Prin urmare, $$ \lim_{N \to \infty, k \to \infty, k \le \sqrt{N}}(1 - \tau_k)\cdot N \approx 2^{n - \log_2 k + 1}\,, $$ Unde $\tau_k$ satisface recidiva $\tau_0 = 0, \tau_{k+1} = e^{-1+\tau_k}$, și $c$ este o anumită constantă.

Deci, deși da, există o oarecare pierdere de entropie din cauza iterării repetate a unei funcții aleatorii, această pierdere crește doar logaritmic în funcție de numărul de iterații. A pierde, să zicem, $32$ biți de entropie, trebuie să repetați hash-ul în jur $2^{32}$ ori. Pentru lungimi mari de ieșire, cum ar fi $256$ biți, acest tip de pierdere este neglijabilă pentru aproape toate scopurile practice.