Pytanie Powinienem użyć losowego silnika rozstawionego ze std :: random_device lub użyć std :: random_device za każdym razem


Mam klasę, która zawiera dwa źródła losowości.

std::random_device rd;
std::mt19937 random_engine;

Zasiewam std::mt19937 z zaproszeniem do std::random_device. Jeśli chcę wygenerować liczbę i nie zależy mi na powtarzalności, powinienem zadzwonić rd() lub random_engine()?

W moim konkretnym przypadku, jestem pewien, że obie będą działały dobrze, ponieważ zostanie to nazwane w jakimś kodzie sieciowym, gdzie wydajność nie jest na wagę złota, a wyniki nie są szczególnie wrażliwe. Jednak interesują mnie pewne "zasady", kiedy stosować sprzętową entropię i kiedy używać liczb pseudolosowych.

Obecnie używam tylko std::random_device zasiać moje std::mt19937 silnik i dowolna generacja liczb losowych potrzebnych do mojego programu, używam std::mt19937 silnik.

edit: Oto wyjaśnienie dokładnie tego, co używam tego konkretnego przykładu dla:

To jest dla programu do grania. Ta konkretna gra pozwala użytkownikowi dostosować swoją "drużynę" przed rozpoczęciem rundy przeciwko przeciwnikowi. Częścią konfiguracji bitwy jest wysłanie zespołu do serwera. Mój program składa się z kilku zespołów i wykorzystuje liczbę losową do określenia, który zespół ma zostać załadowany. Każda nowa bitwa nawiązuje połączenie std::random_device obsadzić generator liczb pseudolosowych. Loguję początkowy stan bitwy, który obejmuje ten zespół, który losowo wybieram i początkowy materiał siewny.

Ta konkretna liczba losowa, o którą pytam w tym pytaniu, dotyczy losowego doboru drużyn (gdzie korzystne jest, aby przeciwnik nie wiedział z wyprzedzeniem, z jakiego zespołu korzystam, ale nie o krytycznym znaczeniu), ale co ja " Naprawdę potrzebna jest reguła. Czy to jest w porządku, aby zawsze używać std::random_device jeśli nie potrzebuję powtarzalności moich liczb, czy istnieje realne ryzyko użycia entropii szybciej niż można ją zebrać?


21
2017-08-05 15:08


pochodzenie




Odpowiedzi:


Standardowa praktyka, o ile mi wiadomo, polega na wysiewaniu generatora liczb losowych liczbą, która nie jest obliczana przez komputer (ale pochodzi z jakiegoś zewnętrznego, nieprzewidywalnego źródła). Tak powinno być w przypadku twojej funkcji rd (). Od tego momentu wywołujesz generator liczb pseudolosowych (PRNG) dla każdej wymaganej liczby pseudolosowej.

Jeśli obawiasz się, że liczby nie są wystarczająco przypadkowe, powinieneś wybrać inny PRNG. Entropia jest rzadkim i cennym zasobem i powinna być traktowana jako taka. Chociaż możesz nie potrzebować teraz wielu losowych liczb, możesz w przyszłości; lub inne aplikacje mogą ich potrzebować. Chcesz, aby ta entropia była dostępna, gdy aplikacja prosi o nią.

Dla twojej aplikacji brzmi to tak, jakby twister mersenne pasował do twoich potrzeb. Nikt, kto gra w Twoją grę nigdy nie poczuje, że załadowane zespoły nie są losowe.


10
2017-08-06 03:00





Jeśli nie używasz go do szyfrowania, dobrze jest wielokrotnie używać mt19937, który jest zaszczepiony przez random_engine.

W dalszej części tej odpowiedzi zakładam, że używasz liczb losowych do szyfrowania w kodzie sieciowym. W skrócie, mt19937 nie nadaje się do tego zastosowania.

http://en.wikipedia.org/wiki/Mersenne_twister#Disadvantages

Istnieje potencjalne ryzyko, że ujawnisz informacje (prawdopodobnie pośrednio) w czasie, aby atakujący mógł zacząć przewidywać losowe liczby. Przynajmniej w teorii, ale o to właśnie chodzi. Z Wikipedii

... ponieważ ta liczba jest wielkością wektora stanu od
  które przyszłe iteracje są tworzone) pozwala przewidzieć wszystkie przyszłe iteracje.

Prostym sposobem zapobiegania wyciekowi informacji o losowych numerach do użytkownika jest używanie jednokierunkowych funkcji skrótu, ale jest w nim znacznie więcej. Powinieneś użyć generatora liczb losowych zaprojektowanego do tego celu:

http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

Różne przykłady (z kodem) znajdują się tutaj http://xlinux.nist.gov/dads/HTML/pseudorandomNumberGen.html


7
2017-08-05 15:15





Jeśli potrzebujesz losowości do symulacji lub gry, to to, co robisz, jest w porządku. Wywołaj losowe urządzenie tylko raz i wykonaj całą resztę za pomocą losowo zainicjowanego pseudo-RNG. Jako bonus należy przechowywać wartość początkową w pliku dziennika, aby móc później odtwarzać sekwencję pseudolosową:

auto const seed = std::random_device()();
// save "seed" to log file
std::mt19937 random_engine(seed);

