Registre à décalage

à rétroaction linéaire
Le registre à décalage à rétroaction linéaire

Le registre à décalage à rétroaction linéaire constitue l’élément de base des

générateurs pseudo-aléatoires utilisés pour la génération de la suite chiffrante.

Définition 1 Un registre à décalage à rétroaction linéaire binaire de longueur

L est composé d’un registre à décalage contenant une suite de L bits
(s i , . . . , s i +L−1) et d’une fonction de rétroaction linéaire.

On l’appelle aussi par son acronyme anglais:

LFSR (Linear Feedback Shift Register)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Fonctionnement d’un LFSR binaire de longueur L

A chaque top d’horloge, le bit de poids faible s i constitue la sortie du registre, et

les autres sont décalés vers la droite ; le nouveau bit s i +L placé dans la cellule
de poids fort du registre est donné par une fonction linéaire :

s i +L = c1 s i +L−1 + c2 s i +L−2 + · · · + cL−1 s i +1 + cL s i

où les coefficients c i sont binaires.

Figure 1 : Registre à décalage à rétroaction linéaire de longueur L .

Définition 2 Les bits (s 0 , . . . , s L−1 ) qui déterminent entièrement la suite produite
constituent l’état initial du registre.

La suite (s n )n≥0 produite par un LFSR de longueur L est donc une suite a récur-
rence linéaire homogène d’ordre L . Inversement, ce type de suite peut toujours
être produite par un LFSR.

On peut remarquer qu’une telle suite est ultimement périodique, c’est-à-dire

qu’il existe une pré-période n 0 telle que la suite (s n )n≥n 0 est périodique.

Proposition 1 La suite s est ultimement périodique, de période

T ≤ 2L − 1

(i.e. il existe un entier i 0 tel que s i = s i +T pour tout i ≥ i 0 ).

Si, de plus, c L = 1, la suite s est périodique (i.e. s i = s i +T pour tout i ≥ 0).

Démonstration –

Notons R i = (s i , s i +1 , . . . , s i +L−1 ) le i -ème registre. Celui-ci détermine com-

plètement les registres ultérieurs. Ce registre peut prendre au plus 2L états.

S’il atteint l’état 0 = (0, . . . , 0) alors les registres successifs sont tous nuls et la
suite elle-même est nulle à partir de là.

S’il n’est jamais nul, parmi [R 0 , R 1 , . . . , R 2L −1 ], au moins deux registres sont

identiques. Supposons R i 0 = R i 0 +T ; alors la suite des registres
[R i 0 , R i 0+1, . . . , R i 0+T −1] se répète indéfiniment.

On a donc s i = s i +T pour tout i ≥ i 0 avec T ≤ 2L − 1.

16
On peut interpréter aussi la relation entre deux registres successifs en termes
matriciels. Notons
0 1 0 0 ... 0
 

 0 0 1 0 ... 0 
 .. .. ... ... ... .. 
 . . . 
A= 

 0 0 ... 0 1 0 
 
 0 0 ... 0 0 1
c L c L−1 . . . c 3 c 2 c 1
En considérant les R i comme des vecteurs colonnes, on a

R i +1 = AR i .
Ainsi, on a R n = A n R 0 .

Remarquons que le déterminant de A est égal à c L . Ainsi, si c L = 1, la matrice

A est inversible et le LFSR ne passe jamais par le registre nul. La condition
R i 0 = R i 0+T devient A i 0 R 0 = A i 0+T R 0 mais comme A est inversible, on en
déduit R 0 = A T R 0 = R T et la suite s est périodique. 17
Complexité linéaire des LFSRs.

Associons à la suite (s n )n≥0 la série géneratrice

sn X n .
X
s(X ) =
n≥0

Définition 3 Soit un LFSR dont la fonction de rétroaction est donnée par la rela-
tion

s i +L = c1 s i +L−1 + c2 s i +L−2 + · · · + cL−1 s i +1 + cL s i .

Son polynôme de rétroaction f est le polynôme de F2 [X ]:

f (X ) = 1 + c 1 X + c 2 X 2 + · · · + c L X L .

On peut alors écrire le développement en série formelle de la suite (s n )n≥0 sous

forme d’une fraction rationnelle.

18
Proposition 2 La suite (s n )n≥0 est produite par un LFSR dont le polynôme de
rétroaction est f (X ) = 1 + c 1 X + c 2 X 2 + · · · + c L X L si et seulement si son
développement en série formelle s(X ) = n≥0 s n X n s’écrit
P

g (X )
s(X ) =
f (X )
où g est un polynôme de F 2 [X ] tel que deg(g ) < deg( f ). En outre, le polynôme
g est entièrement déterminé par l’état initial du registre :
L−1 i
i
X X
g (X ) = X ci − j s j .
i =0 j =0

