如何分析off-by-one錯誤對結果熵的影響？

我正在閱讀 Jean-Philippe Aumasson 的《Serious Cryptography 》一書，以了解有關密碼學的更多資訊。在第 37 頁，作者給出了 Cryptocat 在其 2013 年的 PRNG 實現中的 off-by-one 錯誤範例，如下圖所示：

Cryptocat.random = function() { 
   var x, o = ''; 
   while (o.length < 16) { 
       x = state.getBytes(1); 
       if (x[0] <= 250) {
           o += x[0] % 10;
       }
   } return parseFloat('0.' + o)
}

在使用<=而不是<. 作者指出，生成的值的熵為 45 而不是大約 53 位。

我想知道如何計算 45 位的熵。

事實上，如果程式碼使用<，那麼一切都很好：十進制數字的機率同樣是 1/10。因此 16 位十進制數字的熵將是16*10*1/10*log(10, 2) = 53.1508。

但是，在上述有缺陷的程式碼的情況下，十進制0的機率是26/251，彼此取值的機率是25/251。因此，16 位十進制數字的熵將是16*(26/251*log(251/26, 2) + 9*25/251*log(251/25, 2)) = 53.149。

我沒有任何關於如何獲得 45 位熵的線索。任何人都可以幫助我嗎？

參考：

• https://tobtu.com/decryptocat.php
• https://nakedsecurity.sophos.com/2013/07/09/anatomy-of-a-pseudorandom-number-generator-visualising-cryptocats-buggy-prng/

首先第一個熵計算是不正確的。回想一下（香農）熵的定義：

$$ H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_{,b} \mathrm{P}(x_i)} $$

如果統一選擇一個數字熵是

$$ H(X) = -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 3.3219280… $$

• 案子 $ <250 $ 16位數字；

$$ \begin{align} H_1(X) &= 16 \cdot - \sum_{i=1}^{10}{\frac{1}{10} \log_2\left(\frac{1}{10}\right)}\ H_1(X) &= 16 \cdot 10 \cdot -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 53.15084951…\ \end{align} $$

參見Wolfram Alpha的計算

• 案子 $ \leq250 $ 16位數字；

$$ H_2(X) = 16 \cdot - \left( \frac{26}{251} \cdot \log_2\left(\frac{26}{251}\right)+9 \cdot \frac{25}{251} \cdot \log_2\left(\frac{25}{251}\right) \right) = 53.14921795… $$

參見Wolfram Alpha的計算

這似乎是書中的一個錯誤。目前的勘誤表不包括這個。

差異很小，但可以產生影響，因為 0 會出現更多並且是可區分的。例如，以 1.000.000 個樣本出現 0 約為 103,500 - 大約 10.36%。

      

對於差異的視覺化，請閱讀這個不錯的部落格Anatomy of a pseudorandom number generator – 視覺化 Cryptocat 的錯誤 PRNG

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