Información Tecnológica-Vol. 17 N°3-2006, pág.: 167-178

ARTICULOS VARIOS

Complejidad Lineal y Algoritmo Berlekamp-Massey para la Construcción de Generadores de Secuencias Pseudoaleatorias

Linear Complexity and the Berlekamp-Massey Algorithm in the Construction of Pseudorandom Sequence Generators

Francisco I. Peralta, Gonzalo I. Duchén y Rubén Vázquez
Instituto Politécnico Nacional, ESIME Unidad Culhuacan, Sección de Estudios de Posgrado e Investigación,
Av. Santa Ana, 1000, Col. San Francisco Culhuacan, C. P. 04430, Coyoacan, México D. F.-México (e-mail: gduchen@ieee.org)

Resumen

Este artículo presenta un estudio sobre la construcción de generadores de secuencias pseudoaleatorias. Se muestra que al combinar un lenguaje de descripción de hardware, con el resultado que produce el algoritmo de Berlekamp-Massey, se puede diseñar e implementar en un circuito reprogramable la función de un Registro de Desplazamiento con Retroalimentación Lineal. Se presenta también el diseño del Generador Multivelocidad utilizando combinaciones de la función generada, así como también su simulación utilizando las herramientas que proporciona ALTERA^TM. Inicialmente, se explica el uso de polinomios primitivos en la construcción de Registros de Desplazamiento con Retroalimentación Lineal y se muestra la debilidad de utilizar uno solo en la generación de secuencias pseudoaleatorias. Esto último justifica el uso de arreglos de Registros para su uso en cifradores de flujo.

Palabras claves: Berlekamp-Massey, generadores de secuencias, generador multivelocidad, registros de desplazamiento

Abstract

This article presents a study on the construction of pseudorandom sequence generators. It is shown that by combining a hardware description language and the result of the Berlekamp-Massey algorithm, the function of a linear feedback shift register can be produced and implemented in a reprogrammable chip. It also shows the design of the Multispeed Generator using combinations of the generated function, and its simulation using tools provided by ALTERA^TM. Initially, we explain the use of primitive polynomials in the construction of linear feedback shift registers, and show the weakness of using only one in the generation of pseudorandom sequences. The latter justifies the use of registers on stream ciphers.

Keywords:  Berlekamp-Massey, sequence generators, multispeed generator, shift registers

INTRODUCCIÓN

La protección de información por medio de técnicas criptográficas es, hoy en día, una práctica muy importante para la transferencia segura de datos. La criptografía se puede aplicar por ejemplo, para dar confidencialidad a un mensaje o garantizar la autenticidad de criptogramas y/o remitentes y destinatarios. El criptograma recibido debe ser realmente el enviado, y se espera detectar manipulaciones o alteraciones en el proceso de transmisión. Así mismo, es deseable que sean quienes dicen ser y no remitentes y/o destinatarios fraudulentos. Para ello es necesario algún mecanismo que lo garantice.

Existen distintos tipos de cifrado (Chan et al, 2004) que ayudan a otorgar atributos de seguridad a una comunicación, como el cifrado de flujo que cifra bit a bit los datos de un texto claro, utilizando una secuencia cifrante y una función booleana. Este cifrado, realizado con LFSR (por las siglas en inglés de Linear Feedback Shift Register) posee las siguientes propiedades importantes:

1. Los LFSR se pueden realizar fácilmente en hardware (Danger et al, 2000).

2. Se generan secuencias con un periodo T grande, con T = 2^L-1 y L la longitud del LFSR.

3. Las secuencias tienen buenas propiedades estadísticas, que pueden evaluarse con los postulados de Golomb (Rueppel, 1986):

a. La diferencia en el número de unos y ceros dentro de cada periodo de la secuencia no debe exceder a la unidad.

b. En todo el periodo, (1/2ⁱ) es la fracción (del total de gramas en todo el periodo) de i-gramas de longitud i.

c. La función de autocorrelación AC(k) fuera de fase es constante para todo valor k (Fuster et al., 2001).

4. Debido a su estructura, pueden analizarse usando técnicas algebraicas, una de éstas la complejidad lineal.

En telecomunicaciones es muy utilizado con las siguientes consideraciones:

Cuando el espacio de almacenamiento es limitado.

