Institut de Recherche sur l'Enseignement des Mathématiques de Paris

La cryptographie à clé publique est une composante indispensable de la plupart des protocoles cryptographiques actuels. Ses principaux domaines d'utilisation sont la signature numérique et l'échange de clé. Elle est basée sur des problèmes calculatoires difficiles et en particulier sur la difficulté de la factorisation des entiers et sur la difficulté du calcul des logarithmes discrets dans des groupes biens choisis. La factorisation d'un produit de deux grands nombres premiers ou le calcul d'un logarithme discret dans le groupe multiplicatif Z/pZ* (p premier) sont certes difficiles, mais pas aussi difficiles qu'on le souhaiterait. Il existe en effet des algorithmes sous-exponentiels pour les résoudre. En revanche, on ne connaît actuellement, pour résoudre le problème du logarithme discret dans le groupe des points d'une courbe elliptique bien choisie, que des algorithmes exponentiels. C'est ce qui fait l'intérêt de ces groupes dont la NSA préconise l'utilisation exclusive pour ce type de cryptographie. Nous proposons une visite guidée autour de ces notions.