Generator Pseudolosowy (PRG)
Generatory pseudolosowe (ang. pseudorandom generators - PRG) służą do tworzenia losowych ciągów liczb w ściśle deterministycznych urządzeniach, jakimi są wszystkie komputery. Są stosowane w celu umożliwienia szyfrowania wielu bloków danych za pomocą rozszerzonych kluczy generowanych z sekretnych kluczy o niewielkiej ilości bitów.
G:{0,1}s -> {0,1}n
gdzie:
- n >> s
Generator pseudolosowy musi być nieprzewidywalny - nie może istnieć żaden wydajny algorytm, który otrzymawszy poprzednie bity wyjściowe z PRG mógłby przewidzieć kolejny wygenerowany bit z prawdopodobieństwem niezaniedbywalnie większym niż 0.5.
Generatory pseudolosowe są wykorzystywane do tworzenia funkcji i permutacji pseudolosowych, wykorzystywanych powszechnie w kryptografii (na przykład przy implementowaniu szyfrów blokowych).
Implementacja PRG
Obecnie, generatory pseudolosowe są implementowane w większości systemów operacyjnych (na przykład linuksowy /dev/random) i wielu bibliotekach dla różnych języków programowania. Zwykle ich idea działania jest podobna.
Algorytm najpierw inicjuje wewnętrzny stan generatora bazując na różnych informacjach zewnętrznych (na przykład na aktualnym czasie lub temperaturze). Następnie ten stan jest zmieniany przez cały czas działania generatora na podstawie innych zewnętrznych i losowych danych - częstotliwości i sposobu używania przez użytkownika klawiatury i myszki, wymiany pakietów sieciowych oraz wszelkich tego typu informacji, pochodzących spoza deterministycznego środowiska, w którym pracuje algorytm.
Algorytmy generatorów pseudolosowych przekształcają swój stan wewnętrzny i na tej podstawie zwracają ciągi liczb, które powinny być jak najbardziej losowe. Wszelkie przekształcenia i manipulacje liczbami są tak dobrane, aby jak najbardziej utrudnić analizowanie prawidłowości w zwracanych danych.
Jakość generowanych danych
Istnieje wiele standardów, które określają wymagania, jakie powinny być spełnione przez pseudolosowe generatory pseudolosowe. Przykładowo amerykańska organizacja National Institute of Standards and Technology jest autorem wielu norm, takich jak NIST SP 800-90 i pokrewne.
W celu oceny jakości działania generatorów pseudolosowych stosuje się testy statystyczne. Określają one czy produkowane ciągi liczb wyglądają na losowe i są nieprzewidywalne. Przykładowe testy statystyczne:
- ilość bitów ustawionych na 1 w produkowanym ciągu jest równa mniej więcej ilości bitów zerowych
- ilość par zerowych bitów (00) w produkowanym ciągu jest równa mniej więcej czwartej części wszystkich bitów
- długość najdłuższego ciągu zer lub jedynek jest podobna do prawdopodobnej długości oszacowanej matematycznie