(W przypadku wielu wątków użyj PRNG w głównym wątku, aby wygenerować nasiona dla kolejnych PRNG w zarodkowanych wątkach).

Jeśli potrzebujesz dużo prawdziwej losowości do celów kryptograficznych, PRNG nigdy nie jest dobrym pomysłem, ponieważ długa sekwencja wyników zawiera dużo mniej losowości niż prawdziwa losowość, tzn. Możesz przewidzieć wszystko z małego podzbioru. Jeśli potrzebujesz prawdziwej losowości, powinieneś zebrać ją z jakiegoś nieprzewidywalnego źródła (np. Czujników ciepła, aktywności klawiatury / myszy itp.). Unix /dev/random może być źródłem "prawdziwej przypadkowości", ale może nie wypełniać się bardzo szybko.


7
2017-08-05 15:18



Nie jest prawdą, że można ogólnie wydedukować informacje z PRNG, używając małego zestawu liczb losowych. Dla wielu, tak - ale nie wszystkie. - Johan Lundberg
@JohanLundberg: Wystarczająco fair - przypuszczam, że to zależy od tego, co masz na myśli przez "małe" :-) - Kerrek SB
@KerrekSB Myślę, że powinien być pierwszy wiersz w twoim kodzie auto const seed = std::random_device()();, nie std::random_engine()()? - Ela782
@ Ela782: Absolutnie, dzięki! - Kerrek SB


Możesz chcieć rzucić okiem http://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful to wyjaśnia, dlaczego powinieneś używać uniform_int_distribution i mocnych stron rodziny random_device / mt19937.

W tym filmie Stephan T. Lavavej wyraźnie stwierdza, że ​​w wizualnym C ++ narzędzie random_device może być wykorzystywane do celów kryptograficznych.


3
2017-09-11 22:25



Standard nie wymaga, aby random_device było bezpieczne kryptograficznie. Tak, tak, w Windowsie z Visual C ++ jest to zaimplementowane w ten sposób, ale na innych platformach może być (i nie jest). Możemy zgodzić się, że to trochę głupie, aby nie zapewnić bezpieczeństwa kryptograficznego, ale ... - user7610


Odpowiedź zależy od platformy. Wydaje się, że pamiętam, że w Visual C ++ 2010 std :: random_device jest po prostu mt19937 wysiewany w jakiś nieudokumentowany sposób.

Oczywiście zdajesz sobie sprawę, że każdy schemat szyfrowania ad hoc oparty na generatorze liczb losowych może być bardzo słaby.


2
2017-08-05 19:09





Zakładając, że nie jest to możliwe w celach kryptograficznych, najważniejszą rzeczą do zapamiętania na temat generowania liczb losowych jest myślenie o tym, jak chcesz rozmieścić losowe liczby i jaki jest oczekiwany zakres.

Zwykle standardowe generatory liczb losowych w bibliotekach mają na celu zapewnienie jednolitej dystrybucji. Więc liczby będą się wahać od 0 do jakiegoś RAND_MAX (powiedzmy na maszynie 32-bitowej to 2 ^ 31 -1)

Oto, co należy zapamiętać przy pomocy generatorów liczb pseudolosowych. Większość z nich jest zaprojektowana do generowania losowych liczb, a nie losowych bitów. Różnica jest subtelna. Jeśli potrzebujesz liczb od 0 do 8, większość programistów powie: rand ()% 8 Jest to złe, ponieważ algorytm był do randomizacji 32 bitów. Ale używasz tylko 3 dolnych bitów. Nie dobrze. To nie zapewni jednolitej dystrybucji (zakładając, że tego właśnie szukasz)

Powinieneś użyć 8 * (rand () + 1) / (RAND_MAX), który teraz da ci jednolicie losową liczbę od 0 do 8.

Teraz przy pomocy sprzętowych generatorów liczb losowych możesz wytwarzać losowe bity. Jeśli tak jest, to każdy bit jest generowany niezależnie. Wtedy jest bardziej jak zbiór identycznych niezależnych bitów losowych. Modelowanie tutaj musiałoby być nieco inne. Miej to na uwadze, szczególnie w symulacjach dystrybucja staje się ważna.


-2
2017-08-05 15:32



Rzecz o niskich / wysokich bitach jest prawdziwa dla starych generatorów liczb losowych LCG, ale prawdopodobnie nie ma znaczenia dla nowoczesnych. To nie problem z Mersenne Twister, którego używa OP. - interjay
Używam funkcji biblioteki standardowej C ++ 11 std::uniform_int_distribution generować moje dystrybucje, więc mam tę część. - David Stone
Dodatkowo twoja formuła 8 * (rand() + 1) / (RAND_MAX) jest niepoprawny (spowoduje przepełnienie w liczbach całkowitych, nawet jeśli nie, będzie niewielka szansa, że ​​zostanie zwrócone 8). I RAND_MAX nie jest limitem przy korzystaniu z biblioteki liczb losowych C ++ 11, tylko z rand(). - interjay
Cóż, użyłem tego rand (), a nie generatora liczb losowych C ++ 11 dla przykładu. Tak więc RAND_MAX ma zastosowanie tam. Ale zgadzam się, że mówił o generatorze liczb losowych C ++. - av501