如何計算 PRNG 的輸出熵
假設種子密鑰的熵為 $ H(n) $ 這是 $ n $ - 位長且隨機，PRNG 的輸出位長為 $ 2^n $ ，它將用作長時間執行的密鑰。雖然在這種情況下很明顯，由於 PRNG 的輸出密鑰序列是從輸入種子密鑰導出的，所以 PRNG 的輸出密鑰序列的熵永遠不會超過種子密鑰的熵。 $ H(2^n) \le H(n) $ 在這種情況下，但如何證明呢？
TL;DR：應用的思維過程是錯誤的。熵是隨機變數的函式，而不是任意整數的函式。PRNG 不會增加熵的事實是由於輸入空間有限並且算法沒有其他輸入，因此無法增加熵。
首先，讓我們回顧一下“熵”的正式定義（可以在《應用密碼學手冊》第 2.2 章 PDF中找到）：
定義熵或不確定性_ $ X $ 被定義為 $ H(X)=-\sum_{i=1}^np_i\lg p_i=\sum_{i=1}^np_i\lg (\frac{1}{p_i}) $ 在哪裡，按照慣例， $ p_i\cdot \lg p_i=p_i\cdot \lg (\frac{1}{p_i})=0 $ 如果 $ p_i=0 $ .
符號： $ \lg a $ 是的二進制對數 $ a $ . $ X $ 是一個隨機變數，取每個值 $ x_i $ （從一個有限集如果大小 $ n $ ) 對應的機率 $ p_i $ .
現在讓我們建模 $ m $ - 位串作為隨機變數 $ X $ . 這 $ m $ -bit 字元串可以取 $ n_X=2^m $ 值，每個都有機率 $ p_i=\frac{1}{n_X}=2^{-m} $ . 從而熵 $ H(X) $ 是
$$ H(X)=\sum_{i=1}^np_i\lg (\frac{1}{p_i})=\sum_{i=1}^{2^m}2^{-m}\lg (2^m)=2^m\cdot(2^{-m}m)=m $$正如預期的那樣。
下一步是正確建模“PRNG”。我將它建模為偽隨機生成器(PRG)，因為我假設這就是你的意思。
簡而言之：偽隨機生成器(PRG) 是一種確定性算法，它採用固定長度的輸入並返回更長的輸出。
（不是一個完整的正式定義，通常的定義將限制為多項式大小的輸出，但我們在這裡不需要）
通過這個我們可以模擬我們的 PRG $ \mathcal G: {0,1}^m\rightarrow {0,1}^{2^m} $ . 作為 $ {0,1}^m $ 只能拿 $ 2^m $ 狀態，這是函式的唯一輸入，我們知道最多可以有 $ 2^m $ PRG 的不同輸出。
如果我們將 PRG 輸出建模為隨機變數 $ Y $ ，我們知道（在“最好的情況下”） $ p_i=2^{-m} $ 為了 $ 2^m $ 不同的 $ y_i $ 和 $ n_Y=2^{2^m} $ . 我們進一步知道，對於剩下的 $ 2^{2^{m}}-2^m $ 可能的值 $ y_i $ , $ p_i=0 $ 持有。有了這些資訊，我們可以計算 PRG 熵的上限：
$$ H(Y)=\sum_{i=1}^np_i\lg (\frac{1}{p_i})=\sum_{i=1}^{2^m}2^{-m}\lg (2^m)+\sum^{2^{2^m}-2^m}_{i=1}0\cdot\lg(\frac{1}{0})=2^m\cdot(2^{-m}m)+(2^{2^m}-2^m)\cdot 0=m $$ 注意 $ 0\cdot \lg(\frac{1}{0}) $ 是，按照慣例， $ 0 $ .
正如我們所建模的 $ Y $ 用作最佳“PRG”，很可能沒有 $ 2^m $ 不同的輸出。所以我們可以得出結論
$$ H(X)\geq H(Y) $$正如預期的那樣，因此 PR(N)G 本身不會增加熵。