Czym różnią się liczby pseudolosowe i prawdziwie losowe i dlaczego to ma znaczenie?


665

Nigdy tego nie rozumiem. Powiedzmy, że piszesz mały program w dowolnym języku, który rzuca kostką (używając tylko kości jako przykładu). Po 600 000 rzutach każda liczba zostałaby wyrzucona około 100 000 razy, czego się spodziewałbym.

Dlaczego istnieją strony internetowe poświęcone „prawdziwej przypadkowości”? Z pewnością, biorąc pod uwagę powyższą obserwację, szanse na uzyskanie dowolnej liczby wynoszą prawie dokładnie 1 w stosunku do liczby liczb, jakie może wybrać.

Próbowałem w Pythonie : Oto wynik 60 milionów rolek. Najwyższa zmienność wynosi 0,15. Czy to nie jest tak losowe, jak to się stanie?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0


21
Co rozumiesz przez „rzucić kostką”? Czy ma przymocowane ramię robota i kamerę?
starblue

3
choć zgadzam się z ogólną treścią twojego tonu, że często martwimy się o to zbyt mocno, ale zostało to wykorzystane w prawdziwym życiu: en.wikipedia.org/wiki/Ronald_Dale_Harris
Grady Player

3
Zobacz ten artykuł na temat pokera online, w którym brakuje prawdziwej przypadkowości, dlaczego jest to ważne.
Varaquilex

1
Jeśli po prostu utrzymasz licznik 0-5 i rzucisz kostką odpowiednio, 666 gorylów razy, dostaniesz równy rozkład.
jcora

Odpowiedzi:


1387

Zagrajmy w pokera komputerowego, tylko ty, ja i serwer, któremu obaj ufamy. Serwer używa generatora liczb pseudolosowych, który jest inicjowany 32-bitowym ziarnem tuż przed rozpoczęciem gry. Istnieje więc około czterech miliardów możliwych talii.

Mam w ręce pięć kart - najwyraźniej nie gramy w Texas Hold 'Em. Załóżmy, że karty są rozdawane jedna dla mnie, jedna dla ciebie, jedna dla mnie, jedna dla ciebie i tak dalej. Mam więc pierwszą, trzecią, piątą, siódmą i dziewiątą kartę w talii.

Wcześniej uruchomiłem pseudolosowy generator liczb cztery miliardy razy, raz z każdym ziarnem i zapisałem pierwszą wygenerowaną kartę dla każdego z nich w bazie danych. Załóżmy, że moją pierwszą kartą jest królowa pik. To pokazuje tylko jedną jako pierwszą kartę w jednej na 52 możliwych talii, więc zmniejszyliśmy możliwe talie z czterech miliardów do około 80 milionów.

Załóżmy, że moją drugą kartą jest trójka kier. Teraz uruchamiam moje RNG 80 milionów razy więcej, używając 80 milionów nasion, które produkują królową pik jako pierwszą liczbę. Zajmuje mi to kilka sekund. Zapisuję wszystkie talie, które wytwarzają trójkę, jako trzecią kartę - drugą kartę w mojej ręce. To znowu tylko około 2% talii, więc teraz mamy do 2 milionów talii.

Załóżmy, że trzecia karta w mojej ręce to 7 trefl. Mam bazę danych 2 milionów nasion, które rozdają moje dwie karty; Uruchomiłem mój RNG kolejne 2 miliony razy, aby znaleźć 2% talii, które produkują 7 trefl jako trzecią kartę, a my mamy tylko 40 tysięcy talii.

Widzisz jak to idzie. Uruchomiłem mój RNG 40000 razy więcej, aby znaleźć wszystkie nasiona, które produkują moją czwartą kartę, i to prowadzi nas do 800 talii, a następnie uruchamiam go 800 razy więcej, aby uzyskać ~ 20 nasion, które produkują moją piątą kartę, a teraz po prostu wygeneruj te dwadzieścia talii kart i wiem, że masz jedną z dwudziestu możliwych rąk. Co więcej, mam bardzo dobry pomysł na to, co narysuję.

Czy rozumiesz teraz, dlaczego prawdziwa losowość jest ważna? Sposób, w jaki go opisujesz, wydaje ci się, że dystrybucja jest ważna, ale dystrybucja nie jest tym, co czyni proces losowym. Nieprzewidywalność sprawia, że ​​proces jest losowy.

AKTUALIZACJA

Na podstawie komentarzy (obecnie usuniętych ze względu na ich niekonstruktywny charakter) co najmniej 0,3% osób, które to przeczytały, jest zdezorientowanych co do mojego punktu widzenia. Kiedy ludzie spierają się z punktami, których nie uczyniłem, lub gorzej, argumentują za punktami, które zrobiłem przy założeniu, że ich nie uczyniłem, wtedy wiem, że muszę wyjaśnić jaśniej i dokładniej.

Wydaje się, że istnieje szczególny zamęt w dystrybucji słów, dlatego chcę ostrożnie przywoływać wyrażenia .

Dostępne pytania to:

  • Czym różnią się liczby pseudolosowe i liczby prawdziwie losowe?
  • Dlaczego różnica jest ważna?
  • Czy różnice mają coś wspólnego z rozkładem produkcji PRNG?

Zacznijmy od rozważenia idealnego sposobu na wygenerowanie losowej talii kart do gry w pokera. Następnie zobaczymy, jak inne techniki generowania talii są różne i czy można skorzystać z tej różnicy.

Zacznijmy od założenia, że ​​mamy oznakowane magiczne pudełko TRNG. Jako jego dane wejściowe podajemy mu liczbę całkowitą n większą lub równą jeden, a jako wynik daje nam prawdziwie losową liczbę od jednego do n włącznie. Dane wyjściowe pola są całkowicie nieprzewidywalne (jeśli podano liczbę inną niż jeden), a dowolna liczba między jednym i n jest równie prawdopodobna jak inna; to znaczy, że rozkład jest jednolity . (Istnieją inne bardziej zaawansowane statystyczne kontrole losowości, które moglibyśmy przeprowadzić; ignoruję ten punkt, ponieważ nie ma to związku z moim argumentem. TRNG jest z założenia statystycznie losowy).

Zaczynamy od tasowanej talii kart. Prosimy o podanie numeru od jednego do 52 - to znaczy TRNG(52),. Bez względu na liczbę, którą oddaje, odliczamy tyle kart z naszej posortowanej talii i usuwamy tę kartę. Staje się pierwszą kartą w tasowanej talii. Następnie pytamy TRNG(51)i robimy to samo, aby wybrać drugą kartę i tak dalej.

Innym sposobem na to jest: jest ich 52! = 52 x 51 x 50 ... x 2 x 1 możliwe talie, czyli około 2226 . Jeden z nich wybraliśmy przypadkowo.

Teraz rozdajemy karty. Kiedy patrzę na moje karty, nie mam pojęcia, jakie masz karty. (Poza oczywistym faktem, że nie masz żadnej z moich kart). Mogą to być dowolne karty, z jednakowym prawdopodobieństwem.

Pozwólcie więc, że wyjaśnię to jasno. Mamy jednolity rozkład każdej indywidualnej produkcji TRNG(n); każdy wybiera liczbę od 1 do n z prawdopodobieństwem 1 / n. Rezultatem tego procesu jest to, że wybraliśmy jedną z 52! możliwe talie z prawdopodobieństwem 1/52 !, więc rozkład w zestawie możliwych talii jest również jednolity.

W porządku.

Załóżmy teraz, że mamy mniej magiczne pudełko, oznaczone PRNG. Zanim będzie można go użyć, musi zostać zaszczepiony 32-bitową liczbą bez znaku.

NA BOK: Dlaczego 32 ? Czy nie można go obsadzić liczbą 64-, 256- lub 10000-bitową? Pewnie. Ale (1) w praktyce większość gotowych PRNG jest obsadzonych liczbą 32-bitową, i (2) jeśli masz 10000 bitów losowości, aby zrobić ziarno, to dlaczego w ogóle używasz PRNG? Masz już źródło 10000 bitów losowości!

W każdym razie wróć do tego, jak działa PRNG: po jego zaszczepieniu możesz go używać w taki sam sposób, jak używasz TRNG. Oznacza to, że przekazujesz mu liczbę n, a ona zwraca liczbę od 1 do n włącznie. Ponadto rozkład tej produkcji jest mniej więcej równomierny . Oznacza to, że kiedy poprosimy PRNGo liczbę od 1 do 6, otrzymamy 1, 2, 3, 4, 5 lub 6, każdy mniej więcej jedną szóstą czasu, bez względu na to, jakie było ziarno.

