PICSI

Une première introduction au circuits à décalage à rétroaction linéaire utilisés dans beaucoup de générateurs pseudo-aléatoires

Définition.  Un registre à décalage à rétroaction linéaire, usuellement désigné par l'abréviation anglo-saxonne LFSR (pour Linear Feedback Shift Register), est un dispositif permettant d'engendrer une suite infinie qui satisfait une relation de récurrence linéaire. Plus précisément, un LFSR binaire de longueur L est composé d'un registre à L cellules contenant chacune un bit. Les L bits contenus dans le registre forment l'état interne du LFSR. Ces L cellules sont initialisées par L bits, s₀, ..., s_L−1.

Figure 1:  Registre à décalage à rétroaction linéaire (LFSR)
Ce registre à décalage est contrôlé par une horloge externe. Au cours de chaque unité de temps, chaque bit est décalé d'une cellule vers la droite. Le contenu de la cellule la plus à droite, s_t, sort du registre, alors que la cellule la plus à gauche reçoit le bit de rétroaction, s_t+L. La valeur de ce dernier est obtenue par une combinaison linéaire des valeurs des autres cellules, dont les coefficients sont des éléments fixés qui valent 0 ou 1 et appelés coefficients de rétroaction du LFSR :

st+L = L ∑ i=1  ci st+L−i ,

où la somme est une somme modulo 2 dans le cas d'un LFSR binaire. Ainsi, le LFSR de longueur L et de coefficients de rétroaction c₁, …c_L engendre, à partir de son état initial s₀,…, s_L−1, la suite obtenue par la relation de récurrence linéaire d'ordre L

st+L = L ∑ i=1  ci st+L−i  pour tout t ≥ 0 .

Exemple.   Le tableau 1 donne les états successifs du LFSR binaire de longueur 4 dont les coefficients de rétroaction sont c₁=c₂=0, c₃=c₄=1 à partir de l'état initial (s₀,s₁,s₂,s₃) = (1,0,1,1). Ce LFSR est représenté à la figure 1. Il correspond à la relation de récurrence

st+4 = st+1+st mod 2 .

La suite s₀s₁… engendrée par ce LFSR est 1011100….


Figure 2: LFSR binaire de coefficients de rétroaction (c₁,c₂,c₃,c₄) = (0,0,1,1)

t	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
st	1	0	1	1	1	1	0	0	0	1	0	0	1	1	0	1
st+1	0	1	1	1	1	0	0	0	1	0	0	1	1	0	1	0
st+2	1	1	1	1	0	0	0	1	0	0	1	1	0	1	0	1
st+3	1	1	1	0	0	0	1	0	0	1	1	0	1	0	1	1

Table 1: États successifs du LFSR de coefficients de rétroaction (c₁,c₂,c₃,c₄) = (0,0,1,1), initialisé par (s₀,s₁,s₂,s₃) = (1,0,1,1)

Propriétés statistiques classiques.   On peut démontrer que la suite engendrée par un LFSR possède de bonnes propriétés statistiques lorsque les coefficients de rétroaction du LFSR sont bien choisis. Ces propriétés dépendent essentiellement de la forme du polynôme utilisé pour représenter les coefficients de rétroaction. Ce dernier, appelé polynôme de rétroaction du LFSR, est défini par

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

Par exemple, le polynôme de rétroaction du LFSR de la figure  est P(X) = 1 + X³ + X⁴. Les principales propriétés utiles dans le cadre du chiffrement à flot sont les suivantes.

• Si le polynôme de rétroaction est irréductible, alors la suite engendrée par le LFSR quelle que soit son initialisation (à part l'état nul) ne peut pas être engendrée par un LFSR plus court. La taille du plus petit LFSR permettant de produire une suite donnée est un paramètre fondamental en cryptographie, appelé la complexité linéaire de la suite. En effet, une suite de complexité linéaire Λ peut être entièrement reconstituée dès lors qu'un attaquant en connaît 2 Λ bits consécutifs au moyen de l'algorithme de Berlekamp-Massey (pour plus de détails sur la complexité linéaire et une description complète de cet algorithme, voir la fiche Complexité linéaire et algorithme de Berlekamp-Massey). Autrement dit, le choix d'un polynôme de rétroaction irréductible garantit que la complexité linéaire de toute suite produite par le LFSR est maximale.
• Si le coefficient c_L est non nul (on dit dans ce cas que le LFSR est non-singulier), alors la suite engendrée par le LFSR est une suite périodique de période au plus 2^L−1. En effet, un registre de longueur L peut avoir au plus 2^L états différents, et l'état entièrement nul doit être exclu car il est toujours suivi de lui-même.
• Plus précisément, si le polynôme de rétroaction est un polynôme primitif, alors la plus petite période de la suite engendrée à partir de n'importe quelle initialisation (sauf l'état nul) est égale à 2^L−1.

Pour plus de détails sur ces propriétés ainsi que sur celles des LFSRs non binaires, voir la fiche approfondissement sur les LFSRs.
Utilisation d'un LFSR comme générateur pseudo-aléatoire.   Il est évidemment impossible d'utiliser la suite produite par un LFSR comme suite chiffrante dans un chiffrement à flot. En effet, si les coefficients du LFSR sont publics (ce qui est généralement le cas quand le LFSR est implémenté sous forme d'un circuit électronique), il suffit à un attaquant qui connaît L bits consécutifs de la suite d'appliquer la relation de récurrence pour retrouver tous les bits suivants. Dans le cas où les coefficients de rétroaction sont secrets, l'algorithme de Berlekamp-Massey permet de les reconstituer, ainsi que l'état initial, à partir de 2L bits de suite chiffrante. Toutefois, les LFSR sont des dispositifs extrêmement rapides et d'implémentation peu coûteuse pour engendrer des suites ayant de bonnes qualités statistiques, notamment une période élevée. C'est pour cette raison qu'ils sont souvent utilisés comme module de base dans les générateurs pseudo-aléatoires dédiés, mais au sein d'un dispositif plus complexe.

 

Références

[1]

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

[2]

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

[3]

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