Hash
創建 ak 位隨機字元串
我的目標是創建一個隨機 $ k $ 位串。我的問題可以分為兩部分。
- 如果一個 $ n $ 位串 $ s $ 在計算上與隨機無法區分 $ n $ 位字元串，我們可以說字元串 $ s $ 有 $ n $ 最小熵？
- 但由於某種原因，我不能使用字元串 $ s $ 直接，我需要將其轉換為另一個 $ n $ 位串 $ s’ $ . 在轉換過程中發生了一些不好的事情。每個位的機率 $ 0 $ 或者 $ 1 $ 不是 $ 1/2 $ 了。這是 $ 1/2+e $ . 因此位串的最小熵 $ n $ 變化。讓最小熵 $ s’ $ 是 $ l>k $ . 由於散列函式是很好的隨機性提取器，如果我應用散列函式 $ H $ 在弦上 $ s’ $ 產生 $ k $ 位，我可以說散列函式的輸出是 $ k $ 位隨機字元串？
謝謝您的幫助。
解決第一點，然後沒有。最小熵是所有測量熵的方法中的最小估計。如果您出於加密目的考慮字元串，則傳統上採用最保守的熵估計方法。如果你戴上錫箔帽，那是最安全的方法。
最小熵是：-
如果 s（或 X）是隨機的，則各個字節的機率將均勻分佈。一些 Pr(x) 會高於其他的。這個範圍實際上可能非常大，因為隨機性可能非常討厭。由於最小熵取該範圍的最大 Pr(x)，因此最小熵將始終較低。實際上，對於隨機數據，它可能只低 1 - 2%。儘管對於語言等非隨機數據，它會低得多。
作為圖片，這是 1MB 真正隨機數據的直方圖：-
我們可以假設這是不偏不倚的。然而，單個字節機率（隨機事件）存在顯著差異。因此，必須有一個最大機率。這導致最小熵值為 7.93 位/字節。因此，對於 1MB 的輸出，您只能依靠 992000 字節的熵來進行加密。這比您天真的預期的要少 0.9%。順便說一句，chi 給出了 p = 0.15。
至於你的第二點，我認為這個網站沒有任何共識。有人說雜湊熵提取器只能提取原始熵的一半。不過，這項工作的大部分都是高度理論化的，我不相信它對現實的適用性。另一方面，也有商業設備可以提取一半以上。我個人現在相信提取器可以提取所有源熵。
