估計輸入到 256 位散列的隨機數熵

假設隨機數生成過程輸出大量 0-9 之間的數字。首先，我收集了一堆數字，將它們轉換為二進制並創建了一個點陣圖。

不像你看到的那麼隨機！這就是為什麼你不應該只在電腦程序中使用原始整數作為隨機數的原因。看看當數字轉換為二進制時會發生什麼：

0  00110000
1  00110001
2  00110010
3  00110011
4  00110100
5  00110101
6  00110110
7  00110111
8  00111000
9  00111001

如您所見，前 4 位始終0011不是很隨機。即使看第 5 位也不是很隨機。從 0 到 7 始終是 0 位，只有 8 和 9 才是 1 位。

最後 3 位是隨機的嗎？

0  000
1  001
2  010
3  011
4  100
5  101
6  110
7  111
8  000
9  001

看起來數字 0-7 中的 3 位有所有可能的組合。但是 8 位和 9 位是 1 和 2 的副本。這有關係嗎？是否應該丟棄數字 8 和 9 以消除偏見？

我認為計劃可能是通過加密雜湊（例如 SHA 256）執行所有這些原始整數，然後將其用作密鑰。然而，為了獲得高質量的 256 位輸出，輸入散列的原始整數的正確數量是多少？我假設我需要 256 位輸入才能獲得良好的 256 位輸出，是嗎？

如果我做一些粗略的計算，我會得出：

3 bits of entropy per 8 bit (1 byte) number
256/3 = 85.33

這意味著我需要收集 85~ 個原始整數（682.67 位）並將它們輸入 256 位散列。那個聽起來是對的嗎？

或者最好從每個數字中獲取最後 3 位，直到我有 256 位熵，然後將其轉換為十六進制並通過加密雜湊執行？我想我只見過一個加密雜湊算法將十六進製或文本作為輸入……

有點不清楚，您如何轉換所有數字……例如，您如何將十進制數字解釋為“二進制”和“創建點陣圖”？然後你看看二進製表示並猜猜是什麼……它們只是二進制中的數字 0-9 並添加到一個靜態數字上（不知道它來自哪裡）。

需要考慮的事項：

• 當然數字 0-9 沒有整數大小的熵，這個範圍不是形式 $ 2^{x} $ . 其實是 $ 3.3219… $
• 如果您的數字在 0-9 上均勻分佈，則對固定位的評估將導致熵損失或均勻性損失（或兩者兼而有之）。
• 你的實際目標是什麼？一開始您提到“在電腦程序中”，然後是“將其用作密鑰”。隨機數有很多用途，不同的任務需要不同的屬性（因此需要不同的 PRNG）。

如何解決您的問題？

• 假設您想要 256 位的熵，並且您的 RNG 足以創建加密密鑰（如果您不知道其中的區別，請閱讀此內容）。
• 如果你不想“扔掉”熵，你可以在十進制系統中計算一個大的隨機數並使用你的 RNG（我們稱之為 $ \Re $ ) 對於每個數字。這樣它是均勻分佈的。您可以通過以下公式執行此操作： $ r = \sum_{k=0}^{t}10^k\cdot\Re $ . 你必須選擇 $ t $ 足夠大，至少涵蓋範圍從 $ 0 $ 到 $ 2^{256}-1 $ ， 意思是 $ t \ge 77 $ . 但現在你 $ r $ 仍然均勻分佈在“錯誤範圍”內，因為它可以大於 $ 2^{256} $ .
• 現在您可以決定如果結果高於該值是否要重新開始，這將導致“正確範圍”內的均勻分佈，因為您不會通過偏愛某些值而不是其他值來更改分佈……您只是從錯誤的結果重新開始。
• 或者你可以增加 $ t $ 甚至更多，然後計算 $ r’ = r \text{ mod }2^{256} $ . 這不會導致完美的均勻分佈，但如果 $ r $ 比 $ r’ $ ，真的很接近制服。
• 否則，你也可以在位級別進行拒絕採樣（這就是丟棄一些結果，以便其他結果仍然彼此一致）：從0到9繪製一個數字，如果是8或9，則忽略它並繪製再次。現在，您可以將數字 0-7 的二進製表示形式用作長二進制結果的 3 位。重複此操作並連接 3 位塊。

您甚至可以結合這些技術來優化拒絕結果的數量，但這可能太過分了，這些簡單的解決方案應該可以工作。

PS：關於你的第一個結論

這就是為什麼你不應該只在電腦程序中使用原始整數作為隨機數的原因。

這種說法是不正確的。RNG 通常在整數上執行，並且針對不同的任務有不同的 RNG。您還應該使用什麼作為隨機數？浮點數比整數更難處理，甚至更難實際證明統計屬性因此，RNG 使用整數，因為它們比其他任何東西都好，但屬性取決於實際的 RNG。例如，線性同餘生成器和類似的結構非常快並且週期很長，但是由於順序元素的相關性很大，它們的隨機性質量很差。線性回饋移位寄存器提供更高質量的隨機性，但也可以從短的輸出序列中預測流。出於統計目的Mersenne Twister可能提供最好的性能和高質量的隨機性。

但是對於密碼學，您需要其他屬性（查看本文中的第一個連結）。對於實際的電腦程序：您應該使用安全 PRNG 的標準庫中的實現，例如java 中的SecureRandom。

無論如何，散列通常是為了具有單向屬性，你不能計算回原始消息/對象/輸入/…例如，如果你有散列值，你可以比較兩個項目是否相同，但是沒有其他的。如果你必須猜這個項目，你不能。

引用自：https://crypto.stackexchange.com/questions/11177