L’informatique quantique, on en parle depuis des années en agitant le spectre d’une chute des systèmes de chiffrement. Ce n’est qu’en partie vrai. Dans tous les cas, les centres de recherche planchent sur le (post)quantique depuis des années. Une étape vient d’être franchie avec la sélection par le NIST de quatre algorithmes. 

Deux clés de la quantique : superposition et l’intrication

Avant d’entrer dans le vif du sujet, un rappel important sur l’informatique quantique. Pour faire simple, les bits classiques (qui valent 0 ou 1) sont remplacés par des qubits (ou bits quantiques) qui « peuvent simultanément prendre les valeurs 0 et 1 », explique le CNRS.  On parle de superposition quantique, et il faudra accepter cette notion afin de continuer… 

Autre point très important : « lorsque deux qubits interagissent, leurs états physiques "s’enchevêtrent", si bien que les deux systèmes ne peuvent plus être décrits de façon indépendante – on parle d’états intriqués ». Grâce à la superposition et l’intrication, « un ordinateur quantique peut en théorie avoir accès à la totalité des résultats possibles d’un calcul en une seule étape, là où un ordinateur classique doit traiter l’information de façon séquentielle, un résultat après l’autre ». Une machine quantique propose donc un parallélisme poussé à son paroxysme.

Avec l’algorithme de Shor (1994), la réalité rejoint la fiction

C’est la théorie de fonctionnement d’une machine quantique, encore faut-il disposer d’algorithmes capables d’exploiter cette nouvelle manière de travailler. Là encore, la « révolution » n’est pas nouvelle : en 1994, le mathématicien Peter Shor présente un algorithme éponyme capable de factoriser n’importe quel nombre.

Et alors me direz-vous ? Les conséquences sont très importantes puisque cet algorithme peut en théorie « casser la plupart des systèmes de cryptographie actuels, du chiffrement de nos transactions bancaires aux codages permettant d’échanger des secrets d’État, qui reposent précisément sur l’explosion en temps de calcul de la factorisation pour des nombres de plus en plus grands ».

De plusieurs milliards d’années à… quelques minutes

Alors qu’un ordinateur classique aurait besoin de plusieurs milliards d’années pour factoriser un grand nombre, cela ne prendrait que quelques minutes à une machine quantique. Nous n’en sommes pas encore là, et les machines connues ne disposent pas de suffisamment de qubits pour être inquiétantes. 

Si la quantique peut se révéler très utile pour les algorithmes asymétriques (c’est-à-dire avec une clé publique et une clé privée) reposant sur la factorisation – RSA par exemple –, ce n’est pas le cas avec les algorithmes symétriques (avec une clé secrète). Dans ce cas, l’impact d’un ordinateur quantique est limité « puisqu’il suffit de doubler la taille des clefs en cryptographie symétrique », affirme Bernard Ourghanlian, directeur technique de Microsoft France. Nous avions évoqué ce sujet dans notre premier magazine, désormais téléchargeable gratuitement.

On parle parfois de suprématie quantique, qui correspond au moment où les machines quantiques prendront le dessus sur les autres. Google affirme avoir atteint cette barrière, tandis qu’IBM réfute. Suprématie ou pas, ce n’est pas le plus important : « on est à un point de bifurcation » et savoir « si on a passé le point de bifurcation ou pas exactement, ce n’est pas là qu’est le débat », expliquait récemment Philippe Chomaz, directeur scientifique à la direction de la recherche fondamentale du CEA.

• « Suprématie quantique » chez Google ? IBM réfute, Intel regarde ailleurs
• Suprématie quantique : « on est à un point de bifurcation »

Le post-quantique se prépare depuis des années

Puisque cette nouvelle technologie a déjà plusieurs dizaines d’années, le monde a largement eu le temps de se préparer. Dès 2016, Google par exemple a commencé ses tests sur des algorithmes post-quantique, c’est-à-dire lorsque les ordinateurs quantiques seront arrivés pour de bon. Microsoft s’est aussi lancée il y a plusieurs années. En France, le Plan Quantique prévoit 150 millions d’euros dédiés à la cryptographie post-quantique.

• Les détails du Plan Quantique : 1,8 milliard d’euros, un « ordinateur hybride » à l’horizon 2023

