Un nouvel algorithme secoue la cryptographie

Des chercheurs du Laboratoire lorrain de recherches en informatique et ses applications (CNRS/Université de Lorraine/Inria) et du Laboratoire d'informatique de Paris 6 (CNRS/UPMC) 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. Ils ont ainsi conçu un nouvel algorithme (1) battant en brèche la sécurité d'une variante de ce problème, pourtant étudiée avec attention depuis 1976. Ce résultat, publié sur le site de l'International association of cryptologic research et sur l'archive ouverte HAL sera présenté lors de la conférence internationale Eurocrypt 2014 qui se tiendra à Copenhague du 11 au 15 mai 2014 et publié dans Advances in cryptology. Il permet d'ores et déjà de rejeter plusieurs systèmes cryptographiques supposés jusqu'alors offrir des garanties de sécurité suffisantes. Bien qu'encore théoriques, ces travaux devraient avoir des répercussions, notamment dans les applications cryptographiques des cartes à puces, des puces RFID (2) etc.

Pour protéger la confidentialité de l'information, la cryptographie cherche à utiliser des problèmes mathématiques difficiles à résoudre, même pour les machines les plus puissantes et les algorithmes les plus sophistiqués.

La sécurité d'une variante du logarithme discret, réputé très difficile, a été battue en brèche par quatre chercheurs du CNRS, d'Inria et du Laboratoire d'informatique de Paris 6 (CNRS/UPMC): Pierrick Gaudry, R?zvan B?rbulescu, Emmanuel Thomé et Antoine Joux (3). L'algorithme conçu par ces chercheurs se démarque des meilleurs algorithmes 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 que par les algorithmes précédents. Le calcul de logarithmes discrets associé aux problèmes voulus difficiles pour les applications cryptographiques s'en trouve grandement facilité.

Résoudre cette variante du logarithme discret étant désormais à la portée des calculateurs actuels, il devient donc 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. En effet, il pourrait être adapté afin de tester la solidité d'autres solutions cryptographiques.

Notes:

(1) Une méthode constituée d'une suite d'instructions permettant à un ordinateur de résoudre un problème complexe.

(2) Une puce RFID est une puce informatique couplée à une antenne lui permettant d'être activée à distance par un lecteur et de communiquer avec lui.

(3) Antoine Joux qui était rattaché au Laboratoire parallélisme, réseaux, systèmes, modélisation (PRISM) (CNRS/UVSQ) au moment de la publication en open access est actuellement chercheur au Laboratoire d'informatique de Paris 6 (CNRS/UPMC) et a obtenu depuis la Chaire de cryptologie de la Fondation UPMC.