Sciences

En bref : un nouvel algorithme déjoue les systèmes de cryptographie

ActualitéClassé sous :Mathématiques , cryptologie , algorithme

-

Dans une étude récente, des chercheurs du CNRS ont réussi à déjouer le logarithme discret, l'un des systèmes de protection les plus difficiles à résoudre. Ce travail permet d'ores et déjà de rejeter plusieurs applications cryptographiques et devrait avoir des répercussions importantes sur les systèmes de sécurité.

Des chercheurs viennent de résoudre un pan du problème du logarithme discret, considéré comme l'un des graals de la théorie algorithmique des nombres, à la base de la sécurité de nombreux systèmes cryptographiques utilisés aujourd'hui. © Clément Dorando

La cryptographie est une science qui s'attache à protéger la confidentialité de l'information en utilisant des problèmes mathématiques difficiles à résoudre, même pour les machines les plus puissantes. La sécurité d'une variante du logarithme discret, réputé très complexe, vient cependant d'être battue en brèche par des chercheurs du CNRS. Leurs résultats, publiés dans la collection Lecture Notes in Computer Science, ont été présentés lors de la conférence internationale Eurocrypt 2014 à Copenhague entre le 11 et le 15 mai.

L'algorithme conçu par ces scientifiques se démarque de ceux connus jusqu'alors pour ce problème. D'une part, il est significativement plus simple à expliquer et d'autre part, sa complexité est bien meilleure : ceci signifie qu'il est à même de résoudre des problèmes de logarithmes discrets de plus en plus grands, en voyant son temps de calcul croître beaucoup plus modérément. Le calcul de logarithmes discrets associé aux problèmes voulus difficiles pour les applications cryptographiques s'en trouve donc grandement facilité.

Résoudre cette variante du logarithme discret étant désormais à la portée des calculateurs actuels, il devient inenvisageable de reposer sur sa difficulté dans les applications cryptographiques. Ces travaux sont encore à un stade théorique et l'algorithme doit encore être affiné avant de pouvoir fournir une démonstration pratique de la faiblesse de cette variante du logarithme discret. Néanmoins, ces résultats ouvrent une faille dans la sécurité cryptographique et la voie à d'autres recherches. Il pourrait par exemple être utilisé afin de tester la solidité d'autres solutions cryptographiques.