Tema: Registros de Desplazamiento con Realimentación Lineal (LFSRs)

En este post vamos a ver una descripción muy básica de lo que son los registros de desplazamiento con realimentación lineal (LFSR por su nombre en inglés, Linear Feedback Shift Register). Además, veremos los principales modos de uso de este tipo de registros para realizar cifrados de flujo. Todo ello sin entrar en detalles matemáticos, para los que os refiero a documentos como el Handbook of Applied Cryptography o esta referencia sobre LFSR.
Registros de desplazamiento
Un registro de desplazamiento es básicamente una construcción con varias celdas de memoria conectadas entre sí, donde cada celdas almacena un bit.Así, el valor de todas estas celdas conforman el estado del registro. Cuando se cambia el estado del registro (generalmente al ritmo de un reloj), el nuevo estado del registro se forma simplemente desplazando los bits de cada celda a la celda de su derecha. Así, el bit de más a la derecha sale del registro, y un nuevo bit entra en la celda de más a la izquierda.
En esta figura podemos ver una implementación de registro de desplazamiento de 4 bits:
Registro de desplazamiento

Podemos ver que hay una entrada de datos ( Data In ), 4 puntos donde leer el estado actual del registro (Q1-Q4) y una entrada de reloj que se encarga de governar el registro, indicando en qué momento se debe pasar de un estado al siguiente.
Registros de desplazamiento con realimentación lineal (LFSRs)
Bien, una vez sabemos qué son los registros de desplazamiento es muy sencillo entender cómo funciona un LFSR. Simplemente, tomamos el registro anterior y hacemos que la entrada sea una función lineal de las distintas celdas. Puesto que hay un bucle que alimenta el registro en base a su estado anterior, tenemos realimentación. Además, como esto se hace con una función lineal, tenemos realimentación lineal, lo cual explica el nombre de estas construcciones .
LFSR

Uso de LFSRs en criptografía
Llegados a este punto, posiblemente ya hayáis adivinado que el uso principal de un LFSR en sistemas de cifrado es el de generar una serie de bits pseudo-aleatorios para ser usados como key stream en un cifrado de flujo.
La idea es generar una ristra de bits que no se repitan, con el máximo periodo posible. Para su estudio, generalmente se representan las conexiones de la función de alimentación como un polinomio y se estudian las propiedades que debe tener dicho polinomio para obtener un periodo máximo. Es decir, para que se repite lo menos posible.
Básicamente, hay que conseguir que el LFSR pase por todos los estados posibles antes de volver al primer estado. Es decir, si tenemos un registro de 16 bits, habría que conseguir que el LFSR pase por los 2^16-1 estados posibles antes de volver al primero. Y sí, he dicho 2^16-1 y no 2^16 porque el estado 0 (cero) no debería darse, puesto que entonces el LFSR se va a quedar para siempre en dicho estado y no va a evolucionar. Para los curiosos, un LFSR tendrá longitud máxima si su polinomio generador es un polinomio primitivo (seguro que a alguno os suena esto de los polinomio primitivos, aunque puede que no para bien ).
Dejando a un lado el estudio de estos polinomios, que tiene detalles matemáticos bastante complejos (en mi opinión, que no soy matemático ), un LFSR por sí mismo no debería ser usado como generador de un flujo de claves puesto que sus propiedades hacen que sea bastante predecible. De hecho, para un registro de n bits, obteniendo 2n bits de salida es posible conocer el valor del polinomio generador y ser capaz de descifrar cualquier texto que venga detrás.
Así pues, los LFSR no se usan tal cual en criptografía, sino que se usan generalmente en uno los siguientes de tres modos:

• Combinación no lineal de varios LFSRs: se trata de tomar varios LFSRs y combinar sus salidas de forma no lineal para obtener el flujo de claves.
• Filtro generador no lineal: la salida se genera en base a una función no lineal del estado del LFSR.
• Generadores controlados por reloj: esta variedad se basa en tener varios LFSRs que avanzan siguiendo unas reglas determinadas, en lugar de avanzar cada vez.

Mediante este tipo de construcciones se consigue mejorar las propiedades de los LFSR para poder generar cifrados de flujo seguros. Y hasta aquí llegamos con los LFSR. Para más información, os remito de nuevo a las siguientes referencias:
Handbook of Applied Cryptography
LFSR Reference
[ame="http://en.wikipedia.org/wiki/Linear_feedback_shift_register"]LFSR[/ame] @ Wikipedia
Fuente