Jak zwięźle, przenośnie i dokładnie obsiać mt19937 PRNG?

Wydaje mi się, że widzę wiele odpowiedzi, w których ktoś sugeruje użycie <random>do generowania liczb losowych, zwykle wraz z takim kodem:

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

Zwykle zastępuje to jakąś „przeklętą obrzydliwość”, taką jak:

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

Możemy krytykować stary sposób, argumentując, że time(NULL)zapewnia niską entropię, time(NULL)jest przewidywalny, a wynik końcowy jest niejednolity.

Ale to wszystko jest prawdą w przypadku nowego sposobu: ma po prostu bardziej błyszczącą okleinę.

• rd()zwraca pojedynczy unsigned int. Ma to co najmniej 16 bitów i prawdopodobnie 32. To nie wystarczy, aby zaszczepić 19937 bitów stanu MT.

• Używanie std::mt19937 gen(rd());gen()(zapełnianie 32 bitami i patrzenie na pierwsze wyjście) nie daje dobrego rozkładu wyników. 7 i 13 nigdy nie mogą być pierwszym wyjściem. Dwa nasiona dają 0. Dwanaście nasion daje 1226181350. ( Link )

• std::random_devicemoże być, a czasami jest, zaimplementowany jako prosty PRNG ze stałym nasieniem. Może zatem tworzyć tę samą sekwencję w każdym przebiegu. ( Link ) To jest jeszcze gorsze niż time(NULL).

Co gorsza, bardzo łatwo jest skopiować i wkleić powyższe fragmenty kodu, pomimo problemów, które zawierają. Niektóre rozwiązania tego problemu wymagają pozyskania dużych bibliotek, które mogą nie być odpowiednie dla wszystkich.

W związku z tym moje pytanie brzmi: Jak zwięźle, przenośnie i dogłębnie posiać mt19937 PRNG w C ++?

Biorąc pod uwagę powyższe kwestie, dobra odpowiedź:

• Musi w pełni obsiać mt19937 / mt19937_64.
• Nie można polegać wyłącznie na std::random_devicelub time(NULL)jako źródle entropii.
• Nie powinien polegać na Boost lub innych bibliotekach.
• Powinien zmieścić się w niewielkiej liczbie wierszy, tak aby ładnie wyglądał po wklejeniu do odpowiedzi.

Myśli

• Obecnie std::random_devicesądzę, że dane wyjściowe from mogą zostać zmiksowane (być może przez XOR) z time(NULL)wartościami pochodzącymi z randomizacji przestrzeni adresowej i stałą zakodowaną na stałe (którą można ustawić podczas dystrybucji), aby uzyskać najlepszy możliwy strzał w entropię.

• std::random_device::entropy() nie daje dobrego wskazania, co std::random_devicemoże, a czego nie.

Twierdzę, że największą wadą std::random_devicejest to, że dozwolone jest deterministyczne rozwiązanie awaryjne, jeśli nie jest dostępny CSPRNG. Już samo to jest dobrym powodem, aby nie wysiewać PRNG przy użyciu std::random_device, ponieważ produkowane bajty mogą być deterministyczne. Niestety nie zapewnia interfejsu API, aby dowiedzieć się, kiedy tak się stanie, lub zażądać błędu zamiast niskiej jakości liczb losowych.

Oznacza to, że nie ma całkowicie przenośnego rozwiązania: istnieje jednak przyzwoite, minimalne podejście. Możesz użyć minimalnego opakowania wokół CSPRNG (zdefiniowanego sysrandomponiżej), aby zainicjować PRNG.

Windows

Możesz polegać na CryptGenRandomCSPRNG. Na przykład możesz użyć następującego kodu:

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

Podobne do systemu Unix

W wielu systemach uniksopodobnych powinieneś używać / dev / urandom, jeśli to możliwe (chociaż nie ma gwarancji, że będzie istnieć w systemach zgodnych z 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;
}

Inny

Jeśli nie ma dostępnego CSPRNG, możesz polegać std::random_device. Jednak unikałbym tego, jeśli to możliwe, ponieważ różne kompilatory (w szczególności MinGW) implementują go jako PRNG (w rzeczywistości produkują tę samą sekwencję za każdym razem, aby ostrzegać ludzi, że nie jest ona właściwie losowa).

Wysiew

Teraz, gdy mamy już nasze elementy z minimalnym narzutem, możemy wygenerować pożądane bity losowej entropii, aby zasiać nasz PRNG. W przykładzie użyto (oczywiście niewystarczających) 32-bitowych do zapoczątkowania PRNG i powinieneś zwiększyć tę wartość (która jest zależna od twojego CSPRNG).

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

Porównanie do wzmocnienia

Widzimy podobieństwa do boost :: random_device (prawdziwy CSPRNG) po szybkim spojrzeniu na kod źródłowy . Boost używa MS_DEF_PROVw systemie Windows, który jest typem dostawcy dla PROV_RSA_FULL. Jedyne, czego brakowało, to zweryfikowanie kontekstu kryptograficznego, z którym można to zrobić CRYPT_VERIFYCONTEXT. W * Nix Boost używa /dev/urandom. IE, to rozwiązanie jest przenośne, dobrze przetestowane i łatwe w użyciu.

Specjalizacja w Linuksie

Jeśli chcesz poświęcić zwięzłość dla bezpieczeństwa, getrandomjest to doskonały wybór na Linuksie 3.17 i nowszych oraz na najnowszym Solarisie. getrandomzachowuje się identycznie /dev/urandom, z wyjątkiem tego, że blokuje się, jeśli jądro nie zainicjowało swojego CSPRNG jeszcze po uruchomieniu. Poniższy fragment kodu wykrywa, czy Linux getrandomjest dostępny, a jeśli nie, wraca do /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

