127 votes

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

J'ai l'impression de voir beaucoup de réponses, dans lesquelles quelqu'un suggère d'utiliser <random> pour générer des nombres aléatoires, généralement le long avec un code comme ceci:

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

Habituellement, cela remplace une sorte de "unholy abomination", tels que:

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

On peut critiquer l'ancienne en faisant valoir que l' time(NULL) fournit une faible entropie, time(NULL) est prévisible, et le résultat final est non-uniforme.

Mais cela est vrai de la nouvelle méthode: il a juste plus brillants de placage.

  • rd() renvoie un seul unsigned int. Cela a au moins 16 bits et probablement 32. Ce n'est pas assez de semences MT 19937 bits d'état.

  • À l'aide de std::mt19937 gen(rd());gen() (semis avec 32 bits et en regardant la première sortie) ne donne pas un bon de sortie de la distribution. 7 et 13 ne peut jamais être la première sortie. Deux graines de produire 0. Douze produisent des graines 1226181350. (Lien)

  • std::random_device peut-être, et l'est parfois, mis en œuvre comme un simple GÉNÉRATEUR avec un fixe de semences. Il pourrait donc produire la même séquence sur chaque course. (Lien) C'est encore pire que d' time(NULL).

Pire encore, il est très facile de copier et coller ce qui précède extraits de code, malgré les problèmes qu'ils contiennent. Quelques solutions à ce besoin d'acquérir largish bibliothèques qui peuvent ne pas convenir à tout le monde.

À la lumière de cela, ma question est Comment peut-on, de façon succincte, de façon portable, et soigneusement les semences de la mt19937 PRNG en C++?

Étant donné les questions ci-dessus, une bonne réponse:

  • Doit pleinement les semences de la mt19937/mt19937_64.
  • Ne peut pas reposer uniquement sur std::random_device ou time(NULL) comme source d'entropie.
  • Ne doivent pas compter sur un coup de pouce ou d'autres libaries.
  • Doivent tenir dans un petit nombre de lignes telles qu'il serait agréable à regarder copier-collé dans une réponse.

Pensées

  • Ma pensée est que les sorties de std::random_device peuvent être réduits en purée (peut-être par XOR) avec time(NULL), les valeurs dérivées de l'espace d'adresse de la randomisation, et codé en dur constante (ce qui pourrait être défini lors de la distribution) pour obtenir un best-effort de tir à l'entropie.

  • std::random_device::entropy() ne pas donner une bonne indication de ce que l' std::random_device pourrait ou ne pourrait pas faire.

61voto

Alexander Huszagh Points 6661

Je dirais que le plus grand défaut de avec std::random_device est la qu'il est permis à un déterministe de secours si aucune CSPRNG est disponible. Cela seul est une bonne raison de ne pas semer un GÉNÉRATEUR à l'aide de std::random_device, depuis les octets produit peut être déterministe. Il ne marche malheureusement pas fournir une API pour savoir quand cela se produit, ou à la demande de l'échec au lieu de la basse-qualité de nombres aléatoires.

Qui est, il n'est pas complètement portable solution: cependant, il est décent, approche minimale. Vous pouvez utiliser un petit wrapper autour d'une CSPRNG (défini comme l' sysrandom ci-dessous) pour déclencher le PRNG.

Windows


Vous pouvez compter sur CryptGenRandom, un 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 Unix, vous devez utiliser /dev/urandom quand c'est possible (même si cela n'est pas garanti pour exister sur POSIX systèmes).

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

D'autres


Si aucun CSPRNG est disponible, vous pouvez choisir de s'appuyer sur std::random_device. Cependant, je voudrais éviter si possible, étant donné que divers compilateurs (notamment, MinGW) mettre en œuvre avec un PRNG (en fait, la production de la même séquence à chaque fois pour alerter les humains qu'il n'est pas correctement aléatoire).

Semis


Maintenant que nous avons nos pièces avec un minimum de frais généraux, nous pouvons générer de l'souhaité bits aléatoires de l'entropie à la graine de notre GÉNÉRATEUR. L'exemple utilise (évidemment insuffisant) 32-bits pour déclencher le PRNG, et vous pouvez augmenter cette valeur (qui dépend de votre CSPRNG).

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