Démonstration –

L
X
On a: g (X ) = s(X ) f (X ). Soit, pour tout i ≥ 0 gi = si − j c j .
j =0

Les formules qui se déduisent de cette équation impliquent que g est un polynôme
à partir du rang L . 19
Afin d’obtenir une forme canonique de la série génératrice de (s n )n≥0 , on définit
le polynôme de rétroaction minimal de la suite (ou du registre) : c’est un
diviseur de f (X ), qui de plus est le polynôme de plus bas degré parmi les
polynômes de rétroaction de tous les LFSRs possibles qui générent la suite (s n )n≥0 .

Définition 4 Soit (s n )n≥0 une suite binaire à rétroaction linéaire d’ordre L dont
l’état initial est non nul. Son polynôme de rétroaction minimal est l’unique polynôme
unitaire f 0 de F 2 [X ] tel qu’il existe g 0 ∈ F 2 [X ], avec deg(g 0 ) < deg( f 0 ) et
pg cd (g 0, f 0) = 1, vérifiant
g 0(X )
s(X ) =
f 0(X )
La complexité linéaire du LFSR produisant la suite (s n )n≥0 , notée Λ(s), est alors
égale au degré de f 0 .

En clair, la complexité linéaire d’un LFSR produisant une suite (s n )n≥0 est
la longueur du plus petit LFSR permettant d’engendrer (s n )n≥0 .
Exemple Soit (s n )n≥0 la suite produite par le LFSR suivant :

Son polynôme de rétroaction est :

f (X ) = X 10 + X 7 + X 4 + X 3 + X + 1.
Soit g le polynôme déterminé par l’état initial du registre :

9 n
n
c n−i s i = X 7 + X + 1
X X
g (X ) = X
n=0 i =0
La série génératrice de (s n )n≥0 est :

X ng (X ) X7+ X +1 1
s(X ) = sn X = = 10 7 4 3
= 3
.
n≥0 f (X ) X + X + X + X + X + 1 X + 1
On a donc f 0 (X ) = X 3 + 1, et (s n )n≥0 peut être générée par un LFSR de
longueur 3. La complexité linéaire du LFSR est donc 3. 20
Proposition 3 Si le polynôme de rétroaction minimal du LFSR est primitif et
que son état initial est non nul, alors la suite produite (s n )n≥0 est de période
maximale 2Λ(s) − 1 et est dite suite de longueur maximale.

Démonstration

Soit f le polynôme de rétroaction minimal du LFSR.

 Un calcul simple montre

0 1 0 0 ... 0
0 0 1 0 ... 0
.. .. .. .. .. ..
que le polynôme caractéristique de la matrice A = 
 
. . . . . .  est
0 0 ... 0 0 1
c L c L−1 . . . c 3 c2 c1
X L f (X −1) = f˜(X ).

Les valeurs propres de A sont les racines de f˜. Elles sont toutes distinctes, et
d’ordre 2L − 1, puisqu’elles sont génératrices du groupe cyclique F2L .

Donc A est d’ordre 2L − 1, et c’est la période de la suite (s n )n≥0 .

Critères statistiques

On demande à une suite pseudo-aléatoire, périodique de période N , de satisfaire

certaines des propriétés des suites authentiquement aléatoires.

Parmi ces propriétés, les plus classiques sont les trois critères de Golomb, pro-
posés par celui-ci en 1982.

Bien sûr, ces conditions ne garantissent en aucun cas la sécurité cryptographique!

21
1. Dans chaque période, le nombre de 0 est approximativement égal au nombre
de 1:
¯ ¯
¯NX −1 ¯
(−1)si ¯ ≤ 1.
¯ ¯
¯
¯ i =0 ¯

2. Une série (de 0 ou de 1) est une succession de bits identiques, maximale (i.e.
encadrée par des bits opposés). Dans chaque période, soit S l’ensemble des
séries; si 2k ≤ |S| < 2k+1 , on trouve |S|/2 séries de longueur 1, |S|/4 séries de
longueur 2, . . . , |S|/2k séries de longueur k , et pour chaque longueur, autant de
séries de 0 que de séries de 1.

3. La fonction d’auto-corrélation prend deux valeurs, suivant que τ = 0 ou non:

NX
−1
C (τ) := (−1)si +si +τ .
i =0
Proposition 4 Dans une suite de longueur maximale 2L − 1, toute suite
(s i , s i +1, . . . , s i +L−1) de L éléments non tous nuls apparaît une et une seule
fois par période.

Démonstration

Un registre R i = (s i , s i +1 , . . . , s i +L−1 ) ne peut apparaître qu’une fois par

