Registre à décalage - Définition

Registre à décalage et cryptographie

Génération de pseudo-aléatoire

Un problème fondamental en cryptologie est la production de suites de bits «aussi aléatoires que possible». Un exemple évident étant la génération des clefs de chiffrement (symétrique ou asymétrique).

Ce problème se décompose en fait en deux parties : d'une part la génération de bits par des procédés physiques -- mesure de temps entre frappes de touches sur un clavier, déplacement de la souris, ... --, et d'autre part l'expansion d'une courte suite aléatoire de bits en une suite beaucoup plus grande. Dans ce dernier cas, on parle de suite pseudo-aléatoire.

Le chiffrement par masque jetable illustre bien les enjeux. Dans ce chiffrement, le texte chiffré est produit par addition bit à bit (modulo 2) de la clef de chiffrement. Le déchiffrement est également effectué par addition bit à bit de la clef. Le problème est qu'il est alors nécessaire de partager une donnée secrète, à savoir la clef, de la même taille que le message à échanger. C'est très souvent impraticable. Vient alors l'idée d'engendrer la clef à partir d'un procédé déterministe -- il faut pouvoir le faire au chiffrement et au déchiffrement -- utilisant une donnée secrète plus petite. C'est probablement un peu de là l'origine du chiffrement par flot.

Une première possibilité consiste à choisir un LFSR et à utiliser la donnée secrète partagée comme initialisation du registre. Toutefois, l'algorithme de Berlekamp-Massey met vite fin à cette tentative : une connaissance même très partielle de la suite produite permet de retrouver toutes les informations voulues.

Dans la pratique, les LFSRs ne sont donc pas utilisés de manière isolée, mais essentiellement sous la forme des registres combinés ou filtrés.

Algorithme de Berlekamp-Massey

Un LFSR de taille n produisant des suites récurrentes linéaires d'ordre n, la connaissance de n termes consécutifs d'une suite et de l'équation linéaire -- ou bien de manière équivalente le polynôme de rétroaction -- détermine toute la suite.

Si maintenant on ne suppose plus connu le polynôme de rétroaction, que peut-on déduire de l'observation d'une partie de la sortie du LFSR, par exemple les termes  ? L'algorithme de Berlekamp-Massey répond à cette question de la façon suivante : si L est supérieur où égal à deux fois la taille du plus petit LFSR générant la suite (u_i) alors on peut retrouver le polynôme de rétroaction et l'initialisation du registre. En abrégé : tout. On voit ainsi apparaître la complexité linéaire comme le paramètre permettant d'estimer la quantité d'information nécessaire pour recréer une suite sous forme de LFSR.

L'algorithme de Berlekamp-Massey fut introduit en 1969 par James Massey (Massey, J. L. "Shift-Register Synthesis and BCH Decoding." IEEE Trans. Information Th. 15, 122-127, 1969.). C'est une adaptation d'un algorithme, dû à Elwyn Berlekamp, de décodage de codes correcteurs -- les codes de Bose-Chaudhuri-Hocquenghem.