Cuando los caracteres deben procesarse individualmente y recibirse de la misma forma.

Cuando el error de transmisión tiene una probabilidad alta.

En seguida se presenta una breve discusión acerca de los LFSR, polinomios primitivos y complejidad lineal (Meidl et al, 2002) y (Meidl, 2005). Posteriormente se presenta el algoritmo de Berlekamp-Massey (Greenberg et al, 2004) y cómo utilizar los resultados de éste en la generación tanto del LFSR, como del generador multivelocidad. Ambos diseños se realizaron usando VHDL (VHSIC Hardware Description Language) y se simularon con el sistema MAX+PLUS II de ALTERA. En la parte final se presentan los códigos fuente en VHDL y algunos resultados de simulación.

REGISTRO DE DESPLAZAMIENTO CON RETROALIMENTACIÓN LINEAL

Un LFSR de longitud L consiste en L etapas (o unidades de almacenamiento) numerados desde 0 hasta L-1, cada una capaz de almacenar un bit; tiene una entrada, una salida, una función de retroalimentación y un reloj que controla el flujo de datos entre las distintas etapas. Los primeros datos de la secuencia pseudoaleatoria son los datos iniciales del registro de L etapas (Cheng, 2002).

Durante cada unidad de tiempo se realizan las siguientes operaciones (Menezes et al., 1996):

1. El contenido de la etapa 0 es la que otorga el flujo de salida.

2. El contenido de la etapa i se traslada a la etapa i - 1 considerando que, ; y

3. El nuevo contenido de la etapa L-1 es el bit de retroalimentación s_j, que se calcula por medio de una función booleana que depende de la combinación de los contenidos de ciertas etapas predefinidas.

La figura 1 muestra la estructura general de un LFSR de longitud L. Cada c_i es 0 o 1; el bit s_j es una combinación lógica lineal del contenido de las L etapas, según sea el valor del vector {c}. Los LFSR son máquinas secuenciales lineales, lo cual significa que pueden ser construidos con base en flip-flops y compuertas XOR. Si se inicializan con valores diferentes a cero, se pueden obtener secuencias de números binarios con periodos largos, dependiendo de la posición de las compuertas XOR y el número de etapas que tenga el LFSR (Jenkins, 2003).

Fig. 1: LFSR de longitud L.

Un LFSR puede generar secuencias pseudo-aleatorias de tamaño máximo 2^L - 1 (no 2^L, porque un registro de desplazamiento que se llena con ceros, provoca que la secuencia de salida del LFSR sea una secuencia infinita de ceros). La secuencia resultante se denomina m-secuencia (Schneier, 1996).

Para que un LFSR tenga el periodo máximo (2^L - 1), el polinomio formado por {c} más 1 debe ser un polinomio primitivo módulo 2 (Schneier, 1996). A continuación se dan algunas definiciones para conocer las características que deben cumplir los polinomios primitivos.

POLINOMIOS PRIMITIVOS

El siguiente análisis es importante para poder determinar el grado del polinomio, ya que éste indica cuál será la longitud del LFSR. Como antecedente es necesario saber que un polinomio primitivo es irreducible, aunque no todo polinomio irreducible es primitivo. Por otra parte, un polinomio binario primitivo p(x) de grado L existe sobre todo el campo de Galois y todo campo de Galois tiene al menos un elemento primitivo (Reee, 1989).

Considérense las siguientes definiciones:

Definición. Si hay un polinomio p(x) tal que, r(x)p(x)=s(x), se dice que el polinomio s(x) es divisible por el polinomio r(x) o que r(x) divide a s(x). Un polinomio diferente de cero p(x) que solo es divisible por p(x) se dice irreducible ya que no puede ser escrito como el producto de dos polinomios, cada uno de grado positivo (Rhee, 1989).

Definición. Un polinomio irreducible p(x) de grado L se dice que es primitivo solo si

1) p(x) divide a Xⁿ + 1, cuando n = 2^L - 1, y

2) p(x) no divide a Xⁿ + 1, cuando n < 2^L - 1.

Las razones para usar polinomios primitivos y no factorizables ni irreducibles en la realización de los LFSR son:

LFSR con polinomio de realimentación factorizable.

1) La longitud de la secuencia cifrante depende de la semilla (estado inicial de los registros).

