Aller au contenu

ML-KEM

Un article de Wikipédia, l'encyclopédie libre.

ML-KEM (Module-Lattice-based Key-Encapsulation Mechanism), également connu sous son nom d'origine Kyber ou CRYSTALS-Kyber[1], est mécanisme d'encapsulation de clef (KEM) post-quantique (conçu pour résister aux attaques des ordinateurs quantiques) standardisé en 2024[2]. Il permet d'établir un secret entre deux interlocuteurs sans qu'un attaquant puisse l'intercepter en écoutant les messages échangés. Ce cryptosystÚme asymétrique est basé sur le problÚme algorithmique de l'apprentissage avec erreurs (M-LWE) comme fonction à trappe.

Il a gagné le concours du NIST comme le premier algorithme de cryptographie post-quantique standardisé sous le nom FIPS 203[3].

Propriétés mathématiques

[modifier | modifier le code]
Cette section est vide, insuffisamment détaillée ou incomplÚte. Votre aide est la bienvenue ! Comment faire ?

ML-KEM est basé sur le problÚme algorithmique d'apprentissage avec erreurs modulaire (M-LWE).

Histoire

[modifier | modifier le code]

D'abord connu sous le nom Kyber, ce mĂ©canisme est dĂ©rivĂ© d'une mĂ©thode publiĂ©e en 2005 par Oded Regev[4],[5]. Il fait partie de CRYSTALS (Cryptographic Suite for Algebraic Lattices), une suite composĂ©e de lui-mĂȘme, et de CRYSTALS-Dilithium, un algorithme de signature post-quantique [6].

En 2017, Kyber est soumis au NIST pour le concours de standardisation des primitives cryptographiques post-quantiques. Il s'agit du premier mécanisme d'encapsulation de clef sélectionné pour devenir une norme (FIPS 203) lors du processus de standardisation, au troisiÚme tour[7]. D'aprÚs une note de bas de page du relevé de décision, sa standardisation est conditionnée à divers accords relatifs aux brevets, sans lesquels le NIST pourrait se tourner vers NTRU plutÎt que Kyber d'ici fin 2022[8]. En 2025, lors du quatriÚme tour processus de standardisation, le schéma HQC a été sélectionné comme solution de replis[9].

Lors d'une deuxiÚme phase du processus de standardisation, plusieurs paramÚtres de l'algorithme ont été ajustés, et la compression des clefs publiques a été supprimée[10].

Évolutions

[modifier | modifier le code]

Kyber a subi plusieurs modifications durant le processus de standardisation du NIST. En particulier, lors du deuxiÚme tour, la version Kyber v2 a subi les changements suivants[11] :

  • la compression de la clef publique a Ă©tĂ© supprimĂ©e ;
  • le module q a Ă©tĂ© rĂ©duit de 7681 Ă  3329 ;
  • des paramĂštres de compression du chiffrĂ© ont Ă©tĂ© changĂ©s ;
  • les spĂ©cifications de transformation de Fourier Ă  valeurs dans un corps fini (NTT) ont Ă©tĂ© modifiĂ©es ;
  • la borne d’échantillonnage du bruit a Ă©tĂ© rĂ©duite Ă  η = 2 pour augmenter la vitesse ;
  • la reprĂ©sentation de la clef publique est passĂ©e dans le domaine NTT pour Ă©conomiser des opĂ©rations.

D'autres modifications ont été apportées lors du troisiÚme tour[8] :

  • l'usage de la transformation Fujisaki–Okamoto a Ă©tĂ© modifié ;
  • le niveau de bruit a Ă©tĂ© augmentĂ©, et la compression du chiffrĂ© a Ă©tĂ© rĂ©duite pour le niveau 1 ;
  • l'algorithme d'Ă©chantillionage du paramĂštre A a Ă©tĂ© amĂ©liorĂ©.

Lors de la publication de la version préliminaire publique du standard FIPS 203, d'autres changements ont été apportés[12] :

  • la taille de la clef prĂ©partagĂ©e a Ă©tĂ© fixĂ©e Ă  256 bits ;
  • une diffĂ©rente variante de la transformation Fujisaki–Okamoto est utilisĂ©e ;
  • un usage d'une fonction de hachage sur un alĂ©a gĂ©nĂ©rĂ© a Ă©tĂ© supprimĂ© dans la fonction d'encapsulation de clef, pour se conformer au NIST ;
  • des vĂ©rifications des donnĂ©es d'entrĂ©e ont Ă©tĂ© ajoutĂ©es, notamment Ă  la fonction d'encapsulation.

Enfin, depuis la version préliminaire, les changements suivants ont été apportés au standard FIPS 203[12] :

  • une sĂ©paration de domaines a Ă©tĂ© ajoutĂ©e Ă  la gĂ©nĂ©ration de clef ;
  • la version prĂ©liminaire avait par inadvertance inversĂ©e les indices de la matrice  dans la fonction de gĂ©nĂ©ration et de chiffrement, ceux-ci sont revenus Ă  leur Ă©tat d'origine dans la version finale.

Usage

[modifier | modifier le code]

Les développeurs ont publiés une implémentation de référence dans le domaine public (ou en licence CC0), en C[13].

La librairie liboqs du projet Open Quantum Safe (OQS) contient une implémentation basée sur l'implémentation de référence[14]. Le projet OQC maintient également un module pour Openssl 3.x[15], et a intégré son code dans BoringSSL.

