Cryptographie

Ordinateur quantique : quatre algorithmes conçus pour résister à sa menace

Date:
Mis à jour le 22/09/2022
Début juillet 2022, le NIST dévoilait les quatre algorithmes qui seront normalisés pour se prémunir contre les attaques des ordinateurs quantiques. Les chercheurs Damien Stehlé (équipe-projet AriC) et Pierre-Alain Fouque (équipe-projet CAPSULE), coauteurs respectivement de CRYSTALS-Kyber et CRYSTALS-Dilithium pour l’un et FALCON pour le second, reviennent sur l’origine et l’importance de cette certification.
quantique
© Flickr / Photo Pierre Metivier

 

Le NIST (National Institute of Standards and Technology) lançait en juillet 2016 un appel international à contributions afin d’identifier les meilleurs candidats aux futurs standards de cryptographie postquantique, c’est-à-dire résistant aux ordinateurs quantiques de demain. Après six ans de compétition, l’agence gouvernementale américaine présentait ainsi début juillet le premier groupe d'algorithmes cryptographiques conçus pour résister à la menace d'un futur ordinateur quantique.

Il s’agit de CRYSTALS-Kyber pour le chiffrement à clé publique et les algorithmes d’établissement de clé, et de CRYSTALS-Dilithium, FALCON et SPHINCS+ pour la génération de signatures électroniques.

Pourquoi est-ce une étape importante dans la sécurisation de nos données ?

En 1994, le mathématicien américain Peter Shor secoue le monde de la sécurité informatique en découvrant une technique (par la suite baptisée "algorithme de Shor") capable de réduire considérablement le temps nécessaire pour résoudre les problèmes difficiles sur lesquels repose la sécurité de la cryptographie à clé publique, permettant ainsi de casser efficacement des codes qui résistent généralement des milliers d'années. Ainsi, tous les dispositifs utilisant les systèmes RSA ou les courbes elliptiques deviendraient cassables par un tiers si l'algorithme de Shor était un jour programmé dans un calculateur quantique.

Depuis lors, nombreux sont les scientifiques qui ont prédit l’arrivée plus ou moins lointaine d’un ordinateur quantique capable de casser un protocole cryptographique dans un délai raisonnable. Cependant, les progrès rapides de la technologie quantique rendent aujourd’hui ces machines beaucoup plus proches de nous qu'elles ne l'étaient au milieu des années quatre-vingt-dix, rapprochant les protocoles cryptographiques actuels de leur date d'expiration. En d’autres termes : ce qui est existant aujourd’hui sera cassé par un ordinateur quantique suffisamment puissant.

« Nous en sommes encore loin, les ordinateurs quantiques actuels sont peu expressifs. Ils arrivent à faire mieux que les ordinateurs classiques, mais seulement pour un problème donné, construit spécifiquement. Mais il est possible qu’on construise un ordinateur quantique efficace dans quelques années », explique Pierre-Alain Fouque, professeur à l’Université de Rennes 1, membre de l’IRISA (Inria/CNRS/Université de Rennes 1) et coauteur de FALCON.

« Il est important de prendre les devants car la transition risque d’être très longue, puisque l’on parle de l’intégralité des logiciels qui chiffrent ou qui signent. Il va falloir des années avant que tout le monde ait franchi le pas. Par ailleurs, la menace la plus importante actuellement consiste à retenir les informations qui transitent aujourd’hui pour les déchiffrer rapidement quand on aura un ordinateur quantique », ajoute Damien Stehlé, professeur à l’ENS de Lyon, membre du LIP (Inria/CNRS/ENS de Lyon/Université Claude Bernard Lyon 1) et coauteur de CRYSTALS-Kyber et CRYSTALS-Dilithium.

Des avancées qui ont poussé la NSA à annoncer, en 2015, qu’il devenait urgent de sérieusement considérer les alternatives à la cryptographie actuelle, puis le NIST, en 2016, à donner le coup d'envoi d'un concours visant à développer de tels algorithmes "résistants au quantique". Au total, ce sont près de 70 soumissions au concours qu’a reçues le NIST, pour quatre retenues actuellement.

Des alternatives aux schémas existants

