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

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.

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.

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.

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é.