按位高效，统一，加密安全的随机数生成

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; 
} 

但是，在基数与此问题之间转换数字存在根本差异;为了在基数之间进行转换，我认为需要有足够的关于数字的信息来执行计算 - 目标基的连续分割导致用于构造目标字母表中数字的余数。在这个问题中，我并不需要知道所有这些信息，只要我不偏向数据，这意味着我可以在标记为“填充”的循环中执行所做的操作。