Jak można wykryć, że generator liczb nie jest tak naprawdę losowy?

Słyszałem, że generowanie liczb losowych w komputerach nie jest tak naprawdę losowe, ale nie ma wydajnego algorytmu do ich wykrycia. Jak można to w ogóle wykryć?

Komputery są naprawdę losowe:

Prawdziwa losowość jest niemożliwa dla maszyn Turinga w sensie teoretycznym, a większość komputerów nie jest w stanie wygenerować prawdziwie losowej mocy wyjściowej. Dlatego niektóre współczesne komputery zawierają sprzęt, który umożliwia komputerowi dostęp do zewnętrznego źródła, które, miejmy nadzieję, będzie zawierać pewną losowość. Jednym z przykładów tego, jak można to osiągnąć, jest śledzenie niewielkich wahań temperatury wewnątrz komputera. Losowość można również uzyskać ze źródła zewnętrznego. Ale z tonu twojego postu nie sądzę, że interesują Cię zewnętrzne źródła losowości.

Posiew:

Bez zewnętrznego dodatku wszystko, co robi komputer, jest deterministyczne. Prowadzi to do poważnego problemu: jeśli wywołasz program do generowania liczb losowych, da ci ten sam wynik za każdym razem, jeśli podasz mu to samo wejście. Oczywiście potrzebujemy programu, który generuje losową liczbę, aby zmieniał swoje zachowanie przy każdym uruchomieniu (w przeciwnym razie otrzymamy ten sam „losowy” numer, co nie jest szczególnie pomocne). Jednym z pomysłów jest przekazanie programowi danych wejściowych, które zmieniają się za każdym razem, gdy program jest uruchamiany, tak aby wyświetlała się inna liczba. Nazywamy to wejście „ziarnem”. Generator liczb losowych musi pobrać ziarno, wykonać pewne operacje i podać nam liczbę losową.

Obecny czas systemowy jest klasycznym przykładem zarodka. Daje to długi ciąg z wysoką entropią, a jeśli czas jest śledzony w wystarczająco szczegółowy sposób (tj. Jeśli zegar systemowy używa godzin, wtedy „czas” jest dość słabym ziarnem), prawdopodobnie nie podasz liczby pseudolosowej generator dwa razy ten sam numer.

Algorytmy, które są wystarczająco losowe:

Teraz mamy algorytm, który przynajmniej w jakiś sposób może być inny przy każdym uruchomieniu. Dajemy mu ziarno, a podczas gdy algorytm podaje tę samą liczbę, gdy pojawi się monit z tym samym ziarnem, chcemy, aby generowane przez niego liczby były losowe. Działa to podobnie do powyższego - pobierasz jakieś dane wejściowe i wytwarza ono (na szczęście inne niż dane wejściowe, aby były „losowe”).

Powiedzmy teraz, że wymyśliłeś własny algorytm, aby to zrobić, i twierdzisz, że liczby, które wymyśliłeś, są dość losowe, gdy dałeś mu kilka różnych nasion. Jak sprawdzilibyśmy, jak dobrze?

Teraz chcemy algorytmu, który pobierze ziarno, wykona pewne operacje i wygeneruje liczbę losową. Najprościej mówiąc, algorytm mógłby po prostu wyprowadzić ziarno - nie daje nam tej samej liczby za każdym razem, a losowe nasiona dają nam losowe wyniki. Ale najwyraźniej nie tego chcemy. Z drugiej strony algorytm może być dość skomplikowany, podobnie jak wiele rzeczywistych generatorów pseudolosowych. Jak możemy stwierdzić, które algorytmy dają nam „losowe” liczby z naszych niekoniecznie losowych nasion? Jeśli nie możemy tego dokładnie zrozumieć, w jaki sposób możemy stwierdzić, które są najlepsze?

$1$$n$

Losowo wystarczy, aby oszukać atakującego:

