Hàm băm, tính song ánh và entropy

Điều này đã được trả lời đây cho 1 lần lặp, và đây cho nhiều lần lặp lại, nhưng vì câu trả lời sau đưa ra một đối số heuristic nên tôi sẽ để lại ở đây Bổ đề 4 của Đồ thị hàm và ứng dụng của chúng trong các cuộc tấn công chung vào các cấu trúc hàm băm lặp lại mang lại một xấp xỉ tốt dựa trên Định lý 2 của Thống kê ánh xạ ngẫu nhiên, và (3.10) của Trên chiều cao của cây:

Bổ đề 4. Để cho $f$ là một ánh xạ ngẫu nhiên trong $\mathcal{F}_N$. Chứng tỏ $N = 2^n$. Vì $k \le 2^{n/2}$, kỳ vọng về số nút hình ảnh lặp thứ k trong đồ thị hàm của $f$ Là $$ (1 - \tau_k)\cdot N \approx \left(\frac{2}{k} - \frac{2}{3}\frac{\log k}{k^2} - \frac{c}{ k^2} - \dots \right) \cdot N\,. $$ Nó gợi ý rằng $\lim_{k \to \infty} k\cdot (1 - \tau_k) = 2$. Như vậy, $$ \lim_{N \to \infty, k \to \infty, k \le \sqrt{N}}(1 - \tau_k)\cdot N \approx 2^{n - \log_2 k + 1}\,, $$ ở đâu $\tau_k$ thỏa mãn sự lặp lại $\tau_0 = 0, \tau_{k+1} = e^{-1+\tau_k}$, và $c$ là một hằng số nào đó.

Vì vậy, trong khi có, có một số mất mát entropy do lặp đi lặp lại một hàm ngẫu nhiên, mất mát này chỉ tăng theo logarit trên số lần lặp lại. Để thua, nói, $32$ bit của entropy, bạn cần lặp lại hàm băm xung quanh $2^{32}$ lần. Đối với độ dài đầu ra lớn như $256$ bit, loại tổn thất này không đáng kể đối với hầu hết các mục đích thực tế.