| Gwénolé Ars |  |
 |
Date de l'exposé : 13 juin 2003
Étude de l'algorithme XL
L'algorithme XL est un algorithme utilisé en cryptographie pour déterminer une solution d'un système polynômial dans un corps fini. Cet algorithme est assez efficace : il peut en effet résoudre des cryptosystèmes engendrés par des registres filtrés en temps polynômial avec un nombre de couple clair-chiffré polynômial en la taille de la clef.Il existait auparavant différents algorithmes de résolution de systèmes polynômiaux comme le calcul des bases de Gröbner. Nous allons tout d'abord nous intéresser à certains algorithmes de calcul des bases de Gröbner pour comprendre les calculs effectuées et les critères développés. Puis, nous verrons la structure de l'algorithme XL et les remarques faites par l'auteur sur cet algorithme.
Enfin, nous étudierons ce que calcul exactement l'algorithme XL du point de vue des bases de Gröbner et proposerons un algorithme émulé utilisant le calcul de bases de Gröbner. A partir de cet algorithme émulé, nous effectuerons des comparaisons sur le cryptosystème HFE.
