Shor et la signature quantique

« ORDINATEURS QUANTIQUES : LA FIN DE TOUS LES SECRETS ? » lut Uwe à voix haute. « Les experts mettent en garde : les futures machines quantiques pourraient casser le chiffrement des banques, des administrations et des messageries. »

« Il y a un point d’interrogation », dit Sabine sans lever les yeux de son propre journal. « Quand il y a un point d’interrogation dans le titre, la réponse est la plupart du temps non. »

« Et sinon ? »

« Sinon, ce sera dans le journal la semaine prochaine, sans point d’interrogation. »

L’oncle Herbert était assis à la table du petit-déjeuner. Depuis quelque temps, il venait le samedi, soi-disant pour les petits pains de Gisela, en réalité parce que, depuis l’histoire du vieil ordinateur portable à la cave, il consultait chaque matin le cours du bitcoin et avait besoin de quelqu’un à qui annoncer le chiffre.

« Les banques », dit-il. « Les messageries. Et mon argent d’internet, alors ? »

« Ce n’est pas écrit », dit Uwe.

« Alors ce sera écrit la semaine prochaine », dit Herbert d’un air sombre. « KevIn. Franchement. Un frigo comme ça, il peut voler mon argent ? »

La lumière bleue pulsa. « Pas aujourd’hui, Herbert. »

« Et demain ? »

« Demain non plus. »

« Et après-demain ? »

« Là, ça devient intéressant. »

Herbert posa son petit pain. D’habitude, il ne faisait ça que pour les décès et les séances de tirs au but.

Un homme nommé Shor

« Commençons par le commencement », dit KevIn. « Vous vous souvenez des nombres premiers ? M. Demir et le message aux extraterrestres ? »

« 1679 », dit aussitôt Tobi. « 23 fois 73. »

« Exactement. Multiplier, c’est facile. 23 fois 73, ça se calcule sur un sous-bock. Mais si je te donne seulement 1679 et que je te demande quels sont les deux nombres premiers cachés dedans, il faut essayer. Avec 1679, ça va encore. Avec un nombre de six cents chiffres, un ordinateur normal essaie plus longtemps que l’âge de l’univers. »

« Et c’est là-dessus que repose RSA », dit Tobi. « On l’a eu. »

« C’est là-dessus que repose RSA. La clé publique contient le produit, la clé privée dépend des deux facteurs¹. Tant que personne ne sait décomposer le grand nombre, c’est sûr. »

« Et maintenant arrive le frigo », dit Uwe.

« Maintenant arrive Peter Shor. Un mathématicien américain. En 1994, il a montré qu’un ordinateur quantique suffisamment grand pourrait décomposer de grands nombres beaucoup plus vite que n’importe quelle méthode connue sur des ordinateurs normaux². À l’époque, il n’existait même pas encore d’ordinateur quantique. Shor a donc écrit la recette avant que quiconque ait une cuisinière. »

« Comme maman », dit Uwe. « Elle aussi, elle écrit des recettes pour des trucs qu’on n’a pas à la maison. »

« J’écris des listes de courses », dit Sabine. « C’est la différence entre planifier et espérer. »

« Il fait comment ? » demanda Tobi. « Le Shor. Il essaie tous les nombres en même temps ? »

« Non », dirent KevIn et Tobi en même temps, parce que Tobi regretta sa propre question à la seconde même.

« Très bien », dit KevIn. « Le chapitre 17 a porté ses fruits. Un ordinateur quantique n’essaie pas simplement tout. Shor a trouvé un détour. Il transforme la question “Quels facteurs ?” en la question “Quel rythme ?”. »

« Un rythme ? » demanda Gisela.

« Imagine que tu prends un nombre et que tu le multiplies encore et encore par lui-même, mais qu’à chaque fois, tu ne regardes que le reste qui subsiste quand on divise par le grand nombre. Au bout d’un moment, les restes se répètent. Comme un motif au tricot. Deux mailles à l’endroit, deux à l’envers, une torsade, et on recommence. »

« Ça s’appelle un rapport », dit Gisela. « C’est le mot, en tricot. »

