Generador de reducción automática

Un generador autoencogible es un generador pseudoaleatorio basado en el concepto de generador encogible . Se estudian variantes del generador autoencogible basadas en un registro de desplazamiento con retroalimentación lineal (LFSR) para su uso en criptografía .

A diferencia del generador de contracción , que utiliza un segundo registro de desplazamiento con retroalimentación para controlar la salida del primero, el generador de autocontracción utiliza bits de salida alternos de un solo registro para controlar su salida final. El procedimiento para sincronizar este tipo de generador es el siguiente:

1. Se activa el LFSR dos veces para obtener un par de bits como salida del LFSR.
2. Si el par es 10, la salida es cero.
3. Si el par es 11, la salida es uno.
4. De lo contrario, no se mostrará nada.
5. Regresa al paso uno.

Este ejemplo utilizará el polinomio de conexión x ⁸ + x ⁴ + x ³ + x ² + 1 , y un llenado inicial del registro de 1 0 1 1 0 1 1 0 .

La tabla que se muestra a continuación enumera, para cada iteración del LFSR , su salida intermedia antes de la auto-reducción, así como la salida final del generador. Las posiciones de los puntos de conexión, definidas por el polinomio de conexión, están marcadas con encabezados azules. El estado de la iteración cero representa la entrada inicial.

Al final de cuatro iteraciones, se produce la siguiente secuencia de bits intermedios: 0110 .

El primer par de bits, 01 , se descarta ya que no coincide ni con 10 ni con 11. El segundo par de bits, 10 , coincide con el segundo paso del algoritmo, por lo que se obtiene un cero.

Se crean más bits al continuar sincronizando el LFSR y reduciendo su salida como se describió anteriormente.

Al igual que el generador decreciente, el generador autoencogible es vulnerable a ataques de temporización , ya que la tasa de salida varía según el estado.

En su artículo, ^{[ 1 ]} Meier y Steffelbach demuestran que un generador autoencogible basado en LFSR con un polinomio de conexión de longitud L da como resultado un período de secuencia de salida de al menos 2 ^L/2 , y una complejidad lineal de al menos 2 ^L/2-1 .

Además, demuestran que cualquier generador autoencogible puede representarse como un generador encogible. Lo contrario también es cierto: cualquier generador encogible puede implementarse como un generador autoencogible, aunque el generador resultante no tenga la longitud máxima.

Un ataque presentado por los autores requiere aproximadamente 2 ^0,7L pasos, suponiendo un polinomio de conexión conocido.

Un ataque más avanzado, ^{[ 2 ]} descubierto por Mihaljević, es capaz de romper un registro de cien bits de longitud en aproximadamente 2 ⁵⁷ pasos, utilizando una secuencia de salida de solo 4,9 × 10 ⁸ bits.

Otro ataque ^{[ 3 ]} requiere 2 pasos ^{de 0,694L} .

• Manual de criptografía aplicada