période. Or il y a 2L − 1 registres par période et les registres prennent au plus
2L − 1 valeurs. Donc ils prennent toutes les valeurs une fois.

Corollaire 1 Le premier critère de Golomb est vérifié.

Démonstration

Tout registre R i = (s i , s i +1 , . . . , s i +L−1 ) apparaît une et une seule fois. Son

premier élément s i prendra donc 2L−1 fois la valeur 1, et 2L−1 − 1 fois la valeur
0, car il ne peut pas prendre la valeur (0, . . . , 0).
Corollaire 2 Le deuxième critère de Golomb est vérifié.

Démonstration

Comptons le nombre de fois qu’apparaît une suite de exactement k zéros. Cela

revient à compter le nombre de fois qu’apparaît une suite formée de (1, | . . , 0}, 1)
0, .{z
k
au début d’un registre. Comme tous les registres R i = (s i , s i +1 , . . . , s i +L−1 )
apparaissent une et une seule fois, un registre composé de

. . , 0}, 1, s i +k+2, . . . , s i +L−1)

(1, |0, .{z
k

apparaît 2L−k−2 fois.

22
Corollaire 3 Le troisième critère de Golomb est vérifié.

Démonstration

La suite (s i )0≤i ≤N −1 est obtenue par une relation de récurrence linéaire liée au
registre à décalage donné. La suite (s i +τ )0≤i ≤N −1 est aussi obtenue par une
relation de récurrence linéaire liée au même registre à décalage (obtenue après
un décalage de τ).

La relation de récurrence étant linéaire, la suite (s i + s i +τ )0≤i ≤N −1 est encore

donnée par le même registre à décalage. Il existe donc une suite (t i )0≤i ≤N −1
(toujours donnée par le même registre à décalage) telle que

t i = s i + s i +τ
pour 0 ≤ i ≤ N − 1. D’après le premier corollaire, on a donc, si τ 6= 0
NX
−1 NX
−1
s i +s i +τ
C (τ) := (−1) = (−1)ti = −1.
i =0 i =0
23
L’algorithme de Berlekamp-Massey

On supposera pour simplifier que la suite produite par le LFSR est une suite
de longueur maximale.

Un tel générateur n’est pas cryptographiquement sûr, à cause de l’algorithme de

Berlekamp-Massey, qui calcule (en temps quadratique) la complexité linéaire et
un polynôme engendrant une suite finie.

Le lemme suivant montre qu’il suffit de connaitre 2L bits consécutifs de la suite

pour la retrouver entièrement.

Lemme 1 Soit s une suite récurrente de longueur maximale, de complexité linéaire

L . Si on connait 2L termes consécutifs de cette suite, alors on peut calculer les
coefficients de récurrence en inversant un système linéaire de taille L × L .
Démonstration. — On a la relation linéaire:
    
si s i +1 s i +2 . . . s i +L−1 cL s i +L
 s i +1 s i +2 s i +3 . . . s i +L   c L−1   s i +L+1 
    
 . .. ..   ..  =  ..
... ...
   
 .. . . .   . 
 
..
 s i +L−2 ...... s i +2L−3   c 2   s i +2L−2 
    
.
..
s i +L−1 . ...... s i +2L−2 c1 s i +2L−1
Il suffit de montrer que la matrice S de ce système est inversible. Ses colonnes
sont les vecteurs associés aux registres R i ,. . . ,R i +L−1 . Une combinaison linéaire
nulle non triviale équivaut à

a i R i + · · · + a i +L−1R i +L−1 = 0
donc à

(a i + · · · + a i +L−1 A L−1)R i = 0
donc à l’existence d’un polynôme P non nul de degré au plus égal à L −1 tel que
P (A)R i = 0. Par hypothèse, le polynôme caractéristique de A , égal au polynôme
réciproque du polynôme de rétroaction, est irréductible de degré L , donc premier
à P , donc P (A) est inversible. 24
Théorème 1 Soit (s n )n≥0 une suite binaire à récurrence linéaire de complexité
linéaire Λ(s). L’algorithme de Berlekamp-Massey détermine l’unique LFSR de
longueur Λ(s) qui génère (s n )n≥0 à partir de n’importe quelle suite de 2Λ(s)
bits consécutifs de (s n )n≥0 .

La complexité linéaire d’un LFSR est donc un paramètre déterminant pour sa

sécurité cryptographique: l’observation d’un petit nombre de bits seulement de
la suite permet en effet de la reconstituer entièrement si Λ(s) est petit.

Aussi s’attache-t-on généralement à utiliser des LFSRs dont la complexité linéaire

est égale à leur longueur. C’est en particulier possible si le polynôme de
rétroaction f est irréductible; on est alors assuré qu’il est impossible d’engendrer
(s n )n≥0 à l’aide d’un LFSR plus court.

25
5.3 Description de l’algorithme

Dans la pratique cryptographique, l’attaquant connait seulement un morceau de

la suite s , et il essaie de deviner les bits suivants. En particulier, il peut chercher
si ce bout de suite est le début d’un LFSR.

Dans cette direction, on étend la notion de complexité linéaire aux suites finies:

Définition 5 Etant donnée une suite s = (s 0 , . . . , s n−1 ), et un polynôme

f = 1 + c1 x + · · · + cL xL
(maintenant f n’est plus nécessairement de degré exactement égal à L ), on
dit que (L, f ) engendre s si
L
X
sj = c i s j −i pour tout j = 0, . . . , n − 1.
i =1
Le plus petit L convenable s’appelle la complexité linéaire de s et se note Λ(s).

26
L’algorithme utilise le lemme suivant

Lemme 2 Soit L n la longueur minimale d’un LFSR qui engendre les bits
s 0, s 1, . . . , s n−1 mais qui n’engendre pas s 0, s 1, . . . , s n . Alors la longueur
minimale L n+1 d’un LFSR engendrant s 0 , s 1 , . . . , s n−1 vérifie

L n+1 ≥ max(n + 1 − L n , L n )

L’algorithme de Belekamp-Massey permet de calculer un (L, f ) associé à s ,

avec L = Λ(s). En fait l’algorithme calcule un couple (L, f ) avec L minimal,
successivement pour les suites tronquées s (1) , s (2) ,. . . , s (k) ,. . . , s = s (n) , où
s (i ) = (s 0, . . . , s i −1).

Le temps de calcul de cet algorithme est en n 2 .

27
On peut maintenant décrire l’algorithme.

Théorème 2 Supposons pour k ≥ 1 avoir calculé un couple (L, f ) associé à

s (k) avec L = Λ(s (k)). Soit
L−1
X
d k := s k + c i s k−L+i .
i =0

•Si d k = 0, alors Λ(s (k+1)) = L et (L, f ) engendre s (k+1).

•Si d k = 1, alors soit m le plus grand entier tel que m < k et Λ(s (m)) < L , et
soit g tel que (Λ(s (m) ), g ) engendre s (m) . Alors

– Λ(s (k+1)) = max(L, k + 1 − L)

– s (k+1) est engendré par f + x k−m g .

28
Exemple. Appliquons l’algorithme de Berlekamp-Massey à la suite

0110010101
de longueur 10. Voici les résultats fournis par l’algorithme :
k sk dk L f (X ) m g (X )

Le polynôme de rétroaction est donc 1 + X 4 + X 5 . 29

Combinaison de plusieurs registres

30
Présentation

Même lorsque le polynôme de rétroaction du registre est choisi de manière appro-

priée, la complexité linéaire de la suite produite reste généralement trop faible
pour se prémunir d’une attaque par l’algorithme de Berlekamp-Massey.

Afin de surmonter cet obstacle et d’augmenter la taille de l’espace des clefs,

c’est-à-dire le nombre d’initialisations possibles, on utilise m LFSRs en parallèle,
et on combine leurs sorties par une fonction booléenne

f : Fm
2 −→ F2

appelée fonction de combinaison.

Figure 1 : Combinaison de LFSRs par une fonction booléenne

31
Définitions

Définition 6 Une fonction booléenne à m variables est une application de Fm

2
dans F2 .

On appelle fonction booléenne vectorielle à m variables et n composantes une

application de Fm n
2 dans F2 : c’est la juxtaposition de n fonctions booléennes à m
variables.

Définition 7 On appelle support de la fonction booléenne f l’ensemble des élé-

ments u tels que f (u) 6= 0, et on le note Supp( f ).

On appelle poids de f le cardinal de son support, et on le note w t ( f ).

On définit également pour deux fonctions f et g la distance qui les sépare par

d ( f , g ) = w t ( f + g ).
Et de manière générale, à tout vecteur binaire u on associe un poids w t (u) qui
est égal au nombre de ses composantes non nulles.

Une fonction booléenne est entièrement caractérisée par sa table de vérité, c’est-
à-dire la liste de tous les éléments de Fm
2 avec les valeurs qu’elle prend en chacun
d’eux.

32
Exemple

Considérons le cas m = 3. Voici la définition d’une fonction f par sa table de

vérité :
éléments de F3
2 valeur de f
(0, 0, 0) 0
(0, 0, 1) 1
(0, 1, 0) 1
(1, 0, 0) 0
(0, 1, 1) 0
(1, 0, 1) 0
(1, 1, 0) 1
(1, 1, 1) 1
On a ici Supp( f ) = {(0, 0, 1), (0, 1, 0), (1, 1, 0), (1, 1, 1)} et w t ( f ) = 4.

33
Forme Algébrique Normale d’une fonction booléenne f .

Définition 8 La Forme Algébrique Normale d’une fonction booléenne f à m

variables est l’unique polynôme Q f de F2 [x 1 , . . . , x m ]/(x 12 + x 1 , . . . , x m
2 +x )
m
tel que

f (u 1, . . . , u m ) = Q f (u 1, . . . , u m )

pour tout (u 1 , . . . , u m ) ∈ Fm
2 .

34
Remarque 1 Un polynôme Q f de F2 [x 1 , . . . , x m ]/(x 12 + x 1 , . . . , x m
2 + x ) est
m
souvent représenté par un polynôme de F2 [x 1 , . . . , x m ] de degrés partiels au
plus 1 en les x i : degx ≤ 1.
i

Proposition 5 L’application qui associe à un polynôme de F2 [x 1 , . . . , x m ] de

degrés partiels ≤ 1 son image dans F2 [x 1 , . . . , x m ]/(x 12 + x 1 , . . . , x m
2 + x ) est
m
un isomorphisme d’espaces vectoriel.

Démonstration –

L’application est injective, car un polynôme de degrés partiels ≤ 1 ne peut être

réduit par des polynômes x 2 + x i de degré partiels égal à 2.
i
X i i
L’application est surjective, car un polynôme a i 1,...,i m x 11 . . . x mm est con-
i 1 ,...,i m
j j
a i 1,...,i m x 11 . . . x mm modulo x 12 + x 1, . . . , x m
2 +x
X
gru à m
i 1 ,...,i m

où j k = 0 si i k = 0, j k = 1 sinon. 35
Définition 9 Soit f une fonction booléenne à m variables. On définit sa trans-
formée de Möbius comme la fonction

f ◦ : Fm
2 −→ F2
X
u 7−→ f (v) (mod. 2)
v≤u
avec v ≤ u si et seulement si pour tout i, v i = 1 ⇒ u i = 1.

Ou encore v ≤ u si et seulement si pour tout i, u i = 0 ⇒ v i = 0.

36
Proposition 6 La Forme Algébrique Normale d’une fonction booléenne f à m
variables est égale à
u u
f ◦(u)x 1 1 . . . x mm
X

u=(u 1 ,...,u m )∈Fm

2

Démonstration :

On le démontre par récurrence sur m . Les coefficients de la Forme Algébrique

Normale de f étant binaires, les sommes constituant ces coefficients sont con-
sidérées modulo 2.

1) m = 1: on a

f (x 1) = f (0)(1 + x 1) + f (1)x 1,
et donc

f (x 1) = ( f (0) + f (1))x 1 + f (0).

37
2) récurrence : par hypothèse, on sait que pour tout a ∈ F2 fixé, on a :
X X u u
m−1
f (x 1, . . . , x m−1, a) = f (v 1, . . . , v m−1, a)x 1 1 . . . x m−1
u∈Fm−1 v≤u
2