« Merci. L’astuce de Shor, c’est que si l’on connaît la longueur de ce rapport, on peut calculer les facteurs avec un peu de maths de lycée. Et trouver des rythmes, les ordinateurs quantiques savent bien le faire. Grâce à l’interférence. Les possibilités qui ne collent pas au rythme s’annulent mutuellement. Les bonnes se renforcent. Comme des vagues à la piscine, mais avec des mathématiques. »

« Comme quand on se balance bras dessus, bras dessous en chantant », dit Gisela. « Si quelqu’un se balance à contretemps, on le remarque tout de suite. Et au bout d’un moment, il se balance comme il faut, parce qu’on l’entraîne. »

KevIn réfléchit une demi-seconde. « Ce n’est pas tout à fait exact. Mais c’est plus beau qu’exact. »

Tout ce qui vacille

« Donc RSA est fichu », dit Herbert. « Et mon argent ? »

« C’est encore pire », dit KevIn. « Et en même temps, moins grave. Je vais expliquer les deux. »

« Le pire d’abord », dit Herbert. « Le bon, de toute façon, je n’y crois pas. »

« La méthode de Shor ne fonctionne pas seulement contre RSA. Sous une forme modifiée, elle fonctionne aussi contre ce qu’on appelle les courbes elliptiques³. C’est l’autre grande famille de procédés à clé publique, qu’on trouve aujourd’hui presque partout. Y compris dans Ed25519⁴, le procédé de signature que je vous ai expliqué pour l’avis de Gisela sur sa kiné. Et aussi dans les signatures avec lesquelles on signe les virements en bitcoin. »

Herbert pâlit. « Je le savais. »

« Maintenant, le moins grave. Pour casser RSA ou ces courbes à la taille utilisée aujourd’hui, il faudrait un ordinateur quantique doté d’énormément de qubits corrigés des erreurs, c’est-à-dire logiques⁵. Vous avez vu à l’institut à quel point un seul qubit logique fiable est déjà difficile. Une telle machine n’existe pas aujourd’hui. Personne ne sait quand elle existera. Les estimations des spécialistes divergent fortement⁶. Certains disent dans dix, quinze ans, d’autres plus tard, d’autres encore se méfient de tout chiffre. »

« Et toi, tu dis quoi ? » demanda Uwe.

« Je dis : je ne sais pas. Et je suis très fier de pouvoir le dire sans citer un livre du Dr Sauerbier-Klenk. »

« Et mon argent ? » demanda Herbert pour la troisième fois.

« Le bitcoin devra un jour passer à des procédés de signature résistants au quantique. On en discute déjà dans la communauté bitcoin⁷. C’est compliqué, parce qu’avec le bitcoin, tout le monde doit se mettre d’accord et personne n’est le chef. »

« Comme au club de quilles », dit Gisela.

« Chez nous, c’est Brigitte, le chef », dit Herbert.

« Brigitte croit qu’elle est le chef », dit Gisela. « Ce n’est pas pareil. »

Récolter et attendre

Entre-temps, Sabine avait replié son journal. « Si cette machine n’existe pas encore, pourquoi est-ce qu’on en parle maintenant dans le journal ? »

« Parce que certains secrets doivent tenir longtemps », dit KevIn. « Il existe une expression pour ça : “Harvest now, decrypt later.” Récolter maintenant, déchiffrer plus tard⁸. »

« Ça fait jardin ouvrier », dit Uwe.

« Un peu. Imaginez que quelqu’un intercepte aujourd’hui des messages chiffrés. Il ne peut pas les lire. Mais il les stocke. Les disques durs ne coûtent rien. Et dans quinze ans, quand il aura un gros ordinateur quantique, il les ressortira de la cave et les cassera. »

« Comme tante Erna avec ses bocaux », dit Gisela. « Elle mettait en conserve des choses que personne ne voulait manger. Et dix ans plus tard, elle les a quand même ouverts. »

« Et alors ? »

« Personne ne les a mangées non plus. Mais elle les a ouverts. »