Sur ces quatre algorithmes sélectionnés, trois utilisent les réseaux euclidiens, dont l’utilisation en cryptographie a réellement débuté au milieu des années quatre-vingt-dix (dans les années quatre-vingts, les réseaux étaient utilisés en cryptanalyse (pour casser des cryptosystèmes). Les cryptographes s’étaient alors intéressés à fournir des alternatives aux mécanismes RSA reposant sur des problèmes difficiles pour l’adversaire (code correcteur d’erreur, résolution de systèmes à plusieurs variables, réseaux euclidiens). Ces mécanismes alternatifs, ont continué une existence parallèle à RSA ou aux réseaux elliptiques sans qu’on s’intéresse vraiment à leur implémentation.

« Ce n’était pas un sujet "mainstream" à l’époque, puis dans les années 2000 il y a eu des travaux fondamentaux sur le sujet, et ça a vraiment commencé en 2005. À ce moment-là, je terminais ma thèse et je m’y suis intéressé quand les gros résultats fondateurs commençaient à sortir. Ça n’était pas du tout pratique à l’époque, ça n’existait que sur le papier, mais il y a eu une communauté qui s’est développée autour de ça, les bases se sont établies, et progressivement c’est devenu plus complet », raconte Damien Stehlé.

Une alternative qui se révèle comme ayant de bonnes propriétés. « Les premiers algorithmes présentant une alternative aux mécanismes RSA n’étaient pas exploitables facilement, donc il y a eu pas mal de recherches pour les rendre utilisables. Les messages sont encore un petit peu longs mais on a aujourd’hui de vraies alternatives par rapport à la cryptographie actuellement utilisée », indique Pierre-Alain Fouque.

Pourquoi le NIST a choisi deux schémas de signature basés sur les réseaux euclidiens ?

Chacun des deux schémas de signature sélectionnés a des avantages et des inconvénients. Il n’existe aujourd’hui aucun schéma qui peut être bon à tous les niveaux. Il est donc nécessaire d’offrir des solutions conçues pour différentes situations.

Vers une utilisation concrète

Les quatre protocoles cryptographiques sélectionnés par le NIST feront désormais partie de la norme cryptographique postquantique du NIST, qui devrait être finalisée dans environ deux ans. « C’est l’aboutissement d’années de travail, et ça représente un énorme effort collectif international. Faire de la recherche théorique est toujours plaisant, c’est pour cela qu’on a signé, mais quand on a l’occasion que ce soit utile, c’est satisfaisant. Une partie du travail dans les deux prochaines années va être de décrire très précisément comment fonctionnent ces algorithmes, point par point », explique Damien Stehlé.

« C’est des recherches qui ont une origine très théorique, proches à la fois de la théorie de la complexité et de la théorie algébrique des nombres. Le fait qu’elles aient fini par aboutir à des choses très concrètes est une très belle reconnaissance. Pour les auteurs évidemment, et pour tous ceux qui ont contribué dans ce domaine », ajoute Pierre-Alain Fouque.

En parallèle, quatre autres algorithmes de chiffrement sont à l'étude pour être inclus dans la norme, et le NIST prévoit d'annoncer les lauréats de ce tour à une date ultérieure. Le NIST annonce ses choix en deux étapes en raison de la nécessité de disposer d'une solide variété d'outils de défense. Ainsi, le NIST envisage que plus d'un algorithme soit normalisé pour chaque cas d'utilisation, au cas où l'un d'eux s'avérerait vulnérable.

« Chiffrement et signature sont la colonne vertébrale de la cryptographie, c’est essentiel. Le prochain gros objectif de cette communauté est d’avoir des protocoles plus avancés que chiffrement et signature et suffisamment optimisés pour être concrets et déployables. », conclut Damien Stehlé.

Zoom sur les collaborations derrière les quatre schémas standardisés par le NIST

Les protocoles CRYSTALS sont issus d’une coopération internationale entre dix chercheurs de ARM Limited, NXP Semiconductors, IBM Research Zurich, CWI Amsterdam, MPI-SP, SRI International, l’université de la Ruhr à Bochum (Allemagne), l’université de Waterloo (Canada), l’université Radboud de Nimègue (Pays-Bas) et l’ENS de Lyon.

Falcon a été créé par dix scientifiques de l’université de Rennes, l’université Brown (États-Unis), IBM Research Zurich, NCC Group, Thales et OnBoard Security.

SPHINCS+ a été conçu par dix-neuf chercheurs issus de l’université de technologie d'Eindhoven (Pays-Bas), l’université de l’Illinois à Chicago (États-Unis), l’université de la Ruhr à Bochum (Allemagne), l'Academia Sinica (Chine), la Katholieke Universiteit Leuven (Belgique), l’université technique de Graz (Autriche), genua GmbH, Cisco Systems, Google, InfoSec Global, Infineon Technologies, l’université du Danemark du Sud, l’université Radboud de Nimègue (Pays-Bas), MPI-SP et Cloudflare.

« Les quatre algorithmes sélectionnés et les quatre algorithmes retenus pour le prolongement de la campagne de standardisation résultent de coopérations internationales. Mais la liste de leurs coauteurs et leurs affiliations n’en illustrent pas moins de manière frappante l’extraordinaire vitalité de la recherche française et de la recherche européenne en cryptographie », indique l’ANSSI, dans un article consacré à la sélection par le NIST des quatre schémas.

Un avis que partage Harold Ollivier, directeur du programme QuantumTech@Inria« La compétition du NIST illustre de façon très claire la nécessité d'investir dans la recherche amont et sur le long terme: les techniques utilisées par ces nouveaux algorithmes ont été découvertes sans relation avec l'ordinateur quantique mais sont désormais incontournables pour la sécurisation des données. Pour cela il a fallu soutenir un effort dont les applications n'étaient pas encore prévisibles. C'est en partie ce que l'on cherche à faire avec le programme QuantumTech@Inria en recrutant de façon volontariste d'excellents scientifiques experts dans le traitement quantique de l'information. »