Wie kann man den mt19937 PRNG prägnant, tragbar und gründlich aussäen?

Ich sehe viele Antworten, in denen jemand vorschlägt <random>, Zufallszahlen zu generieren, normalerweise zusammen mit Code wie diesem:

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

Normalerweise ersetzt dies eine Art "unheiligen Greuel" wie:

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

Wir könnten den alten Weg kritisieren , indem wir argumentieren, dass er time(NULL)eine niedrige Entropie liefert, time(NULL)vorhersehbar ist und das Endergebnis ungleichmäßig ist.

Aber all das gilt für den neuen Weg: Er hat nur ein glänzenderes Furnier.

• rd()gibt eine einzelne zurück unsigned int. Dies hat mindestens 16 Bit und wahrscheinlich 32. Das reicht nicht aus, um die 19937-Bit-Zustände von MT zu setzen.

• Die Verwendung std::mt19937 gen(rd());gen()(Seeding mit 32 Bit und Betrachten der ersten Ausgabe) ergibt keine gute Ausgabeverteilung. 7 und 13 können niemals die erste Ausgabe sein. Zwei Samen produzieren 0. Zwölf Samen produzieren 1226181350. ( Link )

• std::random_devicekann und wird manchmal als einfaches PRNG mit einem festen Startwert implementiert. Es kann daher sein, dass bei jedem Lauf dieselbe Sequenz erzeugt wird. ( Link ) Das ist noch schlimmer als time(NULL).

Schlimmer noch, es ist sehr einfach, die oben genannten Codefragmente zu kopieren und einzufügen, trotz der darin enthaltenen Probleme. Einige Lösungen hierfür erfordern den Erwerb größerer Bibliotheken, die möglicherweise nicht für jeden geeignet sind.

Vor diesem Hintergrund lautet meine Frage: Wie kann man das mt19937 PRNG in C ++ kurz, portabel und gründlich aussäen?

Angesichts der oben genannten Probleme eine gute Antwort:

• Muss den mt19937 / mt19937_64 vollständig aussäen.
• Kann sich nicht nur auf std::random_deviceoder time(NULL)als Entropiequelle verlassen.
• Sollte sich nicht auf Boost oder andere Bibliotheken verlassen.
• Sollte in eine kleine Anzahl von Zeilen passen, so dass es gut aussehen würde, wenn es in eine Antwort eingefügt wird.

Gedanken

• Mein aktueller Gedanke ist, dass Ausgaben von std::random_device(möglicherweise über XOR) mit time(NULL)Werten, die aus der Adressraum-Randomisierung abgeleitet wurden , und einer fest codierten Konstante (die während der Verteilung festgelegt werden kann) kombiniert werden können , um eine bestmögliche Entropie zu erzielen.

• std::random_device::entropy() gibt keinen guten Hinweis darauf, was std::random_devicetun könnte oder nicht.

Ich würde argumentieren, dass der größte Fehler std::random_devicedarin besteht, dass ein deterministischer Fallback zulässig ist, wenn kein CSPRNG verfügbar ist. Dies allein ist ein guter Grund, ein PRNG nicht mit zu setzen std::random_device, da die erzeugten Bytes deterministisch sein können. Leider bietet es keine API, um herauszufinden, wann dies geschieht, oder um Fehler anstelle von Zufallszahlen geringer Qualität anzufordern.

Das heißt, es gibt keine vollständig tragbare Lösung: Es gibt jedoch einen anständigen, minimalen Ansatz. Sie können einen minimalen Wrapper um ein CSPRNG (wie sysrandomunten definiert ) verwenden, um das PRNG zu setzen.

Windows

Sie können sich auf CryptGenRandomein CSPRNG verlassen. Beispielsweise können Sie den folgenden Code verwenden:

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-ähnlich

Auf vielen Unix-ähnlichen Systemen sollten Sie nach Möglichkeit / dev / urandom verwenden (obwohl dies auf POSIX-kompatiblen Systemen nicht garantiert ist).

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

