Síntesis
En el presente trabajo se analiza una de las herramientas más utilizadas para la construcción de criptosistemas de cifrado en flujo, los registros de desplazamiento con retroalimentación lineal (LSFRs, siglas en inglés), los cuales están basados en el principio matemático de las sucesiones recurrentes lineales (SRL) sobre los campos finitos binarios. Se brinda la fundamentación teórica de estos mecanismos presentando las definiciones y propiedades principales, que son necesarias para comprender su funcionamiento. Además, se detallan métodos teóricos y prácticos para la obtención de los parámetros de los LSFRs.
Introducción
La teoría de los campos finitos es una rama del Álgebra moderna que se ha convertido en muy actual desde la última mitad del siglo pasado, teniendo sus múltiples aplicaciones en la combinatoria, la teoría de códigos, la teoría matemática de los esquemas de conmutación, la teoría de números, la geometría algebraica, la teoría de Galois y en particular en Criptografía, donde se utilizan en la construcción de la mayoría de los códigos conocidos y su decodificación(Niederreiter, 1986).
Las sucesiones sobre campos finitos cuyos términos dependerán de una manera sencilla de sus predecesores son de importancia para una variedad de aplicaciones ejemplo en la criptografía. Dichas sucesiones son fáciles de generar mediante procedimientos recursivos, lo cual es sin duda una característica ventajosa desde el punto de vista computacional y también tienden a tener propiedades estructurales útiles(Menezes, VanOorschot, & Vanstone, 1996).
En 1917, J. Mauborgne y G. Vernam inventaron un criptosistema perfecto según el criterio de Shannon. Dicho sistema consistía en emplear una sucesión aleatoria de igual longitud que el mensaje, que se usaría una única vez, combinándola mediante alguna función simple e inversible (xor) con el texto en claro bit a bit.
En este trabajo analizaremos una herramienta para la construcción de este tipo de criptosistema, denominado en la criptografía moderna como algoritmo de cifrado en flujo, sobre campos finitos específicos: los binarios, o sea, los campos finitos de característica dos. Dichos criptosistemas no son más que la especificación de un generador pseudoaleatorio, que permiten cifrar mensajes de longitud arbitraria, combinando el mensaje con la sucesión (conjunto de elementos encadenados o sucesivos) mediante la operación or exclusivo bit a bit. Los mismos no proporcionan seguridad perfecta, ya que mientras en el cifrado de Vernam el número de posibles claves es tan grande como el de posibles mensajes, cuando empleamos un generador tenemos, como mucho, tantas sucesiones distintas como posibles valores del estado inicial del registro.Una herramienta a emplear para la construcción de estos criptosistemas la constituye los registros de desplazamiento con retroalimentación lineal (LSFR, estos son un tipo especial de circuitos electrónicos de conmutación que procesan la información presentada de una manera adecuada en forma de elementos del campo), los cuales están basados en el principio matemático de las sucesiones recurrentes lineales (SRL, ecuación que define una sucesión recursiva donde cada término de la sucesión es definido como una función de términos anteriores).
Debido a que permiten generar sucesiones con períodos muy grandes y con buenas propiedades estadísticas, además de su bien conocida estructura algebraica y su facilidad para ser implementados por hardware, estos se encuentran presentes en muchos de los generadores de sucesión propuestos en la literatura.
Actualmente existe una gran variedad de principios de diseño para construir algoritmos de cifrado en flujo, pero uno de los más utilizados desde hace décadas son los registros de desplazamiento con retroalimentación lineal. Hoy por hoy, se reportan algunas deficiencias de seguridad, lo cual ha limitado su utilización y han impuesto transformaciones en su estructura y funcionamiento. No obstante, muchos de estos reportes no presentan información en detalle e incluso en algunos se especula acerca de los resultados planteados.
Desarrollo
1.1 Cifrado en flujo
El cifrado en flujo se realiza bit a bit, mediante el texto claro y la sucesión aleatoria generada.
Véase (López, 2009), (Schneier, 1) y (Bruen & Mollin, 2009)
Sea
los bits de texto claro, texto cifrado y la sucesión aleatoria generada, respectivamente. El cifrado y descifrado en flujo consiste en:
Cifrado: 
i
Descifrado: 
i
Las función fueron denotadas de manera diferente pero, como se puede observar existe una similitud entre estas. La razón de la similitud de la función de cifrado y descifrado se puede mostrar fácilmente. Debemos demostrar que la función de descifrado realmente produce el bit de texto en claro
Se sabe que el bit 
de texto cifrado fue obtenido utilizando la función de cifrado 
Los cifrados de flujo actuales utilizan una sucesión de bits de clave 
generada por un generador de sucesiones pseudoaleatorias que debe tener ciertas propiedades (Como los postulados mencionados en el capítulo anterior). Una manera sencilla de producir sucesiones pseudoaleatorias grandes es utilizar los LFSRs. Los LFSRs se implementan fácilmente en hardware y muchos, pero no todos, de los cifrados de flujo, hoy por hoy, hacen uso de estos. Un ejemplo destacado es el sistema de cifrado A5 / 1 (Biham & Dunkelman, 2000), que está estandarizado para el cifrado de voz en las redes del Sistema Global de la Comunicaciones Móviles (GSM)(Siegmund M. Redl, 1995). Como veremos en este capítulo, a pesar de que un LFSR produce sucesiones con buenas propiedades estadísticas, estos son criptográficamente débiles.
En la actualidad la mayoría de los algoritmos son públicos, por lo que se pueden conocer las características de los mismos y sus vulnerabilidades. Por esta razón, es posible conocer la longitud de los registros de desplazamiento con retroalimentación lineal.
No obstante, si el algoritmo es secreto es posible conocer este dato, mediante la utilización de la ingeniería inversa, si este está implementado en hardware, lo cual es muy frecuente en la utilización de los LFSRs. Tal es el caso del algoritmo mencionado, A5/1. Mientras que, si está implementado en software es posible conocer este parámetro teniendo en cuenta el almacenamiento requerido.
Incluso los propios polinomios utilizados para retroalimentación pueden ser públicos, pero es recomendado que se mantenga como parámetros secretos.
1.2 Ataques de texto claro conocido
Como lo indica su nombre, los LFSRs son lineales. Los sistemas lineales se rigen por relaciones lineales entre sus entradas y salidas. Puesto que, las dependencias lineales pueden ser relativamente fáciles de analizar, esto puede ser una gran ventaja, por ejemplo, en sistemas de comunicación. Sin embargo, un criptosistema donde los bits de la llave sólo intervienen en relaciones lineales hace a un cifrado altamente inseguro. Ahora vamos a investigar cómo el comportamiento lineal de un LFSR conduce a un ataque poderoso (Guarino, 2010) y (Kholosha, 2003).
Si utilizamos un LFSR para cifrado de flujo, la llave secreta 
es el estado inicial de registro, es decir, el vector 
Un ataque posible, es el ataque de texto claro conocido donde un atacante conoce algunos pares de texto claro y su texto cifrado correspondiente. Se puede suponer, además, que el atacante conoce la longitud 
del LFSR. El ataque es tan eficiente que se puede tratar fácilmente un gran número de valores posibles
de manera que esta suposición no es una restricción importante. Sea 
el texto claro conocido y 
el texto cifrado correspondiente. Con estos pares de 
bits de texto claro y texto cifrado, un atacante puede reconstruir 
bits de la sucesión aleatoria generada para el cifrado en flujo:
Para el desarrollo de este epígrafe nos plantearemos la siguiente problemática, un criptoanalista está trabajando para descifrar determinada información, para ello realiza el ataque del texto claro conocido, interceptando los caracteres que se pueden inferir fácilmente de acuerdo al momento y las circunstancias en que esta operación se realice.
Ejemplo 1.2
a. Si el mensaje a cifrar posee referencia a direcciones web es muy común la presencia de los caracteres http:, ftp:, https:, u otras directivas de comunicación, lo cual puede ser utilizado para realizar estos ataques.
Para llegar al estado inicial necesitamos conocer salidas sucesivas, siendo la longitud del registro de desplazamiento con retroalimentación lineal, que se conoce por ser la mayoría de los algoritmos públicos.
De esta manera, la sucesión obtenida mediante este ataque, como subsucesiónde una SRL homogénea binaria producida por un LFSR, la denotaremos por
siendo
el instante de tiempo en que se obtuvo dicha salida 
y el grado del polinomio de conexión
del registro, que coincide con la longitud del mismo (Golomb, 1982), que como se dijo al inicio del capítulo se conoce por ser la mayoría de los algoritmos de llave pública.A través de esta subsucesión se puede obtener el estado inicial, obteniendo la llave secreta, y de esta forma reconstruir la sucesión completa determinando todo el texto claro.
1.3 Obtención del polinomio primitivo de los LFSRs
En la búsqueda del estado inicial 
necesitamos obtener, utilizando el ataque de texto claro conocido, el polinomio de conexión del registro de desplazamiento con retroalimentación lineal. Los coeficientes de dicho polinomio coinciden con los de la sucesión recurrente lineal que representa. Para hallarlo es necesario una parte de la sucesión de salida de elementos consecutivos, siendo el grado del polinomio de conexión. Para la aplicación de este método no es necesario conocer el instante de tiempo donde comienza la sucesión de elementos consecutivos, o sea,
Por la definición de recurrencia lineal (Panario, 2013) podemos obtener el siguiente sistema de ecuaciones expresado en función de términos conocidos por el epígrafe anterior, siendo 
las incógnitas:
Como podemos ver, siempre es posible expresar el estado actual en función de los anteriores. Si la longitud del registro no es muy grande, los cálculos se pueden hacer fácilmente a mano, resolviendo un reducido sistema de ecuaciones por alguno de los métodos clásicos conocidos, como sustitución o reducción y en ocasiones hasta por tanteo. Esto se complica a medida que la longitud aumente. Cuando esto ocurre dicho sistema se puede resolver fácilmente por el método de Gauss (véase (Arachchige, 1991) y (Yoshiyasu Takefusi, 1983) ) el cual está implementado en los anexos por el Laboratorio de Criptografía académeica de la Universidad Central de las Villas (LCA) (Ver anexo 1). Este nos elimina todo tipo de complicación, se ponen ceros o unos en dependencia de si se encuentran o no los términos de la sucesión recurrente lineal homogénea que le anteceden a la subsucesión obtenida, como ya hemos mencionado, por un ataque de texto claro conocido y se aplica el método de Gauss. De esta forma se obtienen los coeficientes 
del polinomio de conexión del registro de desplazamiento con retroalimentación lineal y con esto el polinomio característico asociado a la relación recurrente lineal (Panario, 2013), que según lo planteado,, donde 
es la matriz identidad de orden 
sobre el campo 
y la matriz
se puede considerar como la matriz acompañante del polinomio mónico 
la cual se representa como sigue:
Donde los 
por tanto son ceros y unos.
Ejemplo 1.3
Tenemos el siguiente registro de desplazamiento con retroalimentación lineal 
Para encontrar el polinomio de conexión, como habíamos dicho, necesitamos una subsucesión de salida de 
elementos obtenidas por el ataque de texto claro conocido.
Sea 
dicha subsucesión. Luego se tiene,
1 0 0 0 1 1 0 1 1 1
Planteando el sistema de ecuaciones dado en el epígrafe anterior tendríamos:
Sustituyendo nos queda el reducido sistema:
Resolviendo el mismo se obtiene
Siendo
y 
Obtenemos el polinomio de conexión 
1.4 Procedimientos para la recuperación del estado inicial de los LFSR
Luego de haber obtenido el polinomio de conexión podemos hacer uso la de matriz acompañante, la misma nos es de gran utilidad para recuperar el estado inicial del registro de desplazamiento con retroalimentación lineal.
Sea 
la matriz acompañante a la sucesión recurrente lineal homogénea binaria.
Para todo vector de estado se verifica en la SRL homogénea que 
(Panario, 2013), entonces despejando 
obtenemos 
De esta manera obtenemos el vector de estado inicial, siendo 
el instante de tiempo que se obtuvo la sucesión, 
Ejemplo 1.4
Utilizando el resultado del ejemplo anterior y conociendo el instante de tiempo en que se comenzó a generar dicha subsucesión () podemos recuperar el estado inicial 
El registro de deslazamiento con retroalimentación lineal 
que mostramos es no singular. Cada uno de los posibles estados iniciales del registro no singular produce una sucesión recurrente lineal homogénea sobre el campo binario (sucesión de salida) de posible período máximo (Golomb, 1982) ya que 
es un polinomio primitivo, por lo tanto su período sería:
Además 5 y 31 son primos de Mersenne, entonces la sucesión recurrente lineal es de período máximo.
Como todo vector de estado verifica que 
, entonces se cumple para el estado inicial
Despejando la incógnita se obtiene
Luego necesitamos el cálculo de:
Y de su matriz inversa, la cual se puede obtener por el método de Gauss o utilizando la traspuesta de la adjunta dividida por el determinante de dicha matriz, o sea 
o también utilizando el software El Matemática:
Realizando entonces el producto de matrices obtenemos:
El cual podemos verificar que es el estado inicial a partir del cual se generó la sucesión recurrente lineal homogénea.
Sea el registro de desplazamiento con retroalimentación lineal 
y el estado inicial 
a partir del cual se generó la subsucesión
Las conexiones están dadas según (Golomb, 1982).
Aplicando un correcto funcionamiento del registro obtenemos los 31 estados del registro y justo en el instante de tiempo 
obtenemos el estado a partir del cual se generó la sucesión de salida obtenida por el ataque de texto claro conocido.
00110 0 | 11111 1 | 11000 0 | 01110 0 | 00101 1 | 00100 0 |
10011 1 | 01111 1 | 01100 0 | 10111 1 | 00010 0 | 10010 0 |
11001 1 | 00111 1 | 10110 0 | 01011 1 | 00001 1 | 01001 1 |
11100 0 | 00011 1 | 11011 1 | 10101 1 | 10000 0 | 10100 0 |
11110 0 | 100011 | 11101 1 | 01010 0 | 01000 0 | 11010 1 |
La sucesión de salida que se obtiene es:
Observación: El estado a partir del cual se obtuvieron los elementos de dicha subsucesión y dichos elementos coinciden (rojo subrayado).
Bajo el mismo supuesto y la misma hipótesis plantearemos otro procedimiento para la recuperación del estado inicial. Utilizaremos la definición de recurrencia propuesta en el segundo epígrafe del primer capítulo.
Sea 
el polinomio de conexión del registro de desplazamiento obtenido en el epígrafe anterior, 
la subsucesión de salida que se obtuvo por el ataque de texto claro expuesto en el epígrafe 1.1. Entonces por la definición de sucesión recurrente lineal homogénea (Panario, 2013), siempre es posible expresar cualquier término de la sucesión recurrente lineal homogénea en función de los términos anteriores. De esta manera, podemos representar la ecuación de cualquier término de la recurrencia a partir de en función de los estados anteriores y por consiguiente, del estado inicial 
realizando la recurrencia hacia atrás utilizando la suma
En función de las etapas iniciales sería
Y así sucesivamente
donde
.
Formaríamos entonces un sistema solo en función de las etapas iniciales utilizando la suma
El sistema de ecuaciones anterior siempre se puede resolver, solo que sería costoso computacionalmente en los casos donde el instante de tiempo 
sea muy grande. La cantidad de ecuaciones a formular es 
que es la cantidad de etapas desconocidas del estado inicial y, como se había mencionado, el grado del polinomio de conexión. El planteamiento de las ecuaciones cesa cuando obtengamos las primeras 
ecuaciones a partir del instante de tiempo supuesto conocido. Con este sistema recuperaría el estado inicial.
Ejemplo 1.5
Sea 
el polinomio de conexión del registro de desplazamiento con retroalimentación lineal encontrado en el Ejemplo 3.2, la subsucesión de salida obtenida por el ataque a partir del tiempo 
y 
constituyen las incógnitas.
El sistema se formularía
Sustituyendo los valores de 
en el sistema y realizando la recurrencia hacia atrás se obtiene
Resolviendo este utilizando algún método de los dichos anteriormente obtendríamos
Mediante el análisis criptográfico de los registros de desplazamiento con retroalimentación lineal pudimos obtener, bajo ciertos supuestos, el polinomio de conexión del registro y con este hallar, por dos vías, el estado inicial a partir del cual se generó la SRL homogénea binaria del primer capítulo. Esto no prueba que los registros son vulnerables a ataques por lo que hay que utilizar otros mecanismos para potenciarlos.
Conclusiones
A través de este trabajo se pudo obtener un procedimiento práctico para la obtención de los polinomios de retroalimentación de los registros de desplazamiento lineales a partir del conocimiento de
elementos consecutivos de una sucesión de salida, siendo 
la longitud del registro.Además, se expusieron métodos teóricos para la recuperación del estado inicial de los registros de desplazamiento, los cuales pueden constituir amenazas reales bajos entornos que soporten las suposiciones planteadas.
A partir de estos resultados se puede llegar a la conclusión de que los LSFR no se pueden utilizar por si solos, hay que introducirles otros mecanismos para aumentar su fortaleza.
Bibliografía
1. Arachchige, C. K. (1991). A Fast Algorithm for Gaussian Elimination over GF (2) and Its Implementation on the GAPP.
2. Biham, E., & Dunkelman, O. ( 2000). Cryptanalysis of the A5/1 GSM Stream Cipher. 43–51.
3. Bruen, A., & Mollin, R. (2009). Cryptography and Shift Registers.
4. Golomb, S. (1982). Shift register sequences.
5. Guarino, S. (2010). Ciphertext-only reconstruction of LFSR-based stream ciphers.
6. Kholosha, A. (2003). Investigations in the Design and Analysis of Key-Stream Generators.
7. López, M. J. (2009). CRIPTOGRAFÍA Y SEGURIDAD EN COMPUTADORES.
8. Menezes, A., VanOorschot, P., & Vanstone, S. (1996). Handbook of Applied Cryptography.
9. Niederreiter, R. L. (1986). Introduction to Finite fields.
10. Panario, G. L. (2013). Handbook of finite fields.
11. Schneier, B. (1996 de 1 de 1). Applied Cryptography. Recuperado el 25 de mayo de 2014
12. Siegmund M. Redl, M. K. (1995). An Introduction to GSM.
13. Yoshiyasu Takefusi, T. K. (1983). Fast Matrix Solver in GF(2). Recuperado el 15 de 5 de 2014
Anexo
Algoritmo para generar polinomio primitivo sobre campos binarios (elaborado por el LCA).
UNIVERSIDAD DE CIENFUEGOS
"Carlos Rafael Rodríguez"
Facultad de Ingeniería
Departamento de Matemática Aplicada
ANÁLISIS CRIPTOGRÁFICO DE LOS LFSR
Autores: Lic. Mayara Rosa Mier Macías
MSc. Oristela Cuellar Justiz
Esp. Evaristo José Madarro Capó
2014-2015