L'informatique quantique et la fin du chiffrement

Les ordinateurs quantiques ont de bonnes chances de changer le visage informatique, et cela va doubler pour le cryptage. Pour les méthodes de chiffrement qui reposent sur le fait que le forçage brutal de la clé prend trop de temps avec les ordinateurs classiques, l'informatique quantique semble être son ennemi logique.

Par exemple, le problème mathématique qui est au cœur de RSA et d'autres schémas de chiffrement à clé publique est la factorisation d'un produit de deux nombres premiers. La recherche de la bonne paire en utilisant des méthodes classiques prend environ une éternité, mais l'algorithme de Shor peut être utilisé sur un ordinateur quantique approprié pour effectuer la factorisation requise des nombres entiers en un rien de temps.

Lorsque les ordinateurs quantiques deviennent suffisamment capables, la menace pesant sur une grande partie de nos communications cryptées est réelle. Si l’on ne peut plus se contenter de simplifier le forçage brutal d’un déchiffrement, tous les algorithmes de chiffrement à clé publique d’aujourd’hui sont essentiellement inutiles. Il s'agit du scénario apocalyptique, mais dans quelle mesure sommes-nous proches de ce qui se passe réellement, et que peut-on faire?

La menace du cryptage classique

Pour déterminer la menace réelle, il faut regarder les algorithmes de cryptage classiques utilisés aujourd'hui pour voir quelles parties d'entre eux seraient susceptibles d'être résolues par un algorithme quantique en beaucoup moins de temps que cela ne prendrait pour un ordinateur classique. En particulier, nous devons faire la distinction entre le chiffrement symétrique et asymétrique.

Les algorithmes symétriques peuvent être encodés et décodés avec la même clé secrète, et cela doit être partagé entre les partenaires de communication via un canal sécurisé. Le chiffrement asymétrique utilise une clé privée pour le déchiffrement et une clé publique pour le chiffrement uniquement. Cela permet la cryptographie à clé publique: la clé publique peut être partagée librement sans crainte d'emprunt d'identité car elle ne peut être utilisée que pour crypter et non décrypter.

Comme mentionné précédemment, RSA est un cryptosystème qui est vulnérable aux algorithmes quantiques, en raison de sa dépendance à la factorisation entière. RSA est un algorithme de chiffrement asymétrique, impliquant une clé publique et privée, qui crée le soi-disant problème RSA. Cela se produit lorsque l'on essaie d'effectuer une opération de clé privée alors que seule la clé publique est connue, ce qui nécessite de trouver le ee racines d'un nombre arbitraire, modulo N. Actuellement, il n'est pas réaliste de résoudre classiquement pour des tailles de clé RSA> 1024 bits.

Ici, nous voyons à nouveau ce qui rend l'informatique quantique si fascinante: la capacité de résoudre rapidement des problèmes polynomiaux non déterministes (NP). Alors que certains problèmes NP peuvent être résolus rapidement par les ordinateurs classiques, ils le font en approximant une solution. Les problèmes NP-complets sont ceux pour lesquels aucun algorithme d'approximation classique ne peut être conçu. Un exemple de ceci est le problème du voyageur de commerce (TSP), qui demande de déterminer l'itinéraire le plus court possible entre une liste de villes, tout en visitant chaque ville une fois et en revenant à la ville d'origine.

Même si le TSP peut être résolu avec l'informatique classique pour un plus petit nombre de villes (des dizaines de milliers), les plus grands nombres nécessitent une approximation pour atteindre 1%, car les résoudre nécessiterait des temps d'exécution excessivement longs.

Perfect Forward Secrecy

Un échange de clés Diffie-Helman.

Les algorithmes de chiffrement symétrique sont couramment utilisés pour le trafic en direct, avec uniquement une prise de contact et l'établissement initial d'une connexion en utilisant le chiffrement asymétrique (plus lent) comme canal sécurisé pour l'échange des clés symétriques. Bien que le chiffrement symétrique ait tendance à être plus rapide que le chiffrement asymétrique, il repose sur le fait que les deux parties ont accès au secret partagé, au lieu de pouvoir utiliser une clé publique.

Le chiffrement symétrique est utilisé avec le secret de retransmission (également appelé parfait secret avancé). L'idée derrière FS est qu'au lieu de se fier uniquement à la sécurité fournie par le canal crypté initial, on crypte également les messages avant leur envoi. De cette façon, même si les clés du canal de chiffrement étaient compromises, tout attaquant se retrouverait avec plus de messages chiffrés, chacun chiffré à l'aide d'une clé éphémère différente.

FS a tendance à utiliser l'échange de clés Diffie-Hellman ou similaire, ce qui donne un système comparable à un type de cryptage à usage unique (OTP), qui n'utilise la clé de cryptage qu'une seule fois. En utilisant des méthodes traditionnelles, cela signifie que même après avoir obtenu la clé privée et craqué un seul message, il faut consacrer le même effort à tous les autres messages qu'au premier afin de lire la conversation entière. C'est la raison pour laquelle de nombreux programmes de chat sécurisés comme Signal ainsi que de plus en plus de serveurs compatibles HTTPS utilisent FS.

C'est déjà en 1996 que Lov Grover a proposé l'algorithme de Grover, qui permet une accélération à peu près quadratique en tant qu'algorithme de recherche de boîte noire. Plus précisément, il trouve avec une forte probabilité l'entrée probable dans une boîte noire (comme un algorithme de cryptage) qui a produit la sortie connue (le message crypté).

