Il y a trois semaines, la panique a balayé certains coins du monde de la sécurité après que des chercheurs ont découvert une percée qui, enfin, a mis à portée de main le craquage du schéma de cryptage RSA largement utilisé en utilisant l’informatique quantique.
Les scientifiques et les cryptographes savent depuis deux décennies qu’une méthode de factorisation connue sous le nom d’algorithme de Shor permet théoriquement à un ordinateur quantique disposant de ressources suffisantes de casser RSA. En effet, les nombres premiers secrets qui sous-tendent la sécurité d’une clé RSA sont faciles à calculer à l’aide de l’algorithme de Shor. Calculer les mêmes nombres premiers en utilisant le calcul classique prend des milliards d’années.
La seule chose qui retient ce scénario apocalyptique est la quantité massive de ressources informatiques nécessaires à l’algorithme de Shor pour casser des clés RSA de taille suffisante. L’estimation actuelle est que casser une clé RSA de 1 024 bits ou 2 048 bits nécessite un ordinateur quantique doté de vastes ressources. Plus précisément, ces ressources représentent environ 20 millions de qubits et environ huit heures d’exécution en superposition. (Un qubit est une unité de base de l’informatique quantique, analogue au bit binaire dans l’informatique classique. Mais alors qu’un bit binaire classique ne peut représenter qu’une seule valeur binaire telle que 0 ou 1, un qubit est représenté par une superposition de plusieurs valeurs possibles. États.)
L’article, publié il y a trois semaines par une équipe de chercheurs en Chine, a rapporté avoir trouvé une méthode de factorisation qui pourrait casser une clé RSA de 2 048 bits en utilisant un système quantique avec seulement 372 qubits lorsqu’il fonctionnait en utilisant des milliers d’étapes d’opération. La découverte, si elle était vraie, aurait signifié que la chute du cryptage RSA vers l’informatique quantique pourrait survenir beaucoup plus tôt que la plupart des gens ne le pensaient.
La disparition de RSA est grandement exagérée
Lors de la conférence Enigma 2023 à Santa Clara, en Californie, mardi, l’informaticien et expert en sécurité et en confidentialité Simson Garfinkel a assuré aux chercheurs que la disparition de RSA était grandement exagérée. Pour le moment, a-t-il dit, l’informatique quantique a peu d’applications pratiques, voire aucune.
Publicité
“À court terme, les ordinateurs quantiques sont bons pour une chose, et c’est de faire publier des articles dans des revues prestigieuses”, a déclaré Garfinkel, co-auteur avec Chris Hoofnagle du livre de 2021 Law and Policy for the Quantum Age. “La deuxième chose pour laquelle ils sont raisonnablement bons, mais nous ne savons pas pour combien de temps encore, c’est qu’ils sont raisonnablement bons pour obtenir du financement.”
Même lorsque l’informatique quantique devient suffisamment avancée pour fournir des applications utiles, les applications sont susceptibles de simuler la physique et la chimie et d’effectuer des optimisations informatiques qui ne fonctionnent pas bien avec l’informatique classique. Garfinkel a déclaré que la pénurie d’applications utiles dans un avenir prévisible pourrait entraîner un “hiver quantique”, similaire aux multiples cycles d’hivers d’intelligence artificielle avant que l’IA ne décolle enfin.
Le problème avec l’article publié plus tôt ce mois-ci était sa dépendance à l’algorithme de Schnorr (à ne pas confondre avec l’algorithme de Shor), qui a été développé en 1994. L’algorithme de Schnorr est un calcul classique basé sur des treillis, qui sont des structures mathématiques qui ont de nombreuses applications dans cryptographie constructive et cryptanalyse. Les auteurs qui ont conçu l’algorithme de Schnorr ont déclaré qu’il pourrait améliorer l’utilisation de la méthode d’optimisation quantique heuristique appelée QAOA.
En peu de temps, une foule de chercheurs ont souligné des failles fatales dans l’algorithme de Schnorr qui l’ont pratiquement démystifié. Plus précisément, les critiques ont déclaré qu’il n’y avait aucune preuve à l’appui des affirmations des auteurs selon lesquelles l’algorithme de Schnorr atteint un temps polynomial, par opposition au temps exponentiel obtenu avec les algorithmes classiques.
Le document de recherche d’il y a trois semaines semblait prendre l’algorithme de Shor pour argent comptant. Même lorsqu’il est censé être amélioré à l’aide de QAOA, ce qui n’est actuellement pas pris en charge, on peut se demander s’il fournit une amélioration des performances.
“Tout compte fait, c’est l’un des articles sur l’informatique quantique les plus activement trompeurs que j’ai vus en 25 ans, et j’en ai vu… beaucoup”, a déclaré Scott Aaronson, informaticien à l’Université du Texas à Austin et directeur de son Quantum. Centre d’information, a écrit. “Cela dit, ce n’est en fait pas la première fois que je rencontre l’étrange idée que l’accélération quantique exponentielle pour la factorisation des nombres entiers, que nous connaissons grâce à l’algorithme de Shor, devrait en quelque sorte” déteindre “sur l’heuristique d’optimisation quantique qui n’en incarne aucune. des idées réelles de l’algorithme de Shor, comme par magie sympathique.
