按位高效，統一，加密安全的隨機數生成

Question

我記得有關在數學導向網站上的文章中有效使用隨機位的方法，但我似乎無法在Google中獲得正確的關鍵字找到它了，它不在我的瀏覽器歷史記錄中。

正被提出問題的要點是採取隨機數的序列中的結構域[domainStart，domainEnd）和有效地使用該隨機數序列的比特均勻地伸入範圍[rangeStart，rangeEnd） 。域和範圍都是整數（更準確地說，是long而不是Z）。 這是什麼算法？

實現的角度來看，我有與此簽名的函數：，我需要使用

long doRead(InputStream in, long rangeStart, long rangeEnd); 

in是基於CSPRNG（由硬件RNG，通過SecureRandom的空調供給）;返回的值必須是rangeStart和rangeEnd之間，但這種明顯的實現是一種浪費：

long doRead(InputStream in, long rangeStart, long rangeEnd) { 
    long retVal = 0; 
    long range = rangeEnd - rangeStart; 

    // Fill until we get to range 
    for (int i = 0; (1 << (8 * i)) < range; i++) { 
     int in = 0; 
     do { 
      in = in.read(); 
     // but be sure we don't exceed range 
     } while(retVal + (in << (8 * i)) >= range); 
     retVal += in << (8 * i); 
    } 

    return retVal + rangeStart; 
} 

我相信這是實際上是相同的想法(rand() * (max - min)) + min，只有我們丟棄它可以讓我們在max位。我們丟棄這些位並重試，而不是使用可能錯誤地將結果偏置到較低值的模運算符。由於觸發CSPRNG可能會觸發重新播種（可能會阻塞InputStream），因此我想避免浪費隨機位。亨利指出，這個代碼偏向0和257;班塔爾在一個例子中演示了它。

首先編輯：亨利提醒我，求和調用中心極限定理。我修正了上面的代碼來解決這個問題。

第二次編輯：機械蝸牛建議我查看Random.nextInt（）的源代碼。在閱讀了一段時間之後，我意識到這個問題與基本轉換問題類似。見下面的答案。

Answer 1

您的算法會產生有偏差的結果。我們假設rangeStart=0和rangeEnd=257。如果第一個字節大於0，那就是結果。如果是0，則結果將爲0或256，並且50/50概率。所以0和256比其他任何號碼選擇的可能性要低兩倍。

我做了一個簡單的test來確認這一點：

p(0)=0.001945 
p(1)=0.003827 
p(2)=0.003818 
... 
p(254)=0.003941 
p(255)=0.003817 
p(256)=0.001955 

我認爲你需要做的一樣java.util.Random.nextInt並丟棄整數，而不僅僅是最後一個字節。

Answer 2

將源代碼讀入Random.nextInt（）後，我意識到這個問題與基本轉換問題類似。

而不是一次轉換一個符號，通過一個足夠大的累加器「緩衝區」一次轉換輸入符號的塊會更有效，該緩衝區足以表示域中的至少一個符號和範圍。新代碼如下所示：

public int[] fromStream(InputStream input, int length, int rangeLow, int rangeHigh) throws IOException { 
    int[] outputBuffer = new int[length]; 
    // buffer is initially 0, so there is only 1 possible state it can be in 
    int numStates = 1; 
    long buffer = 0; 
    int alphaLength = rangeLow - rangeHigh; 
    // Fill outputBuffer from 0 to length 
    for (int i = 0; i < length; i++) { 
     // Until buffer has sufficient data filled in from input to emit one symbol in the output alphabet, fill buffer. 
     fill: 
     while(numStates < alphaLength) { 
      // Shift buffer by 8 (*256) to mix in new data (of 8 bits) 
      buffer = buffer << 8 | input.read(); 
      // Multiply by 256, as that's the number of states that we have possibly introduced 
      numStates = numStates << 8; 
     } 
     // spits out least significant symbol in alphaLength 
     outputBuffer[i] = (int) (rangeLow + (buffer % alphaLength)); 
     // We have consumed the least significant portion of the input. 
     buffer = buffer/alphaLength; 
     // Track the number of states we've introduced into buffer 
     numStates = numStates/alphaLength; 
    } 
    return outputBuffer; 
} 

但是，在基數與此問題之間轉換數字存在根本差異;爲了在基數之間進行轉換，我認爲需要有足夠的關於數字的信息來執行計算 - 目標基的連續分割導致用於構造目標字母表中數字的餘數。在這個問題中，我並不需要知道所有這些信息，只要我不偏向數據，這意味着我可以在標記爲「填充」的循環中執行所做的操作。