2) El periodo máximo, T, estará en el intervalo: L ≤ T < 2^L-1.

También pueden existir períodos secundarios que sean divisores de T. Por tanto, no es conveniente usar polinomios factorizables por la dependencia que existe entre la longitud de la secuencia y la semilla, y porque no se garantiza una secuencia de periodo máximo

LFSR con polinomio de realimentación irreducible.

1) La longitud de la secuencia no depende de la semilla.

2) El período T es un divisor de 2^L – 1 y dependerá de qué polinomio se esté utilizando.

Aunque se elimina la dependencia de la semilla tampoco se garantiza una secuencia de periodo máximo.

Por el contrario, un polinomio primitivo garantiza que la longitud de la secuencia generada no dependerá de la semilla y que las secuencias generadas tendrán un periodo máximo 2^L – 1.

Ahora bien, considérese un LFSR definido por [L, C(x)] siendo L la longitud del LFSR y C(x) el polinomio que define su retroalimentación. Se dice que si [L, C(x)] es singular, esto es, C(x) tiene grado menor que L, entonces no todas las secuencias de salida generadas serán periódicas. Por ello se recomienda que el grado del polinomio sea L es decir, el LFSR debe ser no singular.

Periodo de las secuencias de salida de los LFSR

Sea C(x) Є Z₂ un polinomio de grado L

1). Si C(x) es irreducible sobre Z₂, entonces cada uno de los 2^L-1 estados iniciales del LFSR no singular [L, C(x)], producen una secuencia de salida con periodo igual al menor entero positivo n tal que C(x) divide a 1+xⁿ en Z₂. (Este es el caso en que n es un divisor de 2^L-1.)

2). Si C(x) es un polinomio primitivo, entonces cada uno de los 2^L-1 estados iniciales del LFSR no singular [L, C(x)], produce una secuencia de salida con el periodo máximo posible 2^L-1 (Menezes et al., 1996).

COMPLEJIDAD LINEAL

Que un LFSR genere una secuencia con periodo máximo no implica que el cifrar alguna información con ella sea seguro. La complejidad lineal es una métrica importante para analizar a los LFSR y los generadores basados en LFSR, ya que mide la robustez o seguridad de un generador de secuencias pseudoaleatorias o cifrador de flujo. Una complejidad lineal grande no garantiza la seguridad de un cifrador de flujo, para hacerlo, se debe garantizar que la secuencia de salida tenga una complejidad lineal estable y no solamente grande. De acuerdo con Ding et al. (1991), se deben tomar en cuenta dos definiciones para determinar la estabilidad de la complejidad lineal: 1) La complejidad ponderada (Weight Complexity) y 2) La complejidad esférica (Sphere Complexity).

Para determinar la estabilidad, se calcula la complejidad ponderada y la esférica y se comparan por separado con la complejidad lineal. Si difieren sustancialmente, entonces se dice que la complejidad es inestable, en caso contrario es estable. En Criptografía, lo que interesa es conocer qué tanto disminuye la complejidad lineal de una secuencia, después de cambiar un cierto número de bits en ella, pero no cuánto se incrementa.

Concretamente, la complejidad lineal se define como la longitud L, del LFSR más pequeño o SLFSR (del inglés Shortest Linear Feedback Shift Register) que puede imitar la salida del generador. A continuación se darán las definiciones formales relacionadas con la complejidad lineal (Massey, 1996).

Definición. Sea s = s₀, s₁, s₂, ... una secuencia infinita. La subsecuencia que consiste en los primeros n términos de s se denota por sⁿ= s₀, s₁, s₂, ..., s_n-1.

Definición. Un LFSR genera una secuencia s, si hay un estado inicial para el cual la secuencia de salida del LFSR es s. De forma similar, un LFSR genera una secuencia finita sⁿ, si hay algún estado inicial para el cual la secuencia de salida del LFSR tiene sⁿ como sus primeros n términos.

Definición. La complejidad lineal L(s), de una secuencia binaria infinita s, se define como:

1) Si s es la secuencia cero s = 0, 0, 0,…, entonces L(s)=0;

2) Si ningún LFSR genera s, entonces L(s)=¥;

3) De otra forma, L(s) es la longitud del LFSR más pequeño que genera s.

Propiedades de la Complejidad Lineal.

Sean s y t secuencias binarias.

