Słabości rand() w C++

Prawie każdy, kto kiedyś programował w C++ zna funkcję rand() z biblioteki standardowej języka C (plik nagłówkowy cstdlib).
Jednak nie każdy użytkownik zdaje sobie sprawę, jak łatwo można odgadnąć jakie kolejne liczby zostaną "wylosowane". Wystarczy znajomość tylko... 3 kolejnych wyrazów ciągu.

W środowisku Visual C++ Express napisałem taki prosty generator liczb losowych:

http://pastebin.com/f26bdd7fe

Jak widać, wciskamy [ENTER] i dostajemy kolejną liczbę ;) Ale jak dokładnie działa generator liczb losowych? Przecież w komputerze nic losowe nie jest...

Do generowania liczb losowych w C++ stosowany jest liniowy generator kongruencyjny (LCG):

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

W artykule na wikipedii podane są odpowiednie stałe wykorzystywane w środowiskach z rodziny Visual C++. Znając je można napisać następujący program-jasnowidz:

http://pastebin.com/f26d0c0b6

Do odgadnięcia ciągu powyższy "jasnowidz" musi wykonać niewiele ponad 65 tysięcy operacji :) Znajomość 3 kolejnych liczb (niekoniecznie z początku ciągu) daje nam 100% skuteczność w dalszym odgadywaniu ciągu. Znajomość tylko 2 sąsiednich liczb z ciągu "losowego" daje nam "tylko" 50% szans na prawidłowe odgadnięcie dalszych liczb - szanse nadal wysokie, jak na jasnowidza ;)

Aby program ten działał dla kompilatora g++ i wszelkich innych kompilatorów zgodnych z ANSI C wystarczy zmienić "magiczne liczby" w 8 linii:

return (1103515245*x0 + 12345);

Jak widać LCG kompletnie nie nadają się do zastosowań kryptograficznych, a także ich "losowość" jest przeciętna. Natomiast jest to bardzo szybki algorytm, więc standardowa funkcja losowa w większości bibliotek języków programowania jest zaimplementowana właśnie z jego użyciem.

A jeżeli szukamy liczb prawdziwie losowych, polecam następującą książkę:

http://en.wikipedia.org/wiki/A_Million_Random_Digits_with_100,000_Normal_Deviates

Na amazon za jedyne 81 dolarów ;)