Algoritmo de Berlekamp-Massey (ABM)

ALGORITMO DE BERLEKAMP-MASSEY

El algoritmo de Berlekamp-Massey (ABM) hace uso de la complejidad lineal de una secuencia binaria finita sn 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 sk que consiste en los primeros k términos de sn (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 sN = s0, s1, s2, ..., sN-1. Para un polinomio C(D) = 1 + c1D + ... + CLDL, de grado L, sea {L,C(D)} un LFSR que genera la subsecuencia sn= s0, s1, s2, ..., sn-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 dn (Menezes et al., 1996) es la diferencia entre sn 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 sn =s0, s1, s2, s3,…, sn-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:

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.

Secuencia binaria

1ª Iteración

k=0;

Se calcula la discrepancia con sk = s0.

Si d=1, se calcula .

Si d=0, permanece constante.

2ª Iteración

k=1;

Se calcula la discrepancia con s0 y s1.

Si d=1, se calcula.

Si d=0, permanece constante.

3ª Iteración

k=2;

Se calcula la discrepancia con s0, s1 y s2.

Si d=1, se calcula.

Si d=0, permanece constante.

Si k = n-1 entrega L y, en otro caso se incrementa el contador.

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:

sn: 011101101001

El resultado que se obtiene es:

P(X)= 1+X+ X6.

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 Xm+1 es divisible solo por P(X), con m=2L-1 y L = 6, pero no lo es, cuando m<2L-1. Por tanto, la secuencia de salida total generada tiene un periodo máximo (2L-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.

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 ALTERATM 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 AlteraTM. 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+X6 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+X6. 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.

Library

...