Chciałbym podkreślić tę kwestię kilka razy, ponieważ wydaje się, że to ona dezorientuje niektórych komentujących. Dystrybucja PRNG jest jednolita na co najmniej dwa sposoby. Po pierwsze, załóżmy, że wybieramy jakieś konkretne nasienie. Spodziewalibyśmy się, że sekwencja PRNG(6), PRNG(6), PRNG(6)...milion razy dałaby jednolity rozkład liczb między 1 a 6. Po drugie, gdybyśmy wybrali milion różnych nasion i wzywali PRNG(6) jeden raz dla każdego ziarenka, znowu oczekiwalibyśmy jednolitego rozkładu liczb od 1 do 6. Jednorodność PRNG we wszystkich tych operacjach nie ma związku z atakiem, który opisuję .

Mówi się, że proces ten jest pseudolosowy, ponieważ zachowanie pudełka jest w pełni deterministyczne; wybiera jedno z 2 32 możliwych zachowań w oparciu o ziarno. Oznacza to, że po zaszczepieniu PRNG(6), PRNG(6), PRNG(6), ... tworzy sekwencję liczb o jednolitym rozkładzie, ale ta sekwencja jest całkowicie determinowana przez ziarno. Dla danej sekwencji wywołań, powiedzmy PRNG (52), PRNG (51) ... i tak dalej, istnieją tylko 2 32 możliwe sekwencje. Ziarno zasadniczo wybiera, które otrzymamy.

Aby wygenerować talię, serwer generuje teraz ziarno. (Jak? Będziemy wracać do tego punktu). Następnie nazywają PRNG(52), PRNG(51)i tak dalej, aby wygenerować talię, podobnie jak przedtem.

Ten system jest podatny na opisany przeze mnie atak. Aby zaatakować serwer, najpierw z góry zapełniamy własną kopię pudełka wartością 0 oraz pytamy o to PRNG(52)i zapisujemy. Następnie ponownie inicjujemy z 1, pytamy PRNG(52)i zapisujemy to, aż do 2 32 -1.

Teraz serwer pokera, który używa PRNG do generowania talii, musi jakoś wygenerować ziarno. Nie ma znaczenia, jak to robią. Mogą zadzwonić, TRNG(2^32)aby uzyskać naprawdę losowe ziarno. Lub mogą potraktować ten czas jako zalążek, który wcale nie jest przypadkowy; Wiem, która godzina to tyle co ty. Chodzi mi o to, że to nie ma znaczenia, bo mam swoją bazę danych . Kiedy widzę swoją pierwszą kartę, mogę wyeliminować 98% możliwych nasion. Kiedy widzę moją drugą kartę, mogę wyeliminować 98% więcej i tak dalej, aż w końcu mogę przejść do garści możliwych nasion i z dużym prawdopodobieństwem wiedzieć, co masz na ręce.

Teraz jeszcze raz chcę podkreślić, że założenie tutaj jest takie, że gdybyśmy zadzwonili PRNG(6)milion razy, otrzymalibyśmy każdą liczbę mniej więcej jedną szóstą czasu . Ten rozkład jest (mniej więcej) jednolity , a jeśli jednolitość tego rozkładu jest wszystkim, na czym ci zależy , to dobrze. Chodziło o to, czy istnieją inne rzeczy niż to, na PRNG(6)czym nam zależy? a odpowiedź brzmi tak . Dbamy również o nieprzewidywalność .

Innym sposobem spojrzenia na problem jest to, że chociaż dystrybucja miliona połączeń PRNG(6)może być w porządku, ponieważ PRNG wybiera tylko 2 32 możliwe zachowania, nie może wygenerować każdej możliwej talii. Może wygenerować tylko 2 32 z 2 226 możliwych talii; mały ułamek. Więc rozkład w zestawie wszystkich talii jest bardzo zły. Ale znowu, podstawowy atak tutaj polega na tym, że jesteśmy w stanie z powodzeniem przewidzieć przeszłe i przyszłe zachowanie na PRNGpodstawie niewielkiej próbki jego wyników.

Powiem to po raz trzeci lub cztery, aby upewnić się, że to się zatopi. Istnieją tutaj trzy dystrybucje. Po pierwsze, rozkład procesu, który generuje losowe 32-bitowe ziarno. Może to być całkowicie losowe, nieprzewidywalne i jednolite, a atak nadal będzie działał . Po drugie, dystrybucja miliona połączeń do PRNG(6). To może być idealnie jednolite, a atak nadal będzie działał. Po trzecie, rozkład talii wybrany przez pseudolosowy proces, który opisałem. Ten rozkład jest wyjątkowo słaby; tylko niewielka część możliwych talii IRL może być wybrana. Atak zależy od przewidywalności zachowania PRNG na podstawie częściowej wiedzy o jego wyniku .

POMOC: Ten atak wymaga, aby osoba atakująca wiedziała lub była w stanie odgadnąć, jaki jest dokładny algorytm używany przez PRNG. Czy jest to realistyczne, czy nie, pytanie jest otwarte. Jednak projektując system bezpieczeństwa, musisz zaprojektować go tak, aby był zabezpieczony przed atakami, nawet jeśli osoba atakująca zna wszystkie algorytmy w programie . Mówiąc inaczej: część systemu bezpieczeństwa, która musi pozostać tajna, aby system był bezpieczny, nazywa się „kluczem”. Jeśli twój system zależy od bezpieczeństwa od algorytmów, których używasz, będąc tajemnicą, twój klucz zawiera te algorytmy . To jest wyjątkowo słaba pozycja!

Iść dalej.

Załóżmy teraz, że mamy oznaczone trzecie magiczne pudełko CPRNG. Jest to wersja krypto-siły PRNG. Zajmuje 256-bitowe ziarno, a nie 32-bitowe ziarno. Dzieli się z PRNGwłaściwością, którą ziarno wybiera z jednego z 2 256 możliwych zachowań. I podobnie jak nasze inne maszyny, ma tę właściwość, że duża liczba wywołań CPRNG(n)zapewnia jednolity rozkład wyników między 1 in: każde zdarza się 1 / n czasu. Czy możemy skierować przeciwko temu nasz atak?

Nasz oryginalny atak wymaga od nas przechowywania 2 32 mapowań od nasion do PRNG(52). Ale 2 256 to znacznie większa liczba; uruchamianie CPRNG(52)tak wiele razy i zapisywanie wyników jest całkowicie niemożliwe .

Ale przypuśćmy, że istnieje inny sposób, aby wziąć wartość CPRNG(52)i na tej podstawie wydedukować fakt o nasieniu? Do tej pory byliśmy dość głupi, po prostu brutalnie zmuszając wszystkie możliwe kombinacje. Czy możemy zajrzeć do magicznego pudełka, dowiedzieć się, jak to działa i wydedukować fakty na temat nasion na podstawie wyników?

Nie. Szczegóły są zbyt skomplikowane, aby je wyjaśnić, ale CPRNG są sprytnie zaprojektowane, dlatego nie można wydedukować żadnego przydatnego faktu na temat nasion z pierwszego wyjścia CPRNG(52)lub z dowolnego podzbioru wyjścia, bez względu na to, jak duże .

OK, więc załóżmy teraz, że serwer używa CPRNGdo generowania talii. Potrzebuje 256-bitowego ziarna. Jak wybiera to ziarno? Jeśli wybierze jakąkolwiek wartość, którą atakujący może przewidzieć, nagle atak znów stanie się realny . Jeśli uda nam się ustalić, że z 2 256 możliwych nasion, tylko cztery miliardy z nich zostaną wybrane przez serwer, to wrócimy do pracy . Możemy ponownie przeprowadzić ten atak, zwracając uwagę tylko na niewielką liczbę nasion, które mogą zostać wygenerowane.

Serwer powinien zatem działać, aby zapewnić równomierną dystrybucję liczby 256-bitowej - to znaczy, że każdy możliwy seed jest wybierany z prawdopodobieństwem 1/2 256 . Zasadniczo serwer powinien dzwonić, TRNG(2^256)-1aby wygenerować ziarno CPRNG.

Co jeśli mogę zhakować serwer i zajrzeć do niego, aby zobaczyć, który materiał źródłowy został wybrany? W takim przypadku osoba atakująca zna całą przeszłość i przyszłość CPRNG . Autor serwera musi się wystrzegać przed tym atakiem! (Oczywiście, że jeśli uda mi się przeprowadzić ten atak, prawdopodobnie będę mógł po prostu przelać pieniądze bezpośrednio na moje konto bankowe, więc może to nie jest takie interesujące. Chodzi o to, że ziarno musi być trudnym do odgadnięcia sekretem i naprawdę losowa liczba 256-bitowa jest cholernie trudna do odgadnięcia.)