Or pour toutes les valeurs de (v 1 , . . . , v m−1 ) ∈ Fm−1

2 on a

f (v 1, . . . , v m−1, x m )
= f (v 1, . . . , v m−1, 1)x m + f (v 1, . . . , v m−1, 0)(x m + 1)
= ( f (v 1, . . . , v m−1, 0) + f (v 1, . . . , v m−1, 1))x m + f (v 1, . . . , v m−1, 0)

On a donc bien
X X u u
f (x 1, . . . , x m ) = f (v 1, . . . , v m )x 1 1 . . . x mm
u∈Fm
2
v≤u

38
Proposition 7 L’application qui associe à un polynôme Q de F2 [x 1 , . . . , x m ] de
degrés partiels ≤ 1 la fonction booléenne (u 1 , . . . , u m ) 7−→ Q(u 1 , . . . , u m ) est
un isomorphisme d’espaces vectoriels.

Démonstration –

Cette application est surjective puisqu’on a trouvé dans la proposition précé-

dente une Forme Algébrique Normale d’une fonction f .

L’espace vectoriel de ces polynômes a pour base la famille des monômes de

degré partiels inférieurs à 1, qui a 2m éléments. Donc l’ensemble des polynômes
2 m
Q tels que degxi Q ≤ 1 a 2 éléments.

