Ordinateurs quantiques: la fin de la cryptographie?

L’informatique quantique est l’une de ces technologies si mystérieuses que les personnages de télévision les abandonnent lorsqu’ils veulent avoir un son intelligent.

L’informatique quantique en tant qu’idée existe depuis un certain temps – la possibilité théorique a été initialement introduite par Yuri Manin et Richard Feynman en 1982. Au cours des dernières années, cependant, le domaine s’est rapproché de façon inquiétante de l’aspect pratique.

Des entreprises comme Google et Microsoft, ainsi que des organismes gouvernementaux comme la NSA, poursuivent tous avec acharnement des ordinateurs quantiques depuis des années. Une entreprise appelée D-Wave a produit et vend des appareils qui (bien qu’ils ne soient pas des ordinateurs appropriés et ne peuvent exécuter que quelques algorithmes) exploitent les propriétés quantiques et constituent une autre étape incrémentielle sur la route vers une machine quantique entièrement Turing complète .

Il ne semble pas déraisonnable de dire que des percées pourraient se produire qui permettront au premier ordinateur quantique à grande échelle d’être construit en une décennie.

Alors pourquoi tout l’intérêt? Pourquoi devriez-vous vous en soucier? Les ordinateurs deviennent plus rapides tout le temps – quelle est la particularité des ordinateurs quantiques?

Afin d’expliquer pourquoi ces machines sont si importantes, nous allons devoir prendre du recul et explorer exactement ce que sont les ordinateurs quantiques et pourquoi ils fonctionnent. Pour commencer, parlons d’un concept appelé «complexité d’exécution».

Qu’est-ce que la complexité d’exécution?

L’une des grandes surprises des premiers jours de l’informatique a été la découverte que, si vous avez un ordinateur qui résout un problème d’une certaine taille dans un certain laps de temps, doubler la vitesse de l’ordinateur ne le laisse pas nécessairement s’attaquer aux problèmes deux fois plus gros.

Certains algorithmes augmentent le temps d’exécution total très, très rapidement à mesure que la taille du problème augmente – certains algorithmes peuvent être rapidement complétés avec 100 points de données, mais pour compléter l’algorithme avec 1 000 points de données, il faudrait un ordinateur de la taille de la Terre milliards d’années. La complexité d’exécution est une formalisation de cette idée: elle examine la courbe de la vitesse à laquelle la complexité d’un problème croît et utilise la forme de cette courbe pour classer l’algorithme.

Généralement, ces classes de difficulté sont exprimées sous forme de fonctions. Un algorithme qui devient proportionnellement plus difficile lorsque l’ensemble de données sur lequel il travaille augmente (comme une simple fonction de comptage) serait une fonction avec une complexité d’exécution de « n «  (comme dans, il faut n unités de temps à traiter n points de données).

Alternativement, il pourrait être appelé «linéaire», car lorsque vous le représentez graphiquement, vous obtenez une ligne droite. D’autres fonctions peuvent être n ^ 2 ou 2 ^ n ou n! (n factoriel). Ce sont polynomiales et exponentielles. Dans les deux derniers cas, les exponentielles croissent si rapidement que dans presque tous les cas, elles ne peuvent être résolues que pour des exemples très triviaux.

Complexité d’exécution et cryptographie

Si vous entendez ce genre de choses pour la première fois et que cela semble dénué de sens et mystérieux, essayons de fonder cette discussion. La complexité de l’exécution est critique pour la cryptographie, qui repose sur la facilitation du déchiffrement pour les personnes qui connaissent une clé secrète que pour celles qui ne le savent pas. Dans un schéma cryptographique idéal, le déchiffrement devrait être linéaire si vous avez la clé, et 2 ^ k (où k est le nombre de bits dans la clé) si vous ne le faites pas.

En d’autres termes, le meilleur algorithme pour déchiffrer le message sans la clé devrait être simplement de deviner les clés possibles, ce qui est insoluble pour les clés de quelques centaines de bits seulement.