Andere

Wenn kein CSPRNG verfügbar ist, können Sie sich darauf verlassen std::random_device. Ich würde dies jedoch nach Möglichkeit vermeiden, da verschiedene Compiler (insbesondere MinGW) es als PRNG implementieren (tatsächlich wird jedes Mal dieselbe Sequenz erstellt, um die Menschen darauf aufmerksam zu machen, dass es nicht richtig zufällig ist).

Aussaat

Jetzt, da wir unsere Stücke mit minimalem Overhead haben, können wir die gewünschten Bits zufälliger Entropie erzeugen, um unser PRNG zu säen. In diesem Beispiel werden (offensichtlich unzureichende) 32-Bit-Werte zum Setzen des PRNG verwendet, und Sie sollten diesen Wert erhöhen (abhängig von Ihrem CSPRNG).

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

Vergleich zu Boost

Nach einem kurzen Blick auf den Quellcode können wir Parallelen zu boost :: random_device (ein echtes CSPRNG) erkennen . Boost verwendet MS_DEF_PROVunter Windows, dem Anbietertyp für PROV_RSA_FULL. Das einzige, was fehlt, wäre die Überprüfung des kryptografischen Kontexts, mit dem gearbeitet werden kann CRYPT_VERIFYCONTEXT. Unter * Nix verwendet Boost /dev/urandom. IE, diese Lösung ist portabel, gut getestet und einfach zu bedienen.

Linux-Spezialisierung

Wenn Sie bereit sind, Prägnanz für Sicherheit zu opfern, getrandomist dies eine ausgezeichnete Wahl unter Linux 3.17 und höher sowie unter Solaris. getrandomverhält sich identisch mit /dev/urandom, außer dass es blockiert, wenn der Kernel sein CSPRNG nach dem Booten noch nicht initialisiert hat. Das folgende Snippet erkennt, ob Linux getrandomverfügbar ist, und greift nicht darauf zurück /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

Es gibt eine letzte Einschränkung: moderne OpenBSD hat keine /dev/urandom. Sie sollten stattdessen getentropy verwenden.

#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

andere Gedanken

Wenn Sie kryptografisch sichere Zufallsbytes benötigen, sollten Sie den fstream wahrscheinlich durch das ungepufferte Öffnen / Lesen / Schließen von POSIX ersetzen. Dies liegt daran, dass beide basic_filebufund FILEeinen internen Puffer enthalten, der über einen Standard-Allokator zugewiesen wird (und daher nicht aus dem Speicher gelöscht wird).

Dies kann leicht durch Ändern sysrandomvon:

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

Vielen Dank

Besonderer Dank geht an Ben Voigt für den Hinweis, dass FILEgepufferte Lesevorgänge verwendet werden und daher nicht verwendet werden sollten.

Ich möchte auch Peter Cordes für die Erwähnung getrandomund das Fehlen von OpenBSD danken /dev/urandom.

In gewissem Sinne kann dies nicht portabel gemacht werden. Das heißt, man kann sich eine gültige vollständig deterministische Plattform vorstellen, auf der C ++ ausgeführt wird (z. B. ein Simulator, der den Maschinentakt deterministisch und mit "determinierter" E / A steuert), bei der es keine Zufallsquelle gibt, um ein PRNG zu setzen.

Sie können a verwenden std::seed_seqund es mindestens auf die erforderliche Zustandsgröße für den Generator füllen, indem Sie die Methode von Alexander Huszagh verwenden, um die Entropie zu erhalten:

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

Wenn es einen geeigneten Weg gäbe , eine SeedSequence aus einem UniformRandomBitGenerator in der Standardbibliothek zu füllen oder zu erstellen, wäre die Verwendung std::random_devicefür das ordnungsgemäße Seeding viel einfacher.

