Combinatorics in algebraic and logical cryptanalysis

Source abstract

Combinatoire en cryptanalyse algébrique et logique Les attaques cryptographiques que nous décrivons dans cette thèse reposent sur des approches combinatoires, relevant notamment de la théorie des graphes et de la satisfaction sous contraintes. Notre objectif principal concerne l'étude du problème du logarithme discret sur courbes elliptiques. Dans un premier temps, nous nous concentrons sur l'attaque de calcul d'index pour le cas des courbes elliptiques définies sur des extensions de corps finis de degré premier. Au cœur de l'attaque sur ces courbes réside la résolution des systèmes polynomiaux en caractéristique 2. Ainsi, la première phase du calcul d'index, phase de recherche de relations, consiste à résoudre des systèmes d'équations obtenus à partir de polynômes de Semaev, dont les zéros représentent des coordonnées de points. La résolution de ces systèmes répond au problème de décomposition de points. Dans le cadre de cette attaque, premièrement, nous modélisons le problème de décomposition de points sous la forme d'une formule logique et nous le définissons comme une instance du problème SAT. En ajout de cela, nous développons un solveur SAT dédié à ce problème spécifique, nommé WDSat. Le solveur est muni d'une extension qui vise à éliminer les solutions symétriques des polynômes de Semaev sans agrandir le modèle SAT et sans introduire de coût de calcul supplémentaire. Les temps d'exécution expérimentaux montrent que notre approche de résolution utilisant WDSat est significativement plus rapide que les méthodes algébriques actuelles basées sur le calcul de bases de Gröbner. De plus, notre solveur a des meilleures performances que d’autres solveurs SAT couramment utilisés, pour ce problème spécifique. Au final, nous abordons le problème du logarithme discret sur courbes elliptiques dans le cas générique. Notamment, pour la mise en oeuvre de l'attaque de recherche de collisions en contexte parallèle de van Oorschot et Wiener, nous proposons une nouvelle structure de données, ayant des conséquences importantes sur la complexité en mémoire et en temps