Pour la cryptographie à clé symétrique (dans laquelle les deux parties ont la possibilité d’échanger un secret en toute sécurité avant de commencer la communication), c’est assez facile. Pour la cryptographie asymétrique, c’est plus difficile.

La cryptographie asymétrique, dans laquelle les clés de cryptage et de décryptage sont différentes et ne peuvent pas être facilement calculées les unes des autres, est une structure mathématique beaucoup plus difficile à mettre en œuvre que la cryptographie symétrique, mais elle est également beaucoup plus puissante: la cryptographie asymétrique vous permet d’avoir des conversations privées , même sur des lignes taraudées! Il vous permet également de créer des «signatures numériques» pour vous permettre de vérifier d’où provient un message et s’il n’a pas été falsifié.

Ce sont des outils puissants qui constituent le fondement de la vie privée moderne: sans cryptographie asymétrique, les utilisateurs d’appareils électroniques n’auraient aucune protection fiable contre les regards indiscrets.

Parce que la cryptographie asymétrique est plus difficile à construire que symétrique, les schémas de cryptage standard utilisés aujourd’hui ne sont pas aussi solides qu’ils pourraient l’être: la norme de cryptage la plus courante, RSA, peut être piratée si vous pouvez trouver efficacement les facteurs premiers d’un très grand nombre. La bonne nouvelle est que c’est un problème très difficile.

L’algorithme le plus connu pour factoriser de grands nombres dans leurs nombres premiers de composants est appelé le tamis de champ de nombre général, et a une complexité d’exécution qui croît un peu plus lentement que 2 ^ n. Par conséquent, les clés doivent être environ dix fois plus longues afin de fournir une sécurité similaire, ce que les gens tolèrent normalement comme un coût pour faire des affaires. La mauvaise nouvelle, c’est que tout le terrain de jeu change lorsque les ordinateurs quantiques se jettent dans le mix.

Ordinateurs quantiques: changer le jeu Crypto

Les ordinateurs quantiques fonctionnent car ils peuvent avoir plusieurs états internes en même temps, grâce à un phénomène quantique appelé «superposition». Cela signifie qu’ils peuvent attaquer simultanément différentes parties d’un problème, réparties entre les versions possibles de l’univers. Ils peuvent également être configurés de telle sorte que les branches qui résolvent le problème se retrouvent avec le plus d’amplitude, de sorte que lorsque vous ouvrez la boîte sur le chat de Schrodinger, la version de l’état interne qui vous est le plus susceptible d’être présentée est une suffisance -chat chat tenant un message décrypté.

Pour plus d’informations sur les ordinateurs quantiques, consultez notre récent article sur le sujet!

Le résultat est que les ordinateurs quantiques ne sont pas seulement linéairement plus rapides, comme les ordinateurs normaux: obtenir deux, dix ou cent fois plus vite n’aide pas beaucoup quand il s’agit de cryptographie conventionnelle que vous êtes des centaines de milliards de fois trop lent à traiter. Les ordinateurs quantiques prennent en charge des algorithmes qui ont des complexités d’exécution plus petites que celles autrement possibles. C’est ce qui rend les ordinateurs quantiques fondamentalement différents des autres technologies informatiques futures, comme le graphène et le calcul memrister.

Pour un exemple concret, l’algorithme de Shor, qui ne peut être exécuté que sur un ordinateur quantique, peut prendre en log (n) ^ 3 temps, ce qui est considérablement meilleur que la meilleure attaque classique. L’utilisation du tamis de champ numérique général pour factoriser un nombre avec 2048 bits prend environ 10 ^ 41 unités de temps, ce qui équivaut à plus d’un billion de milliards de milliards. En utilisant l’algorithme de Shor, le même problème ne prend qu’environ 1000 unités de temps.

L’effet devient plus prononcé plus les touches sont longues. C’est la puissance des ordinateurs quantiques.

