安全地产生均匀随机的BigInteger [英] Securely generating a uniformly random BigInteger

问题描述

欲安全地生成，在范围[0，N），其中N是一个参数的随机数。然而，System.Security.Cryptography.RandomNumberGenerator只是提供了一个的GetBytes（）方法来填充数组与随机值。

（我需要的随机整数在SRP稍加修改的版本中使用随机数的略微修改部分是在我的掌握中，唯一的原因，我甚至感动加密的东西。）

我写了一个方法来做到这一点，但我在寻找，我做是正确的更好的方法，或者至少确认。

 使用System.Numerics

///＆LT;总结＆gt;生成均匀随机整数的范围在[0，必将）LT; /总结＆gt;
公共静态的BigInteger RandomIntegerBelow（这System.Security.Cryptography.RandomNumberGenerator源，BigInteger的约束）{
    Contract.Requires＆LT; ArgumentException的＆GT;（来源！= NULL）;
    Contract.Requires＆其中; ArgumentException的＆GT;（绑定大于0）;
    Contract.Ensures（Contract.Result＆其中; BigInteger的＆GT;（）＆GT; = 0）;
    Contract.Ensures（Contract.Result＆LT; BigInteger的＆GT;（）＆LT;约束）;

    //获取能够保持低于绑定任何值的字节缓冲区
    变种缓冲液=（结合＆其中;＆所述; 16）.ToByteArray（）; //＆LT;＆LT; 16将两个字节，其中减少重试的可能性稍后

    //计算其中最后一个部分片段开始，为了如果我们最终在它重试
    VAR generatedValueBound = BigInteger.One＆LT;＆LT; （buffer.Length * 8  -  1）; //  -  1占符号位
    Contract.Assert（generatedValueBound＆GT; =绑定）;
    VAR validityBound = generatedValueBound  -  generatedValueBound％的约束;
    Contract.Assert（validityBound＆GT; =绑定）;

    而（真）{
        //生成均匀随机值[0，2 ^（buffer.Length * 8  -  1））
        source.GetBytes（缓冲液）;
        缓冲液[buffer.Length  -  1]＆安培; = 0x7F的; //力符号位为正
        变种R =新的BigInteger（缓冲区）;

        //返回除非在部分片段
        如果（R＆GT; = validityBound）继续;
        返回版本r％的约束;
    }
}
 

解决方案

您code看起来是正确的，公正的。但是，您可能要改变一下，如果你是演出结束后，并根据您所使用的随机源的速度。这样做是为了屏蔽掉几个位，这样的随机值研究比小2 *势必。如果比特的边界长度的是 X （长度的不包括的符号位），然后生成的缓冲 N =（（X + 8）/ 8），字节，并屏蔽掉上（N * 8-X）位。在C＃中，这应该是这样的：

 变种X =位长度（绑定）;
变种N =（（X + 8）/ 8）;
VAR缓冲区=新的字节[N];
VAR面膜= 0xFF的＆GT;＆GT; （8 * N  -  X）;
而（真）{
    source.GetBytes（缓冲液）;
    缓冲区[N  -  1]安培; =面膜;
    变种R =新的BigInteger（缓冲区）;
    如果（R＆LT;约束）
        返回ř;
}
 

通过这种code，你可能要问更多的随机字节从源头上，但你避免模块化减少（即％运营商）。一个适当的PRNG应该比在大整数除法快多了，所以这应该是一个更好的权衡 - 但是这真的取决于随机源的性能，而且，因为它是性能问题，也不能完全回答没有尝试。机会是，作为一个整体的战略调整计划实施的一部分，它不会做任何明显的区别呢。

我已经使用超过位长度（）函数，它似乎并没有在C＃中存在（Java的的BigInteger 类有一个位长度（）的方法，但显然微软忘了包括一个在他们的大整数实现 - 这是一种耻辱，因为它似乎真的实现，包括私有字段名为 _bits 其中认为值）。该位长度可以有效地从重新presentation来计算，以字节为约束价值。因此，code会变成这样的：

  VAR缓冲= bound.ToByteArray（）;
变种N = buffer.length;
变种MSB =缓冲区[N  -  1];
变种掩模= 0;
而（面膜＆LT; MSB）
    掩模=（掩模＆其中;＆小于1）+1;
而（真）{
    source.GetBytes（缓冲液）;
    缓冲区[N  -  1]安培; =面膜;
    变种R =新的BigInteger（缓冲区）;
    如果（R＆LT;约束）
        返回ř;
}
 

我现在用的是事实的编码的长度，以字节为单位，约束的返回情况，的toByteArray（），是precisely值 N ，我需要的。

I want to securely generate a random number in the range [0, N), where N is a parameter. However, System.Security.Cryptography.RandomNumberGenerator only provides a GetBytes() method to fill an array with random values.

(I need the random integers for nonces used in a slightly modified version of SRP. The "slightly modified" part is out of my control, and the only reason I'm even touching crypto stuff.)

I have written a method to do this, but I'm looking for a better way or at least confirmation that I'm doing it right.

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

解决方案

Your code looks correct and unbiased. However, you may want to change it a bit, if you are after performance, and depending on the speed of the random source you are using. The idea is to mask out a few more bits so that the random value r is smaller than 2*bound. If the length in bits of bound is x (length excluding the sign bit), then you generate a buffer of n = ((x+8)/8) bytes, and mask out the upper (n*8-x) bits. In C#, this should look like:

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

With this kind of code, you may have to ask more random bytes from the source, but you avoid the modular reduction (the % operator). A proper PRNG should be much faster than division on big integers, so this should be a better trade-off -- but this really depends on the performance of the random source, and, since it is a question of performance, it cannot be fully answered without trying. Chances are that, as part of an overall SRP implementation, it would not make any noticeable difference anyway.

I have used above a BitLength() function which does not seem to exist in C# (Java's BigInteger class has a bitLength() method, but apparently Microsoft forgot to include one in their big integer implementation -- which is a shame, because it seems that the implementation really includes a private field called _bits which maintains that value). The bit length can be computed efficiently from the representation, in bytes, of the bound value. Thus, the code would become something like this:

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

I am using the fact that the length, in bytes, of the encoding of bound, as returned by ToByteArray(), is precisely the value of n that I need.

这篇关于安全地产生均匀随机的BigInteger的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！