Menu Close
Tasse cassée en trois morceaux
Le rapport entre une tasse et une carte bleue ? Pour un ordinateur, calculer en combien de morceaux la première se brisera est aussi compliqué que trouver le code de la seconde ! Joanna Bourne/Flickr, CC BY

Cartes bleues et sécurité des échanges : vers une cryptographie post-quantique

Les ordinateurs sont de bien utiles compagnons : ils permettent de résoudre de nombreux problèmes auxquels nous sommes confrontés. Fort heureusement, il existe aussi des problèmes hors d’atteintes pour ces derniers. Pensons à nos cartes bleues : il serait problématique qu’un ordinateur soit en mesure de retrouver notre code… C’est justement la menace que fait désormais peser l’ordinateur quantique, un nouveau type d’ordinateur actuellement en conception et reposant sur les lois de la physique quantique.

Heureusement, ce nouvel ordinateur ne signe pas pour autant la fin de la sécurité liée à nos cartes bleues, et de façon plus générale la sécurité numérique. Il existe en effet des problèmes difficiles même pour un ordinateur quantique. La cryptographie post-quantique propose justement de les étudier et de les exploiter afin d’assurer notre sécurité numérique de demain !

Tasse, algorithmes et cryptographie

Nos vies sont aujourd’hui rythmées par les ordinateurs. La raison du succès de ces machines modernes est plutôt simple : elles nous aident à résoudre rapidement de nombreux problèmes du quotidien. Par exemple, étant donné une carte routière ou géographique, comment trouver le chemin le plus court pour aller d’un point A à un point B ? La réponse est finalement plutôt simple : posons la question à notre smartphone ! Ces petits ordinateurs peuvent calculer très rapidement « tous » les chemins possibles et donc nous répondre instantanément. Dès lors, il n’y a plus qu’un pas pour penser que nos compagnons peuvent résoudre presque tout problème imaginable…

Malheureusement, il n’en est rien. Les ordinateurs s’avèrent même extrêmement rapidement limités. Prenons une tasse de café tombant de notre main un matin. Notre smartphone pourra-t-il prédire en combien de morceaux notre tasse favorite va-t-elle se casser ? La tâche semble difficile, même avec une application dédiée. En effet, réaliser une telle simulation demanderait un temps bien trop important à notre téléphone et même un supercalculateur n’y suffirait pas : le nombre de dimensions impliquées dans ce problème est bien trop élevé.

La solution n’est pas à chercher non plus du côté de l’évolution technologique. Même si nous dépassons les espérances de la fameuse Loi de Moore (qui prédit un doublement de notre puissance de calculs tous les deux ans), il faudrait encore attendre des centaines d’années avant d’être en mesure de donner une réponse satisfaisante à notre problème. À l’inverse, nous avons un moyen simple d’y répondre sans avoir recours à la technologie : il suffit de se baisser et de compter les morceaux. Un exercice certes fastidieux, mais qui paraît dans nos cordes…

Cette métaphore de la tasse est inspirée d’une vidéo de Richard Borcherds, médaille Fields, en réaction aux récentes annonces de suprématie quantique, c’est-à-dire la réalisation par un ordinateur quantique d’une tâche inaccessible à un ordinateur classique (ce dont nous reparlerons un peu plus loin).

Or, le fait qu’il existe des problèmes qu’un ordinateur, et même tous les ordinateurs terrestres réunis, n’est pas en mesure de résoudre en un temps raisonnable est le principe fondateur d’une grande partie de la cryptographie moderne, science du secret nous permettant la sécurité numérique. Il existe quantité de problèmes qui sont présumés appartenir à cette catégorie, les plus célèbres dans le cadre de la cryptographie étant ceux dits de la factorisation des entiers et du logarithme discret. Un pan entier de la sécurité numérique repose sur leur difficulté, comme les cartes bleues, nos mises à jour logiciel…

L’écueil des ordinateurs quantiques

Malheureusement, les avancées en physique quantique laissent entrevoir l’arrivée d’un nouvel outil qui pourrait bouleverser l’ordre établi : l’ordinateur quantique. Cet ordinateur « nouvelle génération », n’ayant pas grand-chose à voir avec nos ordinateurs, fonctionnerait en remplaçant les bits, ces 0 et ces 1 qui constituent le langage universel de toutes les machines autour du globe, par des qubits, objets issus des principes de la physique quantique et qui représentent à la fois un 0 et un 1 en « superposition ».