Wracając do mojego wcześniejszego punktu dotyczącego dogłębnej obrony: 256-bitowe ziarno jest kluczem do tego systemu bezpieczeństwa. Idea CPRNG polega na tym, że system jest bezpieczny, dopóki klucz jest bezpieczny ; nawet jeśli każdy inny fakt na temat algorytmu jest znany, tak długo, jak możesz zachować klucz w tajemnicy, karty przeciwnika są nieprzewidywalne.

OK, więc ziarno powinno być zarówno tajne, jak i równomiernie rozmieszczone, ponieważ jeśli nie, możemy przeprowadzić atak. Zakładamy, że rozkład produkcji CPRNG(n)jest jednolity. Co z rozkładem w zestawie wszystkich możliwych talii?

Można powiedzieć: CPRNG ma do dyspozycji 2 256 możliwych sekwencji, ale są tylko 2 226 możliwych talii. Dlatego jest więcej możliwych sekwencji niż talie, więc nic nam nie jest; każda możliwa talia IRL jest teraz (z dużym prawdopodobieństwem) możliwa w tym systemie. To dobry argument, z wyjątkiem ...

2 226 to tylko przybliżenie 52 !. Podziel to. 2 256/52 ! nie może być liczbą całkowitą, ponieważ z jednej strony 52! jest podzielny przez 3, ale nie ma potęgi dwóch! Ponieważ nie jest to teraz liczba całkowita, mamy sytuację, w której wszystkie talie są możliwe , ale niektóre talie są bardziej prawdopodobne niż inne .

Jeśli nie jest to jasne, rozważ sytuację z mniejszymi liczbami. Załóżmy, że mamy trzy karty, A, B i C. Załóżmy, że używamy PRNG z 8-bitowym ziarnem, więc istnieje 256 możliwych nasion. Istnieje 256 możliwych wyników PRNG(3)zależnych od nasion; nie ma możliwości, aby jedna trzecia z nich była A, jedna trzecia z nich była B, a jedna trzecia z nich była C, ponieważ 256 nie jest równomiernie podzielne przez 3. Musi być niewielki błąd względem jednego z nich.

Podobnie 52 nie dzieli się równomiernie na 2 256 , więc niektóre karty muszą mieć pewne odchylenie jako pierwsza wybrana karta, a odchylenie od innych.

W naszym oryginalnym systemie z 32-bitowym ziarnem nastąpiło ogromne odchylenie i ogromna większość możliwych talii nigdy nie została wyprodukowana. W tym systemie można wyprodukować wszystkie talie, ale ich rozkład jest nadal wadliwy . Niektóre pokłady są bardzo nieznacznie bardziej prawdopodobne niż inne.

Teraz pytanie brzmi: czy mamy atak oparty na tej usterce? a odpowiedź jest w praktyce, prawdopodobnie nie . CPRNG są zaprojektowane w taki sposób, że jeśli ziarno jest naprawdę losowe, wówczas obliczenie różnicy między CPRNGi jest niewykonalne obliczeniowo TRNG.

OK, podsumujmy.

Czym różnią się liczby pseudolosowe i liczby prawdziwie losowe?

Różnią się poziomem przewidywalności, którą wykazują.

  • Prawdziwie losowe liczby nie są przewidywalne.
  • Wszystkie liczby pseudolosowe są przewidywalne, jeśli ziarno można określić lub zgadnąć.

Dlaczego różnica jest ważna?

Ponieważ istnieją aplikacje, w których bezpieczeństwo systemu zależy od nieprzewidywalności .

  • Jeśli do wybrania każdej karty zostanie użyty TRNG, wówczas system będzie niedostępny.
  • Jeśli do wybrania każdej karty zostanie użyty CPRNG, system jest bezpieczny, jeśli ziarno jest zarówno nieprzewidywalne, jak i nieznane.
  • Jeśli używany jest zwykły PRNG z małą przestrzenią początkową, wówczas system nie jest bezpieczny, niezależnie od tego, czy ziarno jest nieprzewidywalne czy nieznane; wystarczająco mała przestrzeń nasienna jest podatna na ataki typu brute force opisanego przeze mnie.

Czy różnica ma coś wspólnego z rozkładem produkcji PRNG?

Jednorodność dystrybucji lub jej brak dla poszczególnych połączeń do RNG(n)nie ma związku z atakami, które opisałem.

Jak widzieliśmy, zarówno a, jak PRNGi CPRNGprodukują słabe rozkłady prawdopodobieństwa wyboru dowolnej indywidualnej talii ze wszystkich możliwych talii. PRNGJest znacznie gorzej, ale obie mają problemy.

Jeszcze jedno pytanie:

Jeśli TRNG jest o wiele lepszy niż CPRNG, co z kolei jest o wiele lepsze niż PRNG, dlaczego ktoś używa CPRNG lub PRNG?

Dwa powody.

Po pierwsze: wydatek. TRNG jest drogi . Generowanie naprawdę losowych liczb jest trudne. CPRNG dają dobre wyniki dla dowolnie wielu połączeń z tylko jednym połączeniem do TRNG dla materiału siewnego. Wadą jest oczywiście to , że musisz zachować to ziarno w tajemnicy .

Po drugie: czasami chcemy przewidywalności i zależy nam tylko na dobrej dystrybucji. Jeśli generujesz „losowe” dane jako dane wejściowe programu dla zestawu testowego, a to pokazuje błąd, fajnie byłoby, gdyby ponowne uruchomienie zestawu testowego spowodowało błąd!

Mam nadzieję, że jest to teraz o wiele bardziej jasne.

Wreszcie, jeśli ci się podobało, możesz cieszyć się dalszą lekturą na temat losowości i permutacji:


20
Ok, chłopcy i dziewczęta. Na razie wystarczy komentowanie. Jeśli chcesz to omówić dalej, idź na czat, kthnxbye!
Ivo Flipse

1
@Eric Ale ziarno nie jest resetowane przed każdym losowaniem nowej talii, prawda? Chociaż masz rację, że próbujemy tylko stosunkowo niewiele trajektorii , nie wiesz dokładnie, gdzie w tej chwili jesteś, a trajektorie się przecinają.
AS


Dobre (ale gęste) podejście do zagadnień pokrewnych znajduje się w TAOCP Knuth tom 2, sekcja 3.5 „What is a Random Sequence?” (S. 149), zaczynając od naświetlających definicji sekwencji o równomiernej dystrybucji, k-dystrybucji i ∞-dystrybucji. Sekwencje pseudolosowe omówiono w 3.5.F (str. 170). Zobacz także kryteria pseudolosowości z teorii złożoności i niemieckiego BSI .
ShreevatsaR

160

Jak mówi Eric Lippert, nie chodzi tylko o dystrybucję. Istnieją inne sposoby pomiaru losowości.

Jeden z wczesnych generatorów liczb losowych ma sekwencję w najmniej znaczącym bicie - na przemian zera i jedynki. Dlatego LSB było w 100% przewidywalne. Ale musisz się martwić o coś więcej. Każdy bit musi być nieprzewidywalny.

Oto dobry sposób, aby pomyśleć o problemie. Załóżmy, że generujesz 64 bity losowości. Dla każdego wyniku weź pierwsze 32 bity (A) i ostatnie 32 bity (B) i utwórz indeks w tablicy x [A, B]. Teraz wykonaj test milion razy i dla każdego wyniku zwiększ tablicę o tę liczbę, tj. X [A, B] ++;

Teraz narysuj diagram 2D, w którym im większa liczba, tym jaśniejszy piksel w tym miejscu.

Jeśli jest naprawdę losowy, kolor powinien być jednolity szary. Ale możesz dostać wzory. Weźmy na przykład ten schemat „losowości” w numerze sekwencyjnym TCP systemu Windows NT:

Windows NT

lub nawet ten z Windows 98:

Windows 98

A oto losowość implementacji routera Cisco (IOS). Cisco ISO

