c++ - ¿Cómo sembrar de manera sucinta, portátil y exhaustiva el mt19937 PRNG?

random c++

Question

Parece que veo muchas respuestas en las que alguien sugiere usar <random> para generar números aleatorios, generalmente junto con un código como este:

std::random_device rd;  
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 5);
dis(gen);

Por lo general, esto reemplaza algún tipo de "abominación impía" como:

srand(time(NULL));
rand()%6;

Podríamos criticize la vieja forma argumentando que el time(NULL) proporciona baja entropía, el time(NULL) es predecible y el resultado final no es uniforme.

Pero todo eso es cierto en la nueva forma: solo tiene un enchapado más brillante.

• rd() devuelve un único unsigned int . Esto tiene al menos 16 bits y probablemente 32. Eso no es suficiente para sembrar 19937 bits de estado de MT.

• El uso de std::mt19937 gen(rd());gen() (sembrar con 32 bits y mirar la primera salida) no proporciona una buena distribución de salida. 7 y 13 nunca pueden ser la primera salida. Dos semillas producen 0. Doce semillas producen 1226181350. ( Link )

• std::random_device puede std::random_device , y a veces se implementa, como un PRNG simple con una semilla fija. Por lo tanto, podría producir la misma secuencia en cada ejecución. ( Link ) Esto es incluso peor que el time(NULL) .

Peor aún, es muy fácil copiar y pegar los fragmentos de código anteriores, a pesar de los problemas que contienen. Algunas soluciones a esto requieren la adquisición de largish libraries que pueden no ser adecuadas para todos.

A la luz de esto, mi pregunta es ¿Cómo se puede sembrar de manera sucinta, portátil y completa la PRNG mt19937 en C ++?

Dados los problemas anteriores, una buena respuesta:

• Debe sembrar completamente el mt19937 / mt19937_64.
• No se puede confiar únicamente en std::random_device o time(NULL) como fuente de entropía.
• No debe confiar en Boost u otras bibliotecas.
• Debe caber en un pequeño número de líneas de modo que se vea bien pegado en una respuesta.

Pensamientos

• Mi pensamiento actual es que las salidas de std::random_device pueden std::random_device (tal vez a través de XOR) con time(NULL) , valores derivados de la aleatorización del espacio de direcciones y una constante codificada (que se puede configurar durante la distribución) para obtener un El mejor esfuerzo en la entropía.

• std::random_device::entropy() no da una buena indicación de lo que std::random_device podría o no hacer.

Answer 1

Aquí está mi propia puñalada a la pregunta:

#include <random>
#include <chrono>
#include <cstdint>
#include <algorithm>
#include <functional>
#include <iostream>

uint32_t LilEntropy(){
  //Gather many potential forms of entropy and XOR them
  const  uint32_t my_seed = 1273498732; //Change during distribution
  static uint32_t i = 0;        
  static std::random_device rd; 
  const auto hrclock = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  const auto sclock  = std::chrono::system_clock::now().time_since_epoch().count();
  auto *heap         = malloc(1);
  const auto mash = my_seed + rd() + hrclock + sclock + (i++) +
    reinterpret_cast<intptr_t>(heap)    + reinterpret_cast<intptr_t>(&hrclock) +
    reinterpret_cast<intptr_t>(&i)      + reinterpret_cast<intptr_t>(&malloc)  +
    reinterpret_cast<intptr_t>(&LilEntropy);
  free(heap);
  return mash;
}

//Fully seed the mt19937 engine using as much entropy as we can get our
//hands on
void SeedGenerator(std::mt19937 &mt){
  std::uint_least32_t seed_data[std::mt19937::state_size];
  std::generate_n(seed_data, std::mt19937::state_size, std::ref(LilEntropy));
  std::seed_seq q(std::begin(seed_data), std::end(seed_data));
  mt.seed(q);
}

int main(){
  std::mt19937 mt;
  SeedGenerator(mt);

  for(int i=0;i<100;i++)
    std::cout<<mt()<<std::endl;
}

