Sites Inria

English version

Log discret

D. Baudier - 31/10/2013

Cryptographie : algorithme du log discret

Razvan Barbulescu - Emmanuel Thomé - Pierrick Gaudry

Au printemps 2013, quatre scientifiques ont ouvert l'un des verrous les plus solides du monde de la cryptographie, celui tenu par le logarithme discret. Explications...

Réputé inviolable le logarithme discret ou "log discret" est devenu ces dernières années l’un des outils mathématiques les plus plébiscités par le monde de la cryptographie à clef publique, une discipline essentielle pour protéger les données confidentielles sur Internet ou dans les cartes à puce. Mais la découverte d’un nouvel algorithme par quatre scientifiques – Razvan Barbulescu, Pierrick Gaudry, Emmanuel Thomé et Antoine Joux – pourrait bien changer les choses. Ce quatuor a en effet développé ces derniers mois une solution susceptible de réduire considérablement le degré de complexité du redoutable problème du log discret, du moins dans certaines configurations, heureusement non déployées dans les produits les plus courants.

 

De l’impossible au compliqué

Dans le monde de la cryptographie, le niveau de difficulté d'un problème se mesure au temps de calcul informatique nécessaire pour le résoudre : plus ce délai est long, et plus un « attaquant » aura du mal à accéder aux données secrètes. Jusque-là, le temps de résolution nécessaire aux meilleurs algorithmes pour résoudre le logarithme discret était "sous-exponentiel". Autrement dit, ce temps augmentait très rapidement en fonction de la taille de l'objet mathématique utilisé pour créer le logarithme discret, garantissant ainsi la presque inviolabilité des données qu’il protégeait. La percée effectuée par les quatre scientifiques a en quelque sorte permis de faire descendre le log discret d'une catégorie, puisque son temps de calcul, mesuré en fonction de la taille de l'objet, n'est désormais plus sous-exponentiel, mais quasi-polynomial. Résultat : la résolution du log discret est en théorie à la portée des calculateurs actuels. Il est donc inutilisable pour protéger les données, un attaquant pouvant en trouver la clef à condition d’y mettre les moyens.« Le problème du logarithme discret était considéré comme l'un des "graals" de la théorie algorithmique des nombres, rappelle Pierrick Gaudry, le responsable scientifique de l'équipe Projet Caramel (Cryptologie, Arithmétique : Matériel et Logiciel). Nous sommes donc particulièrement fiers d'avoir contribué à ce sujet. »

 

Le fruit d’une réflexion commune

Si ce résultat a bénéficié de plusieurs décennies de recherche, le pas décisif a été franchi début 2013 à Nancy, site qui regroupe plusieurs équipes de pointe en sécurité informatique, dont l'équipe-projet CARAMEL, spécialisée dans la théorie des nombres appliquée à la cryptographie.« Nous avions invité Antoine Joux, qui venait de réaliser plusieurs avancées successives sur le sujet, pour discuter de ses recherches. Le déclic est venu soudainement, lors d'une discussion. Nous nous sommes alors précipités pour coucher notre découverte sur le papier », se souvient Emmanuel Thomé.

Si ce nouvel algorithme ferme certaines portes aux cryptographes, il ouvre aussi de nouvelles perspectives de recherche dans un domaine qui concerne la sécurité de des données et les transactions au quotidien.

 

Les chercheurs

 

  • Pierrick Gaudry est directeur de recherche au CNRS et responsable scientifique de l'équipe-projet CARAMEL (Cryptologie, Arithmétique : Matériel et Logiciel),
  • Emmanuel Thomé est chargé de recherche à Inria
  • Razvan Barbulescu est doctorant de l’Université de Lorraine.Tous les trois sont membres de l’équipe-projet CARAMEL, qui a obtenu en novembre dernier le prix La Recherche pour le cassage de la clé RSA 768.
  • Antoine Joux, polytechnicien, est aujourd'hui professeur à l'Université Paris VI, et a rejoint récemment l'équipe-projet Inria POLSYS. Il a obtenu en 2013 le prix Gödel pour ses résultats notoires en cryptographie.

Mots-clés : Pierrick gaudry Razvan barbulescu Emmanuel thomé Antoine Joux Caramel Clef publique Arithmetique Algorithme RSA Cryptologie

Haut de page

Suivez Inria tout au long de son 50e anniversaire et au-delà !