Te diagramy są dziełem Michała Zalewskiego . W tym konkretnym przypadku, jeśli można przewidzieć, jaki będzie numer sekwencyjny TCP systemu, można podszyć się pod ten system podczas nawiązywania połączenia z innym systemem - co pozwoliłoby na przejęcie połączeń, przechwycenie komunikacji itp. I nawet jeśli nie jesteśmy w stanie przewidzieć następnej liczby w 100% przypadków, jeśli możemy spowodować utworzenie nowego połączenia pod naszą kontrolą , możemy zwiększyć szansę na sukces. A kiedy komputery mogą wygenerować 100 000 połączeń w ciągu kilku sekund, szanse udanego ataku zmieniają się z astronomicznego na możliwe lub nawet prawdopodobne.


30
To jest tak genialne, że wywołuje łzy w moich oczach. Powinna istnieć aplikacja, która tworzy je dla każdego systemu operacyjnego (mobilnego / stacjonarnego / serwera) i platformy (JVM / Javascript / etc).
HDave

5
Funkcja rand () systemu Windows jest całkiem dobra! Tworzy chmurę, która nie ma żadnych widocznych wzorów. Zobacz moją implementację, aby wypróbować (i inne algorytmy): github.com/Zalastax/visualize_random
Zalastax

93

Chociaż pseudolosowe liczby generowane przez komputery są dopuszczalne w większości przypadków użycia spotykanych przez użytkowników komputerów, istnieją scenariusze, które wymagają całkowicie nieprzewidywalnych liczb losowych.

W aplikacjach wrażliwych na bezpieczeństwo, takich jak szyfrowanie, generator liczb pseudolosowych (PRNG) może generować wartości, które, choć z wyglądu są losowe, są w rzeczywistości przewidywalne przez atakującego. Ktoś, kto próbuje złamać system szyfrowania, może odgadnąć klucze szyfrowania, jeśli użyto PRNG, a osoba atakująca ma informacje o stanie PRNG. Dlatego w takich zastosowaniach konieczny jest generator liczb losowych, który generuje wartości, które są naprawdę niewyobrażalne. Należy pamiętać, że niektóre programy PRNG są zaprojektowane pod kątem bezpieczeństwa kryptograficznego i nadają się do użytku w takich wrażliwych aplikacjach.

Więcej informacji na temat ataków RNG można znaleźć w tym artykule w Wikipedii .


9
PRNG kryptograficzne istnieją i są szeroko stosowane. Mogą one z nasion o niewielkich rozmiarach generować praktycznie nieograniczony strumień liczb losowych. Wyróżnienie takiego strumienia od prawdziwych liczb losowych jest obliczeniowo niewykonalne, dlatego nie można uzyskać żadnych dodatkowych informacji z żadnej części takiego strumienia, a dla dowolnego praktycznego celu liczby są tak dobre jak prawdziwe liczby losowe.
aaaaaaaaaaaa

Myślę, że najprostszym sposobem na wyjaśnienie tego jest zaprogramowanie algorytmów generatora liczb losowych. Oznacza to, że jest zestaw instrukcji, które są przestrzegane. Jeśli istnieje zestaw instrukcji, nie może być losowy.
Keltari

6
@Keltari Brakuje elementu entropii ... Większość RNG (przynajmniej kryptograficznych) zbiera dane z zewnętrznych źródeł (np. Ruch myszy) i wykorzystuje je jako część warunku początkowego - w ten sposób transformacja z Ana Bjest zaprogramowana, ale początkowy stan A(powinien) być niemożliwy do przeoczenia. Linux /dev/randomzachowa przybliżoną ilość dostępnej entropii i przestanie podawać liczby, jeśli spadnie zbyt nisko.
Podstawowy

Z ciekawości - dlaczego lampy lawowe uważa się za „naprawdę przypadkowe”? Rozumiem, że wykazuje raczej nieprzewidywalne zachowanie, ale ktoś, kto wystarczająco dobrze rozumie dynamikę płynów i sposób, w jaki płyny te oddziałują w ziemskim środowisku grawitacyjnym, z pewnością może dać „przewidywalne” wyniki, prawda? Jasne, lampy lawowe są nieprzewidywalne, ale dla mnie wcale nie są przypadkowe, ale wysoce przewidywalne.
theGreenCabbage

1
@theGreenCabbage: Podejrzewam, że lampy lawowe są chaotyczne. Biorąc pod uwagę wystarczająco dobry model komputerowy i wystarczającą liczbę cyfr dokładności, można (co do zasady) przewidzieć zachowanie na chwilę. Ponieważ jednak układ jest chaotyczny, dwie lampy lawowe z najmniejszą zmianą warunków początkowych szybko się różnią. (I ten komentarz ignoruje chaotyczne atraktory).
dmm

76

Próbowałem w Pythonie: Oto wynik 60 milionów rolek. Najwyższa zmienność wynosi 0,15. Czy to nie jest tak losowe, jak to się stanie?

Właściwie to jest tak „dobre”, że jest złe … Wszystkie istniejące odpowiedzi koncentrują się na przewidywalności, biorąc pod uwagę małą sekwencję wartości początkowych. Chcę poruszyć inną kwestię:

    twój rozkład ma znacznie mniejsze odchylenie standardowe niż powinny losowe rzuty

Prawdziwa losowość prostu nie przychodzi dość , że blisko uśrednienie „prawie dokładnie 1 nad tym, jak wiele historii numery można go wybrać z” że używasz jako wskaźnik jakości.

Jeśli spojrzysz na pytanie Stack Exchange dotyczące rozkładów prawdopodobieństwa dla wielu rzutów kostką , zobaczysz wzór na standardowe odchylenie N rzutów kostką (zakładając autentycznie losowe wyniki):

 sqrt(N * 35.0 / 12.0).

Stosując tę ​​formułę, odchylenie standardowe dla:

  • 1 milion rolek to 1708
  • 60 milionów rolek to 13229

Jeśli spojrzymy na twoje wyniki:

  • 1 milion rolek: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) to 804
  • 60 milionów rolek: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) to 3827

Nie można oczekiwać, że odchylenie standardowe skończonej próbki będzie dokładnie zgodne z formułą, ale powinno być bardzo zbliżone. Jednak przy 1 milionie rzutów masz mniej niż połowę właściwego stddev, a przy 60 milionach masz mniej niż jedną trzecią - jest coraz gorzej, a to nie przypadek ...

Pseudo-RNG mają tendencję do przechodzenia przez sekwencję różnych liczb, zaczynając od nasion i nie powracając do pierwotnej liczby przez określony czas. Na przykład implementacje starej rand()funkcji biblioteki C zwykle mają okres 2 ^ 32 i odwiedzą każdą liczbę od 0 do 2 ^ 32-1 dokładnie raz przed powtórzeniem zarodka. Więc jeśli symulowałeś 2 ^ 32 kości rzuca moduł wstępny (%) wyniki obejmowałyby każdą liczbę od 0 do 2 ^ 32, liczenie dla każdego wyniku 1-6 wynosiłoby 715827883 lub 715827882 (2 ^ 32 nie jest wielokrotnością liczby 6), a zatem odchylenie standardowe tylko trywialnie powyżej 0. Używanie zgodnie z powyższym wzorem prawidłowe odchylenie standardowe dla 2 ^ 32 rzutów wynosi 111924. W każdym razie, wraz ze wzrostem liczby rzutów pseudolosowych zbliżasz się do 0 odchylenia standardowego. Można oczekiwać, że problem będzie znaczący, gdy liczba rolek stanowi znaczną część tego okresu, ale niektóre pseudo-RNG mogą wykazywać gorsze problemy - lub problemy nawet z mniejszą liczbą próbek - niż inne.

Więc nawet jeśli nie przejmujesz się słabościami kryptograficznymi, w niektórych aplikacjach możesz martwić się o dystrybucje, które nie mają nadmiernie, sztucznie nawet wyników. Niektóre typy symulacji dość konkretnie próbują ustalić konsekwencje nierównomiernych wyników, które naturalnie występują przy dużych próbach losowo pojedynczych wyników, ale są one niedostatecznie reprezentowane w niektórych wynikach pRNG. Jeśli próbujesz zasymulować reakcję ogromnej populacji na jakieś zdarzenie, ten problem może radykalnie zmienić Twoje wyniki, prowadząc do niesamowicie niedokładnych wniosków.


Podając konkretny przykład: Powiedz matematykowi programistom pokera, że ​​po 60 milionach symulacji rzutów - użył do migotania setek małych „świateł” na ekranie, jeśli było ich 10 013,229 lub więcej szóstek, których matematyk oczekuje 1 stddev od średniej, powinna być niewielka wypłata. Zgodnie z regułą 68–95–99,7 (Wikipedia) powinno to się zdarzać około 16% czasu (~ 68% mieści się w standardowym odchyleniu / tylko połowa na zewnątrz jest powyżej). W przypadku generatora liczb losowych wynika to z około 3,5 standardowych odchyleń powyżej średniej: poniżej 0,025% szansy - prawie żaden klient nie korzysta z tej korzyści. Zobacz tabelę wyższych odchyleń na właśnie wspomnianej stronie, w szczególności:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