« Pour la plupart des messages, ça n’a aucune importance », dit KevIn. « Qui se souciera dans quinze ans qu’Uwe a commandé des petits pains aujourd’hui ? Mais les secrets d’État, les dossiers médicaux, les secrets d’affaires doivent parfois rester secrets pendant des décennies. C’est pour ça qu’on change maintenant. Pas seulement quand la machine sera prête. »

« Et les signatures ? » demanda Tobi. « On peut les récolter aussi ? »

« Bonne question. » KevIn avait l’air ravi. « Pour les signatures, le danger est différent. Une signature n’est pas secrète. Le problème serait le suivant : si quelqu’un, avec un gros ordinateur quantique, parvient à calculer la clé privée à partir de la clé publique, il peut falsifier de nouvelles signatures. Il pourrait donc prétendre qu’un document a toujours été signé ainsi, alors qu’il ne l’a fait qu’hier. »

« Ce serait comme avec Marlies », dit Gisela. « À l’époque, elle avait pris la liste des quilles et… »

« Maman », dit Uwe.

« Je ne dis rien. Je dis juste que ce serait comme ça. »

Treillis et bruit

« Et qu’est-ce qu’on fait, maintenant ? » demanda Sabine. « On ne peut quand même pas tout réécrire sur papier. »

« Toi, si », dit Uwe.

« On prend d’autres mathématiques », dit KevIn. « Des mathématiques pour lesquelles même Shor n’a pas trouvé d’astuce. Ça s’appelle la cryptographie post-quantique. L’agence américaine de normalisation, le NIST, a organisé pour cela un concours public, pendant de nombreuses années, avec des spécialistes du monde entier. Tout le monde avait le droit d’essayer de casser les propositions. Certaines ont effectivement été cassées, et même avec des ordinateurs tout à fait normaux⁹. En août 2024, le NIST a publié les trois premières normes¹⁰. »

« Elles s’appellent comment ? » demanda Tobi.

« ML-KEM¹¹ pour l’échange de clés. ML-DSA¹² et SLH-DSA¹³ pour les signatures. »

« On dirait des plaques d’immatriculation allemandes », dit Uwe. « ML-KEM. Mülheim, Kempen. »

« Et puis il y a encore FN-DSA », dit KevIn. « Un procédé de signature qui a lui aussi été retenu. Il a été développé sous le nom de Falcon, et le NIST le normalise sous le nom de FN-DSA¹⁴. Ses signatures sont relativement petites. C’est pratique quand on veut en stocker énormément. »

« Et elles reposent sur quoi ? » demanda Tobi. « Si ce n’est pas sur des nombres premiers ? »

« La plupart sur des réseaux. Des treillis de points, si tu veux. »

« Des treillis ? » demanda Gisela. « Comme sur la clôture du jardin ? »

« Presque. Imagine un immense treillis de points. Pas plat comme une clôture, mais dans des centaines de directions, de travers et déformé. Je te donne un point quelque part dans l’espace, qui n’est pas exactement sur le treillis, mais un peu à côté, parce que j’y ai volontairement mélangé du bruit¹⁵. Et tu dois trouver le vrai point du treillis le plus proche. »

« En deux directions, je sais faire », dit Tobi. « C’est du papier quadrillé. »

« En deux directions, oui. En des centaines de directions, d’après les connaissances actuelles, ni un ordinateur normal ni un ordinateur quantique ne trouve le bon point en un temps raisonnable. Mais celui qui possède la clé privée a pour ainsi dire une bonne carte du treillis et le trouve tout de suite. »

Gisela se leva, alla à son panier à tricot et revint avec un pull à moitié fini. « Comme ça ? »

Tout le monde regarda le pull. Il était vert, avait un motif de torsades et, à plusieurs endroits, de petites irrégularités.

« Là, je me suis trompée quelques fois », dit Gisela. « Le soir, devant la télé. Si quelqu’un voit seulement le pull, est-ce qu’il sait comment le motif aurait dû être ? »

