La cryptographie post-quantique : à quoi ça sert vraiment ?

Écrit par Charles Papin, Lead Product Engineer chez Evertrust

À moins d'avoir passé les deux dernières années au sein d'une tribu reculée de Micronésie, il y a de fortes chances que le sujet de la cryptographie post-quantique soit déjà parvenu à vos oreilles, parfois sous la forme de l'énigmatique acronyme PQC. Il est en effet devenu assez tendance de parsemer ses conversations mondaines de « PQC » : cela sonne sophistiqué et dans l'air du temps.

Et pourtant, rarement autant de profondeur conceptuelle aura été condensée en si peu de lettres. Chacun des trois mots qui composent l'expression mérite un instant de réflexion.

Prenons d'abord « cryptographie ». Il me suffit sûrement de doubler la taille de mes clés, puisque je suis déjà passé de RSA 1024 à RSA 2048. En quoi cela devrait-il me concerner ?

Ensuite « quantique ». Qu'est-ce que la physique quantique vient faire dans mon parc informatique, exclusivement composé de machines déterministes ?

Et enfin « post ». Qu'y a-t-il après le quantique ? Nous n'avons même pas d'ordinateur quantique digne de ce nom, et nous planifions déjà la suite ?

Tentons d'y voir plus clair, afin que lors de votre prochain débat en bonne compagnie dans une conférence de cybersécurité, vous puissiez défendre en confiance une position éclairée sur un sujet qui nous occupera au moins pendant les dix prochaines années.

« Cryptographie »

Comme chacun sait, la cryptographie est la branche des mathématiques, et par extension de l'informatique, dédiée à la sécurisation des communications entre les personnes et entre les machines. Elle vise en particulier à fournir les garanties suivantes, sans que la liste soit exhaustive :

• Confidentialité : garantir que quiconque n'est pas le destinataire prévu d'un message ne peut pas en comprendre le contenu ;
• Intégrité : garantir qu'un message transmis entre deux parties n'a pas été altéré en transit, ou à tout le moins que toute modification malveillante de son contenu est immédiatement détectée ;
• Authentification : garantir que l'identité de l'émetteur du message peut être prouvée ;
• Non-répudiation : garantir qu'une personne ayant effectué une action ne pourra pas en nier ultérieurement la responsabilité.

Ces garanties sont absolument fondamentales pour nos écosystèmes numériques : elles sont à la racine de toute notion de sécurité dans les systèmes d'information. Sans la machinerie mathématique qui les sous-tend, un acteur malveillant pourrait aisément les contourner. Avec des preuves de sécurité mathématiques, qui ne sont pas infaillibles mais restent solides en l'état actuel de nos connaissances, un tel contournement devient beaucoup, beaucoup, beaucoup plus difficile, voire purement impossible, au vu de la quantité de ressources qu'il exigerait.

Naturellement, la difficulté à casser cette sécurité dépend de la technologie dont dispose l'attaquant. Si nous avions demandé à un lettré chinois du XIIIᵉ siècle de casser une clé RSA de 20 bits, son boulier ne le lui aurait pas permis dans un délai raisonnable. Aujourd'hui, nos ordinateurs classiques savent casser des clés allant jusqu'à 829 bits, le record actuel, établi en 2020, au prix d'un degré diabolique de calcul parallèle. Mais le problème est structuré de telle sorte que l'effort de calcul explose à mesure que la taille de la clé augmente, ce qui permet au défenseur de conserver toujours une longueur d'avance sur l'attaquant.

Avec un ordinateur quantique, en revanche, les choses se présentent tout autrement.

« Quantique »

Le début du XXᵉ siècle a vu naître l'une des plus belles théories physiques que l'esprit humain ait jamais construites, une théorie dont nous n'avons cessé depuis de confirmer la pertinence et l'exactitude, par des expériences que ses fondateurs n'étaient pas en mesure de mener en leur temps.

En quelques mots simples, la théorie quantique dit ceci : aux échelles extrêmement petites, inférieures au milliardième de mètre, la matière se comporte différemment, en suivant d'autres règles que celles qui régissent le monde tangible que nous habitons. Lorsque vous lancez une balle en l'air, un observateur attentif peut, sans grande difficulté, estimer où elle atterrira et quand elle touchera le sol. La physique est déterministe, les lois de la gravitation s'appliquent, et il serait bien surprenant que la balle décide soudain de suivre une trajectoire autre qu'une parabole parfaite.

À l'échelle nanoscopique, au contraire, cette notion de déterminisme ne tient plus. La position, la vitesse ou l'énergie d'une particule donnée ne peuvent pas être déterminées à l'avance. Il existe une certaine probabilité que la particule soit ici, se déplaçant à telle vitesse, et il existe aussi une certaine probabilité qu'elle soit tout à fait ailleurs, à une vitesse différente. La particule ne vit donc pas dans un état unique défini par une position et une vitesse, mais dans plusieurs états à la fois, chacun ayant une certaine probabilité d'être mesuré. C'est ce que l'on appelle la superposition d'états.

Étrange, certes, mais ce n'est pas le plus étrange.

