Dlaczego nie łączymy generatorów liczb losowych?

Istnieje wiele aplikacji, w których używany jest pseudolosowy generator liczb losowych. Dlatego ludzie wdrażają taki, który ich zdaniem jest świetny, aby później stwierdzić, że jest wadliwy. Coś takiego stało się ostatnio z generatorem liczb losowych Javascript. RandU też dużo wcześniej. Istnieją również problemy z niewłaściwym początkowym zaszczepieniem czegoś takiego jak Twister.

Nie mogę znaleźć przykładów połączenia dwóch lub więcej rodzin generatorów ze zwykłym operatorem xor. Jeśli istnieje wystarczająca moc komputera, aby uruchamiać rzeczy takie jak java.SecureRandom lub implementacje Twister, dlaczego ludzie ich nie łączą? ISAAC xor XORShift xor RandU powinien być dość dobrym przykładem, w którym widać słabość jednego generatora łagodzonego przez inne. Powinno to również pomóc w rozkładzie liczb na wyższe wymiary, ponieważ wewnętrzne algorytmy są zupełnie inne. Czy istnieje jakaś fundamentalna zasada, że ​​nie należy ich łączyć?

Jeśli zbudowałbyś prawdziwy generator liczb losowych, ludzie prawdopodobnie doradziliby połączenie dwóch lub więcej źródeł entropii. Czy mój przykład jest inny?

Wykluczam wspólny przykład kilku rejestrów przesuwnych z liniowym sprzężeniem zwrotnym pracujących razem, ponieważ pochodzą one z tej samej rodziny.

IIRC (i to z pamięci), bestseller Rand z 1955 r. A Million Random Digits zrobił coś takiego. Zanim komputery były tanie, ludzie wybrali z tej książki losowe liczby.

Autorzy wygenerowali losowe bity z szumem elektronicznym, ale okazało się to stronnicze (ciężko jest, aby flipflop spędził dokładnie tyle samo razy na flipie i flopie). Jednak połączenie bitów sprawiło, że rozkład był znacznie bardziej jednolity.

Oczywiście możesz łączyć PRNG w ten sposób, jeśli chcesz, zakładając, że są one rozstawione niezależnie. Będzie jednak wolniejszy i prawdopodobnie nie rozwiąże najpilniejszych problemów, jakie mają ludzie.

W praktyce, jeśli masz wymaganie bardzo wysokiej jakości PRNG, używasz sprawdzonego PRNG o sile kryptograficznej i wysiewasz go z prawdziwą entropią. Jeśli to zrobisz, najbardziej prawdopodobny tryb awarii nie stanowi problemu z samym algorytmem PRNG; najbardziej prawdopodobnym trybem awarii jest brak odpowiedniej entropii (lub może błędy implementacji). Xoring wielu PRNG nie pomaga w tym trybie awarii. Tak więc, jeśli chcesz bardzo wysokiej jakości PRNG, prawdopodobnie nie ma sensu go wysyłać.

Alternatywnie, jeśli chcesz statystycznego PRNG, który jest wystarczająco dobry do celów symulacji, zwykle najważniejszą kwestią jest szybkość (generowanie liczb pseudolosowych naprawdę szybko) lub prostota (nie chcesz poświęcać dużo czasu na opracowanie lub wdrożenie). Xor-ing spowalnia PRNG i czyni go bardziej złożonym, więc nie zaspokaja również podstawowych potrzeb w tym kontekście.

Tak długo, jak wykażesz się należytą starannością i kompetencjami, standardowe PRNG są wystarczająco dobre, więc naprawdę nie ma powodu, dla którego potrzebujemy czegoś bardziej wymyślnego (nie ma potrzeby xorowania). Jeśli nie masz nawet minimalnego poziomu opieki lub kompetencji, prawdopodobnie nie wybierzesz czegoś złożonego, takiego jak xoring, a najlepszym sposobem na poprawę sytuacji jest skupienie się na większej dbałości i kompetencjach w wyborze PRNG zamiast na Xor-in.

