SHA-1：可能輸入的數量，可能的輸出數量，有多少輸入具有相同的輸出，
從 Wikipedia 我讀到 SHA-1 函式產生 160 位的輸出，並期望最大消息大小為 $ 2^{64}-1 $ 位。那正確嗎？
如果我訂購所有可能的輸入，我會產生 $ \approx 2^{2^{64}} $ 不同的位數組輸入，對吧？
目前不確定消息 0 是否與消息 00 不同。
我們可以說 SHA-1 接收到一個最大的位數組嗎 $ 2^{64}-1 $ 元素作為輸入？如果位數組小於 $ 2^{64}-1 $ 元素就像接收 0 的其餘部分（或者可能開始接收 0 直到……）？
我不擅長大數字……也許差異很小。如果 0 位數組與 00 位數組不同，可能輸入的數量仍然是 $ \approx 2^{2^{64}} $ .
然後 $ 2^{160} $ 是 $ \approx 2^{2^8} $ .
所以有 $ 2^{2^{64}} $ 可能的輸入 $ 2^{2^{8}} $ 可能的輸出。這意味著有 $ \approx \frac{2^{2^{64}}}{2^{2^8}} $ 每個輸出的輸入。但 $ \frac{2^{2^{64}}}{2^{2^8}} $ 是 $ \approx 2^{2^{64}} $ .
如果 $ 2^{2^{64}} $ 是整個宇宙看起來幾乎整個宇宙都在每個桶內（雜湊輸出）。
這是否意味著如果我隨機選取一組不同的輸入 $ 2^{2^{64}} $ 元素屬於同一個桶的機率很高嗎？
從 Wikipedia 我讀到 SHA-1 函式產生 160 位的輸出，並期望最大消息大小為 $ 2^{64}-1 $ 位。那正確嗎？
是的，看起來不錯。
如果我訂購所有可能的輸入，我會產生大約。 $ 2^{2^{64}} $ 不同的位數組輸入，對吧？
是的。可能輸入的數量是可能的數量之和 $ l $ -位字元串 $ l $ 從 $ 0 $ 至 $ 2^{64}-1 $ :
$$ \sum_{l=0}^{2^{64}-1} 2^l ;=; 2^{2^{64}} - 1 $$
如果位數組小於 $ 2^{64}-1 $ 元素就像接收 0 的其餘部分（或者可能開始接收 0 直到……）？
實際上，SHA-1 的填充旨在防止這種情況發生。如果 $ \text{SHA-1} $ 是一個安全的密碼散列函式，它應該不可能想出任何兩條消息 $ m_1 $ , $ m_2 $ 這樣 $ \text{SHA-1}(m_1) = \text{SHA-1}(m_2) $ （即雜湊衝突）。如果這是真的 $ \text{SHA-1}(m) = \text{SHA-1}(m | 0) $ ( $ | $ 是連接），這將違反此要求。
如果 $ 2^{2^{64}} $ 是整個宇宙看起來幾乎整個宇宙都在每個桶內（雜湊輸出）。
這是一個很好的直覺。 $ 2^{160} $ 是一個巨大的數字，但是 $ 2^{2^{64}} $ 超出天文數字（估計少於 $ 2^{266} $ 可見宇宙中的原子）。這就是密碼散列函式如此有趣的原因。我們知道有數量驚人的碰撞輸入對，但我們找不到任何（或者至少，我們無法使用良好的雜湊函式：SHA-1 已損壞，並且很可能已經有人發現碰撞）。
這是否意味著如果我隨機選取一組不同的輸入 $ 2^{2^{64}} $ 元素屬於同一個桶的機率很高嗎？
如果一個桶意味著一個給定的雜湊輸出，那麼不，機率非常低。讓我們假設 SHA-1 是一個強大的、完整的散列函式。從一組輸入中選擇一個 $ 2^{2^{64}}-1 $ ， 叫它 $ m_1 $ ， 然後讓 $ h_1 = \text{SHA-1}(m_1) $ . 注意 $ h_1 $ 是其中之一 $ 2^{160} $ 可能的值。現在隨機選擇第二個輸入，呼叫它 $ m_2 $ ， 然後讓 $ h_2 = \text{SHA-1}(m_2) $ . 的機率 $ h_2 $ 最終與 $ h_1 $ 是 $ 1/2^{160} $ .
這個解釋可能更符合你的直覺： $ 2^{2^{64}}-1 $ 可能的輸入分為 $ 2^{160} $ 大小相等的桶（至少大約大小相等）。所有這些桶都是巨大的，但是桶太多了，在同一個桶中選擇兩個值的機率仍然很低。