Les ordinateurs quantiques pourraient déchiffrer le chiffrement plus tôt que prévu grâce à un nouvel algorithme

Les ordinateurs quantiques pourraient déchiffrer le chiffrement plus tôt que prévu grâce à un nouvel algorithme

Horodatage: 2 octobre 2023 10h00

L’une des utilisations les plus connues et les plus perturbatrices d’un futur ordinateur quantique est la capacité de déchiffrer le chiffrement. Un nouvel algorithme pourrait réduire considérablement les obstacles à la réalisation de cet objectif.

Malgré tout le battage médiatique autour de l’informatique quantique, d’importants points d’interrogation subsistent. à quoi les ordinateurs quantiques seront réellement utiles. On espère qu’ils pourront tout accélérer, des processus d’optimisation à l’apprentissage automatique, mais dans de nombreux cas, on ne sait pas exactement dans quelle mesure ils seront plus faciles et plus rapides.

Une chose est cependant certaine : un ordinateur quantique suffisamment puissant pourrait rendre inutiles nos principaux systèmes cryptographiques. Même si les énigmes mathématiques qui les sous-tendent sont pratiquement insolubles par les ordinateurs classiques, elles seraient tout à fait réalisables pour un ordinateur quantique suffisamment grand. C'est un problème car ces systèmes sécurisent la plupart de nos informations en ligne.

La grâce salvatrice réside dans le fait que les processeurs quantiques d’aujourd’hui sont loin d’atteindre le type d’échelle requis. Mais selon un signaler dans Sciences, Oded Regev, informaticien de l'Université de New York, a découvert un nouvel algorithme qui pourrait réduire considérablement le nombre de qubits requis.

L’approche retravaille essentiellement l’un des algorithmes quantiques les plus performants à ce jour. En 1994, Peter Shor du MIT a mis au point un moyen de déterminer quels nombres premiers doivent être multipliés entre eux pour donner un nombre particulier : un problème connu sous le nom de factorisation première.

Pour un grand nombre, il s'agit d'un problème incroyablement difficile qui devient rapidement insoluble sur les ordinateurs conventionnels, c'est pourquoi il a été utilisé comme base du système de cryptage RSA populaire. Mais en tirant parti des phénomènes quantiques comme la superposition et l'intrication, l'algorithme de Shor peut résoudre ces problèmes même pour des nombres incroyablement grands.

Ce fait a provoqué une certaine panique parmi les experts en sécurité, notamment parce que les pirates informatiques et les espions peuvent aujourd’hui récupérer des données cryptées et simplement attendre le développement d’ordinateurs quantiques suffisamment puissants pour les déchiffrer. Et même si des normes de chiffrement post-quantique ont été développées, leur mise en œuvre sur le Web pourrait prendre de nombreuses années.

L'attente risque cependant d'être assez longue. La plupart des implémentations de RSA reposent sur des clés d'au moins 2048 617 bits, ce qui équivaut à un nombre de XNUMX chiffres. Chercheurs Fujitsu récemment calculé qu'il faudrait 10,000 jours à un ordinateur quantique totalement tolérant aux pannes et doté de 104 XNUMX qubits pour déchiffrer un nombre aussi grand.

Cependant, le nouvel algorithme de Regev, décrit dans un prépublication publiée le arXiv, pourrait potentiellement réduire considérablement ces exigences. Regev a essentiellement retravaillé l'algorithme de Shor de telle sorte qu'il soit possible de trouver les facteurs premiers d'un nombre en utilisant beaucoup moins d'étapes logiques. Réaliser des opérations dans un ordinateur quantique implique de créer de petits circuits à partir de quelques qubits, appelés portes, qui effectuent des opérations logiques simples.

Dans l'algorithme original de Shor, le nombre de portes nécessaires pour factoriser un nombre est le carré du nombre de bits utilisés pour le représenter, ce qui est noté n2. L'approche de Regev nécessiterait seulement n1.5 portes car il recherche les facteurs premiers en effectuant des multiplications plus petites de plusieurs nombres plutôt que de très grandes multiplications d'un seul nombre. Cela réduit également le nombre de portes requises en utilisant un algorithme classique pour traiter davantage les sorties.

Dans son article, Regev estime que pour un nombre de 2048 XNUMX bits, cela pourrait réduire le nombre de portes requises de deux à trois ordres de grandeur. Si cela est vrai, cela pourrait permettre à des ordinateurs quantiques beaucoup plus petits de déchiffrer le cryptage RSA.

Il existe cependant des limites pratiques. Pour commencer, Regev note que l'algorithme de Shor bénéficie d'une multitude d'optimisations développées au fil des années qui réduisent le nombre de qubits nécessaires à son exécution. On ne sait pas encore si ces optimisations fonctionneront avec la nouvelle approche.

Martin Ekerå, chercheur en informatique quantique au sein du gouvernement suédois, a également déclaré Sciences que l'algorithme de Regev semble avoir besoin d'une mémoire quantique pour stocker les valeurs intermédiaires. Fournir cette mémoire nécessitera des qubits supplémentaires et rongera tout avantage informatique dont elle dispose.

Néanmoins, la nouvelle recherche vient à point nommé rappeler que, lorsqu'il s'agit de la menace que représente l'informatique quantique pour le chiffrement, les poteaux de but bougent constamment, et le passage à des schémas post-quantiques ne peut pas se produire assez rapidement.

Crédit image: Google

Les ordinateurs quantiques pourraient pirater le cryptage plus tôt que prévu grâce au nouvel algorithme PlatoBlockchain Data Intelligence. Recherche verticale. Aï.

Horodatage:

Plus de Singularity Hub