Un nouvel algorithme secoue la cryptographie

Publié par Adrien le 12/05/2014 à 00:00
Source: 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 (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée...) algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de résolution, par le...) 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 brèche est une roche. La Brèche est la place centrale de la ville de Niort ) 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 réseaux de distribution d'électricité et de gaz pour les 8 gestionnaires du secteurs mixte en...) 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 (La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de...) cherche à utiliser des problèmes mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les 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 (En mathématiques, une fonction logarithme est une fonction définie sur à valeurs dans , continue et transformant un produit en somme. Le logarithme de base a où a est un réel strictement...) 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 organisme de recherche scientifique public français (EPST).), d'Inria et du Laboratoire d'informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des machines telles que les...) de Paris (Paris est une ville française, capitale de la France et le chef-lieu de la région d’Île-de-France. Cette ville est construite sur une boucle de la Seine, au centre du bassin parisien, entre les confluents de...) 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 exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri...) 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 changement dans le monde.) 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 (Un stade (du grec ancien στ?διον stadion, du verbe ?στημι istêmi, « se tenir droit et ferme ») est un équipement sportif.) 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 de propositions initiales, ou précédemment démontrées...) 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 (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques...) de résoudre un problème complexe.

(2) Une puce RFID est une puce informatique couplée à une antenne (En radioélectricité, une antenne est un dispositif permettant de rayonner (émetteur) ou de capter (récepteur) les ondes électromagnétiques.) 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 (Un chercheur (fem. chercheuse) désigne une personne dont le métier consiste à faire de la recherche. Il est difficile de bien cerner le métier de...) au Laboratoire d'informatique de Paris 6 (CNRS/UPMC) et a obtenu depuis la Chaire de cryptologie de la Fondation UPMC.
Cet article vous a plus ? Vous souhaitez nous soutenir ? Partagez-le sur les réseaux sociaux avec vos amis et/ou commentez-le, ceci nous encouragera à publier davantage de sujets similaires !
Page générée en 0.391 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique