截斷雜湊對熵的影響
假設我有一個 128 位隨機二進製字元串（128 位熵），然後我使用 SHA-256 對其進行雜湊處理，然後獲取輸出雜湊的前 128 位。獲取的位串是否仍然具有（幾乎）128 位的熵或熵減少到 64 位？（我的意思是另外 64 位熵可能位於輸出雜湊的第二個 128 位中）。
我很困惑，因為在我過去讀過的加密雜湊函式的定義中，有人說如果輸入的一位發生變化，那麼輸出的每一位都以 $ 1/2 $ . 由此看來，我們可以推斷出我們截斷的輸出仍然具有（幾乎*）與輸入相同的熵。是對的嗎？
*：我添加了“幾乎”來表示忽略可能的雜湊衝突。
隨機預言機輸出中的預期熵
輸出的期望熵 $ h $ -bit 隨機預言機 $ h $ -位輸入接近 $ h-0.8272 $ 位，即使是中等的 $ h $ （例如，至少 $ 32 $ ）。作為 $ h $ 增長，預期熵變得任意接近 $ h-\eta $ 位與 $$ \begin{align}\eta&=\frac 1{e\ln(2)}\sum_{i=1}^\infty\frac{\ln(i+1)}{i!}\ &=0.82724538915300508343173\dots\text{bit}\end{align} $$ 其中總和由A193424給出。
證明，我將在哪裡使用 $ a\approx b $ 作為方便的簡寫 $ \displaystyle\lim_{h\to\infty}\frac a b\ =\ 1 $
- 對於預言機實現的特定發行版，讓 $ n_j $ 是精確出現的輸出值的數量 $ j $ 所有輸入的輸出之間的時間。準確的熵 $ H $ 對於該特定分佈，可以從 $ n_j $ 通過應用熵的定義，給出 $$ \begin{align}H&=\sum_{j=1}^{2^h}n_j;\frac j {2^h};\log_2\left(\frac{2^h}j\right)\ &=\frac h{2^h}\sum_{j=1}^{2^h}j;n_j;-\frac 1{2^h}\sum_{j=1}^{2^h}n_j;j;\log_2(j)\end{align} $$ 我們擁有的地方（僅通過計算所有輸入導致的結果） $$ \sum_{j=1}^{2^h}j;n_j;=2^h $$ 因此 $$ h-H=\frac 1{2^h}\sum_{j=1}^{2^h}n_j;j;\log_2(j) $$
- 對於固定 $ j $ 並作為 $ h $ 增長，通過計算可能性，我們可以確定對於隨機分佈，達到任何特定值的機率 $ j $ 時代是 $ \displaystyle\approx\frac 1{e;j!} $ . 因此對於固定 $ j $ 並作為 $ h $ 增長，預期 $ n_j $ 是 $ \displaystyle\approx\frac{2^h}{e;j!} $ .
- 在確切的表達中 $ h-H $ ，總和中的所有項都是非負的。獲得期望的漸近線 $ h-H $ 什麼時候 $ h $ 增長，因此我們可以替換 $ n_j $ 由其期望值，並獲得，當 $ h $ 增長的期望值 $ h-H $ 是 $ \displaystyle\approx\frac 1 e\sum_{j=1}^\infty\frac{j;\log_2(j)}{j!} $ .
- 聲明的結果如下定義 $ i=j-1 $ ，並刪除總和的第一項，即零。
我一直無法找到來源；我發現的最接近的是經驗推導 $ \eta $ Andrea Röck的 4 位小數：基於隨機函式引起的熵損失的碰撞攻擊，WEWoRC 2007，幻燈片；在她的論文中有更多內容。
我的第一個經驗推導是使用一個程序來繪製 $ 2^h $ 偽隨機 $ h $ -位值併計算達到多少個值多少次；為了 $ h=35 $ （我可以用 20GB RAM 做的最大的），三個執行給出了：
run 1 run 2 run 3 0 12640123427 36.79% 12640183855 36.79% 12640308584 36.79% 1 12640408212 36.79% 12640365800 36.79% 12640104651 36.79% 2 6320124091 18.39% 6320013534 18.39% 6320174710 18.39% 3 2106681541 6.13% 2106762262 6.13% 2106726749 6.13% 4 526645276 1.53% 526674914 1.53% 526679947 1.53% 5 105334156 0.31% 105325000 0.31% 105330269 0.31% 6 17561277 0.05% 17551924 0.05% 17556150 0.05% 7 2507918 0.01% 2508727 0.01% 2505282 0.01% 8 313971 0.00% 313943 0.00% 313406 0.00% 9 34748 0.00% 34553 0.00% 34755 0.00% 10 3424 0.00% 3542 0.00% 3546 0.00% 11 291 0.00% 287 0.00% 292 0.00% 12 31 0.00% 24 0.00% 24 0.00% 13 4 0.00% 3 0.00% 2 0.00% 14 1 0.00% 0 0.00% 1 0.00% 15+ 0 0.00% 0 0.00% 0 0.00% entropy 34.172763 bit 34.172758 bit 34.172751 bit應用於問題：SHA-256 輸出的熵被截斷為第一個 $ 128 $ 隨機餵食時的位 $ 128 $ -bit輸入是關於 $ 127.173 $ 位，從非常接近 $ 128 $ 截斷前的位（見最後注）。截斷不會將熵減半，因為兩半不是獨立的。正確的構想是 SHA-256 被截斷為它的第一個 $ 128 $ 位很好 $ 128 $ -bit 雜湊，其行為類似於隨機預言機。
注意：如果我們考慮一個隨機函式 $ {0,1}^{128} $ 到 $ {0,1}^{256} $ , 很可能有一個小 $ k $ （最經常 $ 0 $ 或者 $ 1 $ , 有時 $ 2 $ ， 很少 $ 3 $ 或更多）使得 $ k $ 輸出正好有兩個對應的輸入， $ 2^{128}-2k $ 輸出只有一個，並且 $ 2^{256}-2^{128}+2k $ 輸出沒有（任何輸出達到三次或更多次的機率可以忽略不計）。
因此，在這種最有可能的情況下，當輸入隨機數時，該函式的輸出熵 $ 128 $ -位輸入是 $ -k;2^{-127}\log_2(2^{-127})-(2^{128}-2k);2^{-128}\log_2(2^{-128}) $ ， 那是 $ 128-k;2^{-127} $ .
我們為 SHA-256（未截斷）提供的最佳模型 $ 128 $ -位輸入是從以下函式中隨機選擇的特定函式 $ {0,1}^{128} $ 到 $ {0,1}^{256} $ ，因此我們可以得出 SHA-256 在隨機輸入時輸出的熵 $ 128 $ -bit 輸入很可能正是 $ 128-k;2^{-127} $ 為了 $ k\in{0,1,2} $ , 非常接近 $ 128 $ 位，下降到小數點後 37位左右。