Konkluzja : Zasadniczo sztuczka xor nie rozwiązuje problemów, które ludzie zwykle mają podczas korzystania z PRNG.

W rzeczywistości właśnie ogłoszono coś przełomowego.

Profesor informatyki z Uniwersytetu Teksasu David Zuckerman i doktorant Eshan Chattopadhyay odkryli, że można wygenerować liczbę losową „wysokiej jakości” poprzez połączenie dwóch źródeł losowych „niskiej jakości”.

Oto ich artykuł: Wyraźne ekstraktory z dwóch źródeł i sprężyste funkcje

Załóżmy, że jest pseudolosową sekwencją binarną. Oznacza to, że każdy jest losową zmienną obsługiwaną w , a zmienne niekoniecznie są niezależne. Możemy pomyśleć o wygenerowaniu tej sekwencji w następujący sposób: najpierw próbkujemy jednolicie losowy klucz , a następnie używamy funkcji do wygenerowania sekwencji pseudolosowej.$X_1,\ldots,X_n$$X_i$$\{0,1\}$$X_1,\ldots,X_n$$K$$f(K)$

Jak mierzymy, jak dobra jest pseudolosowa sekwencja ? Chociaż można zmierzyć, jak dobra jest konkretna realizacja (powiedzmy, używając złożoności Kołmogorowa), tutaj skoncentruję się na miarach, które zależą od całego rozkładu zmiennej losowej . Jednym z takich przykładów jest entropia, ale będziemy potrzebować tylko dwóch właściwości naszej miary : (większy oznacza bardziej losową sekwencję)$X_1,\ldots,X_n$$(X_1,\ldots,X_n)$$L$$L(\cdot)$