L’espace des fonctions de Fm dans F a 2 2m éléments.

2 2

L’application est surjective, envoie un ensemble dans un ensemble ayant même

nombre d’élément: elle est donc bijective.

39
Dans la suite une fonction booléenne f sera souvent confondue avec sa Forme
Algébrique Normale Q f .

Définition 10 On appelle degré de f , et on note deg( f ), le degré du polynôme

Q f . Une fonction de degré 1 est dite affine, et si de plus elle est nulle en 0, elle
est linéaire.

40
Pour combiner des LFSRs en vue d’un chiffrement à flot, on utilise dans l’idéal
des fonctions équilibrées , i.e. dont la sortie est uniformément distribuée (ces
fonctions prennent autant de fois la valeur 0 que la valeur 1), de manière à ce que
la suite produite ne soit pas biaisée; on peut éventuellement utiliser une fonction
qui ne soit pas tout à fait équilibrée, pour peu que le biais reste inexploitable.

La suite obtenue par combinaison de LFSRs étant également une suite à récur-
rence linéaire, il est indispensable d’estimer sa complexité linéaire.

Puisque f peut être assimilée à un polynôme, la suite produite par un généra-

teur sera construite à partir des suites engendrées par les m LFSRs à l’aide de
sommes et de produits terme-à-terme. Il convient donc d’étudier la complexité
linéaire d’une suite résultant de la somme ou du produit d’autres suites.