1) Para cualquier n ≥ 1, la complejidad lineal de la subsecuencia sⁿ satisface 0 ≤ L(sⁿ) ≤ n.

2) L(sⁿ) = 0 si y solo si sⁿ es la secuencia cero de longitud n.

3) L(sⁿ) = n si y solo si sⁿ = 0, 0, 0,..., 0 , 1.

4) Si s es periódica con periodo N, entonces L(sⁿ) ≤ N.

5) L(sÅt) ≤ L(s) + L(t), donde sÅt denota la operación XOR de los bits de s y t (Menezes et al., 1996).

Se sabe que el SLFSR generado a partir de una secuencia tiene una gran importancia práctica, en especial en criptografía y teoría de códigos. El algoritmo de Berlekamp-Massey es eficiente para obtener el SLFSR de una secuencia y se desarrolla a continuación.

ALGORITMO DE BERLEKAMP-MASSEY

El algoritmo de Berlekamp-Massey (ABM) hace uso de la complejidad lineal de una secuencia binaria finita sⁿ de longitud n para medir la robustez de un cifrador de flujo (Ding et al., 1991). El algoritmo toma k iteraciones, con la k-ésima iteración escribe la complejidad lineal de la subsecuencia s^k que consiste en los primeros k términos de sⁿ (Menezes et al., 1996). Además, puede generar el SLFSR después de examinar solo 2L bits de la secuencia de salida, donde L es la longitud del LFSR. Una vez generado, se podrá romper el cifrador ya que se conoce el polinomio con el cual se construye el SLFSR, esto es citado por Schneier (1996) y Ekdahl (2003).

Definición. Considere la secuencia binaria finita s^N = s₀, s₁, s₂, ..., s_N-1. Para un polinomio C(D) = 1 + c₁D + ... + C_LD^L, de grado L, sea {L,C(D)} un LFSR que genera la subsecuencia sⁿ= s₀, s₁, s₂, ..., s_n-1. Donde N es la longitud de la secuencia total generada por el LFSR y n es la longitud de una subsecuencia de la secuencia total. La discrepancia d_n (Menezes et al., 1996) es la diferencia entre s_n y el último bit generado por el LFSR:

La demostración de que este algoritmo es correcto se puede consultar en Ding et al. (1991).

EL ABM es un algoritmo iterativo que analiza una secuencia sⁿ =s₀, s₁, s₂, s₃,…, s_n-1, como se muestra en la Tabla 1. En el primer paso se inicializan las variables operativas del programa y las que representan al polinomio de combinación y la complejidad lineal.

La Inicialización de variables se realiza de la siguiente forma:

, , ,    y

Para calcular la discrepancia se usa la ecuación (1). Y para calcular el vector C(x) se hace uso de las variables T(x), B(x), k y m.

y

Tabla 1: Iteraciones del ABM

En la figura 2 se muestra el diagrama de flujo del algoritmo de Berlekamp-Massey.

Por ejemplo, al introducir al ABM una secuencia de bits como la siguiente:

sⁿ: 011101101001

El resultado que se obtiene es:

P(X)= 1+X+ X⁶.

Con este polinomio se puede construir un LFSR que consistirá en 6 etapas y se realizará una operación XOR con las salidas de las etapas 6 y 1. Este polinomio es primitivo, ya que X^m+1 es divisible solo por P(X), con m=2^L-1 y L = 6, pero no lo es, cuando m<2^L-1. Por tanto, la secuencia de salida total generada tiene un periodo máximo (2^L-1) =63.

Las figuras 3 y 4 muestran cada uno de los bits de salida del LFSR de 6 etapas, así como los instantes de inicio y final de la secuencia.

Esta salida se encuentra en el puerto Qsal. Como un LFSR es un circuito sincrónico, cada cambio de estado está sincronizado por un pulso de reloj que se encuentra representado en las figuras 3 y 4 por el puerto clk.

Fig. 2: Diagrama de flujo del algoritmo de Berlekamp – Massey.

Este LFSR contiene un puerto con la etiqueta ci y permite cargar cualquier semilla o estado inicial y empezar la operación.

Es decir, cuando el puerto tiene un 1 lógico se puede cargar la semilla para el LFSR y cuando tiene un 0 lógico el LFSR comienza a realizar las operaciones. Cuando se hace un diseño usando VHDL, la herramienta de ALTERA^TM le asigna por omisión un retardo a cada uno de los dispositivos dentro del circuito integrado utilizando.

