安全地生成一个均匀随机的大整数 (BigInteger)

Question

我希望能够安全地生成一个在区间[0, N)内的随机数，其中N是一个参数。不过，System.Security.Cryptography.RandomNumberGenerator只提供了一个GetBytes()方法来填充数组以获取随机值。

（我需要这些随机整数用作稍微修改过的SRP中使用的nonce。 "轻微修改"部分不在我的控制范围内，而且我接触加密技术的唯一原因就是这个。）

我已经编写了一个方法来完成此操作，但我正在寻找更好的方法或者至少确认我是否正确操作。

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

- Craig Gidney

Answer 1

这个实现看起来正确，可以生成一个范围内的无偏整数。

另一种方法是将随机字节作为二进制小数“0.xxxxxx…”中的无限位数字，将其乘以“bound”，并向下取整。实际上不需要无限位数字，只需要足够多的数字来确定向下取整的结果即可。但我认为这更加复杂。

但是，对于您的协议来说，生成完整范围内的数字可能是不必要的。RFC 5054第3.1节仅需要256位私有指数。该数字来自哈希输出的比特长度加倍，并要求使用安全质数。该RFC的早期草案提到了On Diffie-Hellman key agreement with short exponents，其中在第4节的第一段中进行了解释。

如果您需要更多的随机位，请取range的位长度减1。这就是OpenSSL 为Diffie-Hellman所做的（搜索BN_rand和它之前的行）。这仍然比生成完整范围要容易得多，而且比完整范围短不到两倍，如果这有所区别，您应该使用更大的质数。

- aaz

Answer 2

你的代码看起来正确且没有偏差。但是，如果你想追求性能并且取决于你使用的随机源的速度，你可能需要稍微修改一下它。思路是屏蔽掉更多的位，使得随机值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()方法，但显然Microsoft忘记在其大整数实现中包含一个方法——这是一件遗憾的事情，因为它似乎实际上包括一个名为_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;
}

我利用ToByteArray()返回的编码长度（以字节为单位）正好是我需要的n值。

- Thomas Pornin

---

我也很惊讶没有BitLength成员。我并不特别担心Mod操作的成本，因为我无论如何都必须在结果值上使用ModPow。 - Craig Gidney