Jak działa algorytm losowania w komputerach

Komputer nie rzuca kostką

Procesor nie ma w sobie nic, co działałoby przypadkowo. Każda instrukcja ma jeden określony wynik i właśnie dlatego komputerom można ufać przy obliczeniach. Przy losowaniu ta sama cecha staje się przeszkodą. Są dwa sposoby, żeby sobie z nią poradzić: wyliczać liczby, które tylko wyglądają na losowe, albo mierzyć coś, czego nie da się przewidzieć. W praktyce używa się obu naraz.

Ziarno

Wartość początkowa, od której generator zaczyna liczyć. To samo ziarno daje ten sam ciąg.

Stan

Liczby, które generator pamięta między kolejnymi losowaniami. Każdy krok zmienia stan i wylicza z niego wynik.

Okres

Długość ciągu, po której generator wraca do stanu początkowego i zaczyna powtarzać wyniki.

Entropia

Miara nieprzewidywalności. System zbiera ją ze zdarzeń fizycznych i używa jako ziarna.

Jak liczy generator pseudolosowy

Generator pseudolosowy (PRNG) przechowuje stan i przy każdym wywołaniu robi dwie rzeczy: przekształca stan według stałego wzoru i wylicza z nowego stanu liczbę, którą zwraca. Najprostszy przykład to generator liniowy kongruencyjny (LCG). Jego stan to jedna liczba, a kolejny krok wygląda tak:

X(n+1) = (a · X(n) + c) mod m

Stała a to mnożnik, c to przyrost, a m to moduł, który wyznacza zakres stanów. Poniżej działa LCG z parametrami z przykładowej funkcji rand() opisanej w standardzie języka C. Każdy nowy stan zamieniamy na liczbę od 1 do 100.

Wylosuj kilka liczb, kliknij „Od początku” i losuj dalej. Ciąg powtórzy się co do jednej liczby, a powtórzone wyniki są oznaczone obwódką. Tak działa każdy generator pseudolosowy. W testach i symulacjach to zaleta, bo wynik da się odtworzyć. Przy hasłach i kluczach to wada, bo kto pozna ziarno, pozna wszystkie liczby.

Dlaczego LCG to za mało

LCG jest szybki i prosty, ale ma słabe strony. Najmłodsze bity jego wyników powtarzają się w krótkich cyklach, a punkty utworzone z kolejnych wyników układają się w przestrzeni na płaszczyznach. Dlatego współczesne generatory mają większy stan i bardziej złożony krok. Mersenne Twister z 1997 roku pamięta 624 liczby 32-bitowe i powtarza ciąg dopiero po 2¹⁹⁹³⁷ − 1 wynikach. Rodzina xorshift opiera się na przesunięciach i operacji XOR, dzięki czemu jest bardzo szybka. Historię tych algorytmów opisujemy w artykule o historii generatorów liczb losowych.

Co losuje Twój język programowania

Każdy popularny język ma szybki generator do zwykłych zastosowań i osobną funkcję kryptograficzną. Różnią się algorytmem, a ich nazwy łatwo pomylić.

Specyfikacja JavaScriptu nie mówi, jakiego algorytmu ma używać Math.random(). Silnik V8 z Chrome i Node.js przeszedł pod koniec 2015 roku z generatora MWC1616 na xorshift128+, a inne przeglądarki wprowadziły podobną zmianę mniej więcej w tym samym czasie. Starsza klasa RNGCryptoServiceProvider w C# jest od .NET 6 oznaczona jako przestarzała i zastępuje ją RandomNumberGenerator. Przykłady kodu w czterech językach znajdziesz w artykule o generatorach pseudolosowych i kryptograficznych.

Od bitów do liczby z zakresu

Generator zwraca bity albo dużą liczbę całkowitą. Zwykle potrzebujemy jednak liczby z konkretnego zakresu, na przykład od 1 do 49 przy losowaniu Lotto. Najprostszy pomysł to reszta z dzielenia: wylosuj bajt i weź resztę z dzielenia przez 49. Ten sposób daje przekłamane wyniki.

Bajt ma 256 możliwych wartości, a 256 = 5 · 49 + 11. Wartości od 0 do 244 rozkładają się równo na pięć pełnych przebiegów od 0 do 48. Zostaje 11 wartości (od 245 do 255), które dają reszty od 0 do 10. W efekcie liczby od 0 do 10 wypadają z prawdopodobieństwem 6/256, a pozostałe 5/256. Różnica wynosi 20 procent i przy wielu losowaniach jest wyraźnie widoczna.

