Les systèmes de chiffrement à flot (stream ciphers) sont couramment utilisés puisqu'ils permettent un chiffrement rapide des données tout en consommant peu d'énergie. Leur principe de fonctionnement est relativement simple: un générateur de pseudo-aléa produit une séquence binaire qui est X-orée au message clair, engendrant ainsi le message chiffré (cryptogramme). Le destinataire, muni d'un générateur identique, déchiffre le message reçu en lui appliquant la même opération. La sécurité de ce système repose entièrement sur la difficulté de produire la séquence pseudo-aléatoire: toute personne en mesure de la générer pourra en effet déchiffrer le cryptogramme qu'elle aura intercepté. L'objet de cette thèse était de proposer de nouvelles attaques sur de tels systèmes. Plus précisément, nous nous sommes intéressés à la cryptanalyse à clair connu des registres filtrés: le générateur de pseudo-aléa est, dans ce cas, constitué d'un unique registre à décalage linéaire (LFSR) filtré par une fonction booléenne. La structure de ces deux composantes est supposée entièrement connue du cryptanalyste, lequel dispose, par ailleurs, de quelques bits de la séquence pseudo-aléatoire. Seule l'initialisation du registre à décalage est secrète et conditionne entièrement la sortie du générateur: elle constitue donc la clé secrète du système de chiffrement et notre objet sera précisément de la déterminer. Le document sera organisé de la façon suivante: dans un premier chapitre, nous décrivons la structure du système de chiffrement qu'est le registre filtré, et nous intéressons aux théories auxquelles ses différentes constituantes renvoient naturellement. Nous proposons, dans un second chapitre, un état de l'art des attaques non-algébriques du registre filtré. Suit un chapitre qui présente les fondements du décodage itératif et quelques résultats de simulation permettant d'évaluer l'impact de différents paramètres du système, celui du canal booléen notamment. Nous décrivons ensuite une nouvelle attaque dont le principe s'inspire de celui du décodage itératif, qui utilise non plus des contraintes linéaires mais celles de la fonction booléenne. Le quatrième chapitre est dédié aux attaques par treillis: nous présentons en premier lieu une attaque déterministe, qui, lorsque les conditions d'application sont réunies, permet de cryptanalyser le registre filtré très efficacement, et sans aucune probabilité d'erreur. Les conditions d'application de cet algorithme étant assez restrictives, nous avons étendu son principe à des systèmes moins spécifiques, perdant de ce fait le caractère déterministe de l'attaque originelle. Enfin, dans un dernier chapitre, nous avons développé deux algorithmes: le "SOJA" et le "Probability-Matching". Tous deux exploitent conjointement la structure de la fonction booléenne et l'existence d'équations vectorielles, le SOJA afin de générer des probabilités a posteriori sur les bits de la séquence d'entrée, le Probability-Matching afin d'identifier des vecteurs d'entrée de la fonction présentant des propriétés remarquables.

Les travaux de cette thèse portent sur la cryptanalyse d'un système de chiffrement simple, mais important : le registre filtré. Ils concernent les deux principales familles d'attaques que sont les attaques algébriques et les attaques probabilistes. Pour les attaques algébriques, il est important de pouvoir calculer efficacement l'immunité algèbrique de la fonction booléenne par laquelle le registre est filtré. Cette quantité est intimement liée au comportement des codes de Reed-Muller sur le canal à effacements et son étude a permis la découverte de plusieurs résultats qui s'expriment naturellement dans le cadre de la théorie des codes correcteurs. Nous avons ainsi construit une nouvelle borne sur la probabilité de pouvoir compenser un nombre d'effacements fixé. Cette borne montre que l'immunité algébrique d'une fonction booléenne aléatoire est presque toujours maximale. Nous avons également explicité une méthode de décodage fondée sur des algorithmes d'algèbre linéaire creuse (comme l'algorithme de Wiedemann) qui donne un des algorithmes les plus efficace pour calculer l'immunité algébrique. Pour les attaques probabilistes, un outil très important est de parvenir à trouver efficacement de nombreux multiples de poids faible du registre à décalage du système. Un nouvel algorithme fondé sur les logarithmes discrets à été proposé. Il est particulièrement interessant pour les multiples de poids 4, améliorant dans de nombreux cas pratiques le meilleur algorithme connu. Ce travail s'est poursuivi par une nouvelle cryptanalyse probabiliste du registre filtré qui utilise ces multiples de poids faible pour reconnaître les entrées nulles de la fonction de filtrage. Cette attaque est l'une des plus efficaces connue à l'heure actuelle.