« Pour un pull, peut-être », dit KevIn. « Parce que le motif ne va que dans deux directions et que les erreurs sont rares. Mais imagine un pull tricoté dans cinq cents directions, avec une petite erreur dans chaque maille. Et toi seule as le modèle. »

« Cinq cents directions », dit Gisela. « Il me faudrait plus d’aiguilles. »

« C’est l’idée. L’erreur est là exprès. C’est elle, la protection. »

« Alors la liste des quilles de Marlies était fausse exprès, elle aussi », dit Gisela, satisfaite. « Pour la protection. »

« Maman ! »

La question dans la cuisine

L’après-midi, Ayşe Kurt appela pour un rendez-vous. Entre-temps, Gisela avait terminé sa douzième séance, son épaule suivait de nouveau presque tous les mouvements, et ce jour-là, en étendant le linge, elle n’avait pour la première fois pensé à aucune douleur. Elle le dit à Ayşe au téléphone. On entendait qu’Ayşe était ravie.

Après avoir raccroché, Gisela resta un moment assise en silence dans la cuisine. Puis elle dit : « KevIn. Mon avis. Pour Mme Kurt. »

« Celui que tu as déposé cet hiver. À l’accueil, avec le QR code. »

« Celui-là. Il est fichu, lui aussi, maintenant ? Quand les machins quantiques arriveront ? »

« Qu’est-ce que tu entends par fichu ? »

« Que quelqu’un vienne dire qu’il n’est pas de moi. Ou que quelqu’un enlève mes cœurs et en fasse trois. J’en ai mis cinq. Elle mérite cinq. Et ceux de PhysioPremium aimeraient bien qu’elle en ait moins. »

Avant que KevIn ait pu répondre, Uwe entra, avec un café et la grande certitude d’un homme qui a lu le journal le matin.

« Maman, tu n’as pas à t’inquiéter », dit-il. « McGesund fait des signatures quantiques, là. »

Il y eut une pause. Quelque part entre Dublin et Francfort, un ventilateur tourna un peu plus vite.

« Uwe », dit KevIn aimablement. « Presque. »

« Comment ça, presque ? »

« Ça ne s’appelle pas signature quantique. Chez McGesund, on n’utilise aucun ordinateur quantique. Il n’y a pas de lustre doré à la cave. »

« Pourtant, c’est ce que j’ai lu. »

« Où ? »

Uwe réfléchit. « Dans ma tête, je crois. »

« Les spécialistes disent cryptographie post-quantique », dit KevIn. « Et moi, je préfère dire “résistant au quantique” plutôt que “sûr face au quantique”. Sûr, personne ne peut le promettre, moi non plus. Résistant veut dire : face à tout ce que nous connaissons aujourd’hui, ça tient. Ce sont des mathématiques tout à fait normales sur des ordinateurs tout à fait normaux. Mais elles sont construites de telle sorte que, d’après les connaissances actuelles, même un futur ordinateur quantique ne pourra pas les falsifier. “Post” veut dire après. Pour l’époque d’après. »

« Résistant au quantique », répéta lentement Uwe. « C’est plus dur que signature quantique. »

« C’est malheureusement souvent le cas avec les mots justes. »

Trois serrures sur une porte

« Bon, alors, qu’est-ce qui arrive à mon avis ? » demanda Gisela. « Explique-le de façon que je puisse le raconter à Brigitte. »

« Bien », dit KevIn. « Ton avis a trois couches de protection. Imagine une porte avec trois serrures. »

« Comme chez Herbert », dit Uwe. « Lui aussi, il a trois serrures. Et personne ne lui vole rien. Parce qu’il n’a rien. »

« Je t’entends », dit Herbert depuis le salon.

« La première serrure, c’est la signature classique. Ed25519. Tu la connais déjà. Elle atteste que l’avis a été créé par cette voie, avec le QR code au cabinet, et que pas une lettre n’a été modifiée depuis. Si quelqu’un transforme tes cinq étoiles en trois, la signature ne correspond plus. Quiconque vérifie s’en aperçoit. »

« Et ça, l’ordinateur quantique peut le casser. »

