Come altri hanno spiegato, il "periodo" misura il numero di bit di uscita (o "parole", a seconda della terminologia) dopo di che il PRNG inizia a ripetersi. Per alcuni PRNG questo è relativamente mal definito. Un PRNG è un algoritmo deterministico con uno stato (il contenuto dei suoi buffer interni, contatori e variabili). La sequenza di bit successivamente emessi dipende interamente da quello stato. Se il PRNG usa uno stato finito (cioè si inserisce in una quantità fissa di RAM, senza allocazione dinamica illimitata della memoria) allora matematicamente inizierà a ripetere se stesso ad un certo punto, perché ci sono solo un numero finito di valori possibili per lo stato completo.
Non tutti i PRNG sono reversibili. Il PRNG è deterministico, ovvero da un determinato valore di stato S , il successivo bit di output e lo stato successivo S ' possono essere calcolati in modo non ambiguo. Un PRNG reversibile è tale che a condizione di S , esiste un stato S precedente univoco per cui S è il successore. LFSR sono tradizionali PRNG reversibili.
Un esempio di PRNG non reversibile è il seguente PRNG basato su hash:
- Usiamo una funzione di hash h , con un output n -bit.
- Stato S è un buffer di n bit.
- Per produrre il bit successivo, calcoliamo h (0 || S) (hash della concatenazione di un bit di valore 0, quindi S ); il primo bit dell'output è il bit successivo; quindi calcoliamo il nuovo stato S '= h (1 || S) .
Si noti che questo è solo un esempio; Non rivendico la sicurezza crittografica di quel PRNG. Poiché ci sono solo 2 n valori possibili per S , dobbiamo necessariamente incontrare un valore di stato già visto dopo al massimo 2 < sup> n +1 passi, quindi il "periodo" non sarà più di 2 n . Tuttavia, la funzione che calcola h (1 || x) da x non è una permutazione; si prevede che abbia collisioni. Ciò implica che quando il PRNG "loop", è piuttosto improbabile che ritorni al nostro valore di stato iniziale . Invece, ci aspettiamo (in media, a seconda della funzione di hash h ) che tale PRNG effettui un ciclo su un ciclo di lunghezza su 2 n / 2 ; e raggiungeremo quel ciclo dopo di nuovo una media 2 n / 2 passaggi. Ciò implica che i primi bit 2 n / 2 saranno (probabilmente) non ripetuti.
In questo senso, il "periodo" non misura tutto ciò che si deve sapere su un PRNG. In effetti, è per lo più poco pratico: nell'esempio basato su hash di cui sopra, il "periodo" non può essere misurato prontamente e descrive il comportamento del PRNG in condizioni che in pratica non saranno raggiungibili.
Il punto importante qui è che il periodo non è una misura di sicurezza . I crittografi non si preoccupano del periodo. Period dice qualcosa sulla sicurezza solo nel caso particolare che sia così breve da poter essere realisticamente esplorato. Tuttavia, qualsiasi periodo oltre 2 64 o così è "abbastanza grande" e diventa irrilevante.
Infatti, se la descrizione di un PRNG parla del periodo, allora è un'indicazione molto precisa che il PRNG non è stato progettato o analizzato da un crittografo, e non mira alla sicurezza crittografica (e di solito non lo fornirà neanche). Infatti, il Mersenne Twister è pensato per i grandi lavori di simulazione fisica, in cui non c'è attaccante da sconfiggere tranne una natura senza mente. I crittografi sono più esigenti, dal momento che vogliono contrastare un nemico intelligente che cerca davvero di indovinare i prossimi bit.