La mesure de la position ou de la vitesse d'une particule ne peut pas être arbitrairement précise. À notre échelle, si vous partagez votre position GPS avec un ami, il saura très précisément où vous êtes et à quelle vitesse vous vous déplacez. Dans l'infiniment petit, vous ne pouvez pas connaître simultanément avec une grande précision la position et la vitesse d'un objet. Si vous savez très précisément à quelle vitesse il se déplace, vous ne connaîtrez qu'approximativement la région qu'il occupe, et rien de plus. Si vous savez très précisément où il se trouve, vous aurez une « grande » incertitude sur sa vitesse. Comprenez bien qu'il ne s'agit pas d'une limite de l'instrument de mesure : c'est une propriété intrinsèque de la particule élémentaire elle-même.

Étrange à nouveau, mais ce n'est toujours pas le plus étrange.

Reste le phénomène d'intrication. Prenez une boule de pâte à modeler et divisez-la en deux boules plus petites. Placez la première dans une boîte en bois et la seconde dans une boîte en métal, puis expédiez la boîte en bois à Rio de Janeiro et la boîte en métal à Kuala Lumpur. Ouvrez la boîte en bois : vous découvrez que la boule a pris une forme particulière au cours de son voyage mouvementé. Ouvrez la boîte en métal au même instant : la boule de Kuala Lumpur a pris exactement la même forme, à 20 000 km de là. Évidemment, les choses ne fonctionnent pas ainsi à notre échelle. Mais là où s'appliquent les règles de la physique quantique, ce type de comportement est possible, et il a été prouvé par l'expérience, notamment celle d'Alain Aspect, prix Nobel de physique 2022. Lorsque deux particules préparées dans un certain état intriqué sont séparées par une grande distance et que la première est mesurée dans un état donné, la seconde sera elle aussi mesurée dans ce même état.

Cela, il faut l'admettre, c'était le plus étrange.

Quel rapport, demanderez-vous, tout cela a-t-il avec la cryptographie ?

Les nouvelles règles rendues possibles par la physique quantique, en particulier la superposition d'états, dont nous avons parlé, et les interférences, dont nous n'avons pas parlé, ouvrent un tout nouveau terrain de jeu aux mathématiciens et aux informaticiens. Leur boîte à outils s'agrandit, et les règles du calcul changent.

Et c'est précisément grâce à cette boîte à outils que Peter Shor a découvert, en 1994, un algorithme quantique qui casse la sécurité de RSA. L'humanité était encore loin d'imaginer qu'un ordinateur capable d'exploiter les propriétés quantiques de la matière puisse un jour être construit, mais les règles théoriques que ces propriétés autorisent permettaient déjà de concevoir des façons de calculer jusque-là hors de notre portée.

Si casser RSA revient à visser une vis, les algorithmes classiques ne nous donnent qu'une pince à épiler, là où la physique quantique nous tend une visseuse électrique. Le défenseur avait toujours une longueur d'avance sur l'attaquant, puisqu'il suffisait d'augmenter la taille de la clé pour rendre le problème nettement plus difficile. Avec l'algorithme quantique, doubler la taille d'une clé RSA n'a qu'un effet négligeable pour l'attaquant : la complexité ajoutée est polynomiale, et non exponentielle.

Or, l'évolution majeure de ces dernières années, c'est que cette visseuse électrique devient une réalité industrielle : nous savons désormais construire du matériel quantique capable de mettre en pratique la théorie conçue par Shor et ses successeurs. Les défis techniques sont loin d'être tous résolus, puisque le record de factorisation ne s'établit pour l'instant qu'à 21 bits. La technologie progresse pourtant vite et, compte tenu de la dynamique politique et des capitaux investis, il est assez raisonnable de parier, si l'on en croit les panels d'experts régulièrement interrogés, qu'un ordinateur quantique digne de ce nom verra le jour dans la prochaine décennie. Et le jour où ce sera le cas, RSA ne sécurisera plus rien du tout.

Il est également fort probable que nous ne l'apprendrons que bien après certaines agences gouvernementales bien informées : une telle machine offrirait évidemment de délicieuses capacités de déchiffrement que l'on préférerait peut-être ne pas ébruiter tout de suite.

« Post »-quantique

« Post-quantique » doit se comprendre comme un raccourci pour « à une époque où l'attaquant possède un ordinateur quantique ». Nous entrerons donc dans un monde post-quantique le jour du fameux « Q-Day », c'est-à-dire le jour où un ordinateur quantique suffisamment puissant pour casser de grandes clés RSA sortira des chaînes de production d'un géant américain, chinois ou, espérons-le, européen.

La cryptographie post-quantique est alors la cryptographie conçue pour rester résiliente dans un tel monde. Elle se compose d'algorithmes classiques s'exécutant sur des ordinateurs classiques, mais bâtis sur des problèmes mathématiques dont la résolution, contrairement à celle de RSA, n'est pas accélérée par un ordinateur quantique.

C'est dans ce contexte qu'ont été développés les algorithmes issus de la compétition du NIST (ML-DSA, SLH-DSA, ML-KEM, et bientôt FN-DSA et HQC), ainsi que ceux retenus au niveau européen et normalisés à l'ISO (FrodoKEM, Classic McEliece). Ce sont des algorithmes « classiques », écrits dans des langages de programmation « classiques », s'exécutant sur des processeurs « classiques », mais reposant sur des problèmes mathématiques que l'on croit difficiles à résoudre efficacement, même sur un ordinateur quantique.

Jusqu'à preuve du contraire, bien entendu.