41
Proposition 8 Soient (u n )n≥0 et (v n )n≥0 deux suites à récurrence linéaire de
polynômes de rétroaction minimaux respectifs f u et f v . Alors leur somme est
une suite à récurrence linéaire. La complexité linéaire de leur somme vérifie

Λ(u + v) ≤ Λ(u) + Λ(v)

avec égalité si et seulement si pg cd ( f u , f v ) = 1.

De plus, dans le cas de l’égalité, la période de leur somme est égale au ppcm
des périodes de (u n )n≥0 et (v n )n≥0 .

42
Démonstration

La complexité linéaire de la suite (u n )n≥0 est le degré de son polynôme de

rétroaction minimal, c’est-à-dire de l’unique polynôme unitaire f u de F 2 [X ] tel
que
il existe g u ∈ F 2 [X ], avec deg(g u ) < deg( f u ) et pg cd (g u , f u ) = 1, vérifiant
g (X )
u(X ) = u n X n = f u(X ) .
P
u
P g v (X )
De même pour la suite (v n )n≥0 , et v(X ) = v n X n = f (X ) .
v
Formons u + v :
X g u (X ) g v (X )
(u + v)(X ) = (u n + v n )X n = +
f u (X ) f v (X )
g u (X ) f v (X ) + g v (X ) f u (X ) g u+v (X )
= =
f u (X ) f v (X ) f u+v (X )

où la dernière fraction est irréductible. On a donc

Λ(u + v) = deg f u+v ≤ f u (X ) f v (X ) = Λ(u) + Λ(v)

43
Proposition 9 Soient (u n )n≥0 et (v n )n≥0 deux suites à récurrence linéaire de
polynômes de rétroaction minimaux respectifs f u et f v . Alors leur produit est une
suite à récurrence linéaire.

La complexité linéaire de leur produit vérifie

Λ(uv) ≤ Λ(u)Λ(v)

avec égalité si les polynômes f u et f v sont primitifs, et si

PGC D(Λ(u), Λ(v)) = 1.

Dans ce cas, la période de (uv n )n≥0 est égale au produit des périodes de
(u n )n≥0 et (v n )n≥0.

44
Démonstration

g u (X ) g (X )
u n X n = f (X ) et (v n )n≥0, et v(X ) = v n X n = f v (X ) .
P P
On a u(X ) =
u v

Formons uv :
X
(uv)(X ) = (u n v n )X n

45
Une fraction rationnelle h ∈ F2 (X ) se met de manière unique sous la forme
XA i (X )
h(X ) = B (X ) + (1)
i (X − αi )
ni

où A i (X ) et B (X ) sont des polynômes et deg A i < n i .

Supposons que les polynômes f u et f v soient sans racines multiples. Alors il

existe des éléments µ1 , . . . , µL u de F2L u tels que

Lu
g u (X ) X µi
=
f u (X ) i =1 αi X − 1
d’où
Lu Lu
g u (X ) X n
X nX
µi (αi X ) = X µi (αi )n
X X
u(X ) = u n X n = =
n f u (X ) i =1 n n i =1
d’où
Lu
µi (αi )n
X
un =
i =1
De même il existe des éléments ν1 , . . . , νL v de F2L v tels que

Lu
νi (β)n
X
vn =
i =1
où les β1 , . . . , βL v sont les racines inverses de f v .

µi ν j (αi β j )n et
X
Donc on a un v n =
i,j
n n
µi ν j (αi β j X ) = µi ν j (αi β j X )n
X XX X X
uv(X ) = un v n X =
n n i,j i,j n
X µi ν j g uv (X )
= =
i , j 1 − αi β j X f uv (X )

