通過從 CSPRNG 輸出移位或旋轉位來統一拒絕採樣，安全嗎？

給定一個 CSPRNG（arc4random，使用 ChaCha20 密鑰流），人們希望使用拒絕採樣來獲得較小範圍內的隨機數，從而避免模偏差（arc4random_uniform()）。

OpenBSD 的arc4random_uniform()實現繪製一個 32 位的值並測試它的適合度，拒絕不適合的值。

這不是唯一可能的實現。在Efficiently Generate a Number in a Range中，ME O’Neill 提供了各種其他方法來生成範圍內的隨機數，同時避免模偏差。

特別是，有一種所謂的帶有拒絕（無偏見）的位遮罩——Apple 的方法。按照實際 Apple實現的連結，可以看到它還有另一個技巧：

/*
* Calculate a uniformly distributed random number less than upper_bound
* avoiding "modulo bias".
*
* Uniformity is achieved by trying successive ranges of bits from the random
* value, each large enough to hold the desired upper bound, until a range
* holding a value less than the bound is found.
*/
uint32_t
arc4random_uniform(uint32_t upper_bound)
{
   if (upper_bound < 2)
       return 0;

   // find smallest 2**n -1 >= upper_bound
   int zeros = __builtin_clz(upper_bound);
   int bits = CHAR_BIT * sizeof(uint32_t) - zeros;
   uint32_t mask = 0xFFFFFFFFU >> zeros;

   do {
       uint32_t value = arc4random();

       // If low 2**n-1 bits satisfy the requested condition, return result
       uint32_t result = value & mask;
       if (result < upper_bound) {
           return result;
       }

       // otherwise consume remaining bits of randomness looking for a satisfactory result.
       int bits_left = zeros;
       while (bits_left >= bits) {
           value >>= bits;
           result = value & mask;
           if (result < upper_bound) {
               return result;
           }
           bits_left -= bits;
       }
   } while (1);
}

如果目前值不適合範圍，則不會繪製新值，而是將值移動以丟棄適合測試中涉及的任何位，直到該值適合或沒有足夠的未使用位剩餘。

如果 CSPRNG成本很高，這尤其有用，例如，如果它需要係統呼叫來生成一個值，減少呼叫它的時間，雖然算法複雜，但可能會提高arc4random_uniform()的整體速度。

現在我的問題是：給定一個由 CSPRNG 生成的 32 位值，鑑於 CSPRNG 輸出與隨機流不可區分，每個值都與其他值一樣，為什麼要丟棄每個測試位？

1. 是否可以一次將值移動一位並根據范圍測試結果值？

   do {
       uint32_t value = arc4random();

       for (int bits_left = 32; bits_left >= bits ; bits_left--) {

           uint32_t result = value & mask;

           if (result < upper_bound) {
               return result;

           value = value >> 1; // shift right by one bit
       }
   } while (1);

2. 是否可以一次將值旋轉一位並根據范圍測試結果值？

   do {
       uint32_t value = arc4random();

       for (int i = 0; i < 32; i++) {

           uint32_t result = value & mask;

           if (result < upper_bound) {
               return result;

           value = ror32(value, 1); // rotate right by one bit
       }
   } while (1);

這些優化對建構arc4random_uniform是否安全？

如果沒有，依據是什麼？

這些優化對建構 arc4random_uniform 是否安全？

不，他們不是。

如果沒有，依據是什麼？

因為，在我們測試了 的值並result拒絕它（即它是>= upper_bound). 由於這些位是不均勻的，因此在以後的測試中重用它們會得到不均勻的結果。

讓我們舉一個簡單的例子：假設 upper_bound = 3（因此 mask = 3）。然後，在第一次迭代中，如果值的低兩位是 0、1 或 2，我們將以相等的機率返回它，而不是問題。但是，如果低兩位恰好是 3（即位是 11），我們將不會返回該迭代，因此我們將進入下一個。您的想法會將值向右移動一位，導致低兩位為 x1（其中“x”是我們尚未測試的原始位 2），也就是說，低兩位將是值 1或值 3。如果為 1，則該迭代將返回該值；否則它將跳到下一次迭代。在任何情況下，第二次迭代都不會返回 0 或 2（在後面的迭代中也是如此）；因此我們對 1 有強烈的偏見。

原始程式碼（丟棄拒絕後測試的所有位）沒有這個問題。

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