Registro de desplazamiento con retroalimentación no lineal

Un registro de desplazamiento con retroalimentación no lineal (NLFSR, por sus siglas en inglés) es un registro de desplazamiento cuyo bit de entrada es una función no lineal de su estado anterior.

Para un registro de desplazamiento r de n bits , 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 ]}

Los registros de desplazamiento con retroalimentación no lineal son componentes de los cifradores de flujo modernos , especialmente en aplicaciones RFID y de 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 ).

Se sabe cómo generar un NLFSR de n bits de longitud máxima 2n , generando una secuencia de De Bruijn ^, extendiendo 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 creado una lista de NLFSR de n bits de período máximo para n ≤ 25, así como para n = 27. ^{[ 4 ] [ 1 ]}

Los 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 a cadenas de LFSR para mejorar su calidad y cumplir con los criterios de una función de aptitud, en este caso el protocolo NIST , ^{[ 6 ]} de manera efectiva.

• Achterbahn
• Grano
• Algoritmo KeeLoq
• LAGARTO
• Trivium
• CHALECO