LFSR

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 determinística, 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.

Contenido

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:

x11 + x13 + x14 + x16 + 1

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

Propiedades del flujo de salida

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:

S(D)\ =\ S_0\ +\ S_1D\ +\ S_2D^2\ +\ ...\ +\ S_nD^n

El polinomio de estado muestra el valor de los registros.

De la misma forma se define el polinomio de Conexiones como:

C(D)\ =\ C_0\ +\ C_1D\ +\ C_2D^2\ +\ ...\ +\ C_nD^n\ +\ C_{n+1}D^{n+1}

Donde cada coeficiente Ci vale 0 o 1 dependiendo de si hay conexión o no. Hay que notar que el polinomio de conexiones 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 C0 y la de Cn + 1. La conexión de C0 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 Cn + 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.

De la misma forma De esta manera 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 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í:

S^{(i+1)}(D)\ =\ S^{(i)}(D) \cdot D\ =\ S_0D\ +\ S_1D^2\ +\ S_2D^3\ +\ ...\ +\ S_{n}D^{n+1}

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

S^{(i+1)}(D)\ =\ S^{(i)}(D) \cdot D\ \bmod \ C(D)

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

LFSR de Galois

Usos criptográficos

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.

Aplicaciones en comunicaciones

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:

  • NICAM (digital audio system for television)
  • ATSC (HDTV transmission system -- North America)
  • DVB-T (HDTV transmission system -- Europe, Australasia)

Otros sistemas de comunicación digital que usan LFSR:

  • IBS (INTELSAT business service)
  • IDR (Intermedaite Data Rate service)
  • SDI (Serial Digital Interface transmission)
  • Data transfer over PSTN (according to the ITU-T V recommendations)

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • LFSR — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • LFSR — …   Википедия

  • LFSR — ICAO Airportcode f. Reims Champagne (France) …   Acronyms

  • LFSR — ICAO Airportcode f. Reims Champagne ( France) …   Acronyms von A bis Z

  • LFSR — abbr. Linear Feedback Shift Register (IC) …   United dictionary of abbreviations and acronyms

  • Linear feedback shift register — [ xor gate provides feedback to the register that shifts bits from left to right. The maximal sequence consists of every possible state except the 0000 state.] A linear feedback shift register (LFSR) is a shift register whose input bit is a… …   Wikipedia

  • Linear rückgekoppeltes Schieberegister — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, das zur Erzeugung von streng deterministischen Pseudozufallszahlenfolgen eingesetzt werden kann. Zur… …   Deutsch Wikipedia

  • Correlation attack — In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article)… …   Wikipedia

  • SOSEMANUK — быстрый программно ориентированный поточный шифр Содержание 1 Аннотация 2 Введение 3 Обозначения …   Википедия

  • Registre à décalage à rétroaction linéaire — Un registre à décalage à rétroaction linéaire, ou LFSR (acronyme de l anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite récurrente linéaire, initialement sur le corps fini à 2 élements (0 et …   Wikipédia en Français

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”