• Jeśli jest sekwencją deterministyczną (tj. Ustaloną sekwencją), to . L ( X 1 ⊕ y 1 , … , X n ⊕ y n ) = L ( X 1 , … , X n$y_1,\ldots,y_n$$L(X_1 \oplus y_1, \ldots, X_n \oplus y_n) = L(X_1,\ldots,X_n)$

• Jeśli to dwie niezależne sekwencje pseudolosowe, jest niezależnym bitem losowym, a , a następnie .$\vec{X^0},\vec{X^1}$$T \in \{0,1\}$$\vec{Z} = \vec{X^T}$$L(\vec{Z}) \geq \min(\vec{X^0},\vec{X^1})$

Pierwsza właściwość oznacza, że ​​miara jest niezmienna przy odwróceniu tego bitu. Druga właściwość oznacza, że ​​jeśli pomieszamy dwie dystrybucje , to wynik będzie co najmniej tak dobry, jak gorszy.$i$$\vec{X},\vec{Y}$

Każda rozsądna miara losowości zaspokoi pierwszą właściwość. Drugą właściwość spełniają najbardziej popularne miary, takie jak entropia i min-entropia .$H$$H_\infty$

Możemy teraz stwierdzić i udowodnić twierdzenie pokazujące, że XORing dwóch sekwencji pseudolosowych jest zawsze dobrym pomysłem.

Twierdzenie. Niech będą dwiema niezależnymi pseudolosowymi sekwencjami o tej samej długości i niech będzie dopuszczalną miarą losowości (jedna spełniająca dwa powyższe warunki). Następnie$\vec{X},\vec{Y}$$L$

Dowód. Załóżmy, że . Następnie jest mieszaniną Rozkłady zmieszane zgodnie z podziałem . Ponieważ i mieszanina jest co najmniej tak dobra, jak najgorszy mieszany rozkład, otrzymujemy . $L(X) \geq L(Y)$$X \oplus Y$$X \oplus y$$Y$$L(X \oplus y) = L(X)$$L(X \oplus Y) \geq L(X)$$~\square$

To twierdzenie oznacza, że ​​jeśli XOR wygeneruje dwie pseudolosowe sekwencje wygenerowane przy użyciu dwóch niezależnych kluczy, wynik będzie zawsze co najmniej tak dobry, jak lepsza sekwencja XORed, w odniesieniu do dowolnej dopuszczalnej miary losowości.

W praktyce, aby użyć dwóch niezależnych kluczy, prawdopodobnie pseudolosowo rozszerzamy jeden klucz na dwa klucze. Dwa klucze nie są wówczas niezależne. Jeśli jednak użyjemy „drogiego” sposobu na rozwinięcie jednego klucza na dwa klucze, spodziewamy się, że otrzymane dwa klucze będą „wyglądać” niezależnie, a zatem twierdzenie będzie utrzymywać „moralnie”. W kryptografii teoretycznej istnieją sposoby na sprecyzowanie tego stwierdzenia.

Czy zatem powinniśmy XOR dwa generatory liczb pseudolosowych? Jeśli nie ogranicza nas prędkość, to z pewnością dobry pomysł. Ale w praktyce mamy ograniczenie prędkości. Następnie możemy zadać następujące pytanie. Załóżmy, że otrzymujemy dwa PRNG, każdy z parametrem który kontroluje czas działania (a więc i siłę) generatora. Na przykład może być długością LFSR lub liczbą rund. Załóżmy, że używamy jednego PRNG z parametrem , drugiego z parametrem , a XOR wynik. Możemy założyć, że , więc całkowity czas działania jest stały. Jaki jest najlepszy wybór$T$$T$$T_1$$T_2$$T_1 + T_2 = t$$T_1,T_2$? Tutaj jest kompromis, na który ogólnie trudno jest odpowiedzieć. Może się zdarzyć, że ustawienie jest znacznie gorsze niż lub .$(t/2,t/2)$$(t,0)$$(0,t)$

Najlepszą radą jest trzymanie się popularnego PRNG, który jest uważany za silny. Jeśli możesz poświęcić więcej czasu na wygenerowanie sekwencji, XOR kilka kopii, używając niezależnych kluczy (lub kluczy generowanych przez rozwinięcie jednego klucza za pomocą drogiego PRNG).

Dam temu szansę, ponieważ wystarczająco niepokoi mnie rada zawarta w niektórych innych odpowiedziach.

Niech będą nieskończonymi sekwencjami bitowymi generowanymi przez dwa RNG (niekoniecznie PRNG, które są deterministyczne po poznaniu stanu początkowego), i rozważamy możliwość użycia sekwencji z nadzieją na poprawę zachowania w pewnym sensie. Istnieje wiele różnych sposobów, w których można uznać za lepsze lub gorsze w porównaniu do każdego z i ; oto garstka, które moim zdaniem są znaczące, użyteczne i zgodne z normalnym użyciem słów „lepiej” i „gorzej”:$\vec{X},\vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X}$$\vec{Y}$

• (0) Prawdopodobieństwo prawdziwej losowości sekwencji wzrasta lub maleje
• (1) Prawdopodobieństwo zwiększenia lub zmniejszenia obserwowalnego braku losowości (prawdopodobnie w odniesieniu do niektórych obserwatorów stosujących pewną określoną kontrolę)
• (2) Nasilenie / oczywistość obserwowalnej nieprzypadkowości wzrasta lub maleje.

Najpierw zastanówmy się nad (0), który jest jedynym z trzech, który ma nadzieję, że zostanie sprecyzowany. Zauważ, że jeśli w rzeczywistości jeden z dwóch wejściowych RNG jest naprawdę losowy, bezstronny i niezależny od drugiego, wynik XOR będzie również naprawdę losowy i bezstronny. Mając to na uwadze, rozważ przypadek, w którym uważasz, że jest naprawdę przypadkowym, bezstronnym, izolowanym strumieniem bitów, ale nie jesteś całkowicie pewien. Jeśli są odpowiednimi prawdopodobieństwami, że mylisz się co do każdego z nich, wówczas prawdopodobieństwo, że nie jest tak naprawdę losowy, to , w rzeczywistości znacznie mniej od$\vec{X},\vec{Y}$$\varepsilon_X,\varepsilon_Y$$\vec{X} \oplus \vec{Y}$$\leq \varepsilon_X \varepsilon_Y \lt min\{\varepsilon_X,\varepsilon_Y\}$$\varepsilon_X,\varepsilon_Y$ przyjmuje się, że są bardzo bliskie zeru („uważasz, że są naprawdę przypadkowe”). I w rzeczywistości jest nawet lepsze, gdy weźmiemy również pod uwagę możliwość, że będzie naprawdę niezależny, nawet jeśli żadne z nich nie jest naprawdę losowe: Dlatego możemy stwierdzić, że w sensie (0) XOR nie może zaszkodzić i może potencjalnie bardzo pomóc.$\vec{X},\vec{Y}$

