Generator liczb pseudolosowych

Generator liczb pseudolosowych (ang. pseudo-random number generator lub PRNG) – program lub podprogram, który na podstawie niewielkiej ilości informacji (ziarno, zarodek, ang. seed) generuje deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.

Generatory liczb pseudolosowych nie generują ciągów prawdziwie losowych – generator inicjowany ziarnem, które może przyjąć $k$ różnych wartości, jest w stanie wyprodukować co najwyżej $k$ różnych ciągów liczb. Co więcej, ponieważ rozmiar zmiennych reprezentujących wewnętrzny stan generatora jest ograniczony (zwykle decyzją programisty, do kilkudziesięciu lub kilkuset bitów; a rzadziej, po prostu rozmiarem pamięci komputera), i ponieważ w związku z tym może on znajdować się tylko w ograniczonej liczbie stanów, bez dostarczania nowych danych z zewnątrz musi po jakimś czasie dokonać pełnego cyklu i zacząć generować te same wartości. Teoretyczny limit długości cyklu wyrażony jest przez $2^{n},$ gdzie $n$ to liczba bitów przeznaczonych na przechowywanie stanu wewnętrznego. W praktyce, większość generatorów ma znacznie krótsze okresy.

Do wielu zastosowań, opisany powyżej rodzaj deterministycznej pseudolosowości jest w zupełności wystarczający. W grach komputerowych czy algorytmach probabilistycznych (takich jak np. całkowanie Monte Carlo) potrzebne jest jedynie źródło wartości o cechach przybliżonych do liczb prawdziwie losowych, chociaż jakość losowości może być decydująca dla dokładności obliczeń. Dlatego przy zastosowaniu każdego nowego generatora do celów obliczeń numerycznych należy sprawdzić jego własności statystyczne. W przypadku skorzystania z jednego z dobrze zbadanych generatorów można czasem bezpośrednio obliczyć długość cyklu, a pozostałe właściwości (jak np. równomierność rozkładu) są najczęściej znane. Można też skorzystać z jednego ze standardowych testów (test pokerowy, test serii itp). Generatory liczb pseudolosowych występują w niemal każdym hazardowym automacie do gier. Do tej pory powstały zaledwie dwa typy automatów, które nie zawierają generatora, tj. Futura i Futura Eclipse, gdzie rozgrywka nie zawiera elementu losowości.

Zastosowanie w kryptografii

Szczególną klasę PRNG stanowią generatory uznane za bezpieczne do zastosowań kryptograficznych. Kryptografia opiera się na generatorach liczb pseudolosowych przede wszystkim w celu tworzenia unikalnych kluczy stałych oraz sesyjnych. Ze względu na fakt, że bezpieczeństwo komunikacji zależy od jakości klucza, od implementacji PRNG stosowanych w takich celach oczekuje się między innymi, że:

• Generowane wartości będą każdorazowo praktycznie nieprzewidywalne dla osób postronnych (np. przez wykorzystanie odpowiednich źródeł danych przy tworzeniu ziarna).
• Nie będzie możliwe ustalenie ziarna lub stanu wewnętrznego generatora na podstawie obserwacji dowolnie długiego ciągu wygenerowanych bitów.
• Znajomość dowolnej liczby wcześniej wygenerowanych bitów nie będzie wystarczała, by odgadnąć dowolny przyszły bit z prawdopodobieństwem istotnie wyższym od ${\tfrac {1}{2}}.$
• Dla wszystkich możliwych wartości ziarna, zachowana będzie pewna minimalna, dopasowana do zastosowania długość cyklu PRNG (aby uniknąć ponownego wykorzystania takiego samego klucza).

Proste generatory

Uproszczony liniowy generator kongruencyjny (Linear Congruential Generator) określony jest następującym algorytmem ($a,$ $b,$ i $m$ to odpowiednio dobrane znane stałe):

stan początkowy to wartość ziarna

żeby wygenerować bit:

${\mbox{nowy stan}}=a\times {\mbox{stary stan}}+b\mod m$

${\mbox{wygenerowany bit}}={\mbox{nowy stan}}\mod 2$

Generator ten nie jest bezpieczny – dla pewnych kombinacji parametrów jest prawie losowy, dla innych bardzo szybko staje się okresowy. Dodatkowo, znane są ogólne metody obliczania parametrów i przewidywania zachowania takich PRNG na podstawie obserwacji wyników.

Generatory kryptograficzne

Do budowy PRNG na potrzeby kryptografii najczęściej używa się iteracyjnych wywołań kryptograficznie bezpiecznej funkcji haszującej typu MD5 lub SHA-1, albo stosuje się w podobny sposób sprawdzone szyfry strumieniowe lub blokowe. Aby zapewnić nieprzewidywalność wyników, do okresowej (re-)inicjalizacji takiego PRNG używa się trudne do przewidzenia zdarzenia zewnętrzne, takie jak interwały aktywności wejścia-wyjścia w systemie komputerowym, fluktuacje temperatury procesora lub płyty głównej, albo sygnał z dedykowanych, sprzętowych generatorów szumu uznawanego za prawdziwie niedeterministyczny.

Spośród używanych algorytmów zakwalifikowanych do tej kategorii, na wyróżnienie zasługuje Blum Blum Shub. Zostało wykazane, iż złamanie tego PRNG jest przynajmniej tak samo trudne jak zadanie faktoryzacji iloczynów dużych liczb pierwszych. Jest jednak mniej popularny ze względu na relatywnie niską wydajność w porównaniu z alternatywami.

Zobacz też

• generator liczb losowych
• losowość
• Mersenne Twister
• rejestr przesuwający z liniowym sprzężeniem zwrotnym

Linki zewnętrzne

• Tablica liczb przetasowanych czterocyfrowych Hugo Steinhausa wydana w 1954 roku (z Biblioteki Wirtualnej Nauki)
• How to Generate Pseudorandom Numbers, kanał PBS Infinite Series na YouTube, 13 października 2017 [dostęp 2024-08-29].