Teraz możesz mieć na myśli kryptograficznie bezpieczne generatory pseudolosowe. Myślę, że najlepszym sposobem na wyjaśnienie tego jest powyższy kontekst - tutaj wykorzystujemy naszą przypadkowość do kryptografii, więc kiedy projektujemy testy, tak naprawdę zależy nam na tym, aby ktoś nie był w stanie się złamać nasze bezpieczeństwo poprzez przewidywanie, jaką losową liczbę wybraliśmy. Nie znam twojego poziomu znajomości kryptografii, ale wyobraź sobie, że robimy prosty zamienny szyfr - każda litera jest zastępowana inną literą. Chcemy wybierać te zamienniki losowo, więc są trudne do odgadnięcia przez atakującego. Ale jeśli zdoła zrozumieć, jak działa mój generator liczb losowych, będzie w stanie rozwiązać cały szyfr! Dlatego algorytmy kryptograficzne wymagają generatorów liczb losowych, które są szczególnie trudne do odgadnięcia.

Z tego powodu CSPRG są zdefiniowane pod kątem tego, jak dobrze inne algorytmy je rozwiązują (w tym miejscu ostatecznie dochodzimy do twojego pytania). Mówiąc konkretnie, powiedzmy, że mam CSPRG, który nazywam R. R jest CSPRG wtedy i tylko wtedy, gdy NIE ma żadnego możliwego algorytmu, który mógłby zgadnąć, który bit wyśle ​​później. Jest to prawdą, nawet jeśli znasz wszystkie poprzednie bity, które wyprowadza!

Powiedzmy, że pierwsze pięć bitów, które ma mój CSPRG, to 10100. Nie znasz danych wejściowych, których użyłem do programu, ale masz dostęp do kodu, którego użyłem do napisania mojego CSPRG. Zatem twierdzenie jest takie, że nie można napisać programu, który zdecyduje, czy następny bit będzie wyjściowy 101000 czy 101001.

Tak więc ze względu na kryptografię czasami określane jest, jak dobrze generator liczb pseudolosowych działa pod względem przewidywalności dla innych programów. Zauważ, że nadal daje to wiele intuicji „losowości”, ponieważ (powiedzmy), jeśli wiesz, że wszystkie losowe dane wyjściowe będą nieparzyste, nie jest to kryptograficznie bezpieczne ani nie przechodzi zdrowego testu losowości.

Niedawno znalazłem fajny post o losowości w obliczeniach na blogu MIT CSAIL Theory of Computation Group: Czy możesz powiedzieć, czy coś jest losowe?

Wpis zaczyna się od kilku pomysłów zaczerpniętych ze wspaniałego przemówienia Avi Wigdersona na temat mocy i ograniczeń przypadkowości w obliczeniach, badania pięknego obszaru zrandomizowanych algorytmów oraz zaskakującego związku między pseudolosowością a trudnością obliczeniową .

Następnie podsumowuje niektóre ostatnie wyniki dotyczące kryptografii kwantowej; w szczególności sposób skutecznego testowania, czy dane wyjściowe określonego rodzaju urządzenia są naprawdę losowe (protokoły ekspansji losowości).

Na przykład zobacz najnowsze dzieło Umesh Vazirani, Thomas Vidick, Certyfikowane kości kwantowe (Lub, testowalne wykładnicze zwiększenie losowości)

Streszczenie: Wprowadzamy protokół, za pomocą którego można zastosować parę urządzeń mechaniki kwantowej do wygenerowania n bitów prawdziwej losowości z zarodka bitów jednolitych O (log n). Wygenerowane bity są certyfikowane losowo w oparciu o prosty test statystyczny, który może wykonać użytkownik, i przy założeniu, że urządzenia przestrzegają zasady braku sygnalizacji. Żadne inne założenia nie są oparte na wewnętrznym działaniu urządzeń ....