El diseño del LFSR y el Generador Multi-velocidad que se trata más adelante, han sido simulados en un circuito reprogramable de la familia MAX7000S (EPM7128SLC84-7) y ocupa el 27% de los recursos del chip utilizando MAX+PLUS II de Altera^TM. Es importante mencionar que no se ocupó ninguna directriz especial de síntesis para optimizar el diseño. Con dicha herramienta se pueden crear proyectos jerárquicos completos en VHDL, o combinar archivos de diseño en VHDL con otro tipo de diseños en proyectos jerárquicos. Además, se pueden incorporar funciones a la medida, es decir, funciones que fueron diseñadas para cubrir un aspecto específico de nuestro proyecto. A continuación se muestra la secuencia total generada por el LFSR construido a partir del polinomio 1+X+X⁶ y la semilla 101110.

Secuencia:

011101101001001110001011110010100011000010000011111101010110011…

Con el ABM y tomando solo 2L bits de cualquier porción de esta secuencia (en este caso L = 6 o sea 12 bits), se puede encontrar que el LFSR que genera esa secuencia tiene el polinomio como ya sabemos 1+X+X⁶. Por lo tanto, el cifrado usando la secuencia de salida de un LFSR, no asegura que la información esté protegida, pues es relativamente sencillo obtener esta información con criptoanálisis, si se conocen 2L bits de la secuencia que se usó para cifrarla (salida del LFSR).

GENERADOR MULTIVELOCIDAD EN VHDL

Si combinamos el resultado que ofrece el algoritmo de Berlekamp-Massey con el uso de un lenguaje de descripción de hardware como VHDL, se puede desarrollar un programa que genere un LFSR a partir del polinomio que entregue el algoritmo. El diseño de un LFSR en VHDL es muy sencillo, además se puede aprovechar esta herramienta para construir generadores de secuencias pseudoaleatorias que usan combinaciones de LFSR, como el Generador Multivelocidad de este artículo.

Este generador utiliza 2 LFSR (LFSRL tabla 2 y LFSRM tabla 3) que funcionan a distintas frecuencias de reloj como se muestra en la figura 5 y el código en VHDL en la tabla 4. El LFSR de L etapas trabaja con un reloj d ≥ 2 veces más que el de M etapas con L ≥ M. El factor d es variable y se usa como parte de la clave.

Fig. 3: Inicio de la secuencia pseudoaleatoria del LFSR en t = 14.5 ns.

Fig. 4: Final de la secuencia pseudoaleatoria del LFSR en t = 1.2745 ms.

Fig. 5: Generador multivelocidad de Massey-Rueppel

Según Rueppel (1986) la diferencia de frecuencia entre los LFSR proporciona flexibilidad y seguridad en aplicaciones criptográficas. Se pueden simular diferentes conexiones de retroalimentación sin cambiar físicamente sus estados es decir, el polinomio primitivo que indica la retroalimentación se puede dejar constante y lo que se modifica es la frecuencia, que es más fácil que cambiar los polinomios de retroalimentación.

La incertidumbre acerca de la recursión utilizada en un generador de secuencias pseudoaleatorias hace más difícil el trabajo de un criptoanalista.

En particular, la diferencia de frecuencia entre los LFSR disuade al criptoanalista de intentar un ataque de correlación sobre una combinación no lineal de LFSR, pues intentaría buscar a través de todas las recursiones posibles. Los límites del factor d dependen de la frecuencia de reloj de la tecnología utilizada y de la frecuencia de reloj deseada. Cuando el factor de frecuencia se pone bajo control de una llave secreta, tal diferencia suma un grado más de seguridad en el diseño del generador de secuencias.

Propiedades del generador multivelocidad

Si los LFSR empleados en el generador se forman con polinomios irreducibles, sus grados L y M son primos relativos y los factores d₁ ≠ d₂ se escogen tal que:

Si  y  son los periodos de los LFSR, entonces b(t) tendrá complejidad lineal:

Con periodo:

donde q denota el campo de Galois (GF(q)), en este caso q=2 que denota el campo binario (Rueppel, 1986).

Tabla 2: Código en VHDL del LFSRL.

