Generación segura de un BigInteger uniformemente aleatorio

Question

Deseo generar de forma segura un número aleatorio en el rango [0, N), donde N es un parámetro. Sin embargo, System.Security.Cryptography.RandomNumberGenerator solo proporciona un método GetBytes() para llenar una matriz con valores aleatorios.

(necesito los números enteros aleatorios de valores de uso único utilizadas en una versión ligeramente modificada de SRP. La parte "ligeramente modificado" está fuera de mi control, y la única razón por la que estoy siquiera tocar cosas cripto.)

He escrito un método para hacer esto, pero estoy buscando una forma mejor o al menos la confirmación de que lo estoy haciendo bien.

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

Su código se ve correcto e imparcial. Sin embargo, es posible que desee cambiarlo un poco, si busca rendimiento y depende de la velocidad de la fuente aleatoria que esté utilizando. La idea es enmascarar algunos bits más para que el valor aleatorio r sea menor que 2*bound. Si la longitud en los bits del límite es x (longitud excluyendo el bit de signo), se genera un búfer de n = ((x+8)/8) bytes y se enmascaran los bits (n*8-x) superiores. En C#, esto debe verse como:

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

Con este tipo de código, es posible que tenga que pedir más bytes aleatorios a partir de la fuente, pero evitar la reducción modular (el operador %). Un PRNG apropiado debería ser mucho más rápido que la división en enteros grandes, por lo que debería ser una mejor solución, pero esto realmente depende del rendimiento de la fuente aleatoria y, como se trata de rendimiento, no puede ser completamente respondió sin intentarlo. Lo más probable es que, como parte de una implementación general de SRP, no haga ninguna diferencia notable de todos modos.

he utilizado anteriormente una función BitLength() que no parece existir en C# (clase de Java BigInteger tiene un método bitLength(), pero parece que Microsoft se olvidó de incluir uno en su gran aplicación entero - que es una lástima, porque parece que la implementación realmente incluye un campo privado llamado _bits que mantiene ese valor). La longitud del bit se puede calcular de manera eficiente a partir de la representación, en bytes, del valor bound.De este modo, el código se convertiría en algo como esto:

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

estoy usando el hecho de que la longitud, en bytes, de la codificación de bound, tal como lo devuelve ToByteArray(), es precisamente el valor de n que necesito.

Answer 2

Esa implementación parece correcta para generar enteros sin sesgo en un rango.

Otro enfoque sería tomar los bytes aleatorios como los dígitos infinitos en la fracción binaria 0.xxxxxx..., multiplicar por bound y redondear hacia abajo. Realmente no tomaría dígitos infinitos, solo tantos como sea necesario para determinar cuál es el resultado redondeado. Creo que eso es más complejo sin embargo.

Pero generar números en todo el rango puede ser innecesario para su protocolo. RFC 5054 La sección 3.1 requiere solo exponentes privados de 256 bits. Ese número proviene de duplicar la longitud de bit de la salida de hash y requiere que se use un primo seguro. Un borrador anterior de ese RFC se refirió al On Diffie-Hellman key agreement with short exponents para una explicación, que está en el primer párrafo de la sección 4 allí.

Si prefiere más bits aleatorios, tome la longitud de bit de range menos 1. Esto es lo que OpenSSL does for Diffie-Hellman (busque BN_rand y la línea anterior). Eso es aún más fácil de generar y menos de dos veces más corto que el rango completo, y si eso hace la diferencia, debería usar un primo más grande.