La idea aquí es usar XOR para combinar muchas fuentes potenciales de entropía (tiempo rápido, tiempo lento, std::random-device , ubicaciones de variables estáticas, ubicaciones de almacenamiento dinámico, ubicaciones de funciones, ubicaciones de biblioteca, valores específicos del programa) para hacer un mejor -intento de esfuerzo para inicializar el mt19937. Mientras al menos una vez que la fuente sea "buena", el resultado será al menos esa "buena".

Esta respuesta no es tan corta como sería preferible y puede contener uno o más errores de lógica. Así que lo estoy considerando un trabajo en progreso. Por favor comente si tiene comentarios.

Answer 2

En cierto sentido, esto no se puede hacer de forma portátil. Es decir, uno puede concebir una plataforma válida totalmente determinista que ejecute C ++ (por ejemplo, un simulador que hace avanzar el reloj de la máquina de manera determinista y con E / S "determinada") en la que no hay una fuente de aleatoriedad para sembrar un PRNG.

Answer 3

La implementación en la que estoy trabajando aprovecha la propiedad state_size del mt19937 PRNG para decidir cuántas semillas proporcionar en la inicialización:

using Generator = std::mt19937;

inline
auto const& random_data()
{
    thread_local static std::array<typename Generator::result_type, Generator::state_size> data;
    thread_local static std::random_device rd;

    std::generate(std::begin(data), std::end(data), std::ref(rd));

    return data;
}

inline
Generator& random_generator()
{
    auto const& data = random_data();

    thread_local static std::seed_seq seeds(std::begin(data), std::end(data));
    thread_local static Generator gen{seeds};

    return gen;
}

template<typename Number>
Number random_number(Number from, Number to)
{
    using Distribution = typename std::conditional
    <
        std::is_integral<Number>::value,
        std::uniform_int_distribution<Number>,
        std::uniform_real_distribution<Number>
    >::type;

    thread_local static Distribution dist;

    return dist(random_generator(), typename Distribution::param_type{from, to});
}

Creo que hay margen de mejora porque std::random_device::result_type podría diferir de std::mt19937::result_type en tamaño y rango, por lo que realmente debería tenerse en cuenta.

Una nota sobre std::random_device .

De acuerdo con los C++11(/14/17) 14/17):

26.5.6 Clase random_device [ rand.device ]

2 Si las limitaciones de implementación impiden generar números aleatorios no deterministas, la implementación puede emplear un motor de números aleatorios.

Esto significa que la implementación solo puede generar valores deterministas si se impide que genere valores no deterministas por alguna limitación.

El compilador MinGW en Windows no proporciona valores no deterministas de su std::random_device , a pesar de que están fácilmente disponibles desde el sistema operativo. Por lo tanto, considero que esto es un error y no es una ocurrencia común en implementaciones y plataformas.

Answer 4

No hay nada de malo en sembrar usando el tiempo, suponiendo que no lo necesite para ser seguro (y no dijo que era necesario). La idea es que puede usar el hash para corregir la falta de aleatoriedad. He encontrado que esto funciona adecuadamente en todos los casos, incluidos y en particular para las simulaciones pesadas de Monte Carlo.

Una buena característica de este enfoque es que se generaliza a la inicialización desde otros conjuntos de semillas no realmente aleatorios. Por ejemplo, si desea que cada subproceso tenga su propio RNG (para seguridad de subprocesos), puede inicializar según la ID de subproceso hash.

El siguiente es un SSCCE , destilado de mi base de código (por simplicidad; algunas estructuras de soporte OO eluidas):

#include <cstdint> //`uint32_t`
#include <functional> //`std::hash`
#include <random> //`std::mt19937`
#include <iostream> //`std::cout`

static std::mt19937 rng;