Cuando el generador está restringido a emplear LFSR de longitud L y M ( L > M) con polinomios primitivos sobre GF(2), entonces el número de unos y ceros dentro de un periodo l=(2^M-1)(2^L-1) de la secuencia de salida b(t) son:

La diferencia de U(1) y U(0) dividida entre la longitud l del periodo es

Tabla 3: Código en VHDL del LFSRM.

Tabla 4: Código en VHDL del Generador Multivelocidad.

Debe mencionarse que para q>2, los resoltados estadísticos no son tan fáciles de obtener (Rueppel, 1986). Aunque este generador posee una complejidad lineal alta y excelentes propiedades estadísticas, Zeng et al., (1989) demostraron, que conociendo los polinomios de realimentación, el criptoanalista puede determinar el factor de frecuencia d y el contenido inicial de ambos registros mediante (d-1)(2^l-1) pruebas de consistencia aplicados a un segmento de salida de longitud

PRUEBAS Y RESULTADOS

Se introdujo secuencias de bits al ABM para obtener polinomios que sirven como entrada al código en VHDL para generar los LFSR. A partir de estos, se construye el Generador Multivelocidad. Las secuencias de bits utilizadas en este caso son  las siguientes:

1) Para el LFSR de M etapas:

S=101010001011110000.

2) Para el LFSR de L etapas:

S = 10011101111101110010001.

El ABM  proporcionó para el primer caso el siguiente polinomio:

 ;    M = 7   

que tiene un periodo de 21 con la siguiente semilla: 0101000.

En el segundo caso, el polinomio obtenido es

;  L=10

El periodo de la secuencia de este polinomio es 4 con la siguiente semilla: 1101110111

El código en VHDL para este generador se muestra en la tabla 2 con M = 7 y L = 10 y la simulación se observa en las figuras 6 y 7.

La secuencia de salida del Generador Multivelocidad, usando un factor de frecuencia d=2, es la siguiente.

Secuencia:

100001110111100101000100110011010110010010

Este generador proporciona una secuencia con periodo T = 42. El instante en que el generador comienza a entregar los bits de salida es en t = 34.5 ns, y cuando entrega la secuencia completa es en t = 3.3895 μs. Cada estado en el generador permanece constante durante 80 ns.

Como se observa, no se obtuvo el periodo máximo dado por (2^M_1)(2^L_1) y por lo tanto la complejidad lineal de la ecuación (3), no se cumplirá, debido a que:

1) los polinomios que se obtuvieron por medio del ABM no son primitivos,

2) la condición , no se cumple debido a que , y

3) debido a estas razones las ecuaciones (5), (6) y (7), no se cumplen.

Ahora, se construirá el mismo generador pero usando polinomios primitivos.

1) El LFSR de M-etapas es:  y su semilla es: 101110.

2) El LFSR de L-etapas es:  y su semilla es: 100000000000011.

El factor de frecuencia continuará siendo d=2.

Como se están utilizando LFSR con polinomios primitivos se debe cumplir que:

El periodo de la secuencia de salida debe ser:

El máximo común divisor es:

 y

y el número de 0´s y 1´s como se establece en (5) y (6) es:

En las figuras 8 y 9 se muestran el instante de inicio en  T= 24.5 ns y final en T=165.1457045 ms de la simulación.

Fig. 6: Inicio de la secuencia pseudo aleatoria en t = 34.5 ns

Fig. 7: Final de la secuencia pseudo aleatoria en t = 3.3895 ms.

Fig. 8: Inicio de la secuencia pseudo aleatoria en t = 24.5 ns

Fig. 9: Final de la secuencia pseudo aleatoria en t = 165.1457045 ms

CONCLUSIONES

Se presentó el algoritmo de Berlekamp-Massey como una herramienta muy eficaz para analizar la seguridad de los LFSR. Se mostró que con 2L bits de la secuencia de un LFSR para cifrar información, ésta no se protege y se puede encontrar el polinomio con el cual se construye el SLFSR que genera la secuencia con que se cifró la información.

