.net - 安全地生成均匀随机的 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。如果绑定(bind)的长度以位为单位为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 的私有(private)字段，它维护该值)。位长度可以根据绑定(bind)值的字节表示来有效计算。因此，代码将变成这样:

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

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