Les ordinateurs quantiques vont-ils mettre fin au chiffrement RSA en 2023 ?

Dans les derniers jours de 2022, la communauté informatique a été chamboulée par l’étude d’un groupe de scientifiques chinois. Il y était dit que, dans un futur proche, il serait possible de déchiffrer l’algorithme cryptographique RSA avec une clé de 2048 bits, essentielle pour l’opération des protocoles Internet, en combinant astucieusement l’informatique classique et quantique. Cette menace est-elle vraiment réelle ? C’est ce que nous allons voir.

Les principes de base de l’informatique quantique

Nous savons depuis longtemps qu’un ordinateur quantique peut, en théorie, factoriser très rapidement de grands nombres entiers puis trouver les clés qui correspondent à certains algorithmes cryptographiques asymétriques, dont le chiffrement RSA. Cet article explique en détail ce qu’est un ordinateur quantique, comment il fonctionne et pourquoi il est si difficile à créer. Pour le moment, tous les experts sont d’accord sur le fait qu’il faudra attendre plusieurs dizaines d’années avant qu’un ordinateur quantique suffisamment puissant pour déchiffrer le RSA ne soit construit. Pour factoriser un chiffre de 2048 bits, qui est celui généralement utilisé pour une clé RSA, l’algorithme Shor doit être exécuté sur un ordinateur quantique de plusieurs millions de qubits (bits quantiques). Autrement dit, ça ne va pas arriver dans un futur proche puisque les meilleurs ordinateurs quantiques actuels fonctionnent à 300 – 400 qubits, et ce après des dizaines d’années de recherche.

Ce problème du futur a déjà fait l’objet de diverses réflexions et les experts en sécurité réclament déjà l’adoption d’une cryptographie post-quantique ; autrement dit, des algorithmes qui résistent au piratage effectué par un ordinateur quantique. Il semblerait qu’il faille attendre dix ans ou plus pour une transition en douceur. Ainsi, l’annonce du chiffrement RSA-2048 pour 2023 a fait l’effet d’une bombe.

Des nouvelles de la Chine

Des chercheurs chinois ont pu factoriser une clé de 48 bits sur un ordinateur quantique de 10 qubits. Ils ont calculé qu’ils peuvent escalader l’algorithme et s’en servir pour des clés de 2048 bits avec un ordinateur quantique de 372 qubits seulement. Un tel ordinateur existe déjà, chez IBM notamment, et l’éventuelle substitution de systèmes cryptographiques à travers Internet ne paraît plus si lointaine et ne semble plus être une idée prise à la légère.

Système proposé d’algorithme hybride de factorisation.

L’algorithme de Schnorr est soi-disant utilisé pour avoir une factorisation plus efficace des nombres entiers grâce au calcul classique. Le groupe chinois propose d’utiliser l’optimisation quantique au moment où les calculs informatiques sont les plus intenses.

Des questions ouvertes

La communauté mathématiques a accueilli l’algorithme de Schnorr avec un certain scepticisme. Dans la description de l’étude, l’auteur indiquait que « cela va détruire le système cryptographique RSA « . Cette phrase a été examinée de près et n’a pas fait le poids. Par exemple, le célèbre cryptographe Bruce Scheiner a déclaré que le système  » fonctionne bien avec des modules plus petits, comme ceux testés par le groupe chinois, mais se désagrège avec ceux qui sont plus importants. Personne n’a réussi à prouver que cet algorithme est évolutif en pratique.

L’utilisation de l’optimisation quantique pour la partie la plus  » lourde  » de l’algorithme semble être une bonne idée, mais les experts en informatique quantique doutent de l’efficacité de l’optimisation QAOA pour résoudre ce problème de calcul. On peut effectivement utiliser un ordinateur quantique dans ce cas, mais cela ne va certainement pas faire gagner du temps. Les auteurs mentionnent prudemment ce moment de doute à la fin de leur étude, dans la conclusion :

Il convient de souligner que l’accélération quantique de l’algorithme n’est pas claire à cause de la convergence ambigüe du QAOA.

…

De plus, l’accélération quantique reste inconnue. Il reste beaucoup à faire pour que l’informatique quantique remplace le RSA.

Ainsi, il semblerait que même si vous mettez en place cet algorithme hybride sur un système classique + hybride, il mette autant de temps à deviner les clés RSA qu’un ordinateur classique.

La cerise sur le gâteau est que d’autres paramètres importants doivent être pris en compte en plus du nombre de qubits lorsqu’il s’agit d’un ordinateur quantique : niveaux d’interférences et d’erreurs, ou encore nombre de portes. À en juger par la combinaison des paramètres requis, même les ordinateurs les plus prometteurs de 2023-2024 ne sont probablement pas appropriés pour exécuter l’algorithme chinois à l’échelle voulue.

Quelques conclusions pratiques

Alors que la crypto-révolution est encore une fois remise à plus tard, l’engouement autour de cette étude soulève deux défis en termes de sécurité. Tout d’abord, lorsqu’il faut choisir un algorithme quantique résistant parmi plusieurs propositions afin d’établir une  » norme post-quantique « , les nouvelles approches algébriques, dont l’algorithme de Schnorr susmentionné, doivent être minutieusement étudiées. Ensuite, nous devons assurément considérer les projets de transition vers la cryptographie post-quantique comme une priorité. On pensera que ce problème n’est pas urgent jusqu’à ce qu’il soit trop tard…