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.
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.
Commentaires (14)
#1
Passionnant…même si je n’y bite pas grand chose pour l’instant.
#2
Le plus dur, je trouve, c’est l’intrication quantique.
Et pourtant, me suis taper plusieurs vidéos sur la mécanique quantique… Mais ça a du mal
#2.1
Oui c’est fascinant que deux molécules distantes puissent refléter un état identique à l’autre bout du cosmos sans transmission de données.
#2.2
Oui, mais toujours sans transfert d’information heureusement
#2.3
L’intrication quantique ça ne fonctionnera jamais en dehors des labos pour la bonne et simple raison qu’au moment de lire le résultat des calculs fait par le processeurs quantique cela casse l’intrications quantiques qui est à refaire, par analogie ça revient presque à casser le processeurs à chaque fois que tu lis les résultats du travail de ce dernier.
Ça doit prendre pas mal de temps de refaire une intrications quantique.
Personnellement je vois plus l’intrication quantique comme une unité de calcul spécial que comme un vrai processeur indépendant, à la limite un processeurs quantique est une partie d’un CPU normal au quel on aurait adjoint de 1 à x unité de n Qbits.
#3
Je ne comprend pas ce passage.
Le post quantique permet de casser les algorithmes asymétriques (comme expliqué dans le paragraphe juste avant avec l’algorithme de Shor), et permet de casser les algorithmes symétriques (grâce à la parallélisation extrême, comme expliqué 2 paragraphes avant).
En quoi doubler la clé d’un algorithme symétrique protégerait de la parallélisation extrême ?
#4
Je pensais qu’il existait déjà des algorithmes discrets ne se basant pas sur la factorisation (Diffi-Hellman, Elliptic Curve). On estime que ceux-là serait potentiellement vulnérables? Peut être qu’ils sont trop lents également.
#4.1
Pour ces algorithmes, c’est la gestion des clés qui les rend peu pratiques à grande échelle. NXI a publié un article sur le chiffrement de Vernam qui illustre cette difficulté.
#4.2
Les algorithmes mentionnées (Diffie-Hellman et la crypto utilisant les courbes elliptiques) sont aussi pratiques à utiliser que le RSA vis-à-vis de l’échange de clé.
Diffie-Hellman est justement un algorithme d’échanges d’informations pour se mettre d’accord sur un secret commun au travers d’un canal non sécurisé (comme praticitié d’échange de clé, je crois qu’il n’y a pas mieux :P).
Et les courbes elliptiques utilisent des paires de clés publique/privée comme en RSA, donc aussi facile à partager.
Ces algos sont basés sur la difficultés de calculer un logarithme discret qui semble être facilement résolvable via une variante de l’algorithme de Shor. Donc on est pas forcément mieux lotis via ces algos là.
Je suis pas un expert, donc je vais pas rentrer dans les détails histoire de pas dire de bêtise, mais il y a moyen de trouver des infos sur le net ;)
#5
#6
Fais les stocks, y a régulièrement des news sur le sujet ici, avec chaque fois les mêmes tentatives d’explications aux mêmes novices qui n’y comprennent toujours rien (et dont je fais partie je précise).
Le pire c’est que depuis toutes ces années qu’on en parle, je n’arrive même pas à déterminer s’il y a eu des progrès de faits vers quelque chose de concret. Et je trouve qu’il y a beaucoup d’annonces opaques dont on ne sait rien du concret derrière.
#6.1
y aura de vrai progrès quand au choix:
1/- soit lire les données ne casse plus l’intrications ce qui de facto revient quasiment à casser le processeurs quantique.
ou
2/- les processeurs Quantiques bien que Quantiques n’emploi plus l’intrications pour fonctionner.
parce que bon depuis un moment ils ont démontre que monté en puissance avec 64 Qbit et plus ils savent faire, mais tant que l’intrication quantique est casser au moment de lire les résultats de calcul du processeur quantique et bien c’est juste un joujou de laboratoire et rien d’autre !!!
#7
Et quelque chose permet de penser que cette limitation serait rapidement dépassée ? Parce que sinon, je trouve que les annonces de type “on sait faire” ou “on a atteint la suprématie” ne sont que du vent, on n’a pas l’habitude d’utiliser des processeurs jetables en informatique.
Ca n’a pas l’air d’être la piste privilégiée.
Et donc, au final, si j’ai suffisamment d’argent à y mettre, est-ce qu’aujourd’hui quelqu’un est en mesure de casser ma clé RSA (ou autre algo de même difficulté) en un temps dérisoire avec une machine quantique, oui ou non ? Et ce “ou” n’est pas quantique, c’est oui ou non exclusivement.
#8
La parallélisation extrême pour factoriser un nombre, pas pour n’importe quelle algo ou calcul !
Les algo asysmétriques ont souvent une relation entre clé publique et clé privée. Cette relation se base souvent sur les nombres premiers et la factorisation d’un message en t-uples de nombres premiers.