Zakładając, że mówisz o statystycznej losowości - kryptografia ma inne potrzeby! - istnieje cały szereg testów dopasowania , które mogą wykryć, czy sekwencja liczb pasuje do danego rozkładu. Możesz ich użyć do sprawdzenia, czy generator (pseudo) liczb losowych jest prawidłowy (do jakości testu i wybranego znaczenia).

Zestawy testowe Diehard łączą różne metody.

Jest to obszerny / złożony temat w informatyce, na który niektórzy odpowiedzią SamM. Wydaje się, że twoje konkretne pytanie dotyczy tego, czy komputery mają tak zwane PRNG , czyli generatory liczb pseudolosowych, jak to wykryć?

Krótka odpowiedź jest taka, że ​​nietrywialne PRNG są zbudowane tak, że ich algorytmy nie mogą zostać wykryte (wyprowadzone). Ogólnie rzecz biorąc, jeśli PRNG jest nazywane „bezpiecznym”, nawet jeśli atakujący zna algorytm generujący sekwencję pseudolosową, nie może odgadnąć konkretnych parametrów użytych do wygenerowania sekwencji. W ten sposób pseudolosowość ma wiele głębokich powiązań z kryptografią i można mówić o „złamaniu” PRNG w taki sam sposób, w jaki algorytm kryptograficzny można „złamać”. Istnieje wiele prac naukowych w tej dziedzinie, która jest aktywnym obszarem na czele kryptografii.

W przypadku „trywialnych” PRNG, np. Powiedzmy liniowy generator kongruencjalny , jeśli atakujący zna algorytm użyty do jego wygenerowania i nie jest generowany za pomocą „bignum” , przestrzeń wyszukiwania jest „stosunkowo niewielka”, a atakujący teoretycznie może również znaleźć parametry używane przez poszczególne PRNG w zasadzie przez brutalną siłę i wypróbowanie wszystkich kombinacji.

PRNG mogą zostać w praktyce rozbite (ponownie w zależności od ich „bezpieczeństwa”) w niektórych przypadkach poprzez uruchomienie przeciwko nim dużego zestawu statystycznych testów losowości. np. takie jest uzasadnienie programu „Dieharder” (autorstwa Browna). Istnieje również pakiet NIST .

Wewnętrzna trudność / twardość pękania PRNG nie jest jeszcze ściśle teoretycznie udowodniona, ale jest zasadniczo związana z tak zwanymi „zapadniami” lub „funkcjami jednokierunkowymi”, które można obliczać skutecznie w jednym kierunku, ale „trudno” je odwrócić (odwrócić) . Istnieją pewne otwarte problemy w kryptografii dotyczące twardości losowości. Pytania te ściśle wiążą się z rozdziałami klas złożoności, np. Znanym pytaniem P =? NP.

Pytania na temat łamania PRNG dotyczą również złożoności Kołmogorowa , dziedziny, która bada najmniejsze Maszyny Turinga, które mogą generować sekwencje. złamanie PRNG również ściśle wiąże się ze znalezieniem „najkrótszego” programu do obliczenia sekwencji pseudolosowej. Złożoności Kołmogorowa nie można w ogóle obliczyć.

Jak zauważa Gilles w komentarzu, istnieją sprzętowe RNG zbudowane z fizycznych procesów elektronicznych, takich jak związane z szumem kwantowym. jeśli są odpowiednio zaprojektowane, są nie do złamania.

W rzeczywistości wszystko, co robi klasyczny komputer, jest deterministyczne, w tym sensie, że gdy powierza się im pewne zadania, podąża za nimi w sposób deterministyczny. Dlatego jeśli chcesz mieć jedną liczbę losową, możesz ją obliczyć odpowiednio do czasu (na podstawie czasu wejściowego użytkownika), ale jeśli chcesz mieć zestaw liczb losowych, nie możesz użyć czasu dla kolejnych liczb, ponieważ liczby nie będą już niezależne.

