Liczba pseudolosowa: metody pozyskiwania, zalety i wady

Liczba pseudolosowa to specjalna liczba generowana przez specjalny generator. Generator liczb losowych (PRNG), znany również jako deterministyczny generator bitów losowych (DRBG), to algorytm generowania ciągu liczb, którego właściwości przybliżają cechy ciągów liczb losowych. Sekwencja generowana przez PRNG nie jest prawdziwie losowa, ponieważ jest w całości określona przez wartość początkową, zwaną liczbą początkową PRNG, która może zawierać prawdziwie losowe wartości. Chociaż sekwencje bliższe losowym mogą być generowane za pomocą sprzętowych generatorów liczb losowych, generatory liczb pseudolosowych są w praktyce ważne ze względu na szybkość generowania liczb i odtwarzalność.

Aplikacje

PRNG są kluczowe w takich zastosowaniach jak modelowanie (np. dla metod Monte Carlo), gry elektroniczne (np. dla generowania proceduralnego) i kryptografia. Zastosowania kryptograficzne wymagają, aby dane wyjściowe nie były przewidywalne na podstawie wcześniejszych informacji. Wymagane są bardziej złożone algorytmy, które nie dziedziczą liniowości prostych PRNG.

Wymagania i warunki

Dobre właściwości statystyczne są głównym wymogiem przy produkcji PRNG. Podsumowując, dokładna analiza matematyczna jest potrzebna, aby mieć pewność, że GCG generuje liczby, które są wystarczająco zbliżone do losowych, aby odpowiadać zamierzonemu użyciu.

John von Neumann ostrzegał przed błędnym interpretowaniem PRNG jako naprawdę losowych generatorów i żartował, że "każdy, kto rozważa arytmetyczne metody produkcji liczb losowych, jest z pewnością w stanie grzechu".

Korzystanie z

PRNG może być uruchomiony z dowolnego stanu początkowego. Zawsze będzie generować tę samą sekwencję, gdy zostanie zainicjowana z tym stanem. Okres PRNG definiuje się w następujący sposób: maksymalna w stosunku do wszystkich stanów początkowych długość niepowtarzającego się prefiksu sekwencji. Okres jest ograniczony przez liczbę stanów, zwykle mierzoną w bitach. Ponieważ długość okresu potencjalnie podwaja się z każdym dodanym bitem "stanu", łatwo jest stworzyć PRNG o okresach wystarczająco dużych dla wielu praktycznych zastosowań.

Jeśli stan wewnętrzny PRNG zawiera n bitów, to jego okres może być nie większy niż 2n wyników, jest znacznie krótszy. W przypadku niektórych PRNG czas trwania można obliczyć bez pomijania całego okresu. Rejestry przesuwne z liniowym sprzężeniem zwrotnym (LFSR) są zwykle wybierane tak, aby miały okresy równe 2n − 1.

Liniowe oscylatory kongruentne mają okresy, które można obliczyć przez faktoryzację. Chociaż PRNG będą powtarzać swoje wyniki po osiągnięciu końca okresu, powtarzający się wynik nie oznacza, że koniec okresu został osiągnięty, ponieważ stan wewnętrzny może być większy niż wyjście; jest to szczególnie widoczne w przypadku PRNG z wyjściem jednobitowym.

Możliwe błędy

Błędy wykrywane przez wadliwe PRNG obejmują zakres od niewidocznych (i nieznanych) do oczywistych. Przykładem jest algorytm liczb losowych RANDU, który był używany przez dziesięciolecia na komputerach mainframe. Była to poważna wada, ale jej niedoskonałość przez długi czas pozostawała niezauważona.

W wielu dziedzinach prace badawcze wykorzystujące losowy wybór, symulacje Monte Carlo lub inne metody oparte na PRNG są znacznie mniej wiarygodne niż mogłoby to wynikać z zastosowania PRNG niskiej jakości. Nawet dziś należy niekiedy zachować ostrożność, o czym świadczy ostrzeżenie zawarte w International Encyclopaedia of Statistical Science (2010).

Przykład udanego zastosowania

Jako ilustrację rozważmy szeroko stosowany język programowania Java. W 2017 roku Java nadal polega na liniowym generatorze kongruentnym (LCG) dla swojego PRNG.

Historia

Pierwszym PRNG, który uniknął poważnych problemów i nadal działał dość szybko, był Mersenne Twister (omówiony poniżej), który został opublikowany w 1998 roku. Od tego czasu opracowano inne wysokiej jakości PRNG.

Ale historia liczb pseudolosowych na tym się nie kończy. W drugiej połowie XX wieku do standardowej klasy algorytmów stosowanych w PRNG należały liniowe generatory kongruentne. Wiadomo było, że jakość LCG jest nieodpowiednia, ale lepsze metody nie były dostępne. Press i wsp. (2007) opisali ten wynik w następujący sposób: "Gdyby wszystkie prace naukowe, których wyniki były wątpliwe z powodu [LCG i pokrewnych] zniknęły z półek bibliotecznych, na każdej półce powstałaby luka wielkości twojej pięści".

Dużym postępem w dziedzinie generatorów pseudolosowych było wprowadzenie metod opartych na rekurencji liniowej w polu dwuelementowym; generatory takie związane są z liniowymi rejestrami przesuwnymi ze sprzężeniem zwrotnym. Służyły one jako podstawa Wynalazek generatorów liczb pseudolosowych.

