LFSR

LFSR significa linear feedback shift register, que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a un estado anterior.

El valor inicial se denomina semilla y, como la forma de operar el registro es determinista, la secuencia de valores producidos está completamente determinada por el estado actual o el estado anterior. La secuencia tiene un periodo de repetición, es decir que la secuencia vuelve a generarse y se repite indefinidamente. Cuando el periodo de repetición es máximo, ese LFSR tiene interés criptográfico.

Veamos un ejemplo, tenemos la secuencia [16,14,13,11].

La secuencia tap de un LFSR se puede representar como un polinomio mod 2. Esto significa que los coeficientes del polinomio deben ser 1's o 0's. Esto se llama polinomio de realimentación o característica polinomial.

Por ejemplo, si los taps están en las posiciones de los bits: 16, 14, 13 y 11 ,el polinomio LFSR resultante es:

Las salidas que influyen en la entrada, se denominan taps. Son las que aparecen en el polinomio. Y se indican en azul en el esquema inferior.

Un LFSR se puede caracterizar de forma polinómica según sean sus conexiones y los valores de los registros.

Se define el polinomio de Estado como:

El polinomio de estado muestra el valor de los registros.

De la misma forma se define el polinomio de Conexiones (Polinomio Conectivo)como:

Donde cada coeficiente ${displaystyle C_{i}}$ vale 0 o 1 dependiendo de si hay conexión o no. Hay que notar que el polinomio de conexiones (Polinomio Conectivo) es siempre un grado mayor que el de estado.

De esta manera un LFSR con n registros de desplazamiento tendrá como mínimo 2 conexiones la de ${displaystyle C_{0}}$ y la de ${displaystyle C_{n+1}}$. La conexión de ${displaystyle C_{0}}$ es necesaria porque sin ella el primer registro siempre valdría cero y por tanto no influiría en el comportamiento del LFSR. La conexión ${displaystyle C_{n+1}}$ es necesaria porque asegura la retroalimentación del LFSR. Si este coeficiente valiera 0 (o lo que es lo mismo, no hubiera esta conexión), el LFSR ya no sería de grado n+1.

Por lo tanto para pasar de un estado al siguiente los registros se desplazan. Este desplazamiento se puede expresar en forma polinómica como una multiplicación por D. El polinomio resultante tiene grado n+1 al igual que el polinomio de conexiones. Esto es un problema ya que el polinomio de estado tiene que ser de grado n. Esto se soluciona haciendo que el polinomio resultante sea módulo de C(D).

Si ${displaystyle S^{(i)}(D) }$ es el polinomio de Estado en el estado i-ésimo, en forma polinómica el desplazamiento del polinomio de Estado se expresa así:

Como el grado tiene que ser menor que n+1 se hace el módulo de C(D):

Con lo que resulta un polinomio de grado n como máximo.

Hace tiempo que LFSR se usa como Generador de números pseudoaleatorios para cifradores de flujo, especialmente en criptografía militar, ya que su construcción es muy fácil, basándose en circuitos electrónicos y electromecánicos simples.

El sistema de Posicionamiento Global, GPS usa un LFSR para transmitir rápidamente una secuencia que indica time offsets de alta precisión relativa.

Para mantener transmisiones digitales formadas de patrones de energía que pueden interrumpir otras transmisiones digitales o analógicas. LFSR se usa para hacer más aleatorio el flujo de bits de salida (esta técnica se conoce como scrambling).

Sistemas de broadcasting digital que usan LFSR:

Otros sistemas de comunicación digital que usan LFSR: