Como han explicado otros, el "período" mide el número de bits de salida (o "palabras", según la terminología) después de lo cual el PRNG comienza a repetirse. Para algunos PRNG esto está relativamente mal definido. Un PRNG es un algoritmo determinístico con un estado (el contenido de sus buffers internos y contadores y variables). La secuencia de los bits emitidos posteriormente depende completamente de ese estado. Si el PRNG usa un estado finito (es decir, se ajusta a una cantidad fija de RAM, sin asignación de memoria dinámica ilimitada), entonces matemáticamente comenzará a repetirse en algún punto, porque solo hay un número finito de valores posibles. para el estado completo.
No todos los PRNG son reversibles. El PRNG es determinista, lo que significa que a partir de un valor de estado dado S , el siguiente bit de salida y el estado subsiguiente S ' se pueden calcular de forma inequívoca. Un reversible PRNG es tal que, dado el estado S , existe un único estado anterior S '' para el cual S es el sucesor LFSR son PRNG reversibles tradicionales.
Un ejemplo de PRNG no reversible es el siguiente PRNG basado en hash:
- Utilizamos una función hash h , con una salida de n -bit.
- El estado S es un búfer de n bits.
- Para producir el siguiente bit, calculamos h (0 || S) (hash de la concatenación de un bit de valor 0, luego S ); el primer bit de la salida es el siguiente bit; luego calculamos el nuevo estado S '= h (1 || S) .
Tenga en cuenta que esto es solo un ejemplo; No pretendo la seguridad criptográfica de ese PRNG. Dado que solo hay 2n valores posibles para S , necesariamente debemos encontrar un valor de estado ya visto después de a lo sumo 2 < Sup> n +1 pasos, por lo que el "período" no será más que 2n . Sin embargo, la función que calcula h (1 || x) de x no es una permutación; se espera que tenga colisiones. Esto implica que cuando el PRNG "hace un bucle", es bastante improbable que vuelva a nuestro valor de estado inicial . En cambio, esperamos (en promedio, dependiendo de la función de hash h ) que dicho PRNG realice un ciclo de duración de aproximadamente 2 n / 2 ; y alcanzaremos ese ciclo luego de un nuevo promedio de pasos 2n/2 . Esto implica que los primeros 2n/2 bits producidos (probablemente) no se repetirán.
En ese sentido, el "período" no mide todo lo que se debe saber acerca de un PRNG. De hecho, es en su mayoría poco práctico: en el ejemplo anterior basado en hash, el "período" no se puede medir fácilmente, y describe el comportamiento del PRNG en condiciones que en realidad no serán alcanzables en la práctica.
El punto importante aquí es que el período no es una medida de seguridad . Los criptógrafos no se preocupan por el período. El período dice algo sobre la seguridad solo en el caso especial de que sea tan breve que se pueda explorar de manera realista. Sin embargo, cualquier período más allá de 264 o más es "suficientemente grande" y se vuelve irrelevante.
De hecho, si la descripción de un PRNG habla sobre el período, es una indicación muy clara de que el PRNG no fue diseñado o analizado por un criptógrafo, y no apunta a la seguridad criptográfica (y por lo general tampoco lo proporcionará). De hecho, el Mersenne Twister está destinado a grandes trabajos de simulación de física, donde no hay un atacante que derrotar, excepto una Naturaleza sin mente. Los criptógrafos son más exigentes, ya que quieren derrotar a un enemigo inteligente que intenta realmente adivinar los siguientes bits.