Sucesiones recurrentes lineales sobre campos finitos binarios y su aplicación en la criptografía

RESUMEN

En el presente trabajo se expone y 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.

Palabras Claves: campo finito binario, sucesión recurrente lineal, registro de desplazamiento con retroalimentación lineal, cifrado de flujo.

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.

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 .

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.

En marzo del 2009 se inauguró en nuestra Universidad Central "Martha Abreu" de Las Villas un Laboratorio de Criptografía Académica (LCA), ubicado en la facultad de Matemática, Física y Computación. Con el objetivo de potenciar investigaciones, en el centro del país, relacionadas con el análisis y diseño de algoritmos de cifrado en flujo.

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.

Problema científico:

Debido a lo anterior se hace necesario realizar un estudio sobre la base matemática de este principio de diseño, específicamente de las sucesiones recurrentes lineales sobre campos finitos binarios. De manera que facilite el análisis criptográfico de estos mecanismos y de esta forma explorar y determinar las potencialidades reales de utilización de los registros de desplazamiento con retroalimentación lineal en la construcción de criptosistemas de cifrado en flujo.

Hipótesis de investigación:

El análisis criptográfico de los registros de desplazamiento con retroalimentación lineal, basado en la teoría de las sucesiones recurrentes lineales sobre campos finitos binarios, permitirá determinar las potencialidades reales de utilización de los LFSR en la construcción de criptosistemas de cifrado en flujo.

Objetivo general:

Realizar un análisis criptográfico de los registros de desplazamiento con retroalimentación lineal, basado en la teoría de las sucesiones recurrentes lineales sobre campos finitos binarios.

Para lograr dicho objetivo general, se proponen los siguientes objetivos específicos:

• 1. Exponer la teoría general sobre los campos finitos binarios.

• 2. Profundizar en el estudio de las sucesiones recurrentes lineales sobre campos finitos binarios.

• 3. Presentar las propiedades generales de los LFSRs.

• 4. Determinar la relación entre las sucesiones recurrentes lineales y los registros de desplazamiento con retroalimentación lineal.

• 5. Analizar el funcionamiento de los registros de desplazamiento con retroalimentación lineal.

Para dar cumplimiento a estos objetivos es necesario plantearse las siguientes interrogantes científicas:

• 1. ¿Cuándo un campo finito es binario?

• 2. ¿Qué es una sucesión recurrente lineal binaria?

• 3. ¿Qué es un registro de desplazamiento con retroalimentación lineal?

• 4. ¿Qué relación existe entre las sucesiones recurrentes lineales y los registros de desplazamientos con retroalimentación lineal?

Con el propósito de resolver las interrogantes científicas que responden a los objetivos específicos fue necesario plantearse y solucionar las siguientes tareas de investigación:

• 1. Revisión bibliográfica sobre la teoría de los campos finitos, particularizando en los de característica dos. Consulta de libros, artículos y páginas de internet, entre otras fuentes.

• 2. Estudio de las sucesiones recurrentes lineales en campos finitos binarios.

• 3. Profundización en el estudio de los conceptos generales y funcionamiento de los registros de desplazamiento con retroalimentación lineal.

• 4. Representación de las salidas de los LSFRs como sucesiones recurrentes lineales.

• 5. Caracterización de las salidas de los LSFRs según los postulados de Golomb.

• 6. Exposición de la relación entre el polinomio de conexión y los coeficientes de la recurrencia lineal.

• 7. Explicación de los principios básicos de los ataques con texto claro conocido.

• 8. Obtención de los parámetros de los registros de desplazamiento con retroalimentación lineal.

• 9. Recuperación del estado inicial de los LFSRs.

Métodos de investigación científica:

Método hipotético-deductivo: Al elaborar la hipótesis de investigación a partir de los resultados de la revisión bibliográfica.

Inducción – deducción: Para en el estudio de las fuentes de información, extraer de ellas regularidades y tendencias relacionadas con el tema de investigación y la lógica de pensamiento cuyas interrelaciones y generalizaciones permiten la argumentación y la coherencia de la propuesta que se realice.

