On connait les premiers algorithmes de cryptographie post-quantique

Pour savoir qui a le droit de déchiffrer ou signer un message, la cryptographie à clé publique repose sur des problèmes mathématiques difficiles et n’autorise ces opérations qu’à ceux qui en détiennent la solution. En même temps, tout le monde doit pouvoir chiffrer un message ou vérifier une signature d’un utilisateur donné. Ces processus, généralement invisibles et automatiques, ont par exemple lieu à chaque échange de mails. Les intrus, qui n’ont pas la bonne réponse en leur possession, ne doivent pas pouvoir réaliser l’opération inverse et ainsi calculer la solution qu’ils n’ont pas. La cryptographie a donc choisi une série de problèmes spécifiquement parce qu’ils sont simples à résoudre dans un sens, mais impossibles dans l’autre dans un temps raisonnable, même avec les ordinateurs les plus puissants.

L’essor annoncé des ordinateurs quantiques a cependant changé la donne. Ces derniers ne seront pas simplement des versions améliorées de nos ordinateurs de bureau : fonctionnant avec des principes physiques complètement différents, et au-delà de la seule question de leur puissance, ils pourront résoudre bien plus facilement certains problèmes, dont ceux utilisés par la cryptographie actuelle. Si pour l’instant les premiers démonstrateurs d’ordinateurs quantiques sont encore loin de pouvoir réaliser ce genre de tâches, pas question d’attendre qu’ils le soient pour se prémunir d’un tel risque.

C’est pourquoi le National Institute of Standards and Technology (NIST) – l’agence américaine chargée des normes technologiques - a lancé en 2016 un appel international à contributions pour définir des standards de sécurité adaptés aux futurs développements de l’informatique : la cryptographie post-quantique (lire notre article d’avril 2021).

« Le NIST a lancé cet appel sur la demande de la NSA, précise Pierre-Alain Fouque, professeur à l’Université de Rennes 1 et chercheur au sein de l'Institut de recherche en informatique et systèmes aléatoires (IRISA - CNRS/Université de Rennes 1). Les militaires considèrent en effet des durées de vie particulièrement longues pour la sécurité : il faut vingt ou trente ans pour concevoir et construire un sous-marin, qui va fonctionner pendant plusieurs décennies et dont les communications doivent rester indéchiffrables encore vingt ans après son retrait du service. Or, il est raisonnable de penser que de vrais ordinateurs quantiques pourraient émerger avant que tout le matériel militaire actuel ne soit complètement hors d’usage. »

Le concours s’est déroulé en plusieurs étapes. Quatre-vingt-deux projets ont initialement été soumis, répartis entre deux approches. On retrouve d’abord les schémas de chiffrement à clé publique, qui permettent par exemple à tout le monde d’envoyer un message chiffré à une personne qui sera la seule à pouvoir les lire, puis la génération de signatures électroniques, qui authentifient un acte ou un document. Le NIST a annoncé, le 5 juillet, les résultats du troisième round, où l’on retrouve quatre candidats et huit projets alternatifs. Parmi les algorithmes retenus, CRYSTALS-KYBER est le seul à traiter du chiffrement à clé publique, tandis que CRYSTALS-DILITHIUM, SPHINCS+ et FALCON, auquel participe Pierre-Alain Fouque, sont dédiés à la génération de signatures électroniques.

« L’idée n’est pas de ne garder qu’une seule solution, bien au contraire, insiste Pierre-Alain Fouque. Les quatre schémas actuellement retenus seront standardisés, et certains candidats alternatifs pourraient les rejoindre plus tard. C’est une manière de ne pas mettre tous nos œufs dans le même panier. De même, si trois des projets déjà retenus touchent à la cryptographie à base de réseaux euclidiens, le quatrième round a aussi sollicité des schémas basés sur d’autres hypothèses de sécurité. »

La cryptographie basée sur les réseaux euclidiens utilise comme problème le fait de trouver le plus court vecteur non nul entre deux points, placés sur une grille dans un espace aux très nombreuses dimensions. Basé sur ce principe, FALCON présente plusieurs avantages : sa signature tient par exemple en 666 octets, ce qui est très peu. Cela lui garantit une meilleure sécurité sur les réseaux car la signature peut être envoyée en une seule fois, alors que chez les autres elle doit être découpée entre plusieurs paquets IP. FALCON est également adapté aux QR codes, qui contiennent un maximum de 4000 octets et qui ne peuvent donc pas se permettre d’en consacrer plus de la moitié à la seule cryptographie. Enfin, il convient aussi aux mises à jour de matériel informatique, dont les parties ne disposent individuellement pas forcément d’assez de mémoire et de puissance pour vérifier l’intégrité de leurs logiciels.

En plus de la complémentarité des solutions retenues par le NIST, la prévalence de la recherche française est frappante. Trois des quatre projets et deux des huit propositions alternatives comportent ainsi des scientifiques formés ou travaillant en France.

« C’est une marque de l’excellence de la recherche française, un succès dû à la présence de plusieurs écoles très vivantes, énumère Pierre-Alain Fouque. » Un écosystème également alimenté par des initiatives comme le Programme et équipement prioritaire de recherche (PEPR) dédié aux technologies quantiques, inauguré le 4 mars par le CNRS, Inria et le CEA. On y retrouve d’ailleurs le projet PQ-TLS1 , porté par Pierre-Alain Fouque.

« Treize équipes de chercheurs en cryptographie sont impliquées dans PQ-TLS, explique Pierre-Alain Fouque. On retrouve deux objectifs. Le premier, plus théorique, consiste à soutenir la recherche fondamentale des différentes équipes françaises qui travaillent sur de nouveaux standards. D’un point de vue pratique, nous apportons également un transfert de connaissances pour les professionnels de la cryptographie qui en maîtrisent les principes classiques, mais seraient moins à l’aise avec le tournant quantique que la discipline est en train d’opérer. »

• 1Post quantum transport layer security.