Ordinateurs Quantum La fin de la cryptographie?

L’informatique quantique est l’une de ces technologies si mystérieuses que les personnages de télévision le nomment quand ils veulent sonner intelligemment.

L'informatique quantique est une idée qui existe depuis un certain temps - la possibilité théorique a été introduite à l'origine par Yuri Manin et Richard Feynman en 1982. Cependant, au cours des dernières années, le domaine s'est beaucoup rapproché de l'aspect pratique..

Des entreprises telles que Google et Microsoft, ainsi que des agences gouvernementales telles que la NSA se sont lancées avec fébrilité dans l'informatique quantique depuis des années. Une société appelée D-Wave a produit et vend des périphériques qui (bien qu’ils ne soient pas des ordinateurs appropriés et ne puissent exécuter que quelques algorithmes) exploitent les propriétés quantiques et constituent une autre étape incrémentielle sur la route menant à une solution complète de Turing. Le test de Turing et sera-t-il un jour battu? Quel est le test de Turing et sera-t-il un jour battu? Le test de Turing a pour but de déterminer si les machines pensent. Le programme Eugene Goostman a-t-il vraiment passé 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 pour permettre la construction du premier ordinateur quantique à grande échelle en une décennie..

Alors pourquoi tout cet intérêt? Pourquoi devriez-vous vous en soucier? Les ordinateurs deviennent de plus en plus rapides Quelle est la loi de Moore et quel est son rapport avec vous? [MakeUseOf explique] Qu'est-ce que la loi de Moore et en quoi elle a à voir avec vous? [MakeUseOf explique] La malchance n'a rien à voir avec la loi de Moore. Si c'est votre association, vous la confondez avec la loi de Murphy. Cependant, vous n'étiez pas loin parce que la loi de Moore et la loi de Murphy… En savoir plus - En quoi les ordinateurs quantiques sont-ils si particuliers??

Pour expliquer pourquoi ces machines sont si importantes, nous devrons 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.”

Quelle est la complexité d'exécution?

L'une des grandes surprises des débuts de l'informatique a été la découverte que, si vous avez un ordinateur qui résout un problème d'une certaine taille en un certain laps de temps, le fait de doubler la vitesse de l'ordinateur ne permet pas nécessairement de le résoudre. deux fois plus gros.

Certains algorithmes augmentent très rapidement le temps d’exécution total à mesure que la taille du problème augmente - certains algorithmes peuvent être rapidement complétés avec 100 points de données, mais compléter cet algorithme avec 1000 points de données nécessiterait 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 rapidité avec laquelle la complexité d'un problème augmente et utilise la forme de cette courbe pour classifier l'algorithme..

Généralement, ces classes de difficultés sont exprimées sous forme de fonctions. Un algorithme qui devient proportionnellement plus difficile lorsque le jeu de données sur lequel il travaille augmente (comme une simple fonction de comptage) est considéré comme 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, cela pourrait s'appeler “linéaire”, parce que lorsque vous le représentez, vous obtenez une ligne droite. D'autres fonctions pourraient être n ^ 2 ou 2 ^ n ou n! (n factoriel). Celles-ci sont polynomiales et exponentielles. Dans les deux derniers cas, les exponentielles grandissent si rapidement que dans presque tous les cas, elles ne peuvent être résolues que par des exemples très triviaux..

Complexité d'exécution et cryptographie

Si vous entendez ça pour la première fois et que cela semble insignifiant et mystérieux, essayons de fonder cette discussion. La complexité de l'exécution est essentielle pour la cryptographie, qui consiste à rendre le déchiffrement plus facile pour les personnes connaissant 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 des 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 crypto asymétrique vous permet d'avoir des conversations privées , même sur les lignes tapées! Il vous permet également de créer “signatures numériques” pour vous permettre de vérifier l'origine d'un message et le fait qu'il n'a pas été falsifié.

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

Comme la cryptographie asymétrique est plus difficile à mettre en place que la symétrie, les schémas de cryptage standard utilisés de nos jours ne sont pas aussi puissants qu’ils pourraient l’être: la norme de cryptage la plus courante, RSA, peut être déchiré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.

Le meilleur algorithme connu pour factoriser de grands nombres dans leurs nombres premiers composants est appelé le tamis du champ de nombres général et a une complexité d'exécution qui augmente un peu plus lentement que 2 ^ n. En conséquence, les clés doivent être environ dix fois plus longues pour offrir une sécurité similaire, ce que les gens tolèrent normalement comme coût de transaction. La mauvaise nouvelle est que tout le terrain de jeu change lorsque des ordinateurs quantiques sont mis à contribution..

Ordinateurs Quantum: Changer le jeu de la crypto