Porównujesz tutaj jabłka i pomarańcze. Dwa standardowe odchylenia nie mają ze sobą absolutnie nic wspólnego.
Jbeuh

50

Właśnie napisałem ten generator liczb losowych, aby wygenerować rzuty kostką

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

Używasz go w ten sposób

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

itp. Czy chętnie skorzystasz z tego generatora w programie, który uruchamia grę w kości? Pamiętaj, że jego rozkład jest dokładnie taki, jak można się spodziewać po „prawdziwie losowym” generatorze!

Generatory liczb pseudolosowych robią w zasadzie to samo - generują przewidywalne liczby o prawidłowym rozkładzie. Są złe z tego samego powodu, dla którego powyższy uproszczony generator liczb losowych jest zły - nie są odpowiednie w sytuacjach, w których potrzebujesz prawdziwej nieprzewidywalności, a nie tylko prawidłowego rozkładu.


2
„Generatory liczb pseudolosowych ... generują przewidywalne liczby z prawidłowym rozkładem” - tylko dlatego, że jest to PRNG, nie gwarantuje doskonałej dystrybucji (w rzeczywistości komercyjne generalnie nie, ponieważ dokładnie przyczyny przedstawione w tych odpowiedziach). Chociaż można je przewidzieć, biorąc pod uwagę wystarczające informacje (użyty algo, początkowy materiał siewny, wartości wyjściowe, w / e), nadal mają wariancję.
Brian S

3
Poza tym momencie wiem, ale get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so onjest po prostu zbyt elegancki nie wspominając :)
Janus Troelsen

2
@BrianS W rzeczywistości PRNG, który z czasem nie przeszedł testów dystrybucji, byłby z definicji przewidywalny. Tak więc w przypadku niektórych dużych liczb N, jeśli uda Ci się choć trochę oddalić od N / 2 głów w N rzutach monetą, możesz zacząć obstawiać główki i możesz wygrać więcej, niż przegrasz. Podobnie, jeśli masz doskonały rozkład głów w porównaniu z ogonami, ale głowy zawsze przychodzą w parach, to znowu będziesz miał przepis na wygraną. Testy dystrybucyjne pozwalają stwierdzić, że PRNG jest dobry.
Jon Kiparsky,

1
Zapomniałeś nonlocal next:-).
Kos

5
Jeszcze lepszy przykład: uważa się , że Pi jest normalne , co oznacza, że ​​jakakolwiek sekwencja cyfr o dowolnej długości w dowolnej zasadzie pojawia się nie częściej niż jakakolwiek inna sekwencja tej długości w tej zasadzie. Algorytm, który poproszony o n losowych bitów, bierze kolejne n bitów pi i zwraca je („seed” to bit, od którego zaczynasz), powinien w dłuższej perspektywie dawać idealnie równomierny rozkład. Ale nadal nie chciałbyś tego dla swojego generatora - ktoś, kto zna ostatnią wiązkę wygenerowanych bitów, może znaleźć pierwsze wystąpienie sekwencji, założyć, że twoje ziarno tam jest i prawdopodobnie jest poprawne.
cpast

26

Generowanie liczb losowych, które może przeprowadzić Twój komputer, jest odpowiednie dla większości potrzeb i prawdopodobnie nie spotkasz się z czasem, w którym potrzebujesz naprawdę losowej liczby.

Prawdziwe generowanie liczb losowych ma jednak swoje cele. W zakresie bezpieczeństwa komputerowego, hazardu, dużych prób statystycznych itp.

Jeśli interesują Cię zastosowania liczb losowych, sprawdź artykuł w Wikipedii .


12
Dużym problemem jest to, że potrzebujesz losowych liczb, których atakujący nie może przewidzieć ze względów bezpieczeństwa.
David Schwartz

16
Na pewno znajdziesz się w piekle w czasach, gdy potrzebujesz naprawdę losowej liczby. Wystarczy otworzyć stronę internetową zaczynającą się od https://...
Jan Hudec

3
@JanHudec: Cóż, w codziennym użyciu będziesz potrzebować bezpiecznych liczb losowych od momentu otwarcia dowolnego programu, na długo przed wpisaniem w pasku adresu: zobacz losowość układu przestrzeni adresowej . Dlatego tak się dzieje.
Reid

5
@ JanHudec Mówiłem konkretnie w tym sensie, że musiałbyś użyć internetowego generatora liczb losowych. Prawdziwe liczby losowe są często używane, ale bardzo niewiele osób faktycznie musi je wygenerować.
Alex McKenzie

2
Automaty do gry używają również PRNG, a nie TRNG. Generator działa cały czas, a numer jest wybierany dokładnie w momencie naciśnięcia przycisku wirowania. Suma PRNG i prawdziwie losowego czasu naciśnięcia przycisku wynosi TRNG.
Roger Dahl

26

Liczby losowe generowane przez typowe funkcje w większości języków programowania nie są liczbami czysto losowymi. Są to pseudolosowe liczby. Ponieważ nie są to liczby losowe, można je odgadnąć z wystarczającą ilością informacji o wcześniej wygenerowanych liczbach. Będzie to katastrofa dla bezpieczeństwa w kryptografii .

Na przykład poniższa funkcja generatora liczb losowych glibcnie generuje liczb czysto losowych. Generowany przez niego pseudolosowy numer można odgadnąć. Jest to błąd w kwestii bezpieczeństwa. Historia tego dzieje się katastrofalna. Nie należy tego używać w kryptografii.

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

Ten typ generatora liczb pseudolosowych nigdy nie powinien być nigdy stosowany w miejscach wrażliwych pod względem bezpieczeństwa, nawet jeśli jest to statystycznie znaczące.

Jednym ze słynnych ataków na pseudolosowy klucz jest atak na WEP 802.11b . WEP ma 104-bitowy klucz długoterminowy, połączony z 24-bitowym IV (licznik), aby utworzyć klucz 128-bitowy, który z kolei jest stosowany do algorytmu RC4 w celu wygenerowania pseudolosowego klucza.

( RC4( IV + Key ) ) XOR (message)

Klucze były ściśle ze sobą powiązane. Tutaj tylko IV wzrosło o 1 na każdym kroku, a wszystkie pozostałe pozostały takie same. Ponieważ nie był to wyłącznie przypadek, był katastrofalny i łatwo go zepsuć. Klucz można odzyskać, analizując około 40000 ramek, co jest kwestią minut. Jeśli WEP użyje czysto losowego 24-bitowego IV, może być bezpieczny aż do około 2 ^ 24 (prawie 16,8 miliona) klatek.

Więc jeśli to możliwe, należy korzystać z generatora czystych liczb losowych w kwestiach wrażliwych na bezpieczeństwo.


3
Winiłbym rzeczy WEP za źle zaprojektowany protokół wykorzystujący słaby szyfr. Dzięki nowoczesnym szyfrom strumieniowym możesz używać licznika jako IV.
CodesInChaos

2
Głównym problemem z WEP było powtarzanie klucza w 2 ^ 24 (prawie 16 milionach) klatkach. Gorzej było z powiązanymi kluczami, które umożliwiły złamanie kodu w około 40000 ramkach. Najważniejsze jest to, że klucz nie jest losowy. Jest blisko spokrewniony, więc łatwo go złamać.
Prabhu

1
Pseudolosowość jest zła w kryptografii tylko podczas generowania kluczy kryptograficznych . Poza tym jest w porządku. Rzeczywiście, RC4 to niewiele więcej niż generator liczb pseudolosowych obsadzony 128-bitowym rozszerzeniem klucza XOR na zwykły tekst wiadomości.
Matt

12

Różnica polega na tym, że liczby generowane pseudolosowo są przewidywalne (powtarzalne) po pewnym czasie, w którym nie są prawdziwe liczby losowe. Długość potrzebna do powtórzenia zależy od długości nasion używanych do ich wytworzenia.

Oto całkiem niezły film na ten temat: http://www.youtube.com/watch?v=itaMNuWLzJo


Przewidywalność! = Powtarzanie. Mersenne Twister jest tego dobrym przykładem. Na większości implementacji po 624 Int32 można przewidzieć wszystkie następne liczby, ale sekwencja Mersenne Twister jest znacznie dłuższa (2 ^ 19937-1).
HoLyVieR