Jednak (0) nie jest interesujące dla PRNG, ponieważ w przypadku PRNG żadna z omawianych sekwencji nie ma szans na bycie naprawdę losową.

Dlatego w przypadku tego pytania, które w rzeczywistości dotyczy PRNG, musimy mówić o czymś takim jak (1) lub (2). Ponieważ są to właściwości i ilości, takie jak „obserwowalne”, „surowe”, „oczywiste”, „pozorne”, mówimy teraz o złożoności Kołmogorowa i nie zamierzam tego wyjaśniać. Ale posunę się tak daleko, aby uczynić, miejmy nadzieję, kontrowersyjną tezę, że według takiego środka „01100110 ...” (okres = 4) jest gorszy niż „01010101 ...” (okres = 2), który jest gorszy niż „ 00000000 ... ”(stała).

Teraz można się domyślać, że (1) i (2) będą podążać tą samą tendencją co (0), i dlatego wniosek „XOR nie może zranić” nadal może się utrzymywać. Zwróć jednak uwagę na znaczącą możliwość, że ani ani było zauważalnie nieprzypadkowe, ale że korelacje między nimi powodują, że jest zauważalnie nieprzypadkowy. Najcięższym przypadkiem tego jest oczywiście sytuacja, gdy (lub ), w którym to przypadku jest stały, najgorszy ze wszystkich możliwych wyników; ogólnie łatwo zauważyć, że niezależnie od tego, jak dobre są i ,$\vec{X}$$\vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X} = \vec{Y}$$\vec{X} = \mathrm{not}(\vec{Y})$$\vec{X} \oplus \vec{Y}$$\vec{X}$$\vec{Y}$$\vec{X}$i muszą być „bliskie” niezależności, aby ich xor nie był zauważalnie nielosowy. W rzeczywistości brak zależności, którą można zaobserwować, można rozsądnie zdefiniować jako która nie jest zauważalnie nieprzypadkowa.$\vec{Y}$$\vec{X} \oplus \vec{Y}$

Taka zależność od niespodzianek okazuje się naprawdę dużym problemem.

Przykład tego, co idzie nie tak

Pytanie brzmi: „Wykluczam wspólny przykład kilku rejestrów przesuwnych z liniowym sprzężeniem zwrotnym pracujących razem, ponieważ pochodzą one z tej samej rodziny”. Ale na razie wykluczę to wyłączenie, aby dać bardzo prosty, jasny przykład z życia rzeczy, które mogą się nie udać w XORing.

Moim przykładem będzie stara implementacja rand (), która była w jakiejś wersji Uniksa około 1983 roku. IIRC, ta implementacja funkcji rand () miała następujące właściwości:

• wartość każdego wywołania funkcji rand () wynosiła 15 pseudolosowych bitów, to jest liczb całkowitych z zakresu [0, 32767).
• kolejne zwracane wartości na przemian parzyste-nieparzyste-parzyste-nieparzyste; to znaczy najmniej zmienny bit na przemian 0-1-0-1 ...
• bit najmniej znaczący miał okres 4, następny miał okres 8, ... więc bit najwyższego rzędu miał okres .$2^{15}$
• dlatego sekwencja 15-bitowych wartości zwracanych przez rand () była okresowa z okresem .$2^{15}$

Nie udało mi się znaleźć oryginalnego kodu źródłowego, ale zgaduję, że poskładałem kilka postów z https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A tego zrobił dokładnie to (kod C), co zgadza się z moją pamięcią powyższych właściwości:

#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

Jak można sobie wyobrazić, próba użycia tego rand () na różne sposoby doprowadziła do szeregu rozczarowań.

