Registro de desplazamiento con retroalimentación no lineal

Tipo de registro de desplazamiento

Un registro de desplazamiento de retroalimentación no lineal (NLFSR) es un registro de desplazamiento cuyo bit de entrada es una función no lineal de su estado anterior.

Para un registro de desplazamiento de n bits r su siguiente estado se define como:

${\displaystyle r_{i+1}(b_{0},b_{1},b_{2},\ldots ,b_{n-1})=r_{i}(b_{1},b_{2},\ldots ,f(b_{0},b_{1},b_{2},\ldots ,b_{n-1}))}$,

donde f es la función de retroalimentación no lineal. ^[1]

Aplicaciones

Los registros de desplazamiento con retroalimentación no lineal son componentes de los cifrados de flujo modernos , especialmente en aplicaciones de RFID y tarjetas inteligentes . Se sabe que los NLFSR son más resistentes a los ataques criptoanalíticos que los registros de desplazamiento con retroalimentación lineal ( LFSR ).

Generando

Se sabe cómo generar un NLFSR de n bits con una longitud máxima de 2 ⁿ , generando una secuencia De Bruijn , mediante la extensión de un LFSR de longitud máxima con n etapas; ^[2] pero la construcción de otros NLFSR grandes con períodos largos garantizados sigue siendo un problema abierto. ^{[3] Utilizando métodos de fuerza bruta, se ha elaborado una lista de NLFSR} de n bits con período máximo para n ≤ 25 así como para n = 27. ^{[4] [1]}

Nuevos métodos sugieren el uso de algoritmos evolutivos para introducir no linealidad. ^[5] En estos trabajos, un algoritmo evolutivo aprende cómo aplicar diferentes operaciones en cadenas de LFSR para mejorar su calidad para cumplir con los criterios de una función de aptitud, aquí el protocolo NIST , ^[6] de manera efectiva.

Cifrados basados ​​en NLFSR

• Tren de entrada
• Grano
• Algoritmo KeeLoq
• LAGARTO
• Trivio
• CHALECO

Referencias

1. Rachwalik, Tomasz; Szmidt, Janusz; Wicik, Robert; Zabłocki, Janusz (3 de junio de 2012). Generación de registros de desplazamiento de retroalimentación no lineal con hardware de propósito especial (PDF) . Instituto de Comunicación Militar (Varsovia). p. 1 . Consultado el 3 de mayo de 2017 .
2. CG Günther, "Generador de pasos alternos controlado por la secuencia de Bruijn", Avances en criptología – EUROCRYPT '87, doi :10.1007/3-540-39118-5_2
3. Sobre el análisis y síntesis de registros de desplazamiento de retroalimentación (n, k)-no lineales, 2008.
4. E. Dubrova, "Una lista de NLFSR de período máximo", Archivo de impresión electrónica de criptología, Informe 2012/166, marzo de 2012, http://eprint.iacr.org/2012/166.
5. A. Poorghanad, A. Sadr, A. Kashanipour "Generación de números pseudoaleatorios de alta calidad mediante métodos evolutivos", Congreso IEEE sobre inteligencia computacional y seguridad, vol. 9, págs. 331–335, mayo de 2008 [1]
6. NIST." Un conjunto de pruebas estadísticas para generadores de números aleatorios y pseudoaleatorios para aplicaciones criptográficas". NIST, publicación especial de abril de 2010