Canal-U

Alain Couvreur - Comment domestiquer les codes de Goppa sauvages ?

Le schéma de McEliece est un schéma de chiffrement basé sur les codes correcteurs d'erreurs dont la sécurité repose sur la difficulté à décoder un code aléatoire. Parmi les différentes familles de codes algébriques proposées pour ce schéma, les codes de Goppa classiques sont les seuls à résister à toutes les attaques algébriques, et ce, depuis près de 35 ans. Dans cet exposé, je présenterai une attaque d'un genre nouveau, dite "par filtration" qui permet de retrouver la structure d'un code de Goppa "sauvage" (Wild Goppa code) construit à partir d'une extension de corps quadratique. Cette attaque consiste à utiliser des propriétés multiplicatives du code pour en calculer une filtration (i.e. une famille de sous-codes emboités) dont chaque élément est un code de Goppa classique. Les propriétés algébriques de cette filtration permettent ensuite de retrouver entièrement la structure du code utilisé comme clé publique. Cette attaque a été implémentée en Magma et permet de casser en moins d'une heure des clés proposées par Bernstein, Lange et Peters dont la sécurité était estimée supérieure à 128 bits (Wild McEliece, SAC 2010). Depuis l'introduction du schéma de McEliece, c'est la première attaque polynomiale sur des codes de Goppa classiques n'ayant aucune symétrie apparente.