Nie rozumiem, dlaczego ta odpowiedź nie jest wypychana, ponieważ wydaje mi się, że jest to dokładna i zwięzła odpowiedź na pytanie, przynajmniej częściowo. Pseudolosowe liczby można łatwo przewidzieć po niektórych losowaniach, liczba losowań zmienia się w zależności od „jakości” algorytmu pseudolosowego. Wybór „dobrego” algorytmu uwzględnia aspekty: 1. każda wartość jest rysowana w równej częstotliwości (rozkład), 2. potrzeba „długiego czasu”, aby ponownie uruchomić sekwencję na początku i ponownie zacząć rysować te same liczby w taki sam porządek.
min

„prawdziwe liczby losowe nie są [przewidywalne]”. Na dziś to prawda. Teraz, jeśli wierzymy w teorię Wielkiego Wybuchu i mamy dużą moc do obliczenia stanu Wszechświata w dowolnym momencie po BB, w oparciu o fizykę, to ... jesteśmy w stanie przewidzieć przyszłość, w tym fakt, że Piszę ten bardzo dokładny komentarz. Dobrze?
min

Jest to hipotetycznie prawda, jednak biorąc pod uwagę ogromny stopień entropii zaangażowanej w rzeczywiste działania prawdziwych ciał, wymagana moc obliczeniowa byłaby absurdalnie ogromna. Pomyśl o kontynentach pokrytych komputerami. Ponadto, z powodu zależności od poprzedniego stanu, stan każdego ciała we wszechświecie w każdym momencie musiałby być przechowywany, co z definicji wymagałoby więcej miejsca niż jest dostępne we wszechświecie, całkowicie wypełnionego aparatem pamięci
TheEnvironmentalist

@TheEnvironmentalist - Ah! „Kontynenty pokryte komputerami” ... czy nie o to chodzi w „Poradniku autostopowicza po galaktyce”? ;-)
ysap

10

Załóżmy, że pseudolosowa liczba może odgadnąć przed wygenerowaniem.

W przypadku trywialnych aplikacji pseudolosowość jest w porządku, ponieważ w twoim przykładzie otrzymasz w przybliżeniu prawidłowy procent (około 1/6 całkowitego zestawu wyników) z pewną niewielką zmianą (którą zobaczysz, jeśli rzucisz kostką 600k czasy);

Jednak jeśli chodzi o bezpieczeństwo komputera; Wymagana jest prawdziwa losowość.

Na przykład algorytm RSA rozpoczyna się od wybrania przez komputer dwóch liczb losowych (P i Q), a następnie wykonania kilku kroków w celu wygenerowania liczb specjalnych znanych jako klucze publiczne i prywatne. (Ważną częścią klucza prywatnego jest to, że jest prywatny i nikt go nie zna!)

Jeśli osoba atakująca może wiedzieć, jakie dwie „losowe” liczby wybierze komputer, może wykonać te same kroki, aby obliczyć klucz prywatny (ten, którego nikt inny nie powinien wiedzieć!)

Za pomocą klucza prywatnego osoba atakująca może wykonywać następujące czynności: a) Porozmawiaj z bankiem udając, że jesteś tobą, b) Słuchaj swojego „bezpiecznego” ruchu internetowego i umie go dekodować, c) Zamaskuj między tobą a innymi stronami w Internecie.

Właśnie tam wymagana jest prawdziwa losowość (tj. Niemożność odgadnięcia / obliczenia).


10

Pierwsza liczba losowa, której kiedykolwiek użyłem, miała doskonałą właściwość spośród dwóch kolejnych liczb losowych, druga była większa z prawdopodobieństwem 0,6. Nie 0,5 Trzeci był większy niż drugi z prawdopodobieństwem 0,6 i tak dalej. Możesz sobie wyobrazić, jak to działa spustoszenie dzięki symulacji.

Niektórzy nie uwierzyliby mi, że było to możliwe nawet przy równomiernym rozkładzie liczb losowych, ale oczywiście jest to możliwe, jeśli spojrzymy na sekwencję (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ...) gdzie druga z dwóch liczb jest większa z prawdopodobieństwem 0,6.

Z drugiej strony, w przypadku symulacji ważna może być możliwość odtwarzania liczb losowych. Załóżmy, że wykonujesz symulację ruchu i chcesz dowiedzieć się, w jaki sposób niektóre działania, które możesz podjąć, mogą poprawić ruch. W takim przypadku chcesz móc odtworzyć dokładnie te same dane o ruchu (np. Osoby próbujące wjechać do miasta) za pomocą różnych działań, które próbujesz poprawić.


8

Krótka odpowiedź jest taka, że zwykle ludzie wymagają „prawdziwej przypadkowości” z złego powodu, a mianowicie, że nie rozumieją kryptografii.

Prymitywy kryptograficzne, takie jak szyfry strumieniowe i CSPRNG, są używane do wytwarzania ogromnych strumieni nieprzewidywalnych bitów, gdy zostaną one zasilone kilkoma nieprzewidywalnymi bitami.

Uważny czytelnik zda sobie teraz sprawę, że jest tu problem z ładowaniem: musimy zebrać kilka kawałków entropii, aby wszystko zacząć. Następnie be może je nakarmić do CSPRNG, który z kolei z radością dostarczy wszystkie nieprzewidywalne bity, których potrzebujemy. Zatem sprzętowy RNG jest wymagany do uruchomienia CSPRNG . Jest to jedyny przypadek, w którym entropia jest wymagana w rzeczywistości.

(Myślę, że powinno to zostać opublikowane w dziale Bezpieczeństwo lub Kryptografia).

Edycja: W końcu należy wybrać generator liczb losowych, który jest wystarczająco dobry dla przewidywanego zadania, a jeśli chodzi o generowanie liczb losowych, sprzęt niekoniecznie jest dobry. Podobnie jak złe PRNG, losowe źródła sprzętowe zwykle mają tendencje.

Edycja: niektórzy ludzie zakładają tutaj model zagrożenia, w którym osoba atakująca może odczytać wewnętrzny stan CSPRNG, a stamtąd dochodzi do wniosku, że CSPRNG nie są bezpiecznym rozwiązaniem. To jest przykład słabego modelowania wątków. Jeśli atakujący jest właścicielem twojego systemu, gra jest skończona, prosta i prosta. Nie ma znaczenia, czy w tym momencie korzystasz z TRNG, czy CSPRNG.

Edycja: Tak więc, podsumowując to wszystko ... Entropy jest wymagane, aby zaliczyć CSPRNG. Po wykonaniu tej czynności CSPRNG dostarczy wszystkie nieprzewidywalne bity, których potrzebujemy do aplikacji bezpieczeństwa, znacznie szybciej niż (zwykle) możemy zbierać entropię. Jeśli nieprzewidywalność nie jest wymagana, na przykład w przypadku symulacji, Twister Mersenne zapewni liczby o dobrych właściwościach statystycznych ze znacznie wyższą szybkością.

Edycja: Każdy, kto chce zrozumieć problem bezpiecznego generowania liczb losowych, powinien przeczytać: http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf


2
To niekoniecznie pytanie bezpieczeństwa. Myślę, że istnieją powody, aby używać naprawdę losowych liczb, które nie wiążą się z bezpieczeństwem. Gdybym przeprowadzał jakieś badania naukowe, które zależą od liczb losowych i z jakiegokolwiek powodu krytyczne było, aby liczby były jak najbardziej losowe, z pewnością skorzystałbym ze sprzętowego RNG, aby mieć pewność, że żadne zaobserwowane właściwości nie są należne na dziwactwa z RNG.
Kef Schecter

3
@KefSchecter To ich słyszalne sprzętowe PRNG generalnie mają tendencyjne i / lub skorelowane wyjście. Potrzebują etapu przetwarzania końcowego, aby przekształcić go w jednolite, niezależne wyjście. Nie ma powodu, aby sądzić, że ten etap przetwarzania końcowego jest bardziej niezawodny niż nowoczesny szyfr strumieniowy. Z pewnością bardziej zaufałbym szyfrowi strumieniowemu. Jako dodatkowy bonus jest powtarzalny, co jest cenne w nauce.
CodesInChaos

OK, w porządku. Ale czy to samo nie dotyczyłoby również aplikacji kryptograficznych? Nawet odpowiedź udzielona tutaj mówi, że potrzebujesz sprzętowego RNG, aby uruchomić CSPRNG.
Kef Schecter