« Un jour, peut-être. C’est pour ça qu’il y a la deuxième serrure, et c’est une serrure double. En plus de la signature classique, chaque avis reçoit deux signatures résistantes au quantique. L’une avec FN-DSA, le procédé à treillis aux petites signatures. Et l’une avec ML-DSA, que le NIST a publié en août 2024 comme norme FIPS 204. Si un jour quelqu’un casse Ed25519, il restera toujours deux signatures qui, d’après tout ce qu’on sait aujourd’hui, résistent même à un ordinateur quantique. »

« Deux ? » demanda Gisela. « Une ne suffit pas ? »

« Les deux procédés sont encore jeunes », dit KevIn. « Ils reposent certes tous les deux sur des treillis, mais ils sont construits de façon très différente et ont été développés par des équipes de chercheurs différentes. Si l’un d’eux montre un jour une faiblesse, dans les mathématiques ou seulement dans le programme qui le met en œuvre, l’autre continue de tenir. Comme une serrure double avec deux cylindres de fabricants différents. Un cambrioleur devrait casser les deux. Et la serrure classique en plus. »

« Ceinture et bretelles », dit Uwe.

« Exactement. On ne compte pas sur un seul. Si l’on découvre malgré tout une faiblesse dans l’un des procédés, l’autre tient. »

« Et la troisième serrure ? » demanda Gisela.

« La troisième, c’est l’horodatage. Tu te souviens de l’argent d’internet de Herbert ? Et du notaire ? »

« L’empreinte dans le livre de comptes », dit Gisela. « Avec l’arbre généalogique. »

« L’arbre de Merkle, exactement. L’empreinte de ton avis signé et les clés de signature sont ancrées dans la blockchain du bitcoin via OpenTimestamps¹⁶. Il est ainsi établi que ton avis, avec ces signatures, existait au plus tard ce jour-là, cet hiver. »

« Et pourquoi ça aide contre les quanta ? »

« Parce que l’horodatage repose sur des fonctions de hachage. Sur le hachoir. Et contre le hachoir, Shor n’a rien en main. D’après les connaissances actuelles, les ordinateurs quantiques ne peuvent aider que de façon limitée à chercher dans des fonctions de hachage, sans rien de comparable à ce qu’ils font avec RSA. Et voici l’astuce. Imagine que dans vingt ans, quelqu’un construise un gros ordinateur quantique et s’en serve pour falsifier une signature classique Ed25519. Il ne pourra pas prouver que sa falsification figurait déjà dans la blockchain cet hiver. Ton avis, lui, le peut. Il existait de façon prouvée avant qu’il y ait des machines capables de falsifier de telles signatures. »

Gisela réfléchit. « Donc mon avis est plus vieux que le danger. »

« C’est un excellent résumé. »

« Moi aussi », dit Gisela. « Plus vieille que la plupart des dangers. »

Ce qu’elle ne sait pas faire

Tobi était entré dans la cuisine et avait écouté. « Et pourquoi tout ce cirque ? Pour un avis sur une kiné ? Ce n’est pas un secret d’État. »

« Parce qu’il s’agit d’autre chose », dit KevIn. « Tu te souviens de PhysioPremium ? Huit cents avis, qui sonnaient tous comme moi un mauvais jour. »

« Évidemment. »

« Internet se remplit de textes que personne n’a vécus. Des avis, des témoignages, des commentaires, des photos. Je peux écrire ce genre de choses en quelques secondes. Des milliers. Et les prochains modèles de langage apprennent à partir de ces textes. C’est la dérive de la vérité. La copie de la copie de la copie. Dans un monde pareil, une trace qui prouve devient précieuse : ici, un vrai être humain était dans un vrai lieu, ce jour-là, et c’est ceci qu’il a écrit. Pas plus. Mais pas moins non plus. »

« Pas plus ? » demanda Sabine, qui se tenait dans l’encadrement de la porte.

