Generador de pasos alternos

En criptografía , un generador de pasos alternados ( ASG ) es un generador criptográfico de números pseudoaleatorios utilizado en cifrados de flujo , basado en tres registros de desplazamiento con retroalimentación lineal . Su salida es una combinación de dos LFSR que se escalonan (sincronizan) de manera alternada, dependiendo de la salida de un tercer LFSR.

El diseño fue publicado en 1987 y patentado en 1989 por CG Günther. ^{[1] [2]}

Los registros de desplazamiento con retroalimentación lineal (LFSR) son, estadísticamente hablando, excelentes generadores pseudoaleatorios, con buena distribución e implementación simple. Sin embargo, no se pueden utilizar tal como están porque su salida se puede predecir fácilmente.

Un ASG consta de tres registros de desplazamiento con retroalimentación lineal , que llamaremos LFSR0, LFSR1 y LFSR2 para mayor comodidad. La salida de uno de los registros decide cuál de los otros dos se utilizará; por ejemplo, si LFSR2 genera un 0, se sincroniza LFSR0, y si genera un 1, se sincroniza LFSR1 en su lugar. La salida es el OR exclusivo del último bit producido por LFSR0 y LFSR1. El estado inicial de los tres LFSR es la clave.

Habitualmente, los LFSR utilizan polinomios primitivos de grado distinto pero cercano, preestablecidos en un estado distinto de cero, de modo que cada LFSR genera una secuencia de longitud máxima . Bajo estas suposiciones, el resultado del ASG tiene demostrablemente un período largo, una alta complejidad lineal y una distribución uniforme de subsecuencias cortas.

Código de ejemplo en C :

/* ASG de juguete de 16 bits (demasiado pequeño para un uso práctico); devuelve 0 o 1. */ unsigned ASG16toy ( void ) { static unsigned /* tipo sin signo con al menos 16 bits */ lfsr2 = 0x8102 , /* estado inicial, 16 bits, no debe ser 0 */ lfsr1 = 0x4210 , /* estado inicial, 15 bits, no debe ser 0 */ lfsr0 = 0x2492 ; /* estado inicial, 14 bits, no debe ser 0 */                 /* LFSR2 utiliza x^^16 + x^^14 + x^^13 + x^^11 + 1 */ lfsr2 = ( - ( lfsr2 & 1 )) & 0x8016 ^ lfsr2 >> 1 ;      si ( lfsr2 & 1 ) /* LFSR1 usa x^^15 + x^^14 + 1 */ lfsr1 = ( - ( lfsr1 & 1 )) & 0x4001 ^ lfsr1 >> 1 ; de lo contrario /* LFSR0 usa x^^14 + x^^13 + x^^3 + x^^2 + 1 */ lfsr0 = ( - ( lfsr0 & 1 )) & 0x2C01 ^ lfsr0 >> 1 ;               devolver ( lfsr0 ^ lfsr1 ) & 1 ; }   

Un ASG es muy sencillo de implementar en hardware. En particular, a diferencia del generador de contracción y el generador de contracción automática , se produce un bit de salida en cada reloj, lo que garantiza un rendimiento constante y resistencia a los ataques de sincronización .

Shahram Khazaei, Simon Fischer y Willi Meier ^[3] ofrecen un criptoanálisis del ASG que permite varias compensaciones entre la complejidad temporal y la cantidad de salida necesaria para montar el ataque, por ejemplo, con complejidad asintótica y bits, donde es el tamaño del más corto de los tres LFSR.${\displaystyle O(L^{2}.2^{2L/3})}$${\displaystyle O(2^{2L/3})}$${\estilo de visualización L}$

• Schneier, Bruce. Criptografía aplicada (págs. 383-384), segunda edición, John Wiley & Sons, 1996. ISBN 0-471-11709-9