Kích thước gần đúng của hình ảnh của SHA512

Điều này là không rõ nhưng nghi ngờ là trường hợp. Nếu chúng ta lập mô hình SHA-512 dưới dạng một hàm giả ngẫu nhiên được phân phối đồng đều trên tên miền của nó, thì một ngăn đầu ra cố định sẽ trống nếu tất cả các quả bóng bỏ lỡ nó.

Ở đây chúng tôi đang ném $k$ quả bóng vào $n$ thùng. Thùng đầu ra vẫn trống nếu tất cả các quả bóng bỏ lỡ nó, điều này xảy ra với xác suất $$ (1-1/n)^k = \left[(1-1/n)^n\right]^{k/n}<e^{-k/n} $$ ở đâu $n=2^{512}$ và $k>n$. Nếu chúng ta muốn xác suất này hoàn toàn nhỏ hơn $1/n^2$ chúng ta cần phải giải quyết

$$ e^{-k/n}<\frac{1}{n^2}=e^{- 2 \ln n} $$ cái nào mang lại $k>2 n \ln n.$

Bây giờ chúng ta có thể áp dụng các công đoàn ràng buộc (yếu nhưng câu hỏi là về kích thước miền vô hạn, vì vậy điều này ổn) về phần bổ sung của sự kiện này và lưu ý rằng vì có $n$ thùng xác suất rằng không tí nào bin trống hoàn toàn nhỏ hơn $n(1/n^2)=1/n.$

điều này mang lại $$ k>2^{513+\log_2 \ln 512} $$ nếu tôi không mắc lỗi tính toán.