Comment semer le mt19937 PRNG de manière succincte, portable et complète?

Il me semble voir de nombreuses réponses dans lesquelles quelqu'un suggère d'utiliser <random>pour générer des nombres aléatoires, généralement avec un code comme celui-ci:

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

Habituellement, cela remplace une sorte d '«abomination impie» telle que:

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

Nous pourrions critiquer l'ancienne méthode en affirmant qu'elle time(NULL)fournit une faible entropie, qu'elle time(NULL)est prévisible et que le résultat final n'est pas uniforme.

Mais tout cela est vrai de la nouvelle façon: il a juste un placage plus brillant.

• rd()renvoie un seul unsigned int. Cela a au moins 16 bits et probablement 32. Cela ne suffit pas pour amorcer les bits d'état 19937 de MT.

• Utiliser std::mt19937 gen(rd());gen()(ensemencer avec 32 bits et regarder la première sortie) ne donne pas une bonne distribution de sortie. 7 et 13 ne peuvent jamais être la première sortie. Deux graines produisent 0. Douze graines produisent 1226181350. ( Lien )

• std::random_devicepeut être, et est parfois, implémenté comme un simple PRNG avec une graine fixe. Il peut donc produire la même séquence à chaque exécution. ( Lien ) C'est encore pire que time(NULL).

Pire encore, il est très facile de copier et coller les extraits de code précédents, malgré les problèmes qu'ils contiennent. Certaines solutions à cela nécessitent l'acquisition de grandes bibliothèques qui peuvent ne pas convenir à tout le monde.

À la lumière de cela, ma question est: Comment peut-on semer succinctement, de manière portable et complète le PRNG mt19937 en C ++?

Compte tenu des problèmes ci-dessus, une bonne réponse:

• Doit semer complètement le mt19937 / mt19937_64.
• Ne peut pas compter uniquement sur std::random_deviceou time(NULL)comme source d'entropie.
• Ne devrait pas compter sur Boost ou d'autres bibliothèques.
• Doit tenir dans un petit nombre de lignes de sorte que cela semble bien copié-collé dans une réponse.

Pensées

• Ma pensée actuelle est que les sorties de std::random_devicepeuvent être mélangées (peut-être via XOR) avec des time(NULL)valeurs dérivées de la randomisation de l'espace d'adressage et une constante codée en dur (qui pourrait être définie lors de la distribution) pour obtenir un meilleur effort d'entropie.

• std::random_device::entropy() ne donne pas une bonne indication de ce qui std::random_devicepourrait ou ne pourrait pas faire.

Je dirais que le plus grand défaut std::random_deviceest le fait qu'il est autorisé à un repli déterministe si aucun CSPRNG n'est disponible. Ceci seul est une bonne raison de ne pas amorcer un PRNG en utilisant std::random_device, car les octets produits peuvent être déterministes. Il ne fournit malheureusement pas d'API pour savoir quand cela se produit, ou pour demander un échec au lieu de nombres aléatoires de mauvaise qualité.

Autrement dit, il n'y a pas de solution complètement portable : cependant, il existe une approche décente et minimale. Vous pouvez utiliser un wrapper minimal autour d'un CSPRNG (défini comme sysrandomci-dessous) pour amorcer le PRNG.

les fenêtres

Vous pouvez compter sur CryptGenRandomun CSPRNG. Par exemple, vous pouvez utiliser le code suivant:

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

Sur de nombreux systèmes de type Unix, vous devez utiliser / dev / urandom lorsque cela est possible (bien que cela ne soit pas garanti sur les systèmes compatibles 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;
}

Autre

Si aucun CSPRNG n'est disponible, vous pouvez choisir de vous fier à std::random_device. Cependant, j'éviterais cela si possible, car divers compilateurs (notamment MinGW) l'implémentent avec un PRNG (en fait, produisant la même séquence à chaque fois pour alerter les humains que ce n'est pas correctement aléatoire).

Semis

Maintenant que nous avons nos pièces avec une surcharge minimale, nous pouvons générer les bits d'entropie aléatoire souhaités pour amorcer notre PRNG. L'exemple utilise (évidemment insuffisant) 32 bits pour amorcer le PRNG, et vous devez augmenter cette valeur (qui dépend de votre CSPRNG).

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

Comparaison pour booster

Nous pouvons voir des parallèles pour boost :: random_device (un vrai CSPRNG) après un rapide coup d'œil au code source . Boost utilise MS_DEF_PROVWindows, qui est le type de fournisseur pour PROV_RSA_FULL. La seule chose qui manque serait de vérifier le contexte cryptographique, ce qui peut être fait avec CRYPT_VERIFYCONTEXT. Sur * Nix, Boost utilise /dev/urandom. IE, cette solution est portable, bien testée et facile à utiliser.

Spécialisation Linux

Si vous êtes prêt à sacrifier la concision pour la sécurité, getrandomc'est un excellent choix sur Linux 3.17 et supérieur, et sur Solaris récent. getrandomse comporte de la même manière que /dev/urandom, sauf qu'il se bloque si le noyau n'a pas encore initialisé son CSPRNG après le démarrage. L'extrait de code suivant détecte si Linux getrandomest disponible, et si ce n'est pas le cas, il revient à /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

