Vendredi 21 mars 2014 à 16h00 en salle C47
Alain Couvreur (LIX)
Titre : Une attaque polynomiale du schéma de McEliece basé sur les codes de Goppa "sauvages"
Résumé :
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.
Remarques : Travail commun avec Ayoub Otmani et Jean-Pierre Tillich