static void seed(uint32_t seed) {
    rng.seed(static_cast<std::mt19937::result_type>(seed));
}
static void seed() {
    uint32_t t = static_cast<uint32_t>( time(nullptr) );
    std::hash<uint32_t> hasher; size_t hashed=hasher(t);
    seed( static_cast<uint32_t>(hashed) );
}

int main(int /*argc*/, char* /*argv*/[]) {
    seed();
    std::uniform_int_distribution<> dis(0, 5);
    std::cout << dis(rng);
}

Answer 5

Puede usar un std::seed_seq y llenarlo al menos para el tamaño de estado requerido para el generador usando el método de Alexander Huszagh para obtener la entropía:

size_t sysrandom(void* dst, size_t dstlen); //from Alexander Huszagh answer above

void foo(){

    std::uint_fast32_t[std::mt19937::state_size] state;
    sysrandom(state, sizeof(state));
    std::seed_seq s(std::begin(state), std::end(state));

    std::mt19937 g;
    g.seed(s);
}

Si hubiera una manera adecuada de llenar o crear una SeedSequence desde un UniformRandomBitGenerator en la biblioteca estándar usando std::random_device para sembrar correctamente, sería mucho más simple.

Answer 6

Una plataforma dada puede tener una fuente de entropía, como /dev/random . Nanosegundos desde la Época con std::chrono::high_resolution_clock::now() es probablemente la mejor semilla de la Biblioteca estándar.

Anteriormente he usado algo como (uint64_t)( time(NULL)*CLOCKS_PER_SEC + clock() ) para obtener más bits de entropía para aplicaciones que no son críticas para la seguridad.

Answer 7

Yo diría que el mayor defecto con std::random_device es que se le permite un respaldo determinista si no hay CSPRNG disponible. Esto solo es una buena razón para no sembrar un PRNG usando std::random_device , ya que los bytes producidos pueden ser deterministas. Desafortunadamente, no proporciona una API para averiguar cuándo sucede esto, o para solicitar una falla en lugar de números aleatorios de baja calidad.

Es decir, no existe una solución completamente portátil : sin embargo, existe un enfoque decente y mínimo. Puede usar un contenedor mínimo alrededor de un CSPRNG (definido como sysrandom continuación) para sembrar el PRNG.

Ventanas

Puede confiar en CryptGenRandom , un CSPRNG. Por ejemplo, puede usar el siguiente código:

bool acquire_context(HCRYPTPROV *ctx)
{
    if (!CryptAcquireContext(ctx, nullptr, nullptr, PROV_RSA_FULL, 0)) {
        return CryptAcquireContext(ctx, nullptr, nullptr, PROV_RSA_FULL, CRYPT_NEWKEYSET);
    }
    return true;
}


size_t sysrandom(void* dst, size_t dstlen)
{
    HCRYPTPROV ctx;
    if (!acquire_context(&ctx)) {
        throw std::runtime_error("Unable to initialize Win32 crypt library.");
    }

    BYTE* buffer = reinterpret_cast<BYTE*>(dst);
    if(!CryptGenRandom(ctx, dstlen, buffer)) {
        throw std::runtime_error("Unable to generate random bytes.");
    }

    if (!CryptReleaseContext(ctx, 0)) {
        throw std::runtime_error("Unable to release Win32 crypt library.");
    }

    return dstlen;
}

Unix-Like

En muchos sistemas tipo Unix, debe usar /dev/urandom cuando sea posible (aunque no se garantiza que exista en sistemas compatibles con POSIX).

size_t sysrandom(void* dst, size_t dstlen)
{
    char* buffer = reinterpret_cast<char*>(dst);
    std::ifstream stream("/dev/urandom", std::ios_base::binary | std::ios_base::in);
    stream.read(buffer, dstlen);

    return dstlen;
}

Otro

Si no hay CSPRNG disponible, puede optar por confiar en std::random_device . Sin embargo, evitaría esto si fuera posible, ya que varios compiladores (en particular, MinGW) lo implementan como un Link (de hecho, producen la misma secuencia cada vez para alertar a los humanos de que no es correctamente al azar).