Il y a une dernière mise en garde: OpenBSD moderne n'en a pas /dev/urandom. Vous devriez utiliser getentropy à la place.

#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

d'autres pensées

Si vous avez besoin d'octets aléatoires sécurisés par cryptographie, vous devriez probablement remplacer le fstream par l'ouverture / lecture / fermeture sans tampon de POSIX. C'est parce que les deux basic_filebufet FILEcontiennent un tampon interne, qui sera alloué via un allocateur standard (et donc pas effacé de la mémoire).

Cela pourrait facilement être fait en changeant sysrandomen:

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

Merci

Un merci spécial à Ben Voigt pour avoir signalé les FILEutilisations de lectures tamponnées et ne devraient donc pas être utilisées.

Je voudrais également remercier Peter Cordes pour avoir mentionné getrandom, et le manque d'OpenBSD /dev/urandom.

Dans un sens, cela ne peut pas être fait de manière portative. Autrement dit, on peut concevoir une plate-forme entièrement déterministe valide exécutant C ++ (par exemple, un simulateur qui marche l'horloge de la machine de manière déterministe, et avec des E / S "déterminées") dans laquelle il n'y a aucune source d'aléa pour amorcer un PRNG.

Vous pouvez utiliser a std::seed_seqet le remplir au moins à la taille d'état requise pour le générateur en utilisant la méthode d'Alexander Huszagh pour obtenir l'entropie:

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

void foo(){

    std::array<std::mt19937::UIntType, std::mt19937::state_size> state;
    sysrandom(state.begin(), state.length*sizeof(std::mt19937::UIntType));
    std::seed_seq s(state.begin(), state.end());

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

S'il y avait un moyen approprié de remplir ou de créer une SeedSequence à partir d'un UniformRandomBitGenerator dans la bibliothèque standard, utiliser std::random_devicecorrectement pour l'amorçage serait beaucoup plus simple.

L'implémentation sur laquelle je travaille tire parti de la state_sizepropriété du mt19937PRNG pour décider du nombre de graines à fournir lors de l'initialisation:

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

Je pense qu'il y a place à amélioration parce que cela std::random_device::result_typepourrait différer de la std::mt19937::result_typetaille et de la gamme, ce qui devrait vraiment être pris en compte.

Une note sur std :: random_device .

Selon la C++11(/14/17)(les) norme (s):

26.5.6 Classe random_device [ rand.device ]

2 Si les limitations d'implémentation empêchent de générer des nombres aléatoires non déterministes, l'implémentation peut utiliser un moteur de nombres aléatoires.

Cela signifie que l'implémentation ne peut générer des valeurs déterministes que si elle est empêchée de générer des valeurs non déterministes par une certaine limitation.

Le MinGWcompilateur sur Windowsne fournit pas de valeurs non déterministes à partir de son std::random_device, bien qu'elles soient facilement disponibles à partir du système d'exploitation. Je considère donc cela comme un bogue et peu probable comme un phénomène courant dans les implémentations et les plates-formes.

Il n'y a rien de mal à semer en utilisant le temps, en supposant que vous n'en ayez pas besoin pour être sécurisé (et vous n'avez pas dit que c'était nécessaire). L'idée est que vous pouvez utiliser le hachage pour corriger le caractère non aléatoire. J'ai trouvé que cela fonctionne correctement dans tous les cas, y compris et en particulier pour les simulations de Monte Carlo lourdes.

Une caractéristique intéressante de cette approche est qu'elle se généralise à l'initialisation à partir d'autres ensembles de graines pas vraiment aléatoires. Par exemple, si vous souhaitez que chaque thread ait son propre RNG (pour la sécurité des threads), vous pouvez simplement l'initialiser en fonction de l'ID de thread haché.

Ce qui suit est un SSCCE , distillé de ma base de code (pour plus de simplicité; certaines structures de support OO ont élidé):

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

Voici ma propre tentative à la question:

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

L'idée ici est d'utiliser XOR pour combiner de nombreuses sources potentielles d'entropie (temps rapide, temps lent, std::random-deviceemplacements de variables statiques, emplacements de tas, emplacements de fonctions, emplacements de bibliothèque, valeurs spécifiques au programme) afin de tenter au mieux d'initialiser le mt19937. Tant qu'au moins une fois la source est "bonne", le résultat sera au moins aussi "bon".

Cette réponse n'est pas aussi courte qu'il serait préférable et peut contenir une ou plusieurs erreurs de logique. Je considère donc que c'est un travail en cours. Veuillez commenter si vous avez des commentaires.

• Utilisez getentropy () pour amorcer un générateur de nombres pseudo-aléatoires (PRNG).
• Utilisez getrandom () si vous voulez des valeurs aléatoires (au lieu de, disons, /dev/urandomou /dev/random).

Ils sont disponibles sur les systèmes modernes de type UNIX, tels que Linux, Solaris et OpenBSD.

Une plate-forme donnée peut avoir une source d'entropie, telle que /dev/random. Nanosecondes depuis l'époque avecstd::chrono::high_resolution_clock::now() est probablement la meilleure graine de la bibliothèque standard.

J'ai précédemment utilisé quelque chose comme (uint64_t)( time(NULL)*CLOCKS_PER_SEC + clock() )pour obtenir plus de bits d'entropie pour les applications qui ne sont pas critiques pour la sécurité.