Registre de desplaçament en retroalimentación llineal

Un registre de desplaçament en retroalimentación llineal (LFSR per les seues sigles en anglés) és un registre de desplaçament en el qual l'entrada és un bit provinent d'aplicar una funció de transformació llineal a dos o més estats anteriors.

El valor inicial es denomina llavor i, com la forma d'operar el registre és determinista, la seqüència de valors produïts està completament determinada per l'estat actual o l'estat anterior. La seqüència té un periodo de repetició, és dir que la seqüència torna a generar-se i es repetix indefinidament. Quan el periodo de repetició és màxim, eixe LFSR té interés criptográfico.

Cóm treballa LFSR

Vejam un eixemple, tenim la seqüència [16,14,13,11].

La seqüència tap d'un LFSR es pot representar com un polinomi mod 2. Açò significa que els coeficients del polinomi deuen ser 1's o 0's. Açò es diu polinomi de realimentación o característica polinomial.

Per eixemple, si els taps estan en les posicions dels bits: 16, 14, 13 i 11, el polinomi LFSR resultant és:

$x^{11}+x^{13}+x^{14}+x^{16}+1$

Les eixides que influïxen en l'entrada, es denominen taps. Són les que apareixen en el polinomi. I s'indiquen en blau en l'esquema inferior.

• Si el polinomi és primitiu, sí i solament sí, el LFSR és màxim, o lo que és lo mateix, té periodo màxim.
• El LFSR només serà màxim si el número de taps és parell.
• Els valors de tap en un LFSR màxim són coprimos.
• Pot haver més d'una seqüència tap que faça màxim a el LFSR per a eixa llongitut determinada.
• Una volta trobada una seqüència tap màxima, automàticament seguix una atra. Si la seqüència tap, en un LFSR n-bit, és [n,A,B,C], llavors la seqüència mirror corresponent és [n,n-A,n-B,n-C]. Per eixemple, la seqüència tap [32,3,2,1], té el seu homòlec [32,29,30,31]. Abdós donen com resultat periodo màxim.

Archiu:Lfsr.gif

Propietats del fluix d'eixida

Un LFSR es pot caracterisar de forma polinòmica segons siguen les seues conexions i els valors dels registres.

Es definix el polinomi d'Estat com:

$S(D)=S_0+S_{1}D+S_2{D}^2+\mathrm{...}+S_n{D}^n$

El polinomi d'estat mostra el valor dels registres.

De la mateixa forma es definix el polinomi de Conexions (Polinomi Conectivo)com:

$C(D)=C_0+C_{1}D+C_2{D}^2+\mathrm{...}+C_n{D}^n+C_{n+1}{D}^{n+1}$

A on cada coeficient $C_i$ val 0 o 1 depenent de si hi ha conexió o no. Cal notar que el polinomi de conexions (Polinomi Conectivo) és sempre un grau major que el d'estat.

D'esta manera un LFSR en n registres de desplaçament tindrà com a mínim 2 conexions la de $C_0$ i la de $C_{n+1}$. La conexió de $C_0$ és necessària perque sense ella el primer registre sempre valdria zero i per tant no influiria en el comportament de el LFSR. La conexió $C_{n+1}$ és necessària perque assegura la retroalimentación de el LFSR. Si este coeficient valguera 0 (o lo que és lo mateix, no hi haguera esta conexió), el LFSR ya no seria de grau n+1.

Per lo tant per a passar d'un estat al següent els registres es desplacen. Este desplaçament es pot expressar en forma polinòmica com una multiplicació per D. El polinomi resultant té grau n+1 de la mateixa manera que el polinomi de conexions. Açò és un problema ya que el polinomi d'estat té que ser de grau n. Açò se soluciona fent que el polinomi resultant siga mòdul de C(D).

Si $S^{(i)}(D)$ és el polinomi d'Estat en l'estat i-ésimo, en forma polinòmica el desplaçament del polinomi d'Estat s'expressa aixina:

$S^{(i+1)}(D)=S^{(i)}(D)\cdot D=S_{0}D+S_1{D}^2+S_2{D}^3+\mathrm{...}+S_n{D}^{n+1}$

Com el grau té que ser menor que n+1 es fa el mòdul de C(D):

$S^{(i+1)}(D)=S^{(i)}(D)\cdot DmodC(D)$

En lo que resulta un polinomi de grau n com a màxim.