MosaikHub Magazine

Une percée en informatique rend caduques des procédures de chiffrement

dimanche 26 octobre 2014

Nos ordinateurs ont encore eu chaud. Début avril, c’était une faille repérée dans un logiciel assurant la sécurité des transactions électroniques qui permettait le vol de mots de passe.

Aujourd’hui, quatre mathématiciens et informaticiens du CNRS, de l’Institut national de recherche en informatique et en automatique (Inria) à Nancy et de l’université Pierre-et-Marie-Curie à Paris explique que des équations mathématiques que l’on pensait insolubles en un temps raisonnable peuvent être « cassées » dans des temps « courts ». Entamant de facto la sécurité des systèmes utilisant ces formules.

La sécurité des cartes bancaires, des passeports ou des transactions électroniques… utilise certes des composants électroniques comme des puces mais elle repose aussi sur des propriétés mathématiques. Ainsi, la robustesse du protocole RSA, utilisé dans les cartes bancaires, provient du fait qu’il est facile de multiplier des nombres premiers entre eux mais qu’il est difficile de faire l’opération inverse : trouver les deux nombres connaissant leur produit.

De même dans les passeports électroniques, l’accès aux données est protégé par des opérations dans lesquelles des nombres sont élevés à une certaine puissance. Mais il est difficile de retrouver l’exposant et le nombre initial connaissant le résultat. C’est le problème dit du logarithme discret. Ce dernier est « simple » à résoudre si les nombres sont des entiers. Mais cela se corse si les nombres en question appartiennent à des ensembles « étranges » dans lesquels élever un nomble à la puissance 3 peut donner un grand nombre alors que la puissance 4 peut être un petit nombre.

« C’EST L’UNE DES GRANDES AVANCÉES DANS LE DOMAINE »

C’est à cette opération de logarithme discret que s’est attaquée avec succès l’équipe française qui a présenté son travail, lundi 12 mai à Copenhague, à la conférence Eurocrypt, par la voix de Razvan Barbulescu, l’un des quatre co-auteurs qui a soutenu sa thèse en décembre 2013. L’article a même reçu un prix lors de cette réunion.

Le logarithme discret est considéré comme un problème difficile, soluble en un temps qui varie exponentiellement avec sa taille (c’est-à-dire la taille des nombres impliqués). Le nouvel algorithme résout ce problème en un temps quasi-polynomial, c’est-à-dire plus rapidement.

« Dans le cas où les méthodes actuelles nécessiteraient 2128 opérations, ce qui est infaisable, en théorie notre algorithme ne demanderait que 260 calculs, estime Emmanuel Thomé de l’Inria. Plus on augmente la taille des nombres, plus l’écart avec les solutions existantes augmente. Mais ça reste diablement difficile », ajoute le chercheur.

« C’est l’une des grandes avancées dans le domaine. Un travail remarquable, assure Andreas Enge de l’Inria à Bordeaux, qui n’est pas signataire de l’article. Ce n’est pas une astuce de calcul car on comprend parfaitement pourquoi et dans quels cas ça fonctionne », complète le chercheur.

Malheureusement ou heureusement, l’algorithme ne s’applique pas à toutes les situations reposant sur le logarithme discret. En particulier, cela ne concerne pas la plupart des protocoles effectivement utilisés dans la vie quotidienne. « Mais cela tue certaines variantes », précise Emmanuel Thomé qui cite « divers protocoles comme les signatures électroniques courtes ou des propositions de monnaie électronique ».

Certains scientifiques songent aussi à explorer cette voie pour s’attaquer au problème de la factorisation des entiers, dont les liens avec le logarithme discret existent. Des améliorations de l’algorithme sont également possibles.

DES ATTAQUES NOMBREUSES

« Cela ne met pas par terre le commerce mondial, mais nous avons cassé une barrière de complexité », indique Emmanuel Thomé. Dans l’esprit, cela rappelle la percée des Indiens Agrawal, Kayal et Saxena, qui, en 2002, avaient démontré à la surprise générale que le problème de savoir si un nombre est premier (divisible seulement par un et lui-même) est soluble en un temps polynomial. Cela leur a valu le prix Gödel en 2006.

L’équipe française est une habituée des « attaques ». En 2004, par exemple, Antoine Joux (prix Gödel 2013) avait trouvé que des fonctions cryptographiques, dites de « hachage », avaient des faiblesses. Il a aussi battu des records dans la catégorie du logarithme discret, retrouvant l’exposant et le nombre secret à partir du résultat. Emmanuel Thomé et Pierrick Gaudry, deux autres coauteurs de l’article présenté à Eurocrypt, s’en sont notamment pris, eux, au protocole RSA. En 2010, ils ont ainsi factorisé en un temps « court » un nombre de 232 chiffres.

Désormais ils vont étendre leur idée en s’attaquant à des ensembles plus vastes concernés par les opérations de logarithmes discrets.

David Larousserie
Journaliste au Monde


Accueil | Contact | Plan du site | |

Creative Commons License

Promouvoir & Vulgariser la Technologie