Czy java.util.Random naprawdę jest tak losowy? Jak mogę wygenerować 52! (silnie) możliwe sekwencje?

Użyłem, Random (java.util.Random)aby przetasować talię 52 kart. Jest 52! (8.0658175e + 67) możliwości. Jednak dowiedziałem się, że ziarno dla java.util.Randomjest o longwiele mniejsze przy 2 ^ 64 (1.8446744e + 19).

Stąd jestem podejrzliwy, czy java.util.Random to naprawdę tak losowe ; czy jest w stanie wygenerować wszystkie 52! możliwości?

Jeśli nie, jak mogę w sposób niezawodny wygenerować lepszą losową sekwencję, która może wygenerować wszystkie 52! możliwości?

Wybór losowej permutacji wymaga jednocześnie coraz mniej losowości niż sugeruje to pytanie. Pozwól mi wyjaśnić.

Zła wiadomość: potrzeba więcej losowości.

Podstawową wadą twojego podejścia jest to, że stara się wybierać między ~ 2 ²²⁶ możliwościami, używając 64 bitów entropii (losowego ziarna). Aby rzetelnie wybrać pomiędzy ~ ²²²⁶ możliwościami, będziesz musiał znaleźć sposób na wygenerowanie 226 bitów entropii zamiast 64.

Istnieje kilka sposobów generowania losowych bitów: dedykowany sprzęt , instrukcje procesora , interfejsy systemu operacyjnego , usługi online . W twoim pytaniu jest już domniemane założenie, że możesz w jakiś sposób wygenerować 64 bity, więc po prostu zrób to, co zamierzałeś zrobić, tylko cztery razy, i przekaż nadwyżki na cele charytatywne. :)

Dobra wiadomość: potrzeba mniej losowości.

Gdy masz już 226 losowych bitów, resztę można wykonać deterministycznie, a więc właściwości java.util.Randommożna uczynić nieistotnymi . Oto jak.

Powiedzmy, że wygenerowaliśmy wszystkie 52! permutacje (opatrzcie mnie) i posortuj je leksykograficznie.

Aby wybrać jedną z permutacji, potrzebujemy tylko jednej losowej liczby całkowitej między 0i 52!-1. Ta liczba całkowita to nasze 226 bitów entropii. Użyjemy go jako indeksu do naszej posortowanej listy permutacji. Jeśli indeks jest losowo rozmieszczone równomiernie, nie tylko pan zagwarantować, że wszystkie permutacje mogą być wybrane, zostaną one wybrane equiprobably (która jest silniejsza niż gwarancja pytanie jest pytaniem).

Teraz nie musisz generować wszystkich tych permutacji. Możesz go wytworzyć bezpośrednio, biorąc pod uwagę jego losowo wybraną pozycję z naszej hipotetycznej listy posortowanej. Można tego dokonać w czasie O (n ² ) za pomocą kodu Lehmera ^[1] (patrz także permutacje numeracji i system liczbowy współczynnika ). N jest tutaj wielkością twojej talii, tj. 52.

Jest to implementacja C w tym StackOverflow odpowiedź . Istnieje kilka zmiennych całkowitych, które przepełniłyby się dla n = 52, ale na szczęście w Javie możesz użyć java.math.BigInteger. Resztę obliczeń można przepisać prawie tak, jak jest:

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

^[1] Nie mylić z Lehrerem . :)

Twoja analiza jest poprawna: zaszczepienie generatora liczb pseudolosowych dowolnym konkretnym ziarnem po tasowaniu musi dać tę samą sekwencję, ograniczając liczbę możliwych permutacji do 2 ⁶⁴ . To twierdzenie jest łatwe do zweryfikowania eksperymentalnego poprzez Collection.shuffledwukrotne wywołanie , przekazanie Randomobiektu zainicjowanego tym samym ziarnem i zaobserwowanie, że dwa losowe losowania są identyczne.

Rozwiązaniem tego jest użycie generatora liczb losowych, który pozwala na większe ziarno. Java zapewnia SecureRandomklasę, którą można zainicjować za pomocą byte[]tablicy o praktycznie nieograniczonym rozmiarze. Następnie można przejść instancję SecureRandomaby Collections.shufflewykonać zadanie:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

Ogólnie rzecz biorąc, generator liczb pseudolosowych (PRNG) nie może wybierać spośród wszystkich permutacji listy 52-elementowej, jeśli jego długość stanu jest mniejsza niż 226 bitów.

