Le problème du logarithme discret

La sécurité de Diffie-Hellman tient à une question précise, que les mathématiciens n'ont pas su résoudre efficacement.

L'énoncé

Connaissant g, p et A, retrouver l'exposant a tel que :

g^a mod p = A

C'est le problème du logarithme discret. Sur les nombres réels, le logarithme se calcule sans difficulté. Modulo p, la fonction perd toute régularité : les puissances successives de g sautent de façon désordonnée dans l'intervalle, et rien n'indique si l'on s'approche de la cible.

5^1=5   5^2=2   5^3=10   5^4=4   5^5=20   5^6=8   ...     (mod 23)

Aucune monotonie, donc aucune recherche par dichotomie possible.

Ce qu'on sait faire

Les meilleurs algorithmes connus, comme le crible de corps de nombres, restent sous-exponentiels : bien plus rapides que l'énumération, mais très loin d'être praticables sur un p de 2048 bits.

Attention cependant : ce problème n'est pas prouvé difficile. On sait seulement qu'après des décennies d'efforts, personne n'a trouvé mieux. Toute la cryptographie à clé publique repose sur ce genre de pari.

Les pièges de mise en œuvre

La théorie tient ; les détails tuent. Trois erreurs classiques :

• un p trop petit : en dessous de 1024 bits, l'attaque Logjam (2015) a montré qu'un adversaire bien doté pouvait précalculer l'essentiel du travail pour un p donné, puis casser chaque échange rapidement ;
• un p partagé par des millions de serveurs, qui rentabilise ce précalcul ;
• un g mal choisi, engendrant un sous-groupe trop petit et réduisant d'autant les valeurs possibles.

Et l'avenir

Un ordinateur quantique de taille suffisante résoudrait le logarithme discret en temps polynomial, grâce à l'algorithme de Shor. La même menace pèse sur RSA. C'est la raison pour laquelle les standards post-quantiques sont en cours de déploiement.