Cryptographie à base de codes

De testwiki
Aller à la navigation Aller à la recherche

Modèle:Article général La cryptographie à base de codes est une technique permettant de construire des primitives cryptographiques à clé publique à partir de codes correcteurs d'erreurs[1]. Il s'agit d'une des premières constructions de cryptographie asymétrique, et constitue l'une des directions de recherche explorées pour développer la cryptographie post-quantique[2]Modèle:,[3]. La sécurité de ces constructions repose sur le théorème que le décodage d'un code linéaire est NP-difficile en général[4].

Histoire

En 1978, Elwyn Berlekamp, Robert McEliece et Henk von Tilborg démontrent que le problème consistant à décoder un code linéaire est en général NP-difficile[4]. McEliece en tire un cryptosystème à clé publique[5] à partir des codes algébriques binaires de Goppa, appelé cryptosystème de McEliece[6]. En 1986, Harald Niederreiter publie une construction similaire mais plus rapide, le cryptosystème de Niederreiter[7]Modèle:,[8], qui s'avère en fait équivalent (dual) à celui de McEliece[9]. À ce jour, la version de McEliece a résisté à la cryptanalyse, l'attaque la plus efficace connue étant le décodage par ensemble d'information[10], légèrement plus efficace sur un calculateur quantique, mais aisément contrecarrée en utilisant des paramètres assez grands[11].

Cependant, la taille prohibitive des clés et la complexité importante de l'algorithme de déchiffrement ont poussé au développement de variantes reposant sur d'autres codes. Ainsi il a été proposé de construire sur le même principe des cryptosystèmes à partir des codes de Reed-Solomon[12], de Reed-Muller[13], et plus récemment sur les codes LDPC ou MDPC quasi-cycliques[14]Modèle:,[15]Modèle:,[16]. Toutes ces variantes ont cela dit été rapidement cassées[11]Modèle:,[17]Modèle:,[15]. Il semble que le gain de structure, qui permet de compresser les clés publiques, facilite du même coup grandement le travail de l'attaquant.

Une autre solution consiste à considérer des codes correcteurs pour une autre métrique, en remplaçant par exemple la distance de Hamming par le rang. Si le problème du décodage est a priori plus difficile encode dans ce contexte, en pratique une attaque due à Raphael Overbeck en 2008 a cassé toutes les propositions de ce type[18]. Des recherches se poursuivent sur la possibilité de contourner l'attaque[19].

Enfin, même l'utilisation d'un code de Goppa ne garantit pas la sécurité : si le taux approche 1 des attaques sont connues[20], de même si on considère un code q-aire avec q non premier[21].

Principe général

La cryptographie à base de codes s'appuie sur la notion qu'un code linéaire peut être décrit par une matrice génératrice (ou une matrice de parité), qui sera donc la clé publique. Le chiffrement d'un message consiste simplement à appliquer le code correcteur correspondant, c'est-à-dire à effectuer le produit matrice vecteur, puis ajouter un aléa de poids de Hamming faible ≤t. Le déchiffrement consiste à appliquer l'algorithme de décodage du code correcteur.

Le code retenu pour cette construction est choisi de sorte qu'étant donnée la matrice génératrice du code, il est difficile d'en déduire un algorithme de décodage corrigeant jusqu'à t erreurs. Ainsi, alors que le destinataire légitime du message bénéficie d'un algorithme efficace car spécialisé, un adversaire sera contraint d'appliquer des méthodes génériques, bien moins efficaces. En choisissant les paramètres du code de manière appropriée, on peut rendre le travail de l'adversaire arbitrairement difficile, tout en gardant le travail du destinataire légitime sous contrôle.

Pour éviter que l'adversaire ne « reconnaisse » le code à partir de sa matrice génératrice, on choisit le code parmi une famille assez large pour que la matrice semble aléatoire. On peut combiner cela avec des permutations afin de dissimuler la matrice davantage, au prix d'opérations supplémentaires pour le déchiffrement. Toutefois, l'apport concret de ces variations sur la sécurité du schéma semble mineure[22].

Construit ainsi, un chiffrement à base de codes correcteurs est vulnérable à toute une famille d'attaques classiques. Cela peut toutefois être évité de manière générique en appliquant une transformation due à Kazukuni Kobara et Hideki Imai[23] qui dote le cryptosystème d'une résistance aux attaques adaptatives par chiffrés choisis (IND-CCA2) pratiquement sans augmenter la bande passante par rapport à l'original.

Primitives à base de codes correcteurs

Schémas de chiffrement :

Schémas de signature[25] :

Références

  1. ↑ Modèle:Article
  2. ↑ Modèle:Article
  3. ↑ Modèle:Ouvrage
  4. ↑ 4,0 et 4,1 Modèle:Article
  5. ↑ Modèle:Article
  6. ↑ Modèle:Ouvrage
  7. ↑ Modèle:Article
  8. ↑ Modèle:Ouvrage
  9. ↑ Modèle:Article
  10. ↑ Modèle:Article
  11. ↑ 11,0 et 11,1 Modèle:Article
  12. ↑ Modèle:Article
  13. ↑ Modèle:Article
  14. ↑ Modèle:Ouvrage
  15. ↑ 15,0 et 15,1 Modèle:Article
  16. ↑ Modèle:Article
  17. ↑ Modèle:Article
  18. ↑ Modèle:Article
  19. ↑ Modèle:Article
  20. ↑ Modèle:Article
  21. ↑ Modèle:Article
  22. ↑ Modèle:Article
  23. ↑ Modèle:Article
  24. ↑ Modèle:Article
  25. ↑ Modèle:Ouvrage
  26. ↑ Modèle:Article
  27. ↑ Modèle:Article
  28. ↑ Modèle:Article
  29. ↑ Modèle:Article

Modèle:Portail

Récupérée de "https://fr.wiki.beta.math.wmflabs.org/w/index.php?title=Cryptographie_à_base_de_codes&oldid=17366"