Ta metoda nazywa się losowaniem z odrzucaniem. Funkcje biblioteczne, takie jak random_int() w PHP czy secrets.randbelow() w Pythonie, robią to za programistę. Dlatego lepiej z nich korzystać, niż składać wynik samodzielnie. Podobny problem pojawia się przy liczbach ułamkowych, ale tam różnice są dużo mniejsze, bo zakres możliwych wartości jest ogromny.

Skąd system bierze entropię

Skoro wynik generatora zależy od ziarna, ziarno musi być nieprzewidywalne. Dawniej programy brały na nie aktualny czas, ale czas łatwo zgadnąć z dokładnością do sekundy. Współczesne systemy operacyjne zbierają entropię ze zdarzeń fizycznych i przechowują ją w puli, z której zasilają generator kryptograficzny.

W Linuksie dostęp do generatora dają urządzenia /dev/random i /dev/urandom oraz funkcja getrandom(). Przez lata /dev/random potrafił zatrzymać program, gdy system uznał, że zabrakło entropii. Od jądra 5.6 z 2020 roku oba urządzenia korzystają z tego samego generatora, a /dev/random czeka tylko na samym początku startu systemu, zanim generator zbierze dość entropii. W Windows tę rolę pełni BCryptGenRandom, który zastąpił przestarzałe CryptGenRandom, a w systemach Apple SecRandomCopyBytes.

Najdalej idą generatory kwantowe, które mierzą zjawiska z natury nieprzewidywalne. Najnowszy eksperyment w tej dziedzinie opisujemy w artykule o idealnie losowych liczbach.

Generatory kryptograficzne

Generator kryptograficzny (CSPRNG) to generator pseudolosowy z dodatkowymi gwarancjami. Jego wyników nie da się przewidzieć nawet po obejrzeniu długiego fragmentu ciągu. Zwykły Mersenne Twister tego warunku nie spełnia: po 624 kolejnych wynikach można odtworzyć jego stan i wyliczyć wszystkie następne liczby.

W praktyce takie generatory buduje się z szyfrów i funkcji skrótu. Linux od wersji 4.8 korzysta z szyfru strumieniowego ChaCha20. Standard NIST SP 800-90A opisuje między innymi CTR_DRBG oparty na szyfrze AES w trybie licznika. Fortuna, zaprojektowana przez Nielsa Fergusona i Bruce'a Schneiera, jest podstawą generatorów we FreeBSD i w systemach Apple. Z generatora kryptograficznego korzysta nasz generator haseł.

Jak sprawdza się jakość

Żaden test nie udowodni, że ciąg jest losowy. Testy potrafią za to wykryć konkretne wzorce, których w losowym ciągu być nie powinno: za dużo zer, za długie serie, zależności między sąsiednimi liczbami. Generator, który przejdzie wiele takich testów, uznaje się za dobry do zastosowań statystycznych.

NIST SP 800-22

15 testów amerykańskiego instytutu NIST, między innymi częstości bitów, długości serii i złożoności liniowej.

Diehard

Zestaw George'a Marsaglii z 1995 roku. Dziś służy raczej do wstępnej oceny.

TestU01

Biblioteka Pierre'a L'Ecuyera i Richarda Simarda. Najostrzejszy zestaw, BigCrush, wykonuje 106 testów.

Wynik Mersenne Twistera

Nie przechodzi dwóch testów liniowości w BigCrush. W typowych zastosowaniach nie ma to znaczenia, ale pokazuje, że testy wyłapują subtelne wzorce.

Który generator wybrać

Jeśli nikt nie zyska na przewidzeniu wyniku, wystarczy wbudowany generator pseudolosowy: do gier, symulacji, testów i losowania kolejności w klasie. Gdy wynik musi dać się powtórzyć, ustaw stałe ziarno. Jeśli od nieprzewidywalności zależy bezpieczeństwo, czyli przy hasłach, tokenach, kluczach i linkach do resetu hasła, użyj funkcji kryptograficznej systemu albo języka. Do wyboru liczby z zakresu korzystaj z gotowej funkcji bibliotecznej zamiast z reszty z dzielenia.

Często zadawane pytania