Cryptanalyse algébrique : outils et applications

摘要: Cette these traite de la cryptanalyse algebrique qui consiste a modeliser une primitive cryptographique en un systeme d'equations polynomiales plusieurs variables dans le but resoudre (ou au moins d'en estimer difficulte). Pour resolution, nous utilisons des outils provenant du calcul formel (bases Grobner). Un premiere axe ete modelisation et recherche d'antecedents sur fonctions hachages cryptographiques. Nos travaux permettent d'estimer que cout d'une d'antecedent est inferieure exhaustive pour les plus courantes. Nous observons meme meilleure complexite attaques existantes. deuxieme conception l'etude d'algorithmes tirent parti contexte d'application (corps finis). Notre methode melange l'enumeration elements corps avec bases Grobner. donnons etude fine sa quantifions gain apporte (un exponentiel nombre variables). La ces algorithmes motivee par l'attaque cryptosystemes multivaries. resultats montrer faiblesse certains parametres proposes (pour schema UOV exemple). analysons egalement schemas HFE leurs generalisations Multi-HFE. cette attaque recouvrement cle polynomiale taille chiffre. permet aussi Multi-HFE sont surs originels. Enfin, adaptations d'attaquer variantes sensees renforcer