Histórico-lógico: Para el análisis de la trayectoria evolutiva de la investigación a partir de su objeto, antecedente y desarrollo. En la revisión de la literatura adecuada para la determinación de las tendencias actuales de cómo son usados los campos finitos en los criptosistemas.

Aportes de la investigación:

Los principales aportes de esta investigación son fundamentalmente teóricos, debido a que se presenta un procedimiento para la determinación del polinomio de retroalimentación de los LFSRs, a partir del conocimiento de cierta cantidad de elementos de salida y se exponen métodos para la recuperación del estado inicial, basados en la teoría de las sucesiones recurrentes lineales, bajo ciertos supuestos. Como resultado práctico se propone un algoritmo para la obtención del polinomio de retroalimentación de un LFSR.

Estructura del trabajo:

La tesis está estructurada en tres capítulos:

En el primer capítulo se abordan aspectos fundamentales de la teoría de los campos finitos particularizando en los binarios que son los de interés criptográfico y sobre los que se desarrolla la investigación. Además, especifican algunos conceptos y propiedades sobre las sucesiones recurrentes lineales definidas sobre estos tipos de campos finitos.

En el segundo capítulo se brindan las principales propiedades de los registros de desplazamientos con retroalimentación lineal, así como, de las sucesiones que estos generan. También, se representa la relación existente entre los registros de desplazamientos con retroalimentación lineal y las sucesiones recurrentes lineales.

En el tercer capítulo se exponen algunos métodos para el análisis de los registros de desplazamientos con retroalimentación lineal. Se presenta un procedimiento para la obtención de algunos parámetros de estos mecanismos a partir de la sucesión de salida. Además, se proponen métodos para la recuperación del estado inicial de los registros de desplazamiento con retroalimentación lineal.

CAPÍTULO I.

SUCESIONES RECURRENTES LINEALES SOBRE CAMPOS FINITOS BINARIOS

La teoría de los campos finitos tiene sus orígenes en los siglos XVII y XVIII con el estudio de una clase especial de campos finitos, los llamados campos primos, gracias a los aportes de matemáticos tan reconocidos como Pierre de Fermat (1601-1665), Leonhard Euler (1707-1783), Joseph-Louis Lagrange (1736-1813) y Adrien-Marie Legendre (1752-1833). La teoría general sobre los campos finitos comienza con los trabajos de Carl F. Gauss y Evariste Galois a principios del siglo XIX. También conocidos como campos de Galois, los campos finitos han tenido en los últimos años muchas aplicaciones, entre las que se cuentan los códigos algébricos, los esquemas criptográficos, los generadores de números aleatorios, el procesamiento digital de señales y los códigos de corrección de errores CITATION RLi86 l 1033 (Niederreiter, 1986).

Como se dijo anteriormente las sucesiones sobre campos finitos cuyos términos dependerán de una manera sencilla en sus predecesores son de importancia para una variedad de aplicaciones. 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. De particular interés es el caso en los términos dependen linealmente de un número fijo de sus predecesores, lo que resulta en una sucesión de manera lineal llamada recurrente. Estas sucesiones se emplean, por ejemplo, en la teoría de la codificación, en la criptografía (véase el Capítulo 2), y en varias ramas de la ingeniería eléctrica CITATION RLi86 l 1033 (Niederreiter, 1986). En estas aplicaciones, el campo subyacente que se toma a menudo es , pero la teoría puede ser desarrollada bastante general para cualquier campo finito.

Este capítulo está compuesto por dos epígrafes. El primero está dividido en tres secciones, en primer lugar se aborda las definiciones y propiedades de los campos, en segundo las propiedades de polinomios sobre campos finitos, haciendo énfasis en los polinomios irreducibles y la tercera sección trata la caracterización de los campos finitos y un conjunto de propiedades que estos cumplen y que son importantes para la comprensión del trabajo y la fundamentación del tema a tratar en el próximo capítulo.