W szczególności wynalazek Mersen Twister z 1997 roku pozwolił uniknąć wielu problemów z wcześniejszymi oscylatorami. Twister Mersenne ma okres 219937−1 iteracji (≈4,3 × 106001). Udowodniono, że jest ona równomiernie rozłożona w (do) 623 wymiarach (dla wartości 32-bitowych), a w momencie jej wprowadzenia była szybsza niż inne generatory oparte na statystyce, produkujące ciągi liczb pseudolosowych.

W 2003 roku George Marsaglia przedstawił rodzinę generatorów xorshift, również opartych na liniowym powtarzaniu. Takie generatory są niezwykle szybkie i - w połączeniu z nieliniowym działaniem - przechodzą rygorystyczne testy statystyczne.

W 2006 roku opracowano rodzinę generatorów WELL. Generatory WELL poprawiają w pewnym sensie jakość Twistera Mersenne`a, który ma zbyt dużą przestrzeń stanów i bardzo powolny powrót do niej, generując liczby pseudolosowe z dużą ilością zer.

Kryptografia

PRNG odpowiedni do zastosowań kryptograficznych jest nazywany kryptograficznie zabezpieczonym PRNG (CSPRNG). Wymogiem dla CSPRNG jest to, że atakujący, który nie zna liczby początkowej, ma tylko niewielką przewagę w odróżnianiu sekwencji wyjściowej generatora od sekwencji losowej. Innymi słowy, podczas gdy PRNG musi przejść tylko pewne testy statystyczne, CSPRNG musi przejść wszystkie testy statystyczne, które są ograniczone do czasu wielomianowego w rozmiarze nasion.

Chociaż udowodnienie tej właściwości wykracza poza obecny poziom teorii złożoności obliczeniowej, przekonujący dowód można dostarczyć, redukując CSPRNG do problemu, który jest uważany za złożony, podobny do faktoryzacji liczb całkowitych. Ogólnie rzecz biorąc, zanim algorytm będzie mógł otrzymać certyfikat CSPRNG, mogą minąć lata przeglądów.

Wykazano, że prawdopodobnie NSA wstawiła asymetrycznego backdoora do certyfikowanego przez NIST generatora liczb pseudolosowych Dual_EC_DRBG.

Algorytmy liczb pseudolosowych

Większość algorytmów PRNG produkuje sekwencje, które są równomiernie rozłożone przez dowolny z kilku testów. To jest pytanie otwarte. Jest to jedno z centralnych zagadnień w teorii i praktyce kryptografii: czy istnieje sposób na odróżnienie wyjścia wysokiej jakości PRNG od prawdziwie losowej sekwencji? W tym przypadku rozpoznawacz wie, że użyty został znany algorytm PRNG (ale nie stan, z jakim został zainicjowany) lub użyty został prawdziwie losowy algorytm. Musi rozróżnić.

Bezpieczeństwo większości algorytmów i protokołów kryptograficznych wykorzystujących PRNG opiera się na założeniu, że niemożliwe jest odróżnienie użycia odpowiedniego PRNG od użycia prawdziwie losowego ciągu. Najprostszym przykładem tej zależności są szyfry strumieniowe, których działanie polega najczęściej na wyeliminowaniu lub przesłaniu wiadomości plaintext z wyjściem PRNG, tworząc szyfrogram. Projektowanie kryptograficznie odpowiednich PRNG jest niezwykle trudne, ponieważ muszą one spełniać dodatkowe kryteria. Wielkość okresu jest ważnym czynnikiem w kryptograficznej przydatności PRNG, ale nie jedynym.

Wczesny komputerowy PRNG, zaproponowany przez Johna von Neumanna w 1946 roku, znany jest jako metoda średnich kwadratów. Algorytm jest następujący: weź dowolną liczbę, podnieś ją do kwadratu, usuń środkowe cyfry wynikowej liczby jako "liczbę losową", a następnie użyj tej liczby jako liczby początkowej dla następnej iteracji. Na przykład podniesienie do kwadratu liczby 1111 daje 1234321, co można zapisać jako 01234321, liczba 8-cyfrowa jest kwadratem liczby 4-cyfrowej. Daje to 2343 jako liczbę "losową. Wynik powtórzenia tej procedury to 4896 i tak dalej. Von Neumann używał 10-cyfrowych liczb, ale proces był taki sam.

Wady "średniego kwadratu"

Problem z metodą średniego kwadratu polega na tym, że wszystkie sekwencje w końcu się powtarzają, niektóre bardzo szybko, na przykład: 0000. Von Neumann wiedział o tym, ale uznał to podejście za wystarczające dla swoich celów i martwił się, że matematyczne "poprawki" po prostu ukryją błędy, a nie je usuną.

Von Neumann uważał sprzętowe generatory liczb losowych i pseudolosowych za nieodpowiednie: jeśli nie zapisują one wygenerowanego wyjścia, nie można ich później sprawdzić pod kątem błędów. Gdyby zapisywali swoje dane wyjściowe, wyczerpaliby ograniczoną dostępną pamięć komputera, a tym samym zdolność komputera do odczytu i zapisu liczb. Gdyby liczby były zapisane na kartkach, ich zapisanie i odczytanie zajęłoby znacznie więcej czasu. Zastosowany przez niego komputer ENIAC wykorzystywał metodę "mean square" i przeprowadzał proces uzyskiwania liczb pseudolosowych kilkaset razy szybciej niż odczytywanie liczb z kart dziurkowanych.

Metoda średnich kwadratów została od tego czasu zastąpiona przez bardziej złożone generatory.

Innowacyjna metoda

Ostatnią innowacją jest połączenie średniego kwadratu z sekwencją Weilla. Metoda ta zapewnia wysoką jakość produktu przez długi czas. Pomaga uzyskać lepsze wzory liczb pseudolosowych.