Comme l'a noté Daniel J. Bernstein, la création d'ordinateurs quantiques capables d'exécuter efficacement l'algorithme de Grover nécessiterait au moins le doublement des longueurs de clés symétriques d'aujourd'hui. Ceci en plus de casser RSA, DSA, ECDSA et de nombreux autres systèmes cryptographiques.

Ordinateurs quantiques aujourd'hui

L'observateur d'entre nous a peut-être remarqué que malgré quelques fausses allégations de marketing au cours des dernières années, nous manquons aujourd'hui de véritables ordinateurs quantiques. En ce qui concerne les ordinateurs quantiques qui ont effectivement quitté le laboratoire et sont passés dans un environnement commercial, nous avons des systèmes de recuit quantique, D-Wave étant un fabricant bien connu de ces systèmes.

Les systèmes de recuit quantique ne peuvent résoudre qu'un sous-ensemble de problèmes NP-complets, dont le problème du voyageur de commerce, avec un espace de recherche discret. Il ne serait par exemple pas possible d'exécuter l'algorithme de Shor sur un système de recuit quantique. Le calcul quantique adiabatique est étroitement lié au recuit quantique et est donc également inadapté à un système informatique quantique à usage général.

Cela laisse la recherche informatique quantique d'aujourd'hui donc principalement dans le domaine des simulations, et le cryptage classique est principalement sécurisé (pour l'instant).

Un avenir quantique

Quand pouvons-nous nous attendre à voir des ordinateurs quantiques capables de décrypter chacune de nos communications sans effort? C'est une question délicate. Une grande partie dépend du moment où nous pouvons obtenir un nombre significatif de bits quantiques, ou qubits, ensemble dans quelque chose comme un modèle de circuit quantique avec une correction d'erreur suffisante pour rendre les résultats partout aussi fiables que ceux des ordinateurs classiques.

«IBM quantum computer» par IBM Research est autorisé sous CC BY-ND 2.0

À ce stade, on pourrait dire que nous essayons toujours de comprendre à quoi ressembleront les éléments de base d'un ordinateur quantique. Cela a conduit aux modèles informatiques quantiques suivants:

  • réseau de portes quantiques (portes quantiques)
  • ordinateur quantique unidirectionnel (série de mesures à un qubit)
  • ordinateur quantique adiabatique (voir recuit quantique)
  • ordinateur quantique topologique (tressage d'onsons dans un réseau 2D)

De ces quatre modèles, le recuit quantique a été implémenté et commercialisé. Les autres ont vu de nombreuses réalisations physiques en laboratoire, mais ne sont pas encore à l'échelle. À bien des égards, il n'est pas différent de la situation dans laquelle les ordinateurs classiques se sont retrouvés tout au long du 19e et au début du 20e siècle, lorsque les «  ordinateurs '' successifs se sont retrouvés à passer des systèmes mécaniques aux relais et aux vannes, suivis de transistors discrets et finalement (pour l'instant) d'innombrables transistors intégrés dans des puces singulières.

C'est la découverte de matériaux semi-conducteurs et de nouveaux procédés de production qui a permis aux ordinateurs classiques de prospérer. Pour l'informatique quantique, la question semble être principalement une question de quand nous réussirons à faire de même là-bas.

Un quantum de cryptage

Même si dans une décennie ou plus après la révolution de l'informatique quantique, notre cryptage de qualité militaire à trois niveaux semblera soudainement aussi robuste que le DES, nous pouvons toujours nous consoler en sachant qu'avec l'informatique quantique, nous apprenons également de plus en plus. en savoir plus sur la cryptographie quantique.

À bien des égards, la cryptographie quantique est encore plus excitante que la cryptographie classique, car elle peut exploiter les propriétés mécaniques quantiques. La plus connue est la distribution de clés quantiques (QKD), qui utilise le processus de communication quantique pour établir une clé partagée entre deux parties. La propriété fascinante de QKD est que le simple fait d'écouter cette communication provoquera des changements mesurables. Essentiellement, cela fournit une sécurité inconditionnelle dans la distribution de matériel de clé symétrique, et le chiffrement symétrique est nettement plus résistant aux quantums.

Tout cela signifie que même si les décennies à venir sont susceptibles d'entraîner une sorte de bouleversement qui peut ou non signifier la fin de l'informatique et de la cryptographie classiques, tout n'est pas perdu. Comme d'habitude, la science et la technologie progresseront, et les générations futures regarderont en arrière la technologie primitive d'aujourd'hui avec un certain niveau de perplexité.

Pour l'instant, l'utilisation de TLS 1.3 et de tout autre protocole prenant en charge le secret à terme et le chiffrement symétrique en général est votre meilleur choix.

François Zipponi
Je suis François Zipponi, éditorialiste pour le site 10-raisons.fr. J'ai commencé ma carrière de journaliste en 2004, et j'ai travaillé pour plusieurs médias français, dont le Monde et Libération. En 2016, j'ai rejoint 10-raisons.fr, un site innovant proposant des articles sous la forme « 10 raisons de... ». En tant qu'éditorialiste, je me suis engagé à fournir un contenu original et pertinent, abordant des sujets variés tels que la politique, l'économie, les sciences, l'histoire, etc. Je m'efforce de toujours traiter les sujets de façon objective et impartiale. Mes articles sont régulièrement partagés sur les réseaux sociaux et j'interviens dans des conférences et des tables rondes autour des thèmes abordés sur 10-raisons.fr.