Comparaison De Boost


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

Linux Spécialisation


Si vous êtes prêt à sacrifier la concision de la sécurité, getrandom est un excellent choix sur Linux 3.17 et au-dessus, et sur ces derniers Solaris. getrandom se comporte de manière identique à l' /dev/urandom, à l'exception des blocs si le noyau n'a pas initialisé son CSPRNG encore après le démarrage. L'extrait de code suivant détecte si Linux getrandom est disponible, et si on ne retombe à l' /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: moderne OpenBSD n'a pas /dev/urandom. Vous devez 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'cryptographique sécurisé octets aléatoires, vous devrez probablement remplacer le fstream avec POSIX est sans tampon ouvrir/lire/fermer. C'est parce que les deux basic_filebuf et FILE contiennent une mémoire tampon interne, qui sera allouée par l'intermédiaire d'un allocateur standard (et donc pas effacé de la mémoire).

Cela pourrait facilement être fait en changeant sysrandom à la:

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 souligner FILE utilise tampon lit, et, par conséquent, ne doit pas être utilisé.

Je tiens également à remercier Peter Cordes pour mentionner getrandom, et OpenBSD manque d' /dev/urandom.

23voto

einpoklum Points 2893

Dans un sens, cela ne peut pas être fait de manière portable. En d’autres termes, on peut concevoir une plate-forme pleinement déterministe valide fonctionnant en C ++ (par exemple, un simulateur qui incrémente l’horloge de la machine de manière déterministe et avec une E / S "déterminée") dans laquelle il n’existe aucune source d’aléatoire pour générer un PRNG.

15voto

ratchet freak Points 22412

Vous pouvez utiliser un std::seed_seq et le remplir au moins l'exige la taille de l'état pour le générateur à l'aide de Alexander Huszagh de la méthode pour obtenir de l'entropie:

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 il y a une bonne façon de compléter ou de créer un SeedSequence à partir d'un UniformRandomBitGenerator de la bibliothèque standard, à l'aide de std::random_device pour l'ensemencement correctement serait beaucoup plus simple.

5voto

Galik Points 522

La mise en œuvre, je suis en train de prendre avantage de l' state_size de la propriété de l' mt19937 GÉNÉRATEUR de 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 à l'amélioration, car std::random_device::result_type pourraient différer de std::mt19937::result_type en taille et en gamme, donc ça devrait vraiment être pris en compte.

Une remarque à propos de std::random_device.

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

26.5.6 Classe random_device [ rand.appareil ]

2 Si la mise en œuvre des limitations d'éviter la création de non-déterministe de nombres aléatoires, la mise en œuvre peut employer un nombre aléatoire moteur.

Cela signifie la mise en œuvre ne peut générer déterministe valeurs si elle est dans l'impossibilité de générer des non-déterministe par une certaine limitation.

L' MinGW compilateur sur Windows célèbre ne fournit pas non déterministe valeurs à partir de son std::random_device,, bien qu'ils soient facilement accessibles à partir du Système d'Exploitation. Donc, je considère que c'est un bug et ne risquent pas un phénomène courant à travers les implémentations et les plates-formes.

2voto

Ian Mallett Points 1880

Il n'y a rien de mal avec l'ensemencement en utilisant le temps, en supposant que vous n'en avez pas besoin pour être sûr (et vous n'avez pas dit cela était nécessaire). L'idée est que vous pouvez utiliser le hachage pour corriger la non-aléatoire. J'ai trouvé cela fonctionne correctement dans tous les cas, y compris et en particulier pour lourde les simulations de Monte Carlo.

Une fonctionnalité intéressante de cette approche est qu'il généralise à l'initialisation à partir d'autres pas-vraiment-aléatoire ensembles de graines. Par exemple, si vous souhaitez que chaque thread pour avoir son propre générateur de nombres aléatoires (pour threadsafety), vous pouvez initialiser selon haché ID de thread.

Ce qui suit est une SSCCE, distillée à partir de ma base de code (pour plus de simplicité; certains OO structures de soutien élidée):

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

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X