Cryptographie à base de codes

Pour un article plus général, voir Cryptographie post-quantique.

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],[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],[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],[15],[16]. Toutes ces variantes ont cela dit été rapidement cassées[11],[17],[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 -aire avec 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 . 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'à 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. ↑ (en) Nicolas Sendrier, « Code-Based Cryptography: State of the Art and Perspectives », IEEE Security Privacy, vol. 15, no 4,‎ , p. 44–50 (ISSN 1540-7993, DOI 10.1109/msp.2017.3151345, lire en ligne, consulté le )
  2. ↑ (en) N. Sendrier, « Code-Based Cryptography: State of the Art and Perspectives », IEEE Security Privacy, vol. 15, no 4,‎ , p. 44–50 (ISSN 1540-7993, DOI 10.1109/msp.2017.3151345, lire en ligne, consulté le )
  3. ↑ (en) Nicolas Sendrier, Encyclopedia of Cryptography and Security, Springer, Boston, MA, (DOI 10.1007/978-1-4419-5906-5_378, lire en ligne), p. 215–216
  4. ↑ a et b (en) E. Berlekamp, R. McEliece et H. van Tilborg, « On the inherent intractability of certain coding problems (Corresp.) », IEEE Transactions on Information Theory, vol. 24, no 3,‎ , p. 384–386 (ISSN 0018-9448, DOI 10.1109/tit.1978.1055873, lire en ligne, consulté le )
  5. ↑ (en) Robert McEliece, « A Public-Key Cryptosystem Based On Algebraic Coding Theory », DSN Progress Report. 44,‎ , p. 114-116
  6. ↑ (en) Nicolas Sendrier, Encyclopedia of Cryptography and Security, Springer, Boston, MA, (DOI 10.1007/978-1-4419-5906-5_384, lire en ligne), p. 767–768
  7. ↑ (en) Harald Niederreiter, « Knapsack-type cryptosystems and algebraic coding theory », Problems of Control and Information Theory. Problemy Upravlenija i Teorii Informacii. 15,‎ , p. 159-166
  8. ↑ (en) Nicolas Sendrier, Encyclopedia of Cryptography and Security, Springer, Boston, MA, (DOI 10.1007/978-1-4419-5906-5_385, lire en ligne), p. 842–843
  9. ↑ (en) Yuan Xing Li, R. H. Deng et Xin Mei Wang, « On the equivalence of McEliece's and Niederreiter's public-key cryptosystems », IEEE Transactions on Information Theory, vol. 40, no 1,‎ , p. 271–273 (ISSN 0018-9448, DOI 10.1109/18.272496, lire en ligne, consulté le )
  10. ↑ (en) P. J. Lee et E. F. Brickell, « An Observation on the Security of McEliece’s Public-Key Cryptosystem », Advances in Cryptology — EUROCRYPT ’88, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 275–280 (ISBN 3540459618, DOI 10.1007/3-540-45961-8_25, lire en ligne, consulté le )
  11. ↑ a et b (en) Daniel J. Bernstein, Tanja Lange et Christiane Peters, « Attacking and Defending the McEliece Cryptosystem », Post-Quantum Cryptography, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 31–46 (ISBN 9783540884026, DOI 10.1007/978-3-540-88403-3_3, lire en ligne, consulté le )
  12. ↑ (en) Vladimir Michilovich Sidel'nikov et Sergey O. Shestakov, « On an encoding system constructed on the basis of generalized Reed–Solomon codes », Diskretnaya Matematika 4, no. 3,‎ , p. 57-63
  13. ↑ (en) Vladimir Michilovich Sidel'nikov, « Open coding based on Reed–Muller binary codes », Diskretnaya Matematika 6, no. 2,‎ , p. 3-20
  14. ↑ (en) Marco Baldi, QC-LDPC code-based cryptography, Springer Briefs in Electrical and Computer Engineering, , 120 p. (ISBN 9783319025551, OCLC 879570345, lire en ligne)
  15. ↑ a et b (en) Masoumeh Koochak Shooshtari, Mohammad Reza Aref, Thomas Johansson et Mahmoud Ahmadian-Attari, « Cryptanalysis of McEliece cryptosystem variants based on quasi-cyclic low-density parity check codes », IET Information Security, vol. 10, no 4,‎ , p. 194–202 (DOI 10.1049/iet-ifs.2015.0064, lire en ligne, consulté le )
  16. ↑ (en) R. Misoczki, J. P. Tillich, N. Sendrier et P. S. L. M. Barreto, « MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes », 2013 IEEE International Symposium on Information Theory,‎ , p. 2069–2073 (DOI 10.1109/isit.2013.6620590, lire en ligne, consulté le )
  17. ↑ (en) Anja Becker, Antoine Joux, Alexander May et Alexander Meurer, « Decoding Random Binary Linear Codes in 2n/20: How 1 + 1 = 0 Improves Information Set Decoding », Advances in Cryptology – EUROCRYPT 2012, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 520–536 (ISBN 9783642290107, DOI 10.1007/978-3-642-29011-4_31, lire en ligne, consulté le )
  18. ↑ (en) R. Overbeck, « Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes », Journal of Cryptology, vol. 21, no 2,‎ , p. 280–301 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-007-9003-9, lire en ligne, consulté le )
  19. ↑ (en) Pierre Loidreau, « Designing a Rank Metric Based McEliece Cryptosystem », Post-Quantum Cryptography, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 142–152 (ISBN 9783642129285, DOI 10.1007/978-3-642-12929-2_11, lire en ligne, consulté le )
  20. ↑ (en) J. C. Faugère, V. Gauthier-Umaña, A. Otmani et L. Perret, « A Distinguisher for High-Rate McEliece Cryptosystems », IEEE Transactions on Information Theory, vol. 59, no 10,‎ , p. 6830–6844 (ISSN 0018-9448, DOI 10.1109/tit.2013.2272036, lire en ligne, consulté le )
  21. ↑ (en) Jean-Charles Faugère, Ayoub Otmani, Ludovic Perret et Frédéric de Portzamparc, « Structural cryptanalysis of McEliece schemes with compact keys », Designs, Codes and Cryptography, vol. 79, no 1,‎ , p. 87–112 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-015-0036-z, lire en ligne, consulté le )
  22. ↑ (en) Daniel J. Bernstein, Tanja Lange et Christiane Peters, « Wild McEliece Incognito », Post-Quantum Cryptography, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 244–254 (ISBN 9783642254048, DOI 10.1007/978-3-642-25405-5_16, lire en ligne, consulté le )
  23. ↑ (en) Kazukuni Kobara et Hideki Imai, « Semantically Secure McEliece Public-Key Cryptosystems -Conversions for McEliece PKC - », Public Key Cryptography, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 19–35 (ISBN 3540445862, DOI 10.1007/3-540-44586-2_2, lire en ligne, consulté le )
  24. ↑ (en) Daniel J. Bernstein, Tung Chou et Peter Schwabe, « McBits: Fast Constant-Time Code-Based Cryptography », Cryptographic Hardware and Embedded Systems - CHES 2013, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 250–272 (ISBN 9783642403484, DOI 10.1007/978-3-642-40349-1_15, lire en ligne, consulté le )
  25. ↑ (en) Pierre-Louis Cayrel et Mohammed Meziani, Advances in Computer Science and Information Technology, Springer, Berlin, Heidelberg, coll. « Lecture Notes in Computer Science », (ISBN 9783642135767 et 9783642135774, DOI 10.1007/978-3-642-13577-4_8, lire en ligne), p. 82–99
  26. ↑ (en) Nicolas T. Courtois, Matthieu Finiasz et Nicolas Sendrier, « How to Achieve a McEliece-Based Digital Signature Scheme », Advances in Cryptology — ASIACRYPT 2001, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 157–174 (ISBN 3540456821, DOI 10.1007/3-540-45682-1_10, lire en ligne, consulté le )
  27. ↑ (en) Pierre-Louis Cayrel, Philippe Gaborit et Emmanuel Prouff, « Secure Implementation of the Stern Authentication and Signature Schemes for Low-Resource Devices », Smart Card Research and Advanced Applications, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 191–205 (ISBN 9783540858928, DOI 10.1007/978-3-540-85893-5_14, lire en ligne, consulté le )
  28. ↑ (en) G. Kabatianskii, E. Krouk et B. Smeets, « A digital signature scheme based on random error-correcting codes », Crytography and Coding, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 161–167 (ISBN 9783540639275, DOI 10.1007/bfb0024461, lire en ligne, consulté le )
  29. ↑ (en) Ayoub Otmani et Jean-Pierre Tillich, « An Efficient Attack on All Concrete KKS Proposals », Post-Quantum Cryptography, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 98–116 (ISBN 9783642254048, DOI 10.1007/978-3-642-25405-5_7, lire en ligne, consulté le )