java.util.Randomimplementuje algorytm o module 2 ⁴⁸ ; dlatego jego długość stanu wynosi tylko 48 bitów, czyli o wiele mniej niż 226 bitów, o których mówiłem. Będziesz musiał użyć innego PRNG o większej długości stanu - szczególnie takiego z okresem 52 silni lub dłuższym.

Zobacz także „Tasowanie” w moim artykule na temat generatorów liczb losowych .

Ta uwaga jest niezależna od charakteru PRNG; dotyczy to w równym stopniu kryptograficznych, jak i niekryptograficznych programów PRNG (oczywiście niekryptograficzne programy PRNG są nieodpowiednie, gdy dotyczy to bezpieczeństwa informacji).

Chociaż java.security.SecureRandomzezwala na przekazywanie nasion o nieograniczonej długości, SecureRandomimplementacja może wykorzystywać bazowy PRNG (np. „SHA1PRNG” lub „DRBG”). I zależy od okresu tego PRNG (oraz, w mniejszym stopniu, długości stanu), czy jest on w stanie wybierać spośród 52 silnych permutacji. (Zauważ, że definiuję „długość stanu” jako „maksymalny rozmiar nasion, które PRNG może przyjąć, aby zainicjować swój stan bez skracania lub ściskania tego ziarna ”).

Przepraszam z góry, ponieważ jest to trochę trudne do zrozumienia ...

Po pierwsze, wiesz już, że java.util.Randomto wcale nie jest przypadkowe. Generuje sekwencje w całkowicie przewidywalny sposób z nasion. Masz całkowitą rację, ponieważ ponieważ ziarno ma tylko 64 bity, może wygenerować tylko 2 ^ 64 różnych sekwencji. Jeśli miałbyś w jakiś sposób wygenerować 64 prawdziwe losowe bity i użyć ich do wyboru ziarna, nie możesz użyć tego ziarna do losowego wyboru spośród wszystkich 52! możliwe sekwencje z jednakowym prawdopodobieństwem.

Jednak fakt ten nie ma znaczenia, o ile nie zamierzasz wygenerować więcej niż 2 ^ 64 sekwencji, o ile nie ma nic „specjalnego” ani „zauważalnie specjalnego” w sekwencjach 2 ^ 64, które może wygenerować .

Powiedzmy, że miałeś znacznie lepszy PRNG, który używał 1000-bitowych nasion. Wyobraź sobie, że masz dwa sposoby na zainicjowanie go - jeden sposób zainicjowałby go przy użyciu całego ziarna, a jeden sposób skróciłby ziarno do 64 bitów przed jego zainicjowaniem.

Jeśli nie wiesz, który inicjator jest który, to czy mógłbyś napisać test, aby je rozróżnić? Jeśli nie miałeś (aś) szczęścia na tyle, by skończyć inicjowanie złego z tymi samymi 64 bitami dwa razy, odpowiedź brzmi: nie. Nie można było rozróżnić dwóch inicjatorów bez szczegółowej wiedzy o słabościach w konkretnej implementacji PRNG.

Alternatywnie, wyobraź sobie, że Randomklasa miała tablicę 2 ^ 64 sekwencji, które zostały wybrane całkowicie i losowo w pewnym momencie w odległej przeszłości i że ziarno było tylko indeksem do tej tablicy.

Tak więc fakt, że Randomużywa tylko 64 bitów dla jego nasienie, jest rzeczywiście nie koniecznie problem statystycznie, tak długo jak nie ma znaczącej szansa, że będzie korzystać z tego samego materiału siewnego dwukrotnie.

Oczywiście do celów kryptograficznych 64-bitowe ziarno nie jest wystarczające, ponieważ dwukrotne użycie systemu do tego samego zarodka jest wykonalne obliczeniowo.

EDYTOWAĆ:

Powinienem dodać, że pomimo tego, że wszystkie powyższe informacje są poprawne, faktyczna implementacja java.util.Randomnie jest niesamowita. Jeśli piszesz grę karcianą, może użyj MessageDigestinterfejsu API do wygenerowania skrótu SHA-256 "MyGameName"+System.currentTimeMillis()i użyj tych bitów do przetasowania talii. Zgodnie z powyższym argumentem, tak długo, jak użytkownicy naprawdę nie uprawiają hazardu, nie musisz się martwić, że currentTimeMillispowróci on długo. Jeśli użytkownicy są naprawdę hazardu, a następnie użyć SecureRandombez nasion.