2
@KefSchecter Tak, aplikacje kryptograficzne potrzebują prawdziwych liczb losowych, aby zainicjować CSPRNG. Ale do wszystkiego innego możemy użyć tego CSPRNG.
CodesInChaos

@KefSchecter: Aplikacje kryptograficzne wymagają, aby strumień nie był odtwarzany przez cały świat. Natomiast w zastosowaniach naukowych pomocna jest umiejętność wykazania, że ​​używane „liczby losowe”, których się używa, nie zostały po prostu wybrane do pokazania analizy w dobrym świetle. Na przykład, jeśli ogłosi się po ogłoszeniu swoich metod, że wygeneruje dane w określony sposób przy użyciu numerów loterii stanowych na następny dzień, czytelnicy mogą być pewni, że nie sfałszowali swoich wyników, nawet jeśli losowanie w ciągu tygodnia ma tylko kilkadziesiąt kawałki entropii.
supercat

7

Nie wszystkie PRNG są odpowiednie do wszystkich zastosowań. Na przykład Java.util.SecureRandom używa skrótu SHA1, który ma wielkość wyjściową 160 bitów. Oznacza to, że istnieje 2 160 możliwych strumieni liczb losowych, które mogą z niego pochodzić. Proste. Nie można uzyskać więcej niż 2 160 wartości stanu wewnętrznego. Dlatego nie możesz uzyskać więcej niż 2 160 unikatowych strumieni liczb losowych z jednego ziarna, bez względu na to, skąd pochodzi twoje ziarno. Uważa się, że Windows CryptGenRandom używa stanu 40-bajtowego, ma 2 320 możliwych strumieni liczb losowych.

Liczba sposobów przetasowania standardowej talii z 52 kartami to 52 !, czyli około 2 226 . Tak więc, niezależnie od seedowania, nie można użyć Java.util.SecureRandom do przetasowania talii kart. Istnieje około 2 66 możliwych losowań, których nie może wygenerować. Oczywiście nie wiemy, które to są ...

Tak więc, gdybym miał źródło, powiedzmy, 256 bitów prawdziwej losowości (np. Z karty Quantis RNG), mógłbym zaszczepić PRNG jak CryptGenRandom () tym ziarnem, a następnie użyć PRNG do przetasowania talii karty Jeśli zresetuję z prawdziwą przypadkowością przy każdym losowaniu, wszystko będzie dobrze: nieprzewidywalne i statystycznie losowe. Gdybym zrobił to samo z Java.util.SecureRandom, byłyby tasowania, których nie byłoby możliwe, ponieważ nie można go zaszczepić 256 bitami entropii, a jego stan wewnętrzny nie może reprezentować wszystkich możliwych przetasowań.

Zauważ, że wyniki java.util.SecureRandom byłyby zarówno nieprzewidywalne, jak i statystycznie losowe. Żaden test statystyczny nigdy nie zidentyfikuje problemu! Ale wyjście RNG nie jest wystarczająco duże, aby pokryć pełną domenę wszystkich możliwych wyjść potrzebnych do symulacji talii kart.

I pamiętaj, jeśli dodasz jokerów, będzie 54! którą musisz pokryć, co wymaga około 2 238 możliwości.


2
Dlaczego przejmujesz się, że niektóre losowania nie mogą się zdarzyć? Ograniczenie to nie ma zauważalnego skutku.
CodesInChaos

2
Jestem trochę zdziwiony tym pytaniem. W przypadku ściśle regulowanych firm oferujących gry takie uprzedzenie matematycznie udowodniłoby, że szanse na wygraną w grze karcianej są inne na komputerze niż na papierowej talii kart. Nie ma znaczenia, czy szanse są lepsze czy gorsze. Są INNE. Komputer nie jest moralnie równoważny z prawdziwą talią. Ponadto nie możemy scharakteryzować różnicy. Firma zajmująca się grami, której dotyczą surowe grzywny regulacyjne, byłaby bardzo zainteresowana.
Paco Hope

1
Ale jest wykrywalny. Wykrywa go za pomocą znanego procesu: przeglądu kodu źródłowego i znajomości problematycznej domeny. To jest niezwykłe. NIE mogę korzystać ze zautomatyzowanej analizy statystycznej. Jest tak samo wykrywalny jak ktoś używający java.util.Random lub Mersenne Twister. Analiza statystyczna nie jest jedynym prawidłowym mechanizmem wykrywania niedopasowania RNG / domeny problemowej. Awarie przechodzące przez ten detektor nie są z definicji sukcesem.
Paco Hope

1
Nigdy nie zgadzałem się z tym stwierdzeniem. Powiedziałem, że analiza statystyczna nie jest niezawodnym dowodem, że RNG / PRNG jest poprawny. To jest przykład fałszywie negatywnego. Powinien być niepoprawny, ale test wyniku statystycznego przejdzie go pomyślnie. Jeśli użyję SHA1 (1), SHA1 (2), SHA1 (3) ... SHA1 (n) jako mojego „RNG”, który również przejdzie testy statystyczne. To także źle. Definicja poprawności wykracza poza definicję „przechodzi testy statystyczne”. Zaliczenie testów statystycznych jest konieczne, ale niewystarczające.
Paco Hope

4
@CodesInChaos: Argument „nie wiemy o ataku, który może wykorzystać fakt, że ogromna większość możliwych tasowań IRL nigdy nie zostanie wyprodukowana” nie oznacza, że ​​taki atak jest niemożliwy, tylko że nie nie wiem, co to jest i jak się przed tym bronić. Właściwe podejście w tym przypadku polega na wyeliminowaniu możliwości ataku poprzez wyeliminowanie warunku: stwórz RNG o wystarczającej jakości, aby mógł wygenerować każdą możliwą talię.
Eric Lippert,

6

Liczby pseudolosowe są generowane przy użyciu funkcji matematycznej i wartości początkowej (nazywanej ziarnem ), podczas gdy liczby losowe nie są. Ich przewidywalność sprawia, że ​​są one niezwykle przydatne do powtórki gry, ponieważ wystarczy zapisać dane wyjściowe i dane wejściowe gracza - AI będzie reagować w ten sam „losowy” sposób za każdym razem.


6

Różnica między „prawdziwą” liczbą losową a „pseudo” liczbą losową polega na przewidywalności. Ta odpowiedź została już udzielona.

Jednak przewidywalność niekoniecznie jest zła, jak pokazuje większość przykładów. Oto praktyczny przykład jednego z rzadkich przypadków, w których przewidywalność jest dobra: globalny system pozycjonowania.

Każdy satelita używa odrębnego kodu PRN ( kody Gold ) odpowiedniego do autokorelacji lub korelacji krzyżowej, która jest niezbędna do pomiaru czasu propagacji sygnału. W przypadku tych kodów Gold korelacja między sobą jest szczególnie słaba, umożliwiając jednoznaczną identyfikację satelity, ale umożliwiając obliczenie odległości na podstawie korelacji między emitowaną sekwencją a odbiornikiem.


2

Aby szybko sprawdzić losowość, bierzesz punkty o losowych współrzędnych w [0; 1), a następnie umieszczasz je w sześcianie k-wymiarowym. Następnie wykonujesz procedurę dzielenia tej kostki na podgrupy - każda objętość podmodułu (lub podprzestrzeni) musi być prawidłowo zmierzona za pomocą tej procedury z wahaniami zgodnie ze znanym twierdzeniem.

Jakość przypadkowości jest ważna tam, gdzie się spotykasz ...

  1. cele bezpieczeństwa. Gdy wygenerujesz liczbę do użycia jako parametr do generowania klucza, i jest to dobrze przewidywalne - wróg odkryje ją ze 100% prawdopodobieństwem i zmniejszy pole wyszukiwania.

  2. cele naukowe. W nauce musisz nie tylko mieć średnią średnią w dobrym stanie, ale także należy wyeliminować korelacje między różnymi liczbami losowymi. Więc jeśli weźmiesz (a_i - a) (a_ {i + 1} -a) i znajdziesz jego rozkład, musi on odpowiadać statystykom.

Korelacja par to tak zwana „słaba losowość”. Jeśli chcesz prawdziwej przypadkowości, musisz mieć wysoką korelację rzędu z więcej niż 2 wariancjami.

Obecnie tylko generatory mechaniki kwantowej zapewniają prawdziwą losowość.


1

Dlaczego prawdziwa losowość jest ważna?