Na przykład w pewnym momencie próbowałem symulować sekwencję losowych rzutów monetą, wielokrotnie wykonując:

rand() & 1

czyli najmniej znaczący bit. Wynik był prosty naprzemiennie głowice-ogony-głowice-ogony. Na początku trudno było w to uwierzyć (to musi być błąd w moim programie!), Ale po tym, jak przekonałem się, że to prawda, spróbowałem użyć następnego najmniej znaczącego bitu. Nie jest to o wiele lepsze, jak zauważono wcześniej - ten bit jest okresowy z okresem 4. Dalsze badanie kolejnych wyższych bitów ujawniło wzór, który zauważyłem wcześniej: to znaczy, że każdy następny bit wyższego rzędu miał dwa razy większy okres niż poprzedni, więc w pod tym względem bit najwyższego rzędu był najbardziej przydatny ze wszystkich. Zauważ jednak, że nie było czarno-białego progu „bit jest przydatny, bit nie jest użyteczny” tutaj; wszystko, co możemy naprawdę powiedzieć, to to, że numerowane pozycje bitów miały różny stopień przydatności / bezużyteczności.$i$$i-1$

Próbowałem także dalej mieszać wyniki lub XORing razem wartości zwracane z wielu wywołań funkcji rand (). XORing par kolejnych wartości rand () był oczywiście katastrofą - spowodował wszystkie nieparzyste liczby! Dla moich celów (mianowicie wytwarzanie „pozornie losowej” sekwencji rzutów monetą) wynik XOR o stałej parzystości był nawet gorszy niż naprzemienne zachowanie parzyste i nieparzyste oryginału.

Niewielka odmiana umieszcza to w oryginalnym frameworku: niech będzie sekwencją 15-bitowych wartości zwróconych przez rand () z danym ziarnem , a sekwencją z innego ziarna . Ponownie, będzie sekwencją liczb parzystych lub nieparzystych, co jest gorsze niż pierwotne zachowanie na przemian parzystych / nieparzystych.$\vec{X}$$s_X$$\vec{Y}$$s_Y$$\vec{X} \oplus \vec{Y}$

Innymi słowy, jest to przykład, w którym XOR pogorszył sytuację w sensie (1) i (2), przy jakiejkolwiek rozsądnej interpretacji. Gorzej jest również na kilka innych sposobów:

• (3) Bit najmniej znaczący XOR jest oczywiście stronniczy, tj. Ma nierówne częstotliwości zer i jedynek, w przeciwieństwie do jakiejkolwiek numerowanej pozycji bitu na którymkolwiek z wejść, które są całkowicie niezależne.
• (4) W rzeczywistości dla każdej pozycji bitu istnieją pary nasion, dla których ta pozycja bitu jest tendencyjna w wyniku XOR, a dla każdej pary nasion istnieją (co najmniej 5) pozycje bitu, które są tendencyjne w XOR wynik.
• (5) Okres całej sekwencji 15-bitowych wartości w wyniku XOR wynosi 1 lub , w porównaniu do dla oryginałów.$2^{14}$$2^{15}$

Żaden z (3), (4), (5) nie jest oczywisty, ale wszystkie można łatwo zweryfikować.

Na koniec zastanówmy się nad ponownym wprowadzeniem zakazu PRNG z tej samej rodziny. Problem w tym, jak sądzę, polega na tym, że nigdy tak naprawdę nie jest jasne, czy dwa PRNG są „z tej samej rodziny”, dopóki / chyba że ktoś zacznie używać XOR i zauważy (lub atakujący zauważy), że sytuacja pogorszyła się w sensie (1) i (2), tzn. dopóki nieprzypadkowe wzorce na wyjściu nie przekroczą progu od niezauważonego do zauważonego / zawstydzającego / katastrofalnego, i wtedy jest już za późno.

