PICSI

LFSR q-aires.   On peut définir un LFSR sur tout corps fini à q éléments, F_q de façon similaire au cas binaire. Le LFSR de longueur L sur F_q et de coefficients de rétroaction c₁, …, c_L est le dispositif permettant d'engendrer la suite semi-infinie s₀, s₁, …, d'éléments de F_q qui satisfait la relation de récurrence linéaire

st+L = L ∑ i=1  ci st+L−i,     ∀t ≥ 0 .

Le polynôme de rétroaction du LFSR est alors défini par

P(X) = 1 − L ∑ i=1  ci Xi .

On peut également représenter les coefficients de rétroaction du registre au moyen de son polynôme minimal, qui est le polynôme réciproque du polynôme de rétroaction :

P∗(X) = XL P(1/X) = XL − L ∑ i=1  ci XL−i .

Les LFSR sur une extension du corps F₂ sont classiquement utilisés dans les applications logicielles, où l'unité de base du processeur est l'octet ou le mot de 32 bits. On emploie alors des LFSR sur F_2⁸ ou F_2³².

LFSR non-singuliers.   Un LFSR est dit non-singulier si le degré de son polynôme de rétroaction correspond à la longueur du registre (autrement dit si le coefficient de rétroaction c_L est non nul.) Toute suite engendrée par un LFSR q-aire non-singulier de longueur L est périodique de période inférieure ou égale à q^L−1. Si le LFSR est singulier, alors la suite produite est ultimement périodique, ce qui signifie qu'on obtient une suite périodique si on enlève les premiers termes jusqu'à un certain rang.
Caractérisation des suites produites par un LFSR.   Un LFSR q-aire donné de longueur L peut produire q^L suites différentes, qui correspondent aux q^L initialisations, et ces suites forment un espace vectoriel sur F_q. L'ensemble des suites produites par le LFSR de polynôme de rétroaction P est caractérisé par la propriété suivante. Une suite (s_t)_{t ≥ 0} est produite par un LFSR q-aire de longueur L et de polynôme de rétroaction P si et seulement s'il existe un polynôme Q ∈ F_q[X] de degré strictement inférieur à L tel que le développement en série formelle de (s_t)_{t ≥ 0} vérifie

∑ t ≥ 0  st Xt = Q(X) P(X)  .

De plus, le polynôme Q est entièrement déterminé par les coefficients de P et l'état initial du registre :

Q(X) = − L−1 ∑ i=0  Xi   i ∑ j=0  ci−j sj    ,

où P(X) = ∑_i=0^L c_i Xⁱ. Ceci signifie qu'il y a une bijection entre les suites engendrées par un LFSR de longueur L et de polynôme de rétroaction P et les fractions rationnelles Q(X)/P(X) avec deg(Q) < L. Ce résultat fondamental a deux conséquences importantes du point de vue du chiffrement à flot. Tout d'abord, toute suite produite par le LFSR de polynôme de rétroaction P est également engendrée par tout LFSR dont le polynôme de rétroaction est multiple de P. Cette propriété est utilisée dans plusieurs attaques sur les LFSRs [1,5,6]. De même, une suite produite par le LFSR de polynôme de rétroaction P est également engendrée par un LFSR plus court, de polynôme de rétroaction P′ si les polynômes P et Q intervenant dans la fraction rationnelle Q(X)/P(X) ne sont pas premiers entre eux. Par conséquent, parmi toutes les suites produites par le LFSR de polynôme de rétroaction P, il y en a au moins une qui peut être engendrée par un LFSR plus court dès que P n'est pas irréductible.
Polynôme minimal.   On déduit de la propriété précédente que, pour toute suite (s_t)_{t ≥ 0} vérifiant une relation de récurrence linéaire, il existe un unique polynôme unitaire P₀ tel que le développement en série formelle associé est donné par Q₀(X)/P₀(X) où P₀ et Q₀ sont premiers entre eux. Ainsi, le plus petit LFSR permettant d'engendrer (s_t)_{t ≥ 0} a pour longueur L=max(deg(P₀), deg(Q₀)+1), et son polynôme de rétroaction est égal à P₀. Le polynôme réciproque de P₀, X^L P₀(1/X), est donc le polynôme caractéristique du plus petit LFSR produisant (s_t)_{t ≥ 0}. Il est appelé polynôme minimal de la suite. C'est lui qui détermine la relation de récurrence linéaire d'ordre minimal vérifiée par la suite. Le degré du polynôme minimal d'une suite récurrente linéaire correspond à sa complexité linéaire. Il s'agit de la longueur du plus petit LFSR qui permette d'engendrer cette suite. Le polynôme minimal d'une suite s=(s_t)_{t ≥ 0} de complexité linéaire Λ(s) peut être déterminé à partir de la connaissance de 2Λ(s) bits consécutifs de s au moyen de l'algorithme de Berlekamp-Massey. Pour plus de précisions sur la notion de complexité linéaire et sur l'algorithme de Berlekamp-Massey, voir la fiche correspondant. Exemple.   Considérons le LFSR binaire de longueur 10 décrit à la figure 1.
 