El segundo epígrafe es el más importante, está divido en 4 secciones; el primero se dedica a definir los tipos sucesiones recurrentes lineales sobre campos finitos; el segundo, al período de una sucesión recurrente lineal, el tercero a los métodos básicos de representación de las SRL y el último aborda las SRL sobre campos finitos binarios.

Las definiciones, teoremas y propiedades que se enuncian en el capítulo, se pueden encontrar en CITATION RLi86 l 1033 (Niederreiter, 1986) y CITATION Gar13 l 1033 (Panario, 2013) y lo relacionado a sucesión recurrente lineal en CITATION RLi86 l 3082 (Niederreiter, 1986). Igualmente las demostraciones de todos los teoremas, lemas y definiciones correspondientes a cada epígrafe. Para profundizar en el tema de campos finitos recomendamos también CITATION JAV09 l 3082 (Mendoza, 2009)).

• Conceptos básicos

1.1.1 Campos finitos

Definición 1.1

Un campo es un conjunto no vacío con dos operaciones internas donde

• es un grupo conmutativo.

• es un grupo conmutativo.

• Se cumple la ley distributiva del producto con respecto a la suma.

Es decir, un campo es un anillo conmutativo en el que todo elemento distinto de cero tiene inverso.

Un subcampo de es un subanillo de que es en sí mismo un campo.

Lema 1.2

Un anillo conmutativo es un campo, si y solo si, no contiene ideales distintos de y

Un homomorfismo de campos no es más que un homomorfismo de anillos. Este es siempre inyectivo, porque su núcleo, siendo un ideal propio, tiene que ser cero según el lema anterior.

Es fácil comprobar que la aplicación

donde es el neutro de para el producto, es un homomorfismo de anillos y por tanto su núcleo es un ideal de Pueden producirse entonces dos variantes:

• El núcleo es , entonces puede extenderse a un homomorfismo lo que indica que contiene una copia de En este caso se dice que es de característica cero.

• El núcleo es para algún natural, que además tiene que ser primo (de lo contrario existen en dos elementos distintos de cero cuyo producto es cero). En este caso contiene una copia de

y se dice que es de característica

Este último caso es el que nos interesa, pues los campos finitos tienen característica

específicamente cuando se llaman campos binarios o de característica dos. Podemos percibir que un campo finito no es más que un campo con un número finito de elementos. Y como acabamos de apreciar, su característica es un número primo. Usaremos la notación para referirnos al campo

son los llamados campos primos. Un campo de característica se dice que tiene a como su subcampo primo. Para el caso que nos interesa, cuando la característica es dos, entonces se dice que tiene a como su subcampo primo, siendo .

1.1.2 Polinomios

Sea el anillo de polinomios con coeficientes en el campo

Definición 1.3

Un polinomio se dice irreducible sobre si tiene grado positivo y no puede descomponerse como el producto de dos polinomios de ambos de grado positivo.

Es evidente que los polinomios lineales (de grado uno) son irreducibles.

Una propiedad fundamental del anillo es que es un dominio de integridad si lo es. Así que es un dominio de integridad, con la propiedad adicional de que se cumple la división con resto. Esto es, dados cualesquiera

existen

tales que f=gq+r

donde

grd(f) es el grado del polinomio f)

Se dice que g divide a f y se denota g/f si existe q tal que f=gq La división con resto permite probar que

es un dominio de factorización única.

Cada polinomio no nulo f sobre un campo finito además de su grado grd(f) tiene otra característica numérica entera su orden.

Lema 1.4

Si el polinomio es un polinomio de grado que satisface la condición entonces existe un número natural para el cual el binomio se divide por el polinomio

Definición 1.5

Sea un polinomio no nulo. Si entonces el menor número natural para el cual el polinomio divide a se llama orden del polinomio y se denota por Pero si entonces el polinomio se puede representar de forma única como

donde

y y

y en este caso el orden del polinomio se define como

Teorema 1.6

Si es un polinomio irreducible sobre el campo y entonces divide a

Teorema 1.7

Todo polinomio se puede descomponer de manera única, salvo el orden de los factores, como producto de polinomios irreducibles.

