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.

Cómo trabaja LFSR

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.

  • Si el polinomio es primitivo, sí y solo sí, el LFSR es máximo, o lo que es lo mismo, tiene periodo máximo.
  • El LFSR sólo será máximo si el número de taps es par.
  • Los valores de tap en un LFSR máximo son coprimos.
  • Puede haber más de una secuencia tap que haga máximo al LFSR para esa longitud determinada.
  • Una vez encontrada una secuencia tap máxima, automáticamente sigue otra. Si la secuencia tap, en un LFSR n-bit, es [n,A,B,C], entonces la secuencia mirror correspondiente es [n,n-A,n-B,n-C]. Por ejemplo, la secuencia tap [32,3,2,1], tiene su homólogo [32,29,30,31]. Ambos dan como resultado periodo máximo.


Lfsr.gif
Other Languages