Надежно генерирует равномерно случайный BigInteger - PullRequest
Новая
       34

Надежно генерирует равномерно случайный BigInteger

7 голосов
/ 16 марта 2011

Я хочу безопасно генерировать случайное число в диапазоне [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;
    }
}

Ответы [ 2 ]

1 голос
/ 17 марта 2011

Ваш код выглядит правильным и непредвзятым. Тем не менее, вы можете захотеть немного его изменить, если вы после исполнения, и в зависимости от скорости случайного источника, который вы используете. Идея состоит в том, чтобы замаскировать еще несколько битов, чтобы случайное значение 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;
}

Я использую тот факт, что длина в байтах кодировки bound, возвращаемая ToByteArray(), - это именно то значение n, которое мне нужно.

1 голос
/ 17 марта 2011

Эта реализация выглядит правильно для генерации несмещенных целых чисел в диапазоне.

Другой подход заключается в том, чтобы взять случайные байты в качестве бесконечных цифр в двоичной дроби 0.xxxxxx..., умножить их на bound и округлить в меньшую сторону. На самом деле это не займет бесконечных цифр, столько, сколько необходимо для определения округленного результата. Я думаю, что это более сложно, хотя.

Но генерация чисел во всем диапазоне может быть ненужной для вашего протокола. RFC 5054 раздел 3.1 требует только 256-битных частных показателей. Это число получается из-за удвоения длины битов хеш-вывода и требует использования безопасного простого числа. Более ранний проект этого RFC ссылался на О соглашении ключей Диффи-Хеллмана с короткими показателями для объяснения, которое есть в первом параграфе раздела 4.

Если вы предпочитаете больше случайных битов, возьмите битовую длину range минус 1. Это то, что OpenSSL делает для Диффи-Хеллмана (поиск BN_rand и строки перед ним). Это все еще легче генерировать и менее чем в два раза короче, чем полный диапазон, и если это имеет значение, вы должны использовать большее простое число.

...