Los polinomios irreducibles en juegan el mismo papel que los números primos en así podemos decir que si un polinomio irreducible sobre divide un producto de polinomios en entonces divide al menos a uno de los factores de este producto.

Definición 1.8

Un elemento se dice que es raíz de si se cumple que

De la definición anterior y la división con resto se deduce el siguiente teorema.

Teorema 1.9

Sea irreducible y una raíz de para algún

si y solo si f divide a g

En particular, si consideramos se tiene si y solo si Aplicando este resultado un número finito de veces obtenemos el siguiente teorema.

Teorema 1.10

Un polinomio de grado tiene a lo sumo raíces en

Una consecuencia del resultado anterior es que los polinomios de grado 2 y 3 son irreducibles sobre si y solo si no tienen raíces en

Para ilustrar la utilidad de algunos conceptos y propiedades enunciados hasta el momento, veamos el siguiente ejemplo: hallar los polinomios mónicos (con coeficiente principal igual a 1) irreducibles sobre de grado 4.

Notemos que un polinomio , de cuarto grado, es irreducible si no tiene divisores de grado 1 o 2 en Por tanto podemos calcular todos los productos de las formas y y compararlos con la lista de los polinomios mónicos de grado 4 en Encontramos entonces que

y

son los polinomios irreducibles que buscamos.

1.1.3 Caracterización de los campos finitos

Por el momento sólo tenemos como ejemplo de campo finito a ( primo). A continuación denotaremos por al campo de elementos (no decimos "un campo de elementos" porque un campo finito de un orden determinado es único salvo isomorfismo).

Teorema 1.11