Les ordinateurs quantiques fonctionnent car ils peuvent avoir plusieurs états internes en même temps, via un phénomène quantique appelé “superposition”. Cela signifie qu'ils peuvent attaquer simultanément différentes parties d'un problème, en les divisant en différentes versions. Ils peuvent également être configurés de manière à ce que les branches qui résolvent le problème se retrouvent avec la plus grande amplitude. Ainsi, lorsque vous ouvrez la boîte sur le chat de Schrodinger, la version de l'état interne que vous êtes le plus susceptible de présenter est chat regardant un message décrypté.

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

Le résultat de ceci est que les ordinateurs quantiques ne sont pas simplement linéairement plus rapides, comme le sont les ordinateurs normaux: obtenir deux, dix ou cent fois plus vite n'aide pas beaucoup en matière de cryptographie conventionnelle pour des centaines de milliards de fois. trop lent à traiter. Les ordinateurs Quantum prennent en charge des algorithmes dont la complexité de la durée d'exécution est plus petite que ce qui est possible par ailleurs. C’est ce qui différencie fondamentalement les ordinateurs quantiques d’autres technologies de calcul, telles que le graphène et le calcul de mémoires. La dernière technologie informatique à connaître pour croire La dernière technologie informatique à suivre pour croire Découvrez quelques-unes des dernières technologies informatiques 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 compte de grands nombres. log (n) ^ 3 temps, ce qui est considérablement mieux que la meilleure attaque classique. L'utilisation du tamis à champs de nombres général pour factoriser un nombre sur 2 048 bits prend environ 10 ^ 41 unités de temps, ce qui représente plus d'un billion de milliards de milliards de milliards. En utilisant l'algorithme de Shor, le même problème ne prend qu'environ 1000 unités de temps.

Plus les touches sont longues, plus l’effet est prononcé. C'est la puissance des ordinateurs quantiques.

Ne vous méprenez pas, les ordinateurs quantiques ont de nombreuses utilisations potentielles non perverses. Les ordinateurs Quantum peuvent résoudre efficacement le problème du voyageur voyageur, permettant aux chercheurs de construire des réseaux de transport plus efficaces et de concevoir de meilleurs circuits. Les ordinateurs quantiques ont déjà de puissants usages en intelligence artificielle.

Cela dit, leur rôle en cryptographie sera catastrophique. Les technologies de cryptage qui permettent à notre monde de continuer à fonctionner dépendent de la difficulté du problème de la factorisation des nombres entiers. RSA et les systèmes 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 encombrés de logiciels malveillants et que les gens n'espionnent pas votre navigation sur Internet (si vous utilisez Tor).

La cryptographie sécurise votre compte bancaire et sécurise l'infrastructure nucléaire du monde. Lorsque les ordinateurs quantiques deviennent pratiques, toute cette technologie cesse de fonctionner. La première organisation à développer un ordinateur quantique, si le monde fonctionne toujours sur les technologies que nous utilisons aujourd'hui, sera dans une position terriblement 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 puisse passer à des cryptosystèmes qui resteront sécurisés dans un monde de cryptage quantique..

Les candidats prometteurs incluent le chiffrement basé sur réseau, comme Ring-Learning With Error, qui tire sa sécurité d’un problème d’apprentissage automatique 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 dans l'article de Wikipedia. Méfiez-vous: beaucoup de choses sont complexes et vous constaterez peut-être que vos connaissances en mathématiques doivent être considérablement renforcées avant que vous puissiez vraiment entrer dans les détails..

Il en ressort que les cryptoschèmes post-quantiques sont très cool, mais aussi très jeunes. Ils ont besoin de plus de travail pour être efficaces et pratiques, ainsi que pour démontrer qu'ils sont en sécurité. Si nous sommes en mesure de faire confiance aux cryptosystèmes, c'est parce que nous leur avons lancé assez de génies cliniquement paranoïaques pour que tout défaut évident ait été découvert à présent, et les chercheurs ont prouvé que plusieurs caractéristiques les rendaient forts..

La cryptographie moderne repose sur la lumière en tant que désinfectant, et la plupart des systèmes de cryptographie post-quantique sont tout simplement trop récents pour pouvoir faire confiance à la sécurité mondiale. Ils y parviennent cependant, et avec un peu de chance et de préparation, les experts en sécurité peuvent effectuer la transition avant que le premier ordinateur quantique ne soit mis en service..

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 à leurs intentions. La question de savoir qui développe le premier un ordinateur quantique fonctionnel est une question que tout le monde devrait surveiller très attentivement à l’avenir au cours de la prochaine décennie..

Craignez-vous l'insécurité de la cryptographie pour les ordinateurs quantiques? Quelle est votre prise? Partagez votre opinion dans les commentaires ci-dessous!

Crédits d'image: orb binaire via Shutterstock

En savoir plus sur: Sécurité en ligne.