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, 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 – jeśli generator przyjmuje jako parametr wejściowy ziarno długości k bitów, to będzie w stanie wygenerować dane wyjściowe tylko na 2k sposobów. 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 2n, 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 |
[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ą w praktyce 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
. - 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:
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:
- void srand(unsigned seed) - ustawia argument seed jako ziarno
- int rand() - zwraca liczbę pseudolosową z zakresu pomiędzy 0 a RAND_MAX
