Un generador de contracción automática es un generador pseudoaleatorio que se basa en el concepto de generador de contracción . Se estudian variantes del generador autocontraíble basadas en un registro de desplazamiento de retroalimentación lineal (LFSR) para su uso en criptografía . [ quien? ]
Algoritmo
A diferencia del generador de contracción , que usa un segundo registro de desplazamiento de retroalimentación para controlar la salida del primero, el generador de contracción automática usa bits de salida alternos de un solo registro para controlar su salida final. El procedimiento para sincronizar este tipo de generador es el siguiente:
- Reloj el LFSR dos veces para obtener un par de bits como salida LFSR.
- Si el par es 10, dé un cero.
- Si el par es 11, salga uno.
- De lo contrario, no envíe nada.
- Regrese al paso uno.
Ejemplo
Este ejemplo usará el polinomio de conexión x 8 + x 4 + x 3 + x 2 + 1 , y un llenado de registro inicial de 1 0 1 1 0 1 1 0 .
A continuación, la tabla enumera, para cada iteración del LFSR , su salida intermedia antes de la contracción automática, así como la salida final del generador. Las posiciones de las tomas definidas por el polinomio de conexión están marcadas con encabezados azules. El estado de la iteración cero representa la entrada inicial.
Iteración # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | Salida intermedia | Salida del generador |
---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N / A | N / A |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N / A |
2 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
3 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
4 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
Al final de cuatro iteraciones, se produce la siguiente secuencia de bits intermedios: 0110 .
El primer par de bits, 01 , se descarta porque no coincide con 10 ni con 11 . El segundo par de bits, 10 , coincide con el segundo paso del algoritmo, por lo que se genera un cero.
Se crean más bits al continuar sincronizando el LFSR y reduciendo su salida como se describe anteriormente.
Criptoanálisis
En su artículo, [1] Meier y Steffelbach prueban que un generador autocontraíble 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, muestran que cualquier generador de contracción automática puede representarse como un generador de contracción. Lo inverso también es cierto: cualquier generador de contracción puede implementarse como un generador de contracción automática, aunque el generador resultante puede no tener la longitud máxima.
Un ataque presentado por los autores requiere aproximadamente 2 pasos de 0,7 L , asumiendo 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 alrededor de 2 57 pasos, utilizando una secuencia de salida de sólo 4,9 x 10 8 bits.
Otro ataque [3]
Referencias
- ^ "El generador de auto-encogimiento", Avances en Cryptology-Eurocrypt 1994 (LNCS 950), 205-214, 1995.
- ^ "Un examen de seguridad del generador autocontraíble", Circencester, Reino Unido, diciembre de 1995.
- ^ Zenner, Erik; Krause, Matthias; Suerte, Stefan. "Criptoanálisis mejorado del generador autoencogible" . Seguridad de la información y privacidad 13th Australasian Conference ACISP 2008 : 30 . Consultado el 12 de abril de 2016 .