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
Página siguiente |