(1−αi β j X ). Ce polynôme est invariant par la transformation

Y
avec f uv (X ) =
i,j
x 7−→ x 2. Par conséquent il appartient à F2[X ]. On a donc

Λ(uv) ≤ deg( f uv ) = L u L v = Λ(u)Λ(v)

46
 g uv (X )
Pour voir si Λ(uv) = L u L v , il faut vérifier que f (X ) est irréductible. Comme
uv

X µi ν j g uv (X )
= ,
i , j 1 − αi β j X f uv (X )
cela revient à dire que

– µi ν j 6= 0;

– les αi β j sont tous distincts.

Les polynômes f u et f v étant des polynômes de rétroaction minimaux, on a

µi 6= 0 et νi 6= 0. Donc µi ν j 6= 0.

Si les αi β j ne sont pas tous distincts, il existe i et j tels que αi = β j 6= 1. On a

αi ∈ F2L u et β j ∈ F2L v , donc il existe un sous-corps commun à F2L u et à F2L v ,
ce qui veut dire que PGC D(L u , L v ) 6= 1.

47
Théorème 3 Soient m LFSRs binaires dont les polynômes de rétroaction sont
primitifs et de degrés L 1 , . . . , L m deux-à-deux premiers entre eux. Alors la
complexité linéaire de la suite produite en combinant ces LFSRs par la fonction
booléenne f à m variables est égale à

L = f (L 1, . . . , L m )

où f est vue comme un polynôme de Z[x 1 , x 2 , . . . , x m ] et est évaluée sur les

entiers.

On en déduit donc qu’une fonction de combinaison doit non seulement être équili-
brée, mais aussi avoir un degré le plus élevé possible.

48
Exemple

Le générateur de Geffe (1973)

Le générateur de Geffe est défini par 3 LFSRs dont les polynômes de rétroaction
sont primitifs et de degrés L 1 , L 2 et L 3 deux-à-deux premiers entre eux. Ces
registres sont assemblés par la fonction booléenne

f (x 1, x 2, x 3) = x 1 x 2 + x 2 x 3 + x 3

La complexité de la suite produite par ce générateur est donc L 1 L 2 +L 2 L 3 +L 3 .

49
Le générateur de Geffe

f (x 1, x 2, x 3) = x 1 x 2 + x 2 x 3 + x 3 = x 1 x 2 + (x 2 + 1)x 3

50
Ce générateur de Geffe a deux avantages importants.

D’une part, son rendement comporte une distribution moyenne égale à 0 et à 1,

qui est très rarement le cas quand des opérations de logique du type de produit
sont présentées.

D’autre part, pour décoder ce dispositif sans savoir la clef, il serait nécessaire de
résoudre un système de n d équations, avec n d = n a + n b + n c (n a , n b , n c
indiquant le nombre de registre de A, B et C respectivement), mais ces équations
sont non-linéaires et la solution du système est difficile.

51
Attaque par corrélation de Siegenthaler

Cette attaque, développée par T. Siegenthaler est de type "diviser pour mieux
régner" : elle consiste à retrouver l’initialisation de chacun des registres indépen-
demment des autres.

Pour cela, on exploite l’existence d’une éventuelle corrélation entre la sortie de

la fonction de combinaison f et l’une de ses entrées.

On va regarder un exemple sur le générateur de Geffe.

52
Problème: pour une suite de sortie s(t) donnée, retrouver la clef qui a permis
de la produire.

f (x 1, x 2, x 3) = x 1 x 2 + (1 + x 2)x 3 = x 1 x 2 + x 2 x 3 + x 3 (mod. 2)

• Probabilité de corrélation de la suite x 1(t ) à la suite s(t ):

P (s(t ) = x 1(t )) = P (x 2(t ) = 1) + P (x 2(t ) = 0) P (x 3(t ) = x 1(t ))
1 1 1
= 2 + 2 2
3
= 4

• De même, P (s(t ) = x 3(t )) = 3/4.

• On essaye toutes les initialisations du 1er registre jusqu’à ce que le nombre

de coïncidences entre la suite de sortie s(t) et la sortie x1 (t) de R 1 soit '
probabilité p de corrélation.
 Trouver l’état initial de R 1 prendra 2L 1 essais.

• En répétant l’opération pour les deux autres registres, l’état initial de chaque
LFSR peut être déterminé en environ

2L 1 + 2L 2 + 2L 3 essais

Ce nombre est bien plus petit que le nombre de différentes clefs qui est
environ

2L 1+L 2+L 3 .

