Séminaire du 25 novembre 02, Jean-Charles Faugère, Projet SPACES LIP6/LORIA

Cryptanalyse expérimentale de HFE

HFE (Hidden Fields Equations) est un cryptosystème à clef publique proposé par Jacques Patarin en 96 et n'utilisant pas la théorie des nombres (comme RSA) mais des opérations sur les polynômes à coefficients dans un corps fini. L'idée de HFE est de prendre un polynôme univarié secret à coefficients dans GF$(2^n)$ puis d'exprimer ce polynôme sur GF$(2)$. On obtient ainsi un système algébrique en $n$ variables (la clef publique).

Retrouver le message original connaissant la clef secrète est ``facile'' puisque cela revient à résoudre un problème univarié. En revanche le décryptage du message est un problème très difficile puisqu'il s'agit de résoudre un système algébrique.

Nous montrons dans cet exposé comment les nouveaux algorithmes de base de Gröbner (implantés dans le package F5) permettent de~: \emph{(i)} dériver très facilement un algorithme spécialisé très efficace pour les corps finis\,; \emph{(ii)} casser assez facilement le Challenge de J. Patarin, un exemple réaliste en taille 80 bits\,; \emph{(iii)} mener une étude de complexité expérimentale pour les systèmes HFE.