Perl: dane wyjściowe funkcji rand() są częściowo przewidywalne?

Question

Grałem z perl's rand() i zauważyłem, że dostarczając argument większy niż 2^32, ostatnie bity wyjścia stają się przewidywalne.

Najbardziej wyraźny sposób znalazłem z ilustrujący to z poniższego skryptu:

srand(); for $i (1..10) { printf "%4x\n",rand(2**48)%2**16 } 

Ilekroć wykonać, że wyjście jest

5101 
6378 
2a23 
62f2 
8d15 
effc 
9657 
2d16 
f669 
40c0 

(to nie tylko pierwsze 10 wartości, ale Nie widziałem punktu kopiowania długiej listy "losowych" numerów)

Wywołanie srand() jest zbędne, ale jest po to, aby ułatwić dostarczenie argumentu i zobaczenie, że nie zmienić cokolwiek.

Próbowałem to na:

• Debian Squeeze mających Perla 5.10 (randbits = 48)
• Debiana świszczące mających Perla 5,14 (randbits = 48)
• Jessie Debian mających Perla 5,20 (randbits = 48)

Wiem, że rand() nie ma być kryptograficznie bezpieczny, ale ostatnie 16 bitów jest przewidywalne, jest gorsze niż to, co zrozumiałem. Czy używam żadnej z tych funkcji?

Answer 1

Nie jest to tylko implementacja "domyślnego" materiału siewnego (srand wywołanego bez argumentów lub w ogóle nie wywołanego), jak można sądzić po odpowiedzi Schwern'a, która została powiązana w komentarzu; wszystkie wywołaniasrand (a więc wszystkie środki inicjowania stanu RNG) podlegają temu problemowi.

Obecnie (od 5,20) perl wykorzystuje własną implementację RNG opartą na FreeBSD's drand48 i srand48; wcześniej, perl używany drand48 i srand48, jeśli są dostępne, więc zachowanie na Linuksie było faktycznie takie samo. W obu przypadkach implementacja srand wykorzystuje tylko 32 bity wejścia, umieszczając je w 32-bitowych 32-bitowych stanach RNG; dolne 16 bitów zostało zainicjowanych na 0x330e. Jeśli uruchomisz 0x330e przez jedną rundę algorytmu LCG (tylko dolne 16 bitów poprzedniego stanu są konieczne, aby uzyskać 16 dolnych bitów następnego stanu), pomnożenie przez 0xe66d i dodanie 0x000b, kończy się na 0x5101, który jest pierwsza wartość, którą obserwujesz.

Oczywiście ta przewidywalność w dolnych bitach jest zła i nie jestem pewien, dlaczego nie została ona rozwiązana, zwłaszcza teraz, gdy perl ma własną implementację RNG, która może być z łatwością 48-bitowa. Oczywiście jest to mniej szkodliwe niż posiadanie bitów zawsze zainicjowanych w znanym stanie.

W tej chwili, polecam, jeśli chcesz zrobić coś poważnego z RNG perl, użyj go do co najwyżej 32 bity na połączenie, łącząc wiele połączeń, jeśli to konieczne, aby uzyskać większą precyzję/zasięg.