Figure 1:  Exemple de LFSR binaire de longueur 10

Ce LFSR a pour polynôme de rétroaction

P(X) = 1 + X + X3 + X4 + X7 + X10 ,

et son état initial s₀…s₉ est 1001001001. La série génératrice de la suite produite par ce LFSR est donnée par

∑ t ≥ 0  st Xt = Q(X) P(X)

où Q est obtenu à partir des coefficients de P et de l'état initial :

Q(X) = 1+X+X7 .

On a donc

∑ t ≥ 0  st Xt = 1+X+X7 1 + X + X3 + X4 + X7 + X10 = 1 1+X3  ,

car 1 + X + X³ + X⁴ + X⁷ + X¹⁰ = (1+X+X⁷)(1+X³) dans F₂[X]. Ceci implique que (s_t)_{t ≥ 0} est également engendrée par le LFSR de polynôme de rétroaction P₀(X)=1+X³ décrit à la figure , et que sa complexité linéaire est égale à 3.


Figure 2: LFSR de longueur 3 engendrant la même suite que le LFSR de la figure 1

Période de la suite engendrée par un LFSR.   Le polynôme minimal d'une suite récurrente linéaire joue un rôle majeur puisqu'il détermine à la fois la complexité linéaire et la plus petite période de la suite. En effet, la plus petite période d'une suite récurrente linéaire est égale à l'ordre de son polynôme minimal. L'ordre d'un polynôme P de F_q[X] tel que P(0) ≠ 0 est le plus petit entier positif e tel que P(X) divise X^e−1. En conséquence, s est de période maximale q^Λ(s)−1 si et seulement si son polynôme minimal est primitif (c'est-à-dire d'ordre maximal). Par exemple, la suite produite par le LFSR de la figure  est de période 3 car son polynôme minimal X³+1 est d'ordre 3. On peut vérifier que ce LFSR produit en effet la suite 100100100…. Au contraire, toutes les suites engendrées par le LFSR de la figure 3, sauf la suite entièrement nulle, sont de période 15.


Figure 3: Exemple de LFSR de longueur 4 de période maximale

En effet, le polynôme minimal d'une telle suite correspond au polynôme caractéristique du LFSR P^∗(X)=1+X+X⁴, puisque celui-ci est irréductible. De plus, P^∗ est un polynôme primitif. On voit ici que toute suite s=(s_t)_{t ≥ 0} produite par un LFSR q-aire de longueur L dont le polynôme de rétroaction est primitif est à la fois de complexité linéaire maximale, Λ(s) = L et de période maximale q^L−1. Ces suites sont appelées suites récurrentes linéaires de longueur maximale (m-sequences en anglais). Du fait de leur optimalité, ce sont elles qui sont utilisées dans les générateurs pseudo-aléatoires. En d'autres termes, tout LFSR entrant dans la construction d'un générateur pseudo-aléatoire doit avoir un polynôme de rétroaction primitif.
Propriétés statistiques des suites récurrentes linéaires de longueur maximale.   Les suites récurrentes linéaires de longueur maximale, c'est-à-dire les suites engendrées par un LFSR ayant un polynôme de rétroaction primitif, possèdent un certain nombre de propriétés statistiques qui font qu'elles sont souvent utilisées comme briques de base de générateurs pseudo-aléatoires. Ainsi, toute suite produite par un LFSR binaire de longueur L ayant un polynôme de rétroaction primitif présente notamment les caractéristiques suivantes :

