Sites Inria

English version

Récompense

9/03/2012

Un nouvel algorithme pour augmenter la sécurité des échanges cryptographiques

© Inria / Photo Kaksonen

En décembre dernier à Séoul, l'article "Counting points on genus 2 curves with real multiplication"  de Pierrick Gaudry (LORIA/équipe-projet Caramel), David Kohel (Institut de Mathématiques de Luminy) et Benjamin Smith (équipe Grace, anciennement Tanc) a remporté (conjointement) le prix du meilleur article à la conférence AsiaCrypt 2011, l'une des trois conférences internationales les plus importantes en cryptologie.

"Counting points on genus 2 curves with real multiplication"  exposait une réelle avancée dans le domaine de la cryptographie. La nécessité de chiffrer des informations  pour les transmettre de façon sécurisée est de plus en plus présente dans le monde numérique, pour établir les communications sécurisées, prouver nos identités en ligne, ou encore signer des documents numériques. Pour cela, la méthode le plus souvent employée est un cryptosystème à clé publique , à l’opposé de clé privée  où les deux personnes qui souhaitent échanger des informations doivent également échanger leurs clés privés. Dans le cas d'un cryptosystème à clé publique, chaque instance comme par exemple chaque signature numérique, se base sur un exemple de problème mathématique très difficile, et la sécurité du système dépend entièrement de la difficulté à résoudre ce problème. Pour s’assurer de la difficulté de ces problèmes, des algorithmes de "point counting"  ou comptage de points permettent de vérifier la sécurité du futur cryptosystème.

L'état de l'art en cryptographie à clé publique était basé, jusqu’à maintenant, sur des problèmes avec des courbes elliptiques. Google par exemple les a employées pour ses pages web sécurisées.  Récemment, les chercheurs se sont penchés sur les courbes de genre 2 comme une version améliorée, un successeur des courbes elliptiques . Mais alors que les courbes de genre 2 ont de très belles propriétés théoriques, il y avait un obstacle important à leur utilisation dans la pratique : dans de nombreux cas (notamment le cas du corps premier), leurs algorithmes de comptage de points sont tout simplement beaucoup trop lents.  Pour comparaison, il est possible de compter le nombre de points sur une courbe elliptique cryptographique en quelques secondes ; quand jusqu'à maintenant, le calcul équivalent en genre 2 requérait plusieurs jours, ce qui empêchait leur utilisation ainsi que les expériences.

Dans ce papier, les chercheurs ont présenté un nouvel algorithme pour une classe commode des courbes de genre 2, qui offre une amélioration radicale de la performance pour le comptage de points.  En effet, le nouvel algorithme fonctionne tellement bien qu’il a pulvérisé le record mondial pour le comptage des points en genre 2 (dans le cas du corps premier). Grâce à cette avancée en sécurité informatique, il est désormais possible de facilement construire des courbes de genre 2 appropriées pour les cryptosystèmes contemporains.

Mots-clés : Benjamin Smith Grace Algorithme Saclay - Île-de-France Cryptographie

Haut de page

Suivez Inria