Reconstruction d'un schéma de codage

This thesis investigates the problem of reverse-engineering a classical transmission scheme from an eavesdropped noisy communication. The two main parts of this work are successively focus on the reconstruction of the two main elements in the scheme: the scrambler and the error correcting code, in the order they have to be treated by an attacker, i.e. in the reverse order to that in which they appear in the transmission scheme. The first part deals with the reconstruction of a binary linear codefrom the knowledge of noisy codewords. First, we present and analyse an algorithm due to A. Valembois. The analysis leads us to a new statistical test for finding words that may belong to the dual of the error correcting code used during the transmission. Then, we present a new decoding algorithm based on classical techniques of iterative decoding. This algorithm enables us to correct some errors even if some parity check equations are not valid. Using this decoding algorithm, we then describe a new algorithm forreconstructing a linear code. The second part deals with the reconstruction of a linear scrambler. First, we assume that the attacker knows the exact output of the scrambler. We present different techniques for reconstructing a synchronous scrambler and a self-synchronized scrambler, depending on the assumptions we make on the input stream. Then, we are interested in the general case and we present an algebraic technique for reconstructing a synchronous scrambler when a partof the input sequence is known but when we only know the image of the output sequence by a linear transformation per block.Cette thèse aborde le problème de la reconstruction des composants d'un système de transmission à partir de l'interception d'une communication bruitée. Les deux grandes parties de ce travail s'intéressent successivement aux deux maillons principaux de la chaîne~: le brasseur et le code correcteur d'erreur, dans l'ordre où ils doivent être traités par l'attaquant, c'est-à-dire dans l'ordre inverse de leur apparition dans la chaîne de transmission.La première partie traite donc du problème de la reconstruction d'un code linéaire binaire à partir de la connaissance de mots de code bruités. Dans un premier temps, nous présentons et analysons une méthode suggérée par A. Valembois dans sa thèse. Cette analyse nous amène à présenter un nouveau test statistique permettant de trouver des mots susceptibles d'appartenir au dual du code utilisé lors de la transmission. Puis nous présentons un nouvel algorithme de décodage fondé sur les techniques classiques de décodageitératif. Cet algorithme nous permet de corriger des erreurs même si certaines des équations de parité trouvées par le test statistique ne sont pas valides. Nous décrivons alors un nouvel algorithme de reconstruction utilisant cet algorithme de décodage.La seconde partie traite du problème de la reconstruction d'un brasseur linéaire. Dans un premier temps, nous supposons que l'attaquant dispose de la sortie exacte du brasseur. Nous présentons alors différentes techniques permettant de reconstruire un brasseur synchrone ou auto-synchronisant en fonction des hypothèses envisagées sur l'entrée du brasseur. Ensuite, nous nous intéressons au cas général et nous présentons alors une technique algébrique permettant de reconstruire un brasseur synchrone quandl'attaquant connaît simplement l'image de sa sortie par une transformation linéaire par bloc et une partie de la suite en entrée