Jestem zaniepokojony innymi odpowiedziami, które udzielają niekwalifikowanej porady, że „XOR nie może zaszkodzić” na podstawie teoretycznych miar, które wydają się źle wykonywać modelowanie tego, co większość ludzi uważa za „dobre” i „złe” na temat PRNG w prawdziwym życiu. Ta rada jest sprzeczna z wyraźnymi i rażącymi przykładami, w których XOR pogarsza sytuację, takimi jak przykład rand () podany powyżej. Chociaż można sobie wyobrazić, że stosunkowo „silne” PRNG mogłyby konsekwentnie wykazywać odwrotne zachowanie, gdy XORed do zabawkowego PRNG, który był rand (), dzięki czemu XOR był dla nich dobrym pomysłem, nie widziałem żadnych dowodów w tym kierunku, teoretycznych lub empiryczny, więc nie wydaje mi się rozsądne zakładanie, że tak się dzieje.

Osobiście, będąc ugryzionym z zaskoczenia przez XORing rand () w mojej młodości i niezliczonymi innymi powiązaniami z niespodziankami przez całe moje życie, nie mam powodu, aby sądzić, że wynik będzie inny, jeśli spróbuję ponownie podobnej taktyki. Właśnie dlatego osobiście byłbym bardzo niechętny wobec XOR razem wielu PRNG, chyba że przeprowadzono bardzo obszerną analizę i weryfikację, aby dać mi pewność, że może to być bezpieczne dla poszczególnych RNG, o których mowa. Jako potencjalne lekarstwo na to, kiedy mam niskie zaufanie do jednego lub więcej indywidualnych PRNG, XOR nie jest w stanie zwiększyć mojej pewności, więc raczej nie użyję go do takiego celu. Wyobrażam sobie, że odpowiedź na twoje pytanie jest taka, że ​​jest to powszechne przekonanie.

OŚWIADCZENIE: Ta odpowiedź dotyczy wyłącznie „Nie robimy tego”, a nie „oto matematyczny dowód, dlaczego może lub nie może działać”. Nie twierdzę, że XOR wprowadza (lub nie) jakiekolwiek luki w zabezpieczeniach kryptograficznych. Chodzi mi tylko o to, że doświadczenie pokazuje nam, że nawet najprostsze schematy prawie zawsze powodują nieprzewidziane konsekwencje - i dlatego ich unikamy.

„Losowość” to tylko wierzchołek góry lodowej, jeśli chodzi o RNG i PRNG. Istnieją inne cechy, które są ważne, np. Jednolitość.

Wyobraź sobie zwykłą kostkę, która sama w sobie jest całkiem dobrym RNG. Ale powiedzmy teraz, że potrzebujesz zakresu 1-5 zamiast 1-6. Pierwszą rzeczą, która przychodzi na myśl, jest po prostu wymazanie 6 twarzy i zastąpienie jej dodatkowym 1. „Losowość” pozostaje (wyniki są nadal naprawdę losowe), jednak jednorodność bardzo cierpi: teraz 1 jest dwa razy bardziej prawdopodobne niż inne wyniki.

Łączenie wyników z wielu RNG jest podobnie śliskie nachylenie. Na przykład. proste dodanie 2 rzutów kostką całkowicie usuwa wszelką jednolitość, ponieważ „7” jest teraz 6 razy bardziej prawdopodobne niż „2” lub „12”. Zgadzam się, że XOR wygląda lepiej niż dodawanie na pierwszy rzut oka, ale w PRNG nic nie wychodzi, jak wygląda na pierwszy rzut oka.

Właśnie dlatego trzymamy się znanych implementacji - ponieważ ktoś spędził mnóstwo czasu i pieniędzy na ich badaniu, a wszystkie niedociągnięcia są dobrze znane, zrozumiałe i można je obejść. Wdrażając własne, możesz stworzyć luki i powinieneś podjąć podobne wysiłki, aby to udowodnić. Jak pokazuje przykład dodawania kości, łączenie nie może bardzo różnić się od tworzenia nowego od zera.

Bezpieczeństwo to łańcuch tak silny, jak jego najsłabszy element. Praktyczna zasada bezpieczeństwa: za każdym razem, gdy łączysz 2 rzeczy, zwykle dostajesz sumę wad, a nie sumę mocnych stron.