Le CNRS rappelle que l'objectif de la cryptographie post-quantique est non seulement de développer des systèmes résistants aussi bien aux ordinateurs quantiques que classiques, mais aussi « pouvant interagir avec les protocoles et réseaux de communication existants ».

Dans tous les cas, le temps joue contre nous. Peu importe si un ordinateur quantique arrive dans une semaine ou  dix ans, des acteurs malveillants et/ou des services de renseignement n’attendent pas pour collecter et stocker des données, en vue de les décrypter un jour à l'aide d'ordinateurs quantiques.

Quatre algorithmes sélectionnés par le NIST

C’est dans ce flou artistique que le National Institute of Standards and Technology (NIST), du département américain du Commerce, vient d'annoncer (comme prévu) les quatre premiers algorithmes qui feront partie de la norme cryptographique post-quantique du NIST. Elle « devrait être finalisée dans environ deux ans ». 

C’est l’occasion pour l’INS2I (institut des sciences de l'information et de leurs interactions) du CNRS de se mettre en avant : « Trois des quatre algorithmes sélectionnés […] ont reçu des contributions de laboratoires rattachés à l’INS2I, et une nouvelle phase de soumission (round 4) implique plusieurs autres laboratoires du CNRS ».

L'annonce fait suite à une initiative lancée en 2016, après que le NIST avait appelé les cryptographes du monde à concevoir puis vérifier des méthodes de chiffrement « capables de résister à une attaque d'un futur ordinateur quantique plus puissant que les machines relativement limitées disponibles aujourd'hui ».

Voici CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON et SPHINCS+. 

« Pour le chiffrement à clé publique et les algorithmes d’établissement de clé, le seul algorithme retenu est CRYSTALS-KYBER », indique le CNRS. « Parmi ses avantages figurent des clés de chiffrement relativement petites que deux parties peuvent échanger facilement, ainsi que sa rapidité d'exécution », ajoute le NIST. 

Pour les signatures numériques, utilisées lorsque nous devons vérifier des identités lors d'une transaction numérique ou signer un document à distance, le NIST a sélectionné trois algorithmes : CRYSTALS-Dilithium, FALCON et SPHINCS+. 

Les examinateurs ont noté la grande efficacité des deux premiers, et le NIST recommande CRYSTALS-Dilithium comme algorithme principal, avec FALCON pour les applications qui nécessitent des signatures plus petites que celles que Dilithium peut fournir. Le troisième, SPHINCS+, « est un peu plus imposant et plus lent que les deux autres », mais a été retenu car basé sur une approche mathématique différente.

Quatre algorithmes supplémentaires sont à l'étude pour inclusion dans la norme, mais le NIST prévoit d'annoncer les finalistes de ce tour à une date ultérieure.

Un accord entre CNRS, NIST et l’Université de Limoges

Enfin, le Centre national pour la recherche scientifique annonce un accord de licence entre le NIST, le CNRS et l’Université de Limoges. En effet, « deux des solutions finalistes pourraient s’appuyer sur des familles de brevets déposées dès 2010 par les enseignants-chercheurs Philippe Gaborit et Carlos Aguilar-Melchor (Université de Limoges et laboratoire CNRS Xlim), et détenues conjointement par le CNRS et l’Université de Limoges ». 

Le Centre s’explique : 

« le CNRS et l’Université de Limoges, soutenus par France Brevets, se sont entendus sur les termes d’un accord de licence dont les parties prenantes se félicitent. L’accord permet ainsi de valoriser une propriété intellectuelle issue des résultats de la recherche publique française.

Grâce à l'accord de licence annoncé entre le NIST, le CNRS et l'Université de Limoges, les opérateurs et les utilisateurs finaux des normes cryptographiques dérivées des algorithmes PQC sélectionnés n'auront pas besoin d’obtenir une licence distincte sur cette famille de brevets du CNRS. Cela favorisera l'adoption rapide et généralisée de ces normes cryptographiques, un objectif commun du NIST et du CNRS ».

Dans tous les cas, l’aventure de l’informatique quantique et des algorithmes post-quantiques ne fait que commencer. Le nombre de qubits augmente régulièrement et on atteindra à coup sûr la suprématie un jour… reste à savoir quand.