Ordinateurs quantiques: la fin de la cryptographie?

Publicité

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 agences gouvernementales 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 n'exécutent que quelques algorithmes) exploitent les propriétés quantiques et constituent une autre étape incrémentielle sur la route pleinement Turing-complet Quel est le test de Turing et sera-t-il jamais battu?Le test de Turing est destiné à déterminer si les machines pensent. Le programme Eugene Goostman a-t-il vraiment réussi le test de Turing, ou les créateurs ont-ils simplement triché?

Lire la suite machine quantique.

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 toujours plus rapides Quelle est la loi de Moore et qu'est-ce que cela a à voir avec vous? [MakeUseOf explique]La malchance n'a rien à voir avec la loi de Moore. Si c'est l'association que vous aviez, vous la confondez avec la loi de Murphy. Cependant, vous n'étiez pas loin car la loi de Moore et la loi de Murphy ... Lire la suite - 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 de une certaine taille dans un certain laps de temps, doubler la vitesse de l'ordinateur ne permet pas nécessairement de résoudre les 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 complétés rapidement compte tenu de 100 points de données, mais pour terminer l'algorithme, compte tenu de 1000 points de données, il faudrait un ordinateur de la taille de la Terre pour un milliard ans. 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 pourraient ê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 chiffrement et de déchiffrement sont différentes et ne peuvent pas être facilement calculées les unes par rapport aux autres, est une méthode mathématique beaucoup plus difficile. structure à 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 lignes! 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 comme ils pourraient l'être: la norme de chiffrement 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. En conséquence, 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 des 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é est un chat à l'air suffisant tenant un déchiffré message.

Pour plus d'informations sur les ordinateurs quantiques, consultez notre récent article sur le sujet Comment fonctionnent les ordinateurs optiques et quantiques?L'ère Exascale arrive. Savez-vous comment fonctionnent les ordinateurs optiques et quantiques, et ces nouvelles technologies deviendront-elles notre avenir? Lire la suite !

Le résultat est que les ordinateurs quantiques ne sont pas simplement plus rapides linéairement, comme les ordinateurs normaux: en obtenir deux, dix ou cent fois plus rapide n'aide pas beaucoup en matière 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 graphène et calcul memrister La dernière technologie informatique que vous devez voir pour croireDécouvrez quelques-unes des dernières technologies informatiques qui devraient transformer le monde de l'électronique et des PC au cours des prochaines années. Lire la suite .

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 de nombre 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 est d'autant plus prononcé que les touches sont longues. C’est la puissance des ordinateurs quantiques.

Ne vous méprenez pas - les ordinateurs quantiques ont beaucoup d'utilisations potentielles non perverses. 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. RSA et les schémas de chiffrement associés vous permettent de vous fier au bon site Web, aux fichiers que vous le téléchargement n'est pas criblé 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 donnent l'espoir 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 cryptage sur réseau, comme Ring-Learning With Error, qui tire sa sécurité d'un complexe manifestement problème d'apprentissage automatique, et la cryptographie multivariée, qui tire sa sécurité de la difficulté de résoudre de très grands systèmes de simples équations. Vous pouvez en savoir plus sur ce sujet sur le Article Wikipédia. Méfiez-vous: beaucoup de ces choses sont complexes, et vous trouverez peut-être que votre expérience 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. que des lacunes évidentes auraient été découvertes à ce jour, et les chercheurs ont prouvé diverses caractéristiques qui les rendent fort.

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