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 (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées...) 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 Brêche ou Brèche est une rivière française située dans le département de l'Oise. La...) 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 (ORES, l'Opérateur des Réseaux Gaz & Électricité est le l'opérateur des...) 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 (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide...) 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 (Le Centre national de la recherche scientifique, plus connu sous son sigle CNRS, est le plus grand...), d'Inria et du Laboratoire d'informatique (L´informatique - contraction d´information et automatique - est le domaine...) de Paris (Paris est une ville française, capitale de la France et le chef-lieu de la région...) 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é (La complexité est une notion utilisée en philosophie, épistémologie (par...) 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 (Le temps est un concept développé par l'être humain pour appréhender le...) 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 (En mathématiques, une démonstration permet d'établir une proposition à partir...) 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.