En criptografía , un generador de pasos alternos ( ASG ) es un generador de números pseudoaleatorios criptográfico utilizado en cifrados de flujo , basado en tres registros de desplazamiento de retroalimentación lineal . Su salida es una combinación de dos LFSR que están escalonados (sincronizados) de forma alterna, 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]
Descripción general
Los registros de desplazamiento de retroalimentación lineal (LFSR) son, estadísticamente hablando, excelentes generadores pseudoaleatorios, con buena distribución e implementación simple. Sin embargo, no se pueden usar tal cual porque su salida se puede predecir fácilmente.
Un ASG comprende tres registros de desplazamiento de retroalimentación lineal , que llamaremos LFSR0, LFSR1 y LFSR2 por conveniencia. La salida de uno de los registros decide cuál de los otros dos se utilizará; por ejemplo, si LFSR2 emite un 0, LFSR0 se sincroniza, y si emite un 1, LFSR1 se sincroniza 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 estos supuestos, la salida del ASG tiene un período largo, una complejidad lineal alta e incluso una distribución de subsecuencias cortas.
Código de ejemplo en C :
/ * Juguete ASG de 16 bits (demasiado pequeño para un uso práctico); devuelve 0 o 1. * / unsigned ASG16toy ( void ) { static unsigned / * unsigned type con al menos 16 bits * / lfsr2 = 0x8102 , / * estado inicial, 16 bits, no debe ser 0 * / lfsr1 = 0x4210 , / * el estado inicial, 15 bits, no debe ser 0 * / lfsr0 = 0x2492 ; / * estado inicial, 14 bits, no debe ser 0 * / / * LFSR2 usa x ^^ 16 + x ^^ 14 + x ^^ 13 + x ^^ 11 + 1 * / lfsr2 = ( - ( lfsr2 & 1 )) & 0x8016 ^ lfsr2 >> 1 ; if ( lfsr2 & 1 ) / * LFSR1 use x ^^ 15 + x ^^ 14 + 1 * / lfsr1 = ( - ( lfsr1 & 1 )) & 0x4001 ^ lfsr1 >> 1 ; else / * LFSR0 use x ^^ 14 + x ^^ 13 + x ^^ 3 + x ^^ 2 + 1 * / lfsr0 = ( - ( lfsr0 & 1 )) & 0x2C01 ^ lfsr0 >> 1 ; return ( lfsr0 ^ lfsr1 ) & 1 ; }
Un ASG es muy sencillo de implementar en hardware. En particular, al contrario que el 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 una resistencia a los ataques de sincronización .
Seguridad
Shahram Khazaei, Simon Fischer y Willi Meier [3] dan un criptoanálisis del ASG que permite varias compensaciones entre la complejidad del tiempo 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.
Referencias
- ^ Günther, CG (1988). "Generadores de pasos alternos controlados por secuencias de De Bruijn" . Avances en criptología - EUROCRYPT '87 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 304 : 5-14. doi : 10.1007 / 3-540-39118-5_2 . ISBN 978-3-540-39118-0 - a través de SpringerLink.
- ^ Gunther, Christoph-Georg (28 de marzo de 1989). "US4817145A - Generador para generar secuencias de cifrado binario" . Patentes de Google .
- ^ Khazaei, Shahram; Fischer, Simon; Meier, Willi (2007). "Reducción de los ataques de complejidad en el generador de pasos alternos" . Áreas seleccionadas en criptografía . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 4876 : 1-16. doi : 10.1007 / 978-3-540-77360-3_1 . ISBN 978-3-540-77360-3 - a través de SpringerLink.
- Schneier, Bruce. Criptografía aplicada (p383-384), segunda edición, John Wiley & Sons, 1996. ISBN 0-471-11709-9