Cette thèse est consacrée à l'étude d'objets cryptographiques liés à
la combinatoire et à la théorie des codes correcteurs : les systèmes à
clef publique exploitant la difficulté de la recherche d'un mot de
poids minimal dans un code linéaire quelconque, et les fonctions
sans-corrélation et résilientes qui sont des outils essentiels à la
génération de suites pseudo-aléatoires et à la conception de
primitives cryptographiques conventionnelles.
Nous développons un algorithme probabiliste de recherche de mots de
poids faible dans un code linéaire de grande taille qui améliore
toutes les attaques précédemment connues contre les cryptosystèmes à
mots de poids faible. L'étude de sa complexité par la théorie des
chaînes de Markov montre notamment que le système de chiffrement de
McEliece employé avec ses paramètres originaux n'assure généralement
pas une sécurité suffisante. Cet algorithme nous permet également de
déterminer la distance minimale de certains codes BCH de longueur 511.
Nous généralisons par ailleurs les notions de fonctions
sans-corrélation et de fonctions résilientes aux fonctions définies
sur un alphabet fini quelconque et nous caractérisons ces propriétés
de différentes manières. Nous mettons ensuite en évidence l'existence
d'un compromis entre le degré de la forme algébrique normale et
l'ordre de non-corrélation de toute fonction définie sur un corps fini
et nous construisons des familles infinies de fonctions t-résilientes
de degré optimal. Ce résultat induit un nouveau critère de sécurité
pour les primitives cryptographiques conventionnelles qui enrichit la
notion de multipermutation introduite par Schnorr et Vaudenay. Nous
développons enfin une construction générale qui produit des nouvelles
fonctions résilientes ayant un grand nombre de variables.