Die Implementierung, an der ich arbeite, nutzt die state_sizeEigenschaft des mt19937PRNG, um zu entscheiden, wie viele Seeds bei der Initialisierung bereitgestellt werden sollen:

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

Ich denke, es gibt Raum für Verbesserungen, da diese std::random_device::result_typesich std::mt19937::result_typein Größe und Reichweite unterscheiden können, sodass dies wirklich berücksichtigt werden sollte.

Ein Hinweis zu std :: random_device .

Gemäß den C++11(/14/17)Standards:

26.5.6 Klasse random_device [ rand.device ]

2 Wenn Implementierungsbeschränkungen das Generieren nicht deterministischer Zufallszahlen verhindern, kann die Implementierung eine Zufallszahlen-Engine verwenden.

Dies bedeutet, dass die Implementierung möglicherweise nur deterministische Werte generiert , wenn durch eine Einschränkung verhindert wird, dass nicht deterministische Werte generiert werden .

Der MinGWCompiler on Windowsliefert bekanntlich keine nicht deterministischen Werte von ihm std::random_device, obwohl sie vom Betriebssystem leicht verfügbar sind. Daher halte ich dies für einen Fehler und wahrscheinlich nicht für ein häufiges Auftreten zwischen Implementierungen und Plattformen.

Es ist nichts Falsches daran, Zeit zu verwenden, vorausgesetzt, Sie brauchen sie nicht, um sicher zu sein (und Sie haben nicht gesagt, dass dies notwendig ist). Die Erkenntnis ist, dass Sie Hashing verwenden können, um die Nicht-Zufälligkeit zu beheben. Ich habe festgestellt, dass dies in allen Fällen angemessen funktioniert, auch und insbesondere für schwere Monte-Carlo-Simulationen.

Ein nettes Merkmal dieses Ansatzes ist, dass er auf die Initialisierung von anderen nicht wirklich zufälligen Sätzen von Samen verallgemeinert wird. Wenn Sie beispielsweise möchten, dass jeder Thread über ein eigenes RNG verfügt (aus Gründen der Thread-Sicherheit), können Sie die Initialisierung nur anhand der Hash-Thread-ID durchführen.

Das Folgende ist eine SSCCE , die aus meiner Codebasis destilliert wurde (der Einfachheit halber wurden einige OO-Unterstützungsstrukturen entfernt):

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

Hier ist mein eigener Stich bei der Frage:

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

Die Idee hier ist, XOR zu verwenden, um viele potenzielle Entropiequellen (schnelle Zeit, langsame Zeit, std::random-devicestatische variable Positionen, Heap-Positionen, Funktionspositionen, Bibliothekspositionen, programmspezifische Werte) zu kombinieren , um einen bestmöglichen Versuch zur Initialisierung der zu unternehmen mt19937. Solange mindestens eine Quelle "gut" ist, ist das Ergebnis mindestens "gut".

Diese Antwort ist nicht so kurz wie vorzuziehen und kann einen oder mehrere Logikfehler enthalten. Ich halte es also für eine laufende Arbeit. Bitte kommentieren Sie, wenn Sie Feedback haben.

• Verwenden Sie getentropy (), um einen Pseudozufallszahlengenerator (PRNG) zu erstellen.
• Verwenden Sie getrandom (), wenn Sie zufällige Werte möchten (anstelle von beispielsweise /dev/urandomoder /dev/random).

Diese sind auf modernen UNIX-ähnlichen Systemen wie Linux, Solaris und OpenBSD verfügbar.

Eine bestimmte Plattform kann eine Entropiequelle haben, wie z /dev/random. Nanosekunden seit der Epoche mit std::chrono::high_resolution_clock::now()ist wahrscheinlich der beste Samen in der Standardbibliothek.

Ich habe zuvor so etwas verwendet (uint64_t)( time(NULL)*CLOCKS_PER_SEC + clock() ), um mehr Entropie für Anwendungen zu erhalten, die nicht sicherheitskritisch sind.