Codes de Reed-Muller et cryptanalyse du registre filtré.

Les travaux de cette these portent sur la cryptanalyse d'un systeme de chiffrement simple, mais important : le registre filtre. Ils concernent les deux principales familles d'attaques que sont les attaques algebriques et les attaques probabilistes. Pour les attaques algebriques, il est important de pouvoir calculer efficacement l'immunite algebrique de la fonction booleenne par laquelle le registre est filtre. Cette quantite est intimement liee au comportement des codes de Reed-Muller sur le canal a effacements et son etude a permis la decouverte de plusieurs resultats qui s'expriment naturellement dans le cadre de la theorie des codes correcteurs. Nous avons ainsi construit une nouvelle borne sur la probabilite de pouvoir compenser un nombre d'effacements fixe. Cette borne montre que l'immunite algebrique d'une fonction booleenne aleatoire est presque toujours maximale. Nous avons egalement explicite une methode de decodage fondee sur des algorithmes d'algebre lineaire creuse (comme l'algorithme de Wiedemann) qui donne un des algorithmes les plus efficace pour calculer l'immunite algebrique. Pour les attaques probabilistes, un outil tres important est de parvenir a trouver efficacement de nombreux multiples de poids faible du registre a decalage du systeme. Un nouvel algorithme fonde sur les logarithmes discrets a ete propose. Il est particulierement interessant pour les multiples de poids 4, ameliorant dans de nombreux cas pratiques le meilleur algorithme connu. Ce travail s'est poursuivi par une nouvelle cryptanalyse probabiliste du registre filtre qui utilise ces multiples de poids faible pour reconnaitre les entrees nulles de la fonction de filtrage. Cette attaque est l'une des plus efficaces connue a l'heure actuelle.