También se presentó el Generador Multivelocidad de Massey-Rueppel. Como el polinomio generado por el ABM no es primitivo, no se garantiza ofrecer un periodo máximo al implementarlo en un LFSR. Por tanto, construir generadores más robustos, como el Generador Multivelocidad, con estos polinomios que no cumplen con las propiedades de construcción de este generador en particular, no se podrá obtener una secuencia con periodo máximo. Con polinomios primitivos y cumpliendo las propiedades del Generador Multivelocidad, se pueden obtener secuencias con periodos máximos y buenas propiedades criptográficas. Además, utilizar VHDL hace más sencilla la construcción de generadores de secuencias pseudoaleatorias.

El campo de la criptografía aún está abierto y queda todavía mucho trabajo por realizar. Se están empezando a desarrollar sistemas de criptografía cuántica y el campo del cifrado caótico también ofrece grandes posibilidades. En estos casos, las herramientas presentadas en este trabajo pueden ser de utilidad. Se puede, por ejemplo, analizar la posibilidad de utilizar cambios de frecuencia caóticos en el generador multivelocidad, como una forma adicional de cifrado.

AGRADECIMIENTOS

Se agradece el apoyo otorgado por el CONACyT y la COFAA para la realización de este trabajo de investigación.

REFERENCIAS

Chan, K. S. y F., Fekri, “A Block Cipher Cryptosystem Using Wavelets Transforms Over Finite Fields”, IEEE Transactions on Signal Processing, 52(10), 2975-2991(2004).         [ Links ]

Cheng, M., “Generalised Berlekamp-Massey algorithm”, IEE Proceedings Comunications,  149(4), 207-210(2002).        [ Links ]

Danger, J. L.; A., Ghazel; E., Boutillon; H., Lamari; “Efficient FPGA implementation of Gaussian noise generator for communication channel emulation”, 7th IEEE International Conference on Electronics, Circuits and Systems ICECS, 1,  366-369(2000).        [ Links ]

Ding C., G. Xiao, y W. Shan, “The Stability Theory of Stream Ciphers”, Springer-Verlag Berlin Heidelberg(1991).        [ Links ]

Ekdahl P., “On LFSR based Stream Ciphers - analysis and design”, Ph.D. Thesis, Faculty of Technology, Lund University, (2003).         [ Links ]

Fuster A., D. de la Guia, L. Hernandez, F. Montoya y J. Muñoz, “Técnicas Criptográficas de protección de datos”, 2a Edición, Alfaomega (2001).        [ Links ]

Greenberg, S., Feldblum, N., Melamed, G., “Implementation of the Berlekamp-Massey algorithm using a DSP”, Proceedings of the 11th IEEE International Conference on Electronics, Circuits and Systems,ICECS, 358-361(2004).        [ Links ]

Jenkins J., “CipherStream Protocol: How CoolRunner-II CPLDs Protect FPGA IP”, Xilinx, 1, 1-14(2003).         [ Links ]

Massey J. L., y S. Serconek, “Linear Complexity of Periodic Sequences: A General Theory, Advances in Cryptology”, CRYPTO'96, Lecture Notes in Computer Science No. 1109, Springer, New York, USA 358-371(1996).        [ Links ]

Meidl, W., “On the stability of 2/sup n/-periodic binary sequences”, IEEE Transactions on Information Theory,51,  3, 1151-1155 (2005).        [ Links ]

Meidl, W., H., Niederreiter; “On the expected value of the linear complexity and the k-error linear complexity of periodic sequences”, IEEE Transactions on Information Theory, 48 (11), 2817-2825(2002).        [ Links ]

Menezes A., P. Van, Oorschot, y S. Vanstone, “Handbook of Applied Cryptography”, CRC Press (1996).        [ Links ]

Rhee M., “Error Correcting Coding Theory”, Mc Graw-Hill Communications Series (1989).        [ Links ]

Rueppel R. A., “Analysis and Desing of Stream Ciphers”, Springer-Verlag (1986).        [ Links ]

Schneier B., Applied Cryptography: Protocols Algorithms and Source Code in C, Second Edition, John Wiley & Sons, USA (1996).        [ Links ]

Zeng, K. C., C. H. Yang, y T. R. Rao, “On the Linear Consistency Test (LTC) in Crypto-analysis with Applications”, Proc Crypto´89, Lecture Notes in Computer Science, 164-174(1989)        [ Links ]

©  2014  Centro de Información Tecnológica

Casilla de Correos 724

La Serena

FonoFax: 56-51-551158


citchile@entelchile.net