Ludzie używają pseudolosowych generatorów, które mają ziarno, tj. Liczby, która jest używana do obliczania wszystkich liczb generatora liczb pseudolosowych (w bardziej wyrafinowanych przypadkach symulacji lub innych zadań może być potrzebnych więcej nasion , jeśli potrzebny jest więcej niż jeden zestaw niezależnie losowych liczb). Ziarno ma zwykle wartość 0 lub określoną liczbę, jeśli chcesz odtwarzalnych wyników, lub czas, jeśli Ty i inne wyniki niemożliwe do odtworzenia.

Fakt, że generatory liczb pseudolosowych są wystarczająco dobre, polega na tym, że podążają one za „podstawowymi cechami generowania liczb pseudolosowych”, aby można je było skutecznie obliczać i zachowywać się jak prawdziwe liczby losowe:

• wyprodukowane liczby muszą być zgodne z rozkładem jednolitym (z tego rozkładu można osiągnąć dowolny inny rozkład);
• wyprodukowane liczby muszą być statystycznie niezależne;
• sekwencja jest odtwarzalna (ten punkt jest narzucony ze względu na tę właściwość sprzętu klasycznego komputera i dlatego nazywane są „liczbami pseudolosowymi”);
• okres sekwencji musi być wystarczająco duży;
• generowanie liczb musi być szybkie.

Z każdej liczby sekwencji liczb pseudolosowych obliczana jest nowa liczba (zwykle pracujemy z liczbami całkowitymi). Istnieje jednak okres n w sekwencji generatorów liczb pseudolosowych przygotowanych do pracy w określonej bazie ze skończoną liczbą dostępnych bitów w celu wyrażenia liczb (np. Binarnych). Jeśli to n nie byłoby wystarczająco duże, pojawiałyby się poważne problemy, ale nie martw się, informatycy dobrze wybierają nasiona i inne parametry pseudolosowych generatorów, aby mieć dobre n.

Na przykład możliwy generator liczb pseudolosowych z liniową zbieżną metodą, który jest jednym z najstarszych i najlepiej znanych algorytmów generowania liczb pseudolosowych, można zdefiniować odpowiednio:

ma cztery wartości:
- x_0 ≥ 0
- a ≥ 0
- c ≥ 0
- m> x_0, gdzie:

x0 jest wartością początkową, a, c i m są stałymi, gdzie: m> a, m> c, i tworzy sekwencję z fornulą:

x_ {i + 1} = (a * x_i + c) MOD m

Wartości tych stałych muszą być starannie wybrane. Jedną z możliwości jest:

x_ {i + 1} = (1664525 * x_i + 1013904223) MOD 2 ^ 32, sygn. [1-2]

Istnieją inne algorytmy bardziej wyrafinowane do generowania liczb losowych, które pozwalają uniknąć niektórych problemów z poprzednich algorytmów, w tym: [3]

• krótsze niż oczekiwane okresy dla niektórych stanów początkowych (takie stany początkowe można w tym kontekście nazwać „słabymi”);
• brak jednolitości rozkładu dla dużych ilości generowanych liczb;
• korelacja kolejnych wartości;
• zły rozkład wymiarowy sekwencji wyjściowej;
• odległości między miejscami, w których występują pewne wartości, są rozkładane inaczej niż w losowym rozkładzie sekwencji.

W przyszłości klasyczne komputery mogą zostać połączone z systemami kwantowymi, które mogą dostarczać naprawdę losowe liczby i dostarczać je. [4]

odniesienia:
[1] http://en.wikipedia.org/wiki/linear_congruential_generator
[2] William H. i in. (1992). „Receptury numeryczne w fortran 77: Sztuka obliczeń naukowych” (wyd. 2). ISBN 0-521-43064-X.
[3] http://en.wikipedia.org/wiki/pseudorandom_number_generator
[4] http://www.technologyreview.com/view/418445/first-evidence-that-quantum-processes-generate-truly-random-numbers /