Siembra

Ahora que tenemos nuestras piezas con una sobrecarga mínima, podemos generar los bits deseados de entropía aleatoria para sembrar nuestro PRNG. El ejemplo utiliza (obviamente insuficiente) 32 bits para inicializar el PRNG, y debe aumentar este valor (que depende de su CSPRNG).

std::uint_least32_t seed;    
sysrandom(&seed, sizeof(seed));
std::mt19937 gen(seed);

Comparación para impulsar

Podemos ver paralelos para impulsar :: random_device (un verdadero CSPRNG) después de un rápido vistazo al código fuente . Boost usa MS_DEF_PROV en Windows, que es el tipo de proveedor para PROV_RSA_FULL . Lo único que falta sería verificar el contexto criptográfico, que se puede hacer con CRYPT_VERIFYCONTEXT . En * Nix, Boost usa /dev/urandom . Es decir, esta solución es portátil, bien probada y fácil de usar.

Especialización Linux

Si está dispuesto a sacrificar la concisión por seguridad, getrandom es una excelente opción en Linux 3.17 y superior, y en Solaris reciente. getrandom comporta de manera idéntica a /dev/urandom , excepto que bloquea si el kernel aún no ha inicializado su CSPRNG después del arranque. El siguiente fragmento detecta si getrandom Linux está disponible y, si no, vuelve a /dev/urandom .

#if defined(__linux__) || defined(linux) || defined(__linux)
#   // Check the kernel version. `getrandom` is only Linux 3.17 and above.
#   include <linux/version.h>
#   if LINUX_VERSION_CODE >= KERNEL_VERSION(3,17,0)
#       define HAVE_GETRANDOM
#   endif
#endif

// also requires glibc 2.25 for the libc wrapper
#if defined(HAVE_GETRANDOM)
#   include <sys/syscall.h>
#   include <linux/random.h>

size_t sysrandom(void* dst, size_t dstlen)
{
    int bytes = syscall(SYS_getrandom, dst, dstlen, 0);
    if (bytes != dstlen) {
        throw std::runtime_error("Unable to read N bytes from CSPRNG.");
    }

    return dstlen;
}

#elif defined(_WIN32)

// Windows sysrandom here.

#else

// POSIX sysrandom here.

#endif

OpenBSD

Hay una advertencia final: OpenBSD moderno no tiene /dev/urandom . Deberías usar getentropy en getentropy lugar.

#if defined(__OpenBSD__)
#   define HAVE_GETENTROPY
#endif

#if defined(HAVE_GETENTROPY)
#   include <unistd.h>

size_t sysrandom(void* dst, size_t dstlen)
{
    int bytes = getentropy(dst, dstlen);
    if (bytes != dstlen) {
        throw std::runtime_error("Unable to read N bytes from CSPRNG.");
    }

    return dstlen;
}

#endif

otros pensamientos

Si necesita bytes aleatorios criptográficamente seguros, probablemente debería reemplazar el fstream con abrir / leer / cerrar sin búfer de POSIX. Esto se debe a que basic_filebuf y FILE contienen un búfer interno, que se asignará a través de un asignador estándar (y, por lo tanto, no se borrará de la memoria).

Esto podría hacerse fácilmente cambiando sysrandom a:

size_t sysrandom(void* dst, size_t dstlen)
{
    int fd = open("/dev/urandom", O_RDONLY);
    if (fd == -1) {
        throw std::runtime_error("Unable to open /dev/urandom.");
    }
    if (read(fd, dst, dstlen) != dstlen) {
        close(fd);
        throw std::runtime_error("Unable to read N bytes from CSPRNG.");
    }

    close(fd);
    return dstlen;
}

Gracias

Un agradecimiento especial a Ben Voigt por señalar que FILE usa lecturas almacenadas en búfer y, por lo tanto, no debe usarse.

También me gustaría agradecer a Peter Cordes por mencionar getrandom , y la falta de /dev/urandom OpenBSD.