Jest jeszcze jedno ostatnie zastrzeżenie: współczesne OpenBSD nie ma /dev/urandom. Zamiast tego powinieneś użyć getentropy .

#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

inne przemyślenia

Jeśli potrzebujesz zabezpieczonych kryptograficznie losowych bajtów, prawdopodobnie powinieneś zamienić fstream na niebuforowane open / read / close POSIX. Dzieje się tak, ponieważ oba basic_filebufi FILEzawierają wewnętrzny bufor, który zostanie przydzielony przez standardowy alokator (a zatem nie zostanie usunięty z pamięci).

Można to łatwo zrobić, zmieniając sysrandomna:

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

Dzięki

Specjalne podziękowania dla Bena Voigta za wskazanie FILEzastosowań odczytów buforowanych i dlatego nie należy ich używać.

Chciałbym również podziękować Peterowi Cordesowi za wspomnienie getrandomi brak OpenBSD /dev/urandom.

W pewnym sensie nie można tego zrobić przenośnie. Oznacza to, że można wyobrazić sobie w pełni deterministyczną platformę, na której działa C ++ (powiedzmy, symulator, który deterministycznie ustawia taktowanie zegara maszynowego i ze „zdeterminowanymi” I / O), w której nie ma źródła losowości do zapoczątkowania PRNG.

Możesz użyć a std::seed_seqi wypełnić go co najmniej do wymaganego rozmiaru stanu dla generatora, korzystając z metody uzyskania entropii Aleksandra Huszagha:

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

Gdyby istniał właściwy sposób na wypełnienie lub utworzenie SeedSequence z UniformRandomBitGenerator w standardowej bibliotece, użycie std::random_devicedo prawidłowego wysiewu byłoby znacznie prostsze.

Implementacja, nad którą pracuję, wykorzystuje state_sizewłaściwość mt19937PRNG, aby zdecydować, ile nasion ma dostarczyć podczas inicjalizacji:

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

Myślę, że jest miejsce na ulepszenia, ponieważ std::random_device::result_typemogą różnić się std::mt19937::result_typerozmiarem i zakresem, więc należy to wziąć pod uwagę.

Uwaga o std :: random_device .

Zgodnie z C++11(/14/17)normami:

26.5.6 Klasa random_device [ rand.device ]

2 Jeżeli ograniczenia implementacji uniemożliwiają generowanie niedeterministycznych liczb losowych, implementacja może wykorzystywać silnik liczb losowych.

To oznacza, że realizacja może generować tylko deterministyczne wartości, jeżeli nie ma możliwości generowania niedeterministycznym te przez jakiś ograniczeń.

MinGWKompilator na Windowspokazowo nie przewiduje niedeterministycznym wartości od jej std::random_device, mimo nich jest łatwo dostępne z poziomu systemu operacyjnego. Dlatego uważam to za błąd i prawdopodobnie nie jest to częste zjawisko w różnych implementacjach i platformach.

Nie ma nic złego w wysiewaniu przy użyciu czasu, zakładając, że nie potrzebujesz go do zabezpieczenia (i nie powiedziałeś, że jest to konieczne). Wgląd jest taki, że możesz użyć haszowania, aby naprawić nie-losowość. Zauważyłem, że działa to prawidłowo we wszystkich przypadkach, w tym iw szczególności w przypadku ciężkich symulacji Monte Carlo.

Jedną z fajnych cech tego podejścia jest to, że uogólnia ono inicjalizację z innych niezupełnie losowych zestawów nasion. Na przykład, jeśli chcesz, aby każdy wątek miał swój własny RNG (dla bezpieczeństwa wątków), możesz po prostu zainicjować na podstawie zahaszowanego identyfikatora wątku.

Poniżej znajduje się SSCCE , wydestylowane z mojego kodu (dla uproszczenia; niektóre struktury wspierające OO zostały usunięte):

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

Oto moja własna odpowiedź na pytanie:

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

Pomysł polega na tym, aby użyć XOR do połączenia wielu potencjalnych źródeł entropii (szybki czas, powolny czas, std::random-devicestatyczne lokalizacje zmiennych, lokalizacje sterty, lokalizacje funkcji, lokalizacje bibliotek, wartości specyficzne dla programu), aby podjąć najlepszą próbę zainicjowania mt19937. Tak długo, jak przynajmniej raz źródło jest „dobre”, wynik będzie przynajmniej taki „dobry”.

Ta odpowiedź nie jest tak krótka, jak byłoby to preferowane i może zawierać jeden lub więcej błędów logicznych. Więc uważam, że to praca w toku. Prosimy o komentarz, jeśli masz opinię.

• Użyj getentropy (), aby zapoczątkować generator liczb pseudolosowych (PRNG).
• Użyj getrandom (), jeśli chcesz mieć wartości losowe (zamiast, powiedzmy, /dev/urandomlub /dev/random).

Są one dostępne w nowoczesnych systemach typu UNIX, takich jak Linux, Solaris i OpenBSD.

Dana platforma może mieć źródło entropii, takie jak /dev/random. Nanosekundy od Epoki z std::chrono::high_resolution_clock::now()to prawdopodobnie najlepsze ziarno w Bibliotece Standardowej.

Wcześniej używałem czegoś w rodzaju, (uint64_t)( time(NULL)*CLOCKS_PER_SEC + clock() )aby uzyskać więcej bitów entropii dla aplikacji, które nie są krytyczne dla bezpieczeństwa.