Algebraic cryptanalysis of hyperelliptic curves based systems

Cryptanalyse algébrique des systèmes à base de courbes hyperelliptiques Dans cette thèse, nous présentons des attaques algébriques sur des schémas cryptographiques. Nous nous intéressons en particulier au problème du logarithme discret sur le groupe des points rationnels d'une courbe elliptique ou sur la Jacobienne d'une courbe hyperelliptique de genre g ≥ 2 définie sur des extensions de corps. Pour résoudre ce problème, les cryptanalystes utilisent l'algorithme du calcul d'indices qui se fait en 4 étapes: le choix d'une base de factorisation appropriée, l'étape de recherche de relations, la phase d'algèbre linéaire et la phase de descente. L'étape cruciale est l'étape de recherche de relations qui aboutit souvent à la résolution de systèmes polynomiaux aléatoires multivariés. Le plus souvent, la résolution de ces systèmes se fait en utilisant les bases de Gröbner. La complexité du calcul des bases de Gröbner d'un système polynomial est mesurée par le solving degree de ce système qui est le degré maximal des polynômes intervenant dans le calcul de sa base de Gröbner. Tout d'abord, nous donnons de meilleures bornes sur la complexité du calcul des bases de Gröbner des systèmes polynomiaux surdéterminés provenant de la cryptographie. Ensuite, nous exploitons les endomorphismes et les points de 2-torsion de plusieurs courbes elliptiques et hyperelliptiques de genre g ≥ 2 pour réduire la taille de la base de factorisation en vue d'améliorer la complexité du calcul d'indices