安全地生成一个随机的BigInteger

Question

我想安全地生成[0,N]范围内的随机数,其中N是一个参数.但是,System.Security.Cryptography.RandomNumberGenerator仅提供GetBytes()方法以使用随机值填充数组.

(我需要在稍微修改过的SRP版本中使用的随机整数."略微修改"的部分是我无法控制的,这是我甚至接触加密内容的唯一原因.)

我已经写了一个方法来做到这一点,但我正在寻找一种更好的方法,或者至少确认我做得对.

using System.Numerics

///<summary>Generates a uniformly random integer in the range [0, bound).</summary>
public static BigInteger RandomIntegerBelow(this System.Security.Cryptography.RandomNumberGenerator source, BigInteger bound) {
    Contract.Requires<ArgumentException>(source != null);
    Contract.Requires<ArgumentException>(bound > 0);
    Contract.Ensures(Contract.Result<BigInteger>() >= 0);
    Contract.Ensures(Contract.Result<BigInteger>() < bound);

    //Get a byte buffer capable of holding any value below the bound
    var buffer = (bound << 16).ToByteArray(); // << 16 adds two bytes, which decrease the chance of a retry later on

    //Compute where the last partial fragment starts, in order to retry if we end up in it
    var generatedValueBound = BigInteger.One << (buffer.Length * 8 - 1); //-1 accounts for the sign bit
    Contract.Assert(generatedValueBound >= bound);
    var validityBound = generatedValueBound - generatedValueBound % bound;
    Contract.Assert(validityBound >= bound);

    while (true) {
        //generate a uniformly random value in [0, 2^(buffer.Length * 8 - 1))
        source.GetBytes(buffer);
        buffer[buffer.Length - 1] &= 0x7F; //force sign bit to positive
        var r = new BigInteger(buffer);

        //return unless in the partial fragment
        if (r >= validityBound) continue;
        return r % bound;
    }
}

Answer 1

您的代码看起来正确且公正。但是，如果您追求性能，并且根据您所使用的随机源的速度，您可能需要对其进行一些更改。这个想法是屏蔽掉更多的位，以便随机值r小于2*bound。如果边界的长度（以位为单位x）为（长度不包括符号位），则生成字节缓冲区n = ((x+8)/8)，并屏蔽高位(n*8-x)。在 C# 中，这应该如下所示：

var x = BitLength(bound);
var n = ((x + 8) / 8);
var buffer = new Byte[n];
var mask = 0xFF >> (8 * n - x);
while (true) {
    source.GetBytes(buffer);
    buffer[n - 1] &= mask;
    var r = new BigInteger(buffer);
    if (r < bound)
        return r;
}

使用这种代码，您可能需要从源中请求更多随机字节，但您可以避免模块化缩减（运算%符）。适当的 PRNG 应该比大整数除法快得多，因此这应该是一个更好的权衡 - 但这实际上取决于随机源的性能，并且由于这是一个性能问题，因此不能完全没有尝试就回答了。很可能，作为整体 SRP 实施的一部分，无论如何它都不会产生任何明显的差异。

我在上面使用了一个BitLength()在 C# 中似乎不存在的函数（Java 的BigInteger类有一个bitLength()方法，但显然微软忘记在他们的大整数实现中包含一个方法——这是一个耻辱，因为看起来该实现确实包含一个私有的方法）被调用的字段_bits保持该值）。位长度可以根据bound值的字节表示有效地计算出来。因此，代码将变成这样：

var buffer = bound.ToByteArray();
var n = buffer.length;
var msb = buffer[n - 1];
var mask = 0;
while (mask < msb)
    mask = (mask << 1) + 1;
while (true) {
    source.GetBytes(buffer);
    buffer[n - 1] &= mask;
    var r = new BigInteger(buffer);
    if (r < bound)
        return r;
}

bound我使用的事实是，返回的编码长度（以字节为单位ToByteArray()）正是n我需要的值。