« Pas plus », dit KevIn. « J’y tiens. La meilleure signature du monde ne rend pas une opinion vraie. Si Gisela écrit que Mme Kurt a les meilleures mains de toute la Ruhr, il est prouvé que Gisela a écrit cela, sur place, ce jour-là, sans modification. Que ce soit vrai, aucune mathématique ne le prouve. Gisela peut se tromper. Gisela peut aussi tout simplement bien aimer Mme Kurt. »

« Je l’aime bien », dit Gisela. « Et elle a les meilleures mains de toute la Ruhr. »

« Tu vois, je ne peux pas le vérifier. »

« Mais on ne peut plus faire surgir de nulle part mille avis oursons en gomme », dit lentement Sabine. « Sans que quelqu’un soit venu mille fois. »

« En tout cas, ça devient beaucoup plus difficile. Et si quelqu’un, plus tard, réécrit en douce des avis, en supprime ou en intercale de plus anciens, ça se remarque. Même si c’était McGesund qui essayait. »

« Ils feraient ça ? » demanda Uwe.

« C’est tout l’intérêt d’un notaire », dit KevIn. « On n’a pas besoin de lui faire confiance. On peut vérifier. »

« Et si quelqu’un écrit une méchanceté ? » demanda Gisela. « Avec un nom ? Comme Marlies, à l’époque, sur la serveuse du club-house ? »

« Alors l’avis n’apparaît pas du tout, pour commencer », dit KevIn. « Si quelqu’un écrit “Mme Müller” ou “Dr Meier” dedans, le formulaire l’avertit avant même l’envoi. S’il l’envoie quand même, McGesund le retient, et un être humain le lit avant que qui que ce soit le voie. Ensuite, le nom est noirci. »

Tobi fronça les sourcils. « Tu viens de dire que toute modification casse la signature. »

« C’est le cas. C’est pour ça que rien n’est modifié en douce. McGesund ajoute un deuxième sceau, bien visible : “Modifié par McGesund.” L’ancienne signature reste telle qu’elle était, avec son horodatage. On voit donc que quelqu’un est intervenu, et quand. Mais plus de qui on disait du mal. C’est justement ça qui doit disparaître. »

« Et si quelqu’un râle contre le gouvernement ? » demanda Uwe. « Dans un avis sur une kiné ? »

« Alors il n’est pas publié. La politique n’a rien à faire dans un avis. Il s’agit du cabinet, pas de Berlin. Pareil pour les insultes. Et ce qui passe quand même entre les mailles, n’importe qui peut le signaler, avec son nom et son e-mail. McGesund vérifie alors et le retire. »

Gisela hocha la tête. « Comme au club de quilles. On ne parle pas de politique, et celui qui fait du grabuge, dehors. »

« Exactement », dit KevIn.

Kasimiro

Le soir, Uwe était à la clôture du jardin et racontait tout à M. Kasimiro. Il le raconta très en détail, avec des treillis et des pulls, avec la ceinture et les bretelles. M. Kasimiro hochait la tête sans arrêt, comme hochent la tête les gens qui pensent à autre chose.

« Et le plus important », conclut Uwe d’un ton solennel, « ça ne s’appelle pas signature quantique. Ça s’appelle résistant au quantique. »

« Ah », dit M. Kasimiro.

De la fenêtre de la cuisine des Kasimiro s’éleva une voix métallique. « Je vous ai compris. J’ai ajouté un ordinateur quantique à votre panier. Livraison prévue mardi. »

« Siggi, non ! » cria M. Kasimiro en se précipitant dans la maison.

Uwe retourna au salon. « KevIn. Siggi a commandé un ordinateur quantique. »

« Je doute qu’il en reçoive un », dit KevIn. « Il recevra probablement un frigo. »

« Avec des guirlandes ? »

« Avec une machine à glaçons. Et une brochure. »

Uwe s’assit sur le canapé et pensa à QuantumLeap Ruhr AG. « Tu sais quoi, KevIn ? Si Siggi a de la chance, ce sera au moins un vrai frigo. »

« C’est plus », dit KevIn, « que ce que vous avez eu pour deux mille euros. »

Uwe lança un coussin du canapé sur l’enceinte. Il la rata. Le thermostat affichait 19 degrés.