La librairie wolfSSL maintient sa propre implémentation de ML-KEM[16].

Il existe diverses implémentations dans divers langages de programmation, dont JavaScript[17] ou Java[18].

Certaines implémentations matérielles optimisée existent, résistantes aux attaques par canaux auxillaires[19],[20].

Amazon Web Services (AWS) a intégré Kyber dans leur service de gestion de clefs en 2020 comme option d'hybridation post-quantique pour TLS[21].

En 2023, Signal (service de messagerie chiffrĂ©e implĂ©mente Post-Quantum Extended Diffie–Hellman (PQXDH), un mĂ©canisme d'encapsulation de clef basĂ© sur ML-KEM[22] au Signal Protocol.

Notes et références

[modifier | modifier le code]

Notes

[modifier | modifier le code]
  • (en) Cet article est partiellement ou en totalitĂ© issu de l’article de WikipĂ©dia en anglais intitulĂ© « ML-KEM » (voir la liste des auteurs).

Références

[modifier | modifier le code]
  1. ↑ (en-US) Dustin Moody, « What was NIST thinking? : Round 2 of the NIST PQC "Competition" » [archive du ] AccĂšs libre [PDF], sur csrc.nist.gov (consultĂ© le )
  2. ↑ (en) National Institute of Standards and Technology, « Module-Lattice-Based Key-Encapsulation Mechanism Standard », csrc.nist.gov, U.S. Department of Commerce, no Federal Information Processing Standard (FIPS) 203,‎ (DOI 10.6028/NIST.FIPS.203, lire en ligne, consultĂ© le )
  3. ↑ (en-US) « NIST introduces first post-quantum encryption standards | Kaspersky official blog », (consultĂ© le )
  4. ↑ (en-GB) « Lattice-Based Cryptography, The Complete Guide To FIPS 203 », (consultĂ© le )
  5. ↑ Oded Regev, « On lattices, learning with errors, random linear codes, and cryptography », Journal of the ACM (JACM), Association for Computing Machinery, vol. 56, no 6,‎ , p. 34:1–34:40 (ISSN 0004-5411, DOI 10.1145/1568318.1568324, lire en ligne, consultĂ© le )
  6. ↑ Peter Schwabe, « CRYSTALS », sur pq-crystals.org (consultĂ© le )
  7. ↑ (en) Adnan Masood PhD, « Quantum Sundays |21⟩ Federal Transition to Post‑Quantum Cryptography — Kyber Key Exchange and  », sur Medium, (consultĂ© le )
  8. 1 2 Roberto Avanzi, Joppe Bos, LĂ©o Ducas, Eike Kiltz, TancrĂšde Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien StehlĂ©. CRYSTALS–Kyber (Round 3 presentation) June 9, 2021.
  9. ↑ (en-US) Kevin Townsend, « NIST Announces HQC as Fifth Standardized Post Quantum Algorithm », sur SecurityWeek, (consultĂ© le )
  10. ↑ (en) Leon Botros, Matthias J. Kannwischer et Peter Schwabe, « Memory-Efficient High-Speed Implementation of Kyber on Cortex-M4 », dans Progress in Cryptology – AFRICACRYPT 2019, vol. 11627, Springer International Publishing, , 209–228 p. (ISBN 978-3-030-23695-3, DOI 10.1007/978-3-030-23696-0_11, lire en ligne)
  11. ↑ Roberto Avanzi, Joppe Bos, LĂ©o Ducas, Eike Kiltz, TancrĂšde Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien StehlĂ©. CRYSTALS–Kyber (Round 2 presentation) 23 aoĂ»t 2019.
  12. 1 2 National Institute of Standards and Technology (US), « Module-lattice-based key-encapsulation mechanism standard », CrossRef, National Institute of Standards and Technology (U.S.), no NIST FIPS 203,‎ (DOI 10.6028/NIST.FIPS.203, lire en ligne, consultĂ© le )
  13. ↑ (en) pq-crystals, « kyber/LICENSE at main · pq-crystals/kyber », sur GitHub (consultĂ© le )
  14. ↑ « Kyber – Open Quantum Safe » [archive du ] (consultĂ© le )
  15. ↑ open-quantum-safe/oqs-provider, Open Quantum Safe, (lire en ligne)
  16. ↑ (en-US) Shizuka Ishikiriyama, « wolfCrypt Post Quantum | Products - wolfSSL », (consultĂ© le )
  17. ↑ Anton Tutoveanu, antontutoveanu/crystals-kyber-javascript, (lire en ligne)
  18. ↑ Steven K. Fisher, fisherstevenk/kyberJCE, (lire en ligne)
  19. ↑ B. Dang, Kamyar Mohajerani, K. Gaj (2021), High-Speed Hardware Architectures and Fair FPGA Benchmarking of CRYSTALS-Kyber, NTRU, and Saber (PDF) (de)
  20. ↑ Arpan Jati, Naina Gupta, A. Chattopadhyay, S. Sanadhya (2021),A Configurable Crystals-Kyber Hardware Implementation with Side-Channel Protection (PDF) (de)
  21. ↑ « Round 2 post-quantum TLS is now supported in AWS KMS | AWS Security Blog », sur aws.amazon.com, (consultĂ© le )
  22. ↑ (en) signalapp, « Add Kyber KEM and implement PQXDH protocol · signalapp/libsignal@ff09619 », sur GitHub (consultĂ© le )
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=ML-KEM&oldid=240325663 Â».