53
Théorème 4 Soit f une fonction booléenne de combinaison à m variables. Pour
1 ≤ i ≤ m , on note
p i = P r [ f (X 1, . . . , X m ) = X i ]
où les X i sont m variables aléatoires indépendantes uniformément distribuées
dans F2 . Soient c 1 , . . . , c N N bits de la suite chiffrante. Alors la corrélation αi
entre le chiffré et la sortie du i-ème LFSR, définie par
N
cj s ij
αi =
X
(−1) (−1)
j =1

est une variable aléatoire de moyenne m i et de variance σ2 , avec

i
m i = N (2p i − 1) et σ2i = 4N p i (1 − p i )
De même, la corrélation α0 entre la suite chiffrante et une suite aléatoire s 0
indépendante de s 1 , . . . , s m est une variable aléatoire de moyenne m 0 et de
variance σ2
0 , avec
m 0 = 0 et σ20 = N .
54
On suppose fixé i . On le supprimera des formules.

On a
N N
cj s ij
αi = (−1)c j +s j
X X
(−1) (−1) =
j =1 j =1
Donc l’espérance de αi est donnée par
N
c j +s j ¢
X ¡
E (α) = E (−1)
j =1
On a

P (c j + s j = 0) = P (c j = s j ) = P ( f (X 1, . . . , X m ) = X i ) = p i
D’où
¡ c j +s j ¢
E (−1) = 1P (c j +s j = 0)+(−1)P (c j +s j = ±1) = p −(1−p) = 2p −1
et

E (α) = N (2p − 1)
D’autre part
 
N
2 ¡X c j +s j ¢2 
E (α ) = E  (−1)
j =1
N N
c j 0 +s j 0
³¡ ´ ³ ´
c j +s j ¢2 c j +s j
X X
= E (−1) + E (−1) (−1)
j =1 j 6= j 0 =1
N
c j 0 +s j 0
³ ´
c j +s j ¢
X ¡
= N+ E (−1) E (−1)
j 6= j 0 =1
= N + N (N − 1)(2p − 1)2.
La fonction f est indépendante du temps (donc de l’indice j ). Par conséquent les
événements c j + s j et c j 0 + s j 0 sont indépendants.
La variance est égale à

E (α2) − E 2(α) = N + N (N − 1)(2p − 1)2 − (N (2p − 1))2

= 4N p(1 − p).

55
On voudrait mener une attaque à clair connu : on connaît un certain nombre de
bits de la suite chiffrante et on voudrait retrouver l’état d’initialisation des registres.

La fonction de combinaison f et les polynômes de rétroaction des n LFSRs étant

supposés connus, l’idée consiste à déterminer l’initialisation de chaque LFSR in-
dépendamment les uns des autres.

Pour cela, il suffit d’utiliser habilement une éventuelle corrélation entre la sortie
(σ) d’un registre et la sortie (s) de la suite chiffrante: d’où une attaque par cor-
rélation.

Si l’initialisation du registre i n’est pas correcte, la suite (σ) sera complètement

décorrélée de la suite (s) et αi aura une distribution normale de moyenne nulle
et de variance N .

Par contre, si l’initialisation du registre est correcte, la corrélation αi entre la suite

s et σ suit une loi normale de moyenne non nulle.

56
L’algorithme est alors le suivant :

• Calculer p i ,

• pour chacune des (2L i − 1) initialisations possibles du i ème registre,

• calculer la corrélation entre la suite s et σ produite sur N bits,

• si αi ' N (1−2p i ) alors l’initialisation est correcte sinon l’initialisation n’est

pas correcte.
L’attaque par corrélation de Siegenthaler permet donc de retrouver l’initialisation
des registres en

Lj
(2L j − 1) essais,
Y X
(2 − 1) +
j,pj =0,5 j,pj 6=0,5

alors qu’une recherche exhaustive nécessite

m
(2L j − 1) essais,
Y

j=1

Des raffinements de cette attaque ont été étudiés par W. Meier et O. Staffelbach,
ainsi que V. Chepyzhov et B. Smeets.

57
Dans un système combinant m LFSR on peut éviter ce type d’attaque en choi-
sissant f non corrélée à l’ordre k pour k petit.

Définition 11 On dit que f est non-corrélée à l’ordre k si, pour X 1 , . . . , X m

des variables aléatoires binaires équidistribuées indépendantes, la variable aléa-
P
toire f (X 1 , . . . , X m ) est indépendante des variables i ∈I X i , où I est un sous-
ensemble de {1, . . . , m} de cardinal au plus égal à k .

On dit que f est k -résiliente si f est non-corrélée à l’ordre k , et équilibrée.

Cela revient à dire que

à !
x i = 2m−1,
X
dH f ,
i ∈I
pour tout sous-ensemble I de cardinal au plus égal à k .