Ne vous méprenez pas – les ordinateurs quantiques ont beaucoup d’utilisations non malveillantes potentielles. Les ordinateurs quantiques peuvent résoudre efficacement le problème des vendeurs itinérants, permettant aux chercheurs de construire des réseaux d’expédition plus efficaces et de concevoir de meilleurs circuits. Les ordinateurs quantiques ont déjà des utilisations puissantes en intelligence artificielle.

Cela dit, leur rôle dans la cryptographie va être catastrophique. Les technologies de cryptage qui permettent à notre monde de continuer à fonctionner dépendent du problème de factorisation des nombres entiers qui est difficile à résoudre. Le RSA et les schémas de cryptage associés vous permettent de croire que vous êtes sur le bon site Web, que les fichiers que vous téléchargez ne sont pas criblés de logiciels malveillants et que les gens n’espionnent pas votre navigation sur Internet (si vous utilisez Tor).

La cryptographie protège votre compte bancaire et sécurise l’infrastructure nucléaire mondiale. Lorsque les ordinateurs quantiques deviennent pratiques, toute cette technologie cesse de fonctionner. La première organisation à développer un ordinateur quantique, si le monde travaille toujours sur les technologies que nous utilisons aujourd’hui, va être dans une position extrêmement puissante.

Alors, l’apocalypse quantique est-elle inévitable? Y a-t-il quelque chose que nous pouvons faire pour cela? Il s’avère que… oui.

Cryptographie post-quantique

Il existe plusieurs classes d’algorithmes de chiffrement qui, à notre connaissance, ne sont pas beaucoup plus rapides à résoudre sur un ordinateur quantique. Celles-ci sont connues collectivement sous le nom de cryptographie post-quantique et permettent d’espérer que le monde pourra passer à des systèmes de cryptage qui resteront sécurisés dans un monde de cryptage quantique.

Les candidats prometteurs incluent le chiffrement sur réseau, comme Ring-Learning With Error, qui tire sa sécurité d’un problème d’apprentissage automatique manifestement complexe, et la cryptographie multivariée, qui tire sa sécurité de la difficulté de résoudre de très grands systèmes d’équations simples. Vous pouvez en savoir plus sur ce sujet sur le Article Wikipédia. Méfiez-vous: beaucoup de ces choses sont complexes, et vous constaterez peut-être que votre formation en mathématiques doit être considérablement renforcée avant de pouvoir vraiment creuser dans les détails.

La leçon à retenir de tout cela est que les cryptoschémas post-quantiques sont très cool, mais aussi très jeunes. Ils ont besoin de plus de travail pour être efficaces et pratiques, mais aussi pour démontrer qu’ils sont sûrs. La raison pour laquelle nous pouvons faire confiance aux cryptosystèmes est parce que nous leur avons lancé suffisamment de génies cliniquement paranoïdes depuis assez longtemps pour que des lacunes évidentes aient été découvertes à ce jour, et les chercheurs ont prouvé diverses caractéristiques qui les rendent solides.

La cryptographie moderne dépend de la lumière comme désinfectant, et la plupart des schémas cryptographiques post-quantiques sont tout simplement trop nouveaux pour faire confiance à la sécurité mondiale. Ils y arrivent, cependant, et avec un peu de chance et un peu de préparation, les experts en sécurité peuvent terminer le changement avant que le premier ordinateur quantique ne soit mis en ligne.

S’ils échouent, cependant, les conséquences peuvent être désastreuses. La pensée de quiconque ayant ce genre de pouvoir est troublante, même si vous êtes optimiste quant à ses intentions. La question de savoir qui a développé le premier un ordinateur quantique fonctionnel est une question que tout le monde devrait surveiller très attentivement au cours de la prochaine décennie.

Êtes-vous préoccupé par l’insécurité de la cryptographie pour les ordinateurs quantiques? Quelle est votre opinion? Partagez votre opinion dans les commentaires ci-dessous!

Crédits image: Orbe binaire Via Shutterstock