Cette différence fondamentale offre de nouvelles possibilités algorithmiques puissantes, comme l’a démontré P. Shor en 1994, en prouvant qu’un ordinateur quantique fonctionnel (c’est-à-dire un ensemble de qubits sur lequel on serait capable d’effectuer un certain nombre d’opérations prédéfinies) était en mesure de résoudre les problèmes de la factorisation et du logarithme discret bien plus efficacement que ne le pourrait jamais un ordinateur classique. Adieu nos cartes bleues ! Depuis, d’autres domaines où les ordinateurs quantiques pourraient s’avérer révolutionnaires ont été découverts, de façon plus positive cette fois. C’est par exemple le cas de la chimie où le calcul quantique pourrait permettre d’améliorer la modélisation des états d’une molécule.

Plusieurs piliers sur lesquels sont branchés des brassées de fils, surmontés de cylindres mi-transparents, mi-dorés. Le tout est très volumineux
Intérieur d’un ordinateur quantique. IBM Research/Flickr, CC BY-ND

Aujourd’hui, nous sommes encore loin d’avoir un ordinateur quantique fonctionnel : ces fameux qubits sont difficiles à manipuler et la route est encore longue à la fois sur le plan théorique et pratique. Les annonces de suprématie quantique dont nous parlions plus haut, c’est-à-dire la réalisation d’une tâche avec un ordinateur quantique qui est hors d’atteinte de nos ordinateurs du quotidien, concernaient en réalité des problèmes qui avaient été spécialement conçus dans le but même d’être plus faciles pour un ordinateur quantique que pour un ordinateur classique. Les applications prometteuses des ordinateurs quantiques, par exemple casser notre sécurité numérique, restent pour l’instant hors de portée des acteurs les plus avancés.

Les efforts investis dans la poursuite de la suprématie quantique sont cependant à la hauteur de la tâche, et une véritable course est lancée entre les grands acteurs du domaine, comme Google ou IBM. La menace n’est donc pas à prendre à la légère pour les cryptographes : on pourrait bien voir arriver un ordinateur quantique fonctionnel d’ici une dizaine d’années.

La cryptographique post-quantique

« Est-ce donc la fin de la cryptographie ? » pourrait-on alors se demander. Fort heureusement, la réponse à cette question est sans doute non. Car tout comme les ordinateurs classiques, les ordinateurs quantiques ne sont pas tout-puissants. C’est précisément le postulat sur lequel se fonde une nouvelle branche de la cryptographie : la cryptographie post-quantique. Celle-ci a pour but d’étudier de nouveaux problèmes mathématiques qui seraient durs à la fois pour les ordinateurs classiques, mais aussi pour les ordinateurs quantiques.

Récemment, le NIST, institut de standardisation américain, a lancé une compétition dans le but d’identifier et de standardiser les candidats prometteurs. Après plusieurs tours d’écrémage successif, la compétition va bientôt arriver à son terme et l’annonce des premières solutions soumises à la standardisation devrait tomber dans les mois à venir. De la multitude de propositions initiales ont émergées plusieurs grandes familles, dont les plus notables sont sans doute les cryptographies à base de réseaux euclidiens et de codes correcteurs, mêlant efficacité, compacité et bonne expérience des problèmes mathématiques sous-jacents.

Cependant, en cryptographie traditionnelle comme post-quantique, rien n’est gravé dans le marbre. On ne peut pas exclure la possibilité de voir, demain ou dans six mois ou un an, arriver un groupe d’individus avec un nouvel algorithme qui permettrait de casser un problème sur lequel se fonde la cryptographie post-quantique. Nous en avons eu la preuve récemment avec l’un des protocoles finalistes de la compétition du NIST, dont la sécurité vient d’être sérieusement remise en cause par une nouvelle attaque, prouvant que la sécurité numérique induite par un tel système ne serait pas assurée.

Ceci est d’autant plus vrai que la cryptographie post-quantique doit se prémunir d’une menace encore plus sérieuse : les ordinateurs quantiques eux-mêmes ! Or nous sommes bien loin d’avoir compris toutes les possibilités de ces nouvelles machines. Cela justifie le besoin d’avoir des solutions de repli et c’est pour cela que d’autres familles d’objets mathématiques tels que les systèmes multivariés ou encore les isogénies sont aussi étudiées de très près.

En résumé, l’établissement de notre future sécurité numérique soulève encore de nombreuses questions ! Comme cela est illustré par l’appel du NIST, les scientifiques sont à pied d’œuvre pour proposer des solutions à la fois sûres et efficaces, prêtes à être déployées sur nos ordinateurs et smartphones dans les prochaines années.

Want to write?

Write an article and join a growing community of more than 155,800 academics and researchers from 4,513 institutions.

Register now