Entropy

使用遮罩與熵之間的關係

  • September 25, 2016

這是作業的一部分,我不確定我應該從結果中得出什麼結論。

我們應該生成兩個 1024 字節的單詞,一個使用隨機生成 0 和 1 (50%/50%) 的算法,另一個使用具有“秘密”機率分佈的算法。我會打電話給他們word 1word 2從現在開始。

我們應該先計算每個字位的經驗熵,然後再計算每個字節的經驗熵。

我得到以下結果:

word 1(每比特):1.00

word 1(每字節字節數):7.79

word 2(每比特):0.95

word 2(每字節字節數):0.81

然後我們應該生成一個隨機的 1024 字節遮罩並將其應用於每個單詞,給我們word 1mword 2m. 這次的結果是:

word 1m(每比特):1.00

word 1m(每字節字節數):7.81

word 2m(每比特):1.00

word 2m(每字節字節數):7.81

我不確定這些結果是什麼意思!當然,我注意到每個字節的經驗熵word 2很低的事實,這可能意味著某些特定字節比其他字節出現的頻率更高,但我不知道會發生什麼word 2m

不確定我說得很清楚,請不要猶豫,要求澄清。謝謝 !

均勻隨機源具有最大熵:每位 1 位。這是完全不可預測的。

無法測量源的熵,因為您只能獲得它的部分、有限的視圖。如果您在第一個中沒有看到任何模式 $ n $ 位,這並不能證明來源不會重複 $ n $ 位。相反,一個理想的隨機源可以返回 $ n $ 相同的位,這是非常不可能的(機率 $ 2^{-n} $ )。因此,當您通過採樣來估計均勻隨機源的熵時,您可以期望獲得大約 1 位/位的熵測量值,而非隨機源通常具有較少(但前提是您的熵估計設法捕捉到非隨機性)。

您將得到 1 位/位和 7.79 ≈ 8 位/字節(顯然不是 7.79 字節/字節:它是一個介於 0 和 1 之間的數字)作為源 1 的熵估計,它應該是均勻隨機的。這在預期範圍內。

對於源 2,您將獲得 0.95 位/位和 0.81 位/字節。這表明源 2 具有幾乎相等數量的 0 和 1,但是連續位之間存在非常強的相關性,因為將字節分組在一起給出了低熵估計.

當您應用均勻隨機蒙版時,生成的組合本身就會變得隨機。這是因為每個位都有 0.5 的機會被翻轉,所以源中的每個 0 位在組合中成為 0 或 1 的機會相同,源中的每個 1 位在組合中也有相同的機會成為 0 或 1組合。使用隨機遮罩的源 1 和使用隨機遮罩的源 2 的熵估計值接近預期的 1 位/位。

請注意,遮罩是異或,而不是與。按位且具有均勻隨機源的方法只會通過將大約一半的位強制為 0 來降低熵。

這種與任意源異或的不可預測遮罩導致不可預測組合的觀察是流密碼的基礎。

引用自:https://crypto.stackexchange.com/questions/40079