Points de vue alternatifs

Analyse et veille des médias internationaux : géopolitique, économie, numérique...


Des chercheurs du CNRS conçoivent un algorithme qui va "secouer" la cryptographie

Publié par Kiergaard sur 12 Mai 2014, 16:23pm

Catégories : #Numérique

Des chercheurs du CNRS conçoivent un algorithme qui va "secouer" la cryptographie

Des chercheurs d'un laboratoire du CNRS viennent de concevoir un algorithme facilitant grandement le calcul de logarithmes discrets. Ces derniers sont au cœur des méthodes cryptographiques utilisées aujourd'hui, puisqu'ils sont associés aux problèmes mathématiques qui en fondent la sécurité. Bien qu'à un stade théorique, cette découverte permet de "rejeter plusieurs systèmes cryptographiques" supposés adéquats et "ouvre une faille dans la sécurité cryptographique.

 

Communiqué du CNRS :

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, Razvan Barbulescu, Emmanuel Thomé et Antoine Joux. 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 [se] 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.

Une version préliminaire (fin 2013) de cet article est disponible. Voir le communiqué de fin 2013 du laboratoire.

"Ce résultat ne concerne heureusement pas toutes les instances du problème; les systèmes déployés actuellement ne sont a priori pas touchés. Toutefois, cette découverte vient de réduire à néant le travail de certains chercheurs qui s'intéressaient à la conception de systèmes cryptographiques prenant comme hypothèse de départ la difficulté d'un problème qui n'est désormais plus considéré comme difficile; c'est par exemple le cas de certains travaux sur les couplages.  Même si l'histoire s'est accélérée ces derniers mois, puisque ce résultat s'appuie sur un travail précédent d'Antoine Joux qui avait déjà révélé certaines failles, c'est le fruit de longues recherches pour ces scientifiques qui s’intéressent depuis plusieurs années au logarithme discret. 

Rendu public en juin dernier suite au dépôt de l’article sur le serveur de preprint de l'IACR ( International Association of Cryptologic Research ), spécifique aux cryptographes, ce résultat a eu un impact conséquent sur la communauté, puisqu’il a brisé les présupposés de tous les experts du domaine, notamment en cryptographie basée sur les couplages. Ce résultat, même s’il reste théorique, ouvre d’autres perspectives dans cette thématique de recherche ou une véritable course s’est engagée pour la sécurité de nos données, de nos transactions et permettra des applications dans le quotidien non négligeables : vote électronique, fiabilité de la signature, e-commerce, VPN."

 

Cette découverte et les recherches qui suivront sont très importantes. En effet, même les solutions les plus avancées en matière de cryptographie, comme la cryptographie sur courbes elliptiques repose sur ce problème du logarithme discret. Concernant la cryptographie dite "Pairing-Based" (à base de couplage), les auteurs notent dans leur conclusion que certaines faiblesses sont relevées. 
Nous avions évoqué la cryptographie sur les courbes elliptiques dans le cadre de notre article sur les rapports controversés entre la NSA et RSA, un des leaders mondiaux en matière de cryptographie. 

 

Archives

Nous sommes sociaux !

Articles récents