Perl: l'output di rand() è parzialmente prevedibile?

Question

Stavo giocando con perl's rand() e ho notato che quando si fornisce un argomento più grande di 2^32, gli ultimi bit dell'output diventano prevedibili.

Il modo più chiaro che ho trovato di illustrare è con il seguente script:

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

Ogni volta che eseguo che l'uscita è

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

(Non sono solo i primi 10 valori, ma Non ho visto un punto copiare una lunga lista di numeri "casuali")

La chiamata a srand() è superflua, ma è lì per rendere più facile fornire un argomento, e vedere che non lo fa cambia qualcosa.

Ho provato questo su:

• Debian Squeeze con Perl 5.10 (randbits = 48)
• Debian wheezy con Perl 5.14 (randbits = 48)
• Debian Jessie con Perl 5.20 (randbits = 48)

So che rand() non dovrebbe essere crittograficamente sicuro, ma gli ultimi 16 bit prevedibili sono peggiori di quelli che avevo capito. Sto usando una qualsiasi delle funzioni sbagliate?

Answer 1

Non si tratta solo dell'implementazione del seme "predefinito" (srand chiamato senza argomento o non chiamato affatto), come si potrebbe pensare dalla risposta di Schwern che era collegata in un commento; tutte le chiamatesrand (e quindi tutti i mezzi per inizializzare lo stato RNG) sono soggette a questo problema.

Attualmente (dal 5.20) perl utilizza la propria implementazione RNG basata su drand48 di FreeBSD e srand48; prima di questo, perl usato drand48 e srand48 se disponibile, quindi il comportamento su Linux era effettivamente lo stesso. In entrambi i casi, l'implementazione di srand utilizza solo 32 bit di input, posizionandoli nei 32 bit superiori dello stato RNG a 48 bit; i 16 bit inferiori vengono inizializzati su 0x330e. Se si esegue 0x330e attraverso un round dell'algoritmo LCG (solo i 16 bit inferiori dello stato precedente sono necessari per ottenere i 16 bit inferiori dello stato successivo), moltiplicando per 0xe66d e aggiungendo 0x000b, si finisce con 0x5101 che è il il primo valore che osservi

Ovviamente questa prevedibilità nei bit in basso è negativa, e non sono sicuro del motivo per cui non è stata affrontata soprattutto ora che perl ha una propria implementazione RNG che potrebbe facilmente essere pulita a 48 bit. Ovviamente è meno dannoso che avere il alto bit sempre inizializzato ad uno stato conosciuto, comunque.

Al momento, vorrei raccomandare che se si vuole fare qualcosa di serio con RNG di Perl, usarlo per al massimo 32 bit per chiamata, combinando più chiamate se necessario per ottenere una maggiore precisione/gamma.