• équilibre : l'écart entre le nombre de zéros et le nombre de uns dans tout ensemble de 2^L−1 bits consécutifs de la suite est de 1.
• propriétés des plages : on appelle plage (run en anglais) tout ensemble de 0 consécutifs encadrés par deux 1, ou tout ensemble de 1 consécutifs encadrés par deux 0. Par exemple, dans la suite 0100011 figure une plage de 0 de longueur 4. Si l'on considère l'ensemble des plages à l'intérieur de (2^L−1) bits consécutifs d'une suite récurrente linéaire de longueur maximale, alors la moitié d'entre elles sont des plages de longueur 1, un quart sont des plages de longueur 2, un huitième sont des plages de longueur 3,..., et finalement une seule plage est de longueur (L−1) et une seule est de longueur L. De plus, parmi toutes les plages de longueur k ≤ L−2, il y a autant de plages de 0 que de plages de 1.
• auto-corrélation à deux niveaux : la fonction d'auto-corrélation pour une suite binaire de période N est définie par
  

  C(τ) = N−1 ∑ t=0  (−1)st + st+τ .

  La valeur de C(τ) mesure donc la distance entre la suite s₀s₁ …s_N−1 et la suite obtenue en la décalant de τ positions, c'est-à-dire s_τ s_τ+1 …s_N−1s₀ s₁ …s_τ−1. En effet, C(τ) correspond à la différence entre le nombre de positions en lesquelles ces deux suites coïncident et le nombre de positions en lesquelles elles diffèrent. Autrement dit
  

  C(τ) = N − 2 |{t,   0 ≤ t ≤ N−1,     st ≠ st+τ mod N}| .

  On a donc trivialement que C(τ)=N si τ est un multiple de la période N puisque les deux suites considérées sont identiques. De plus, toute suite produite par un LFSR binaire de polynôme de rétroaction primitif vérifie
  

  C(τ) = −1

  pour tout τ qui n'est pas un multiple de 2^L−1. Cette propriété est notamment utilisée en télécommunications dans les techniques de synchronisation.
• propriétés du multigramme : le L-uplet (s_t, s_t+1, …, s_t+L−1) parcourt l'ensemble des 2^L−1 L-uplets non nuls quand t varie entre 0 et 2^L−2.

Les trois premières propriétés détaillées précédemment sont connues sous le nom de postulats de Golomb [2].
Exemple : les 31 premiers bits de la suite engendrée à partir de l'état initial 10000 par le LFSR de longueur 5 de polynôme de rétroaction primitif x⁵+x³+1 sont

1000010101110110001111100110100

On peut vérifier que cette suite comporte 16 uns et 15 zéros. Elle est donc équilibrée. Cette suite est constituée de 16 plages, parmi lesquelles on trouve 8 plages de longueur 1 (4 de zéros et 4 de uns), 4 plages de longueur 2 (2 de zéros et 2 de uns), 2 plages de longueur 3 (une de zéros et une de uns), une plage de zéros de longueur 4 et une plage de uns de longueur 5.

 

Références

[1]

A.  Canteaut, M.  Trabbia. << Improved fast correlation attacks using parity-check equations of weight 4 and 5 >>. Advances in Cryptology - EUROCRYPT 2000, 1807 Lecture Notes in Computer Science, 573-588. Springer-Verlag, 2000.

[2]

S.W. Golomb. Shift register sequences. Aegean Park Press, 1982.

[3]

G.  Gong. << Sequence analysis >>. Lecture Notes for CO739x, http://www.comsec.uwaterloo.ca/~ggong/CO739x/seq-main.ps, 1999.

[4]

R.  Lidl, H.  Niederreiter. Finite Fields. Cambridge University Press, 1983.

[5]

H.  Molland. << Improved Linear Consistency Attack on Irregular Clocked Keystream Generators >>. Fast Software Encryption - FSE`04, 3017 Lecture Notes in Computer Science, 109-126. Springer-Verlag, 2004.

[6]

H.  Molland, T.  Helleseth. << An improved correlation attack against irregular clocked and filtered generator >>. Advances in Cryptology - CRYPTO 2004, 3152 Lecture Notes in Computer Science, 373-389. Springer-Verlag, 2004.

[7]

R.A. Rueppel. Analysis and Design of stream ciphers. Springer-Verlag, 1986.