Zamierzam zająć się tym trochę inaczej. Masz rację - twoje PRNG nie będzie w stanie trafić wszystkich 52! możliwości.

Pytanie brzmi: jaka jest skala twojej gry karcianej?

Jeśli tworzysz prostą grę w stylu klondike? Zatem zdecydowanie nie potrzebujesz wszystkich 52! możliwości. Zamiast tego spójrz na to w ten sposób: gracz będzie miał 18 quintillion różnych gier. Nawet biorąc pod uwagę „problem urodzinowy”, musieliby rozegrać miliardy rozdań, zanim wpadną na pierwszą zduplikowaną grę.

Jeśli wykonujesz symulację Monte Carlo? Więc prawdopodobnie nic ci nie jest . Być może będziesz musiał poradzić sobie z artefaktami z powodu „P” w PRNG, ale prawdopodobnie nie będziesz mieć problemów po prostu z powodu niskiej przestrzeni początkowej (ponownie, patrzysz na kwintilliony wyjątkowych możliwości). z drugiej strony, jeśli pracujesz z dużą liczbą iteracji, to tak, twoja niska przestrzeń początkowa może być przełomowa.

Jeśli tworzysz grę karcianą dla wielu graczy, szczególnie jeśli na linii są pieniądze? Będziesz musiał trochę popracować nad tym, jak strony pokera online poradziły sobie z tym samym problemem, o który pytasz. Ponieważ chociaż problem niskiej przestrzeni początkowej nie jest zauważalny dla przeciętnego gracza, można ją wykorzystać, jeśli jest warta zainwestowania czasu. (The poker wszyscy przeszli przez fazę, gdzie ich PRNGs były „hacked”, pozwalając ktoś zobaczyć zakryte karty wszystkich innych graczy, po prostu przez dedukcję ziarno od odsłoniętych kart). Jeśli jest to sytuacja, że jesteś w, don „t po prostu znaleźć lepsze PRNG - trzeba traktować je jako poważnie jako problem Crypto.

Krótkie rozwiązanie, które zasadniczo jest takie samo jak dasblinkenlight:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

Nie musisz się martwić o stan wewnętrzny. Długie wyjaśnienie, dlaczego:

Po utworzeniu SecureRandominstancji w ten sposób uzyskuje ona dostęp do generatora liczb losowych specyficznych dla systemu operacyjnego. Jest to albo pula entropii, do której uzyskuje się dostęp do wartości, które zawierają losowe bity (np. Dla timera nanosekundowego precyzja nanosekundowa jest zasadniczo losowa) lub wewnętrzny generator liczb sprzętowych.

Te dane wejściowe (!), Które mogą nadal zawierać fałszywe ślady, są wprowadzane do kryptograficznie silnego skrótu, który usuwa te ślady. Właśnie dlatego te CSPRNG są używane, a nie same w sobie! SecureRandomPosiada licznik, który śledzi liczbę bitów użyto ( getBytes(), getLong()itd.) I napełnia ponownie SecureRandomz entropii bitów, gdy konieczne .

W skrócie: Po prostu zapomnij o zastrzeżeniach i użyj SecureRandomjako prawdziwego generatora liczb losowych.

Jeśli uważasz liczbę za zwykłą tablicę bitów (lub bajtów), być może możesz użyć (Bezpiecznych) Random.nextBytesrozwiązań sugerowanych w tym pytaniu Przepełnienie stosu , a następnie zamapować tablicę na new BigInteger(byte[]).

Bardzo prostym algorytmem jest zastosowanie SHA-256 do sekwencji liczb całkowitych rosnących od 0 w górę. (W razie potrzeby można dodać sól, aby „uzyskać inną sekwencję”.) Jeśli założymy, że wyjście SHA-256 jest „tak dobre, jak” równomiernie rozłożone liczby całkowite między 0 a 2 ^256-1, to mamy wystarczającą entropię dla zadanie.

Aby uzyskać permutację z wyjścia SHA256 (wyrażonego jako liczba całkowita), wystarczy po prostu ją zmniejszyć modulo 52, 51, 50 ... jak w tym pseudokodzie:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]