Istnieją dwa główne powody, dla których konieczna jest prawdziwa losowość:

  1. Jeśli używasz RNG do kryptografii (w tym do gier hazardowych na prawdziwe pieniądze i prowadzenia loterii), to PRNG sprawi, że będziesz szyfrował znacznie słabiej niż matematyczna analiza tego (która zakłada TRNG), w którą byś uwierzył. PRNG tak naprawdę nie będzie losowy, ale będzie miał wzorzec - przeciwnicy mogą wykorzystać wzorzec do złamania szyfru, który powinien być nie do wykrycia.
  2. Jeśli używasz RNG do symulacji „losowych” danych wejściowych, na przykład do testowania błędów lub symulacji, to PRNG osłabia twoje podejście. Kiedy nie odkryjesz żadnych błędów, zawsze będą istniały dokuczliwe wątpliwości: czy istnieje błąd, który nie jest zauważalny we wzorcu mojego PRNG, ale pojawiłby się, gdybym tylko użył TRNG? Czy odkrycie mojej symulacji dokładnie opisuje rzeczywistość, czy też odkryte przeze mnie zjawisko jest po prostu artefaktem wzoru PRNG?

Poza tymi obszarami to naprawdę nie ma znaczenia. Zastrzeżenie: Jeśli twój PRNG jest bardzo, bardzo zły, może być nadal nieodpowiedni - nie chcesz tworzyć gry w kości, w której kostki zawsze się pojawiają, nawet twoim graczom się to nie spodoba.

Dlaczego PRNG Pythona nie jest wystarczająco dobry?

Jest bardzo mało prawdopodobne, że będziesz w stanie wykryć pułapki prawdziwego PRNG za pomocą tak prostej metodologii. Analiza statystyczna RNG jest sama w sobie dziedziną nauki, a dostępne są bardzo wyrafinowane testy do oceny „losowości” algorytmu. Są one znacznie bardziej zaawansowane niż prosta próba.

Każdy twórca oprogramowania, który tworzy biblioteki świata rzeczywistego, taki jak programiści Python, wykorzystuje te testy statystyczne jako miernik, aby sprawdzić, czy ich implementacja PRNG jest wystarczająco dobra. Tak więc, z wyjątkiem przypadków faktycznego nadzoru programisty, jest bardzo mało prawdopodobne, że będziesz w stanie łatwo wykryć wzorzec w PRNG w świecie rzeczywistym. To nie znaczy, że nie ma wzorca - PRNG ma wzorzec z definicji.


0

Zasadniczo nie można udowodnić, że źródło jest przypadkowe za pomocą analizy matematycznej wyniku, potrzebujesz np. Modelu fizycznego, który mówi, że źródło jest losowe (jak w rozpadzie radioaktywnym).

Możesz po prostu uruchomić testy wsadowe, aby znaleźć korelację statystyczną w danych wyjściowych, w takim przypadku dane okazują się nieprzypadkowe (ale także losowe źródło może mieć nieprzypadkowe dane wyjściowe lub nie będzie to naprawdę losowe, jeśli nie da określonego wynik). W przeciwnym razie, jeśli testy zostaną zaliczone, można powiedzieć, że dane są pseudolosowe.

Zaliczenie niektórych testów losowości oznacza tylko, że masz dobry PRNG (generator pseudolosowych liczb losowych), co może być przydatne w aplikacjach, w których bezpieczeństwo nie jest zaangażowane.

Jeśli chodzi o bezpieczeństwo (tj. Szyfrowanie, generowanie soli klucza, generowanie liczb losowych do hazardu ...) nie wystarczy mieć dobry PRNG, musi mieć dodatkowe cechy, takie jak funkcja wyjściowa, której nie można łatwo odgadnąć na podstawie poprzednich danych wyjściowych, funkcja musi mieć pożądany koszt obliczeniowy (wystarczająco ograniczony, aby był użyteczny, ale wystarczająco wysoki, aby pokonać brutalne próby wymuszenia), sprzęt, który uruchamia tę funkcję - lub urządzenie, w dzisiejszym dziwnym przypadku jest to urządzenie analogowe - nie powinno łatwo ulegać manipulacji itp.

Posiadanie dobrego PRNG może być przydatne w grach do tworzenia nowych i nieprzewidywalnych wzorców, a także w szyfrowaniu - zbyt kłopotliwe, aby wyjaśnić w jednym poście, po prostu pomyśl jako rola kciuka, jakie wyjście z procedury szyfrowania powinno być pseudolosowe, nie pokazujące wzorców które mogą powiązać poprzednie zaszyfrowane dane z następującymi zaszyfrowanymi danymi lub powiązać dane w postaci zwykłego tekstu z danymi zaszyfrowanymi lub powiązać dwa różne teksty zaszyfrowane (aby można było zgadywać na zwykłym tekście) ...


-4

Krótka historia:

Generuje losowe ziarno przy użyciu bieżącej mikrosekundy systemu.

Ta sztuczka jest dość stara i nadal działa.

Wyłączając czynnik brutalności, w którym mogę określić każdą kombinację poprzez „obstawianie” wszystkich możliwych liczb i nie o to chodzi w tym pytaniu, zwłaszcza gdy większość losowych liczb jest zaokrąglana przed jego użyciem.

Powiedzmy przykład, że mogę określić użyte ziarno, używając tylko 10 wartości. Znając ziarno, mogę odgadnąć kolejną wartość.

Gdybym użył seed = 1, mógłbym uzyskać następną sekwencję:

1, 2, 3, 4, 5, 6, 7, 8, 9 ... (i dedukuję, że ziarno użyło id 1 i następnej wartości 10)

Ale co się stanie, jeśli zmieni się wysyłanie co „n-tych” wartości ?. Zmiana zarodka o bieżące mikrosekundy jest tanią sztuczką (to znaczy, że nie wymaga wielu cykli procesora).

Zatem sekwencja jest teraz: (seed = 1) 1, 2, 3, 4, 5, (seed = 2), 7, 9, 11, 13 ... (15?)

W tym przypadku:

a) Nie mogę odliczyć, które ziarno zostało użyte.

b) Ergo, nie mogę zgadnąć następnej wartości.

c) Jedyne przypuszczenie, które mogę zrobić, to odjąć, że następne ziarno może być liczbą większą.

W każdym razie większość współczesnych algorytmów generatora losowego już używa tej sztuczki pod maską.

Prawdziwy fakt jest taki, że nie potrzebujemy komputera kwantowego do stworzenia „prawdziwej” liczby losowej, niedokładność naszego kryształu kwarcu naszego komputera działa jak generator losowy, również losowa wydajność naszego procesora jest również zmienna bez uwzględnienia że procesor zwykle wykonuje kilka zadań jednocześnie.


2
Jest to dość zły pomysł i jest źródłem podatności na zagrożenia, które wymagają naprawdę nieprzewidywalnej sekwencji. Jeśli wziąć mikrosekundy, masz tylko 10 ^ 6 możliwości nasion, które są raczej niskie.
HoLyVieR

@HoLyVieR: z pewnością jest to zły pomysł, jeśli zależy Ci na bezpieczeństwie, ale nie jest tak zły, jak się wydaje: normalnie używasz mikrosekund od uruchomienia systemu (lub epoki unix ...), co znacznie zwiększa zakres możliwych wartości.
mikera

1
@mikera Nie ma nic lepszego, czas przetwarzania żądania jest przewidywalny. Jest to wektor podatności na zagrożenia dla dużej liczby funkcji resetowania hasła. Te skrypty wygenerowały „losowy” token za pomocą Twojej techniki, a atakujący mógł znaleźć wygenerowany token, ponieważ znalezienie czasu, w którym zostało wykonane, jest dość trywialne ... w tym samym czasie wysłano żądanie zresetowania hasła + - 150ms.
HoLyVieR

Jasne, że sytuacja jest bardzo zła. Ale sytuacja, w której stan został zaszczepiony podczas uruchamiania systemu, a atakujący nie ma dobrego sposobu na odgadnięcie czasu uruchamiania, nie jest wcale taki zły. Możesz łatwo wybrać 10 ^ 12 mikrosondond do wyboru, co może sprawić, że niektóre rodzaje ataków będą niemożliwe. Żeby było jasne: wszystkie te rozwiązania są dość złe z punktu widzenia kryptografii, ale stałe znaczenie .
mikera

W przypadku serwerów internetowych informacje o czasie pracy systemu są czasami oferowane publicznie. Lub można go pobrać ze strony stanu „Incydenty. Serwer ponownie.”. Lub możesz pingować, czekać na długi przestój i zauważyć, że może to być restart komputera (co dałoby setki milionów czasu na sprawdzenie, co jest raczej niskie).
Dereckson
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.