El anillo de restos donde es un polinomio mónico irreducible de grado es un campo. Este será el campo , que se llama extensión algebraica de de grado (y se obtiene al adjuntarle a una raíz del polinomio irreducible

Este campo está conformado por los polinomios de de grado menor que , por tanto tiene elementos. Sea una raíz de se puede representar como el conjunto de los polinomios en de grado con coeficientes en en este caso se llama elemento definitorio de Es decir

Este teorema da una forma de representar los elementos del campo mediante la raíz de un polinomio irreducible sobre a este se le llama polinomio característico de la extensión

Ejemplo 1.12

Siendo raíz de , que es irreducible sobre Entonces puede representarse por el conjunto

con la suma y la multiplicación usuales en

y reduciendo los elementos de grado mayor que uno mediante la relación Si queremos calcular por ejemplo

se tendría

Otra forma de ver la extensión es como espacio vectorial de dimensión sobre La representación que acabamos de dar nos permite tomar al conjunto donde es el elemento definitorio de como una base de a esta base se le llama base polinomial. Los elementos de quedarán representados entonces en la forma donde

Vimos cómo se extiende el campo adjuntando la raíz de un polinomio irreducible de grado para obtener el campo ¿Pero qué podemos decir de un campo que contiene a

Teorema 1.13

Sea un campo finito que contiene a entonces tiene elementos, para algún

La demostración se obtiene considerando a

como espacio vectorial finito dimensional sobre de dimensión

Del teorema anterior se deduce una característica esencial de los campos finitos.

Teorema 1.14

Sea un campo finito de característica entonces tiene elementos, para algún

Teorema 1.15

Dado el campo finito con elementos, todo subcampo de

tendrá entonces elementos, donde es un divisor de

La demostración se obtiene al aplicar el teorema 1.11 considerando a como subcampo de por tanto tiene característica y es una potencia del orden de

Definición 1.16

Sean los campos y donde es una extensión de Si un polinomio tiene todas sus raíces en , y es la menor extensión de con esta característica, se dice que es el campo de descomposición de F sobre o que se descompone en

Teorema 1.17

Sea un campo y un polinomio de grado positivo en entonces existe un campo de descomposición de

sobre Dos campos de descomposición de sobre son isomorfos bajo un isomorfismo que deja fijos los elementos de y deja invariante el conjunto de las raíces de

Es evidente que el campo de descomposición de un polinomio es el menor campo que contiene todas sus raíces, así que el teorema anterior se deduce del proceso de adjuntar a

las raíces de y la segunda parte de la unicidad de los campos finitos.

De lo visto sobre polinomios irreducibles y su relación con las extensiones de campos podemos deducir que un polinomio cualquiera sobre un campo se descompone en factores lineales con y factores irreducibles (de grado

sobre >1 Está claro que si se adjuntan todas las raíces de se obtiene su campo de descomposición. Una pregunta interesante es la siguiente: ¿Se obtendrá el campo de descomposición de si se extiende adjuntándole un subconjunto de las raíces de La respuesta yace en el siguiente teorema.

Teorema 1.18

Si es un polinomio irreducible sobre de grado entonces tiene una raíz en Es más, todas las raíces de se hallan en y están dadas por los elementos de

Corolario 1.19

Si es irreducible sobre de grado entonces es su campo de descomposición. Si no es irreducible sobre su campo de descomposición es el menor campo en que se descomponen todos los factores irreducibles de

Definición 1.20

Los elementos de una extensión de se llaman conjugados de Fq con respecto a

En el siguiente teorema veremos una propiedad útil sobre los elementos de resultado de que sea un grupo (de orden finito) bajo la operación de multiplicación.

Teorema 1.21

Todo elemento cumple la propiedad

Del teorema anterior se deduce una característica del polinomio de particular importancia en la teoría de campos finitos.

Lema 1.22

El polinomio se descompone en como y

es su campo de descomposición.

Del lema anterior se deduce que todo elemento de un campo finito es raíz de un polinomio en considerar por ejemplo al polinomio mónico de menor grado con esta propiedad para un elemento determinado

se le llama polinomio mínimo de

sobre

y se demuestra fácilmente que dicho polinomio es irreducible.

Los teoremas 1.13, 1.14 y 1.15 ofrecen una visión más clara sobre el número de elementos en un campo finito, la que en cierto sentido se refuerza con el siguiente teorema.

Teorema 1.23

Para todo primo y natural existe un campo finito con elementos

Para la demostración se considera el campo de descomposición del polinomio sobre el campo primo Siendo dicho campo de descomposición, se considera entonces el conjunto o sea, el conjunto de raíces de en f se demuestra entonces que es un subcampo de y al contener todas las raíces de , por la definición 1.14 Así que S=F es un campo con elementos.

Existen además otras formas de representar un campo una muy común es como potencias de un elemento fijo. Para verlo, primero es necesario enunciar el siguiente teorema.

Teorema 1.24

El grupo multiplicativo de un campo (denotado es cíclico. Un generador de se llama elemento primitivo de

De este teorema se deducen conclusiones importantes.

Teorema 1.25

Toda extensión de un campo se puede considerar como una extensión de al adjuntarle un solo elemento (a este tipo de extensiones se les denomina simples).

Para la demostración se considera extender al adjuntarle un elemento primitivo de De este razonamiento se deduce también que para cualquier natural existe un polinomio irreducible en de grado este será el polinomio mínimo de un elemento primitivo de

Teorema 1.26

Los elementos conjugados de un con respecto a cualquier subcampo de

tienen un mismo orden en el grupo multiplicativo

Se demuestra a partir de la relación entre el orden de un elemento en un grupo cíclico y el orden de para lo que se tiene en cuenta que am para cualquier

El polinomio mínimo de un elemento

está dado por y su grado es un divisor de .

Definición 1.27

Sea una extensión de cuyo elemento definitorio es raíz de un polinomio irreducible de grado Si todo elemento de se puede expresar como una potencia de (equivalentemente, es un elemento primitivo de se dice entonces que es un polinomio primitivo.

Al ser un grupo cíclico, siempre existe en él un elemento (y un polinomio) primitivo.

Esto nos permite plantear siempre que sea raíz de un polinomio primitivo sobre

La definición anterior se puede transcribir como sigue:

Definición 1.28

El polinomio de grado se llama polinomio primitivo sobre el campo si es el polinomio mínimo sobre el campo de cierto elemento primitivo de la extensión del campo