Generator liczb pseudolosowych

Z Wikipedii

Generator liczb pseudolosowych (Pseudo-Random Number Generator, lub PRNG) to 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 ewentualnie 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).

Spis treści

1 Zastosowanie w kryptografii
2 Proste generatory
3 Generatory kryptograficzne
4 Implementacja w C
- 4.1 Linki zewnętrzne

[edytuj] 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 seeda).
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 $\begin{matrix}\frac 1 2\end{matrix}$ .
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).

[edytuj] 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.

[edytuj] 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.

[edytuj] Implementacja w C

W bibliotece standardowej C zaimplementowane zostały dwie funkcje do obsługi generatora liczb pseudolosowych (nie nadają się do zastosowań kryptograficznych):