« Comment casser le RSA avec un ordinateur quantique ? » le résultat d’une recherche théorique publié par un groupe de chercheurs chinois

Un groupe de chercheurs chinois vient de publier un article affirmant qu’ils peuvent – bien qu’ils ne l’auraient pas encore fait – casser le RSA 2048 bits. Les chercheurs ont combiné les techniques classiques de factorisation par réduction de treillis avec un algorithme d’optimisation approximative quantique, le quantum approximate optimization algorithm (QAOA). De lavis de certains spécialistes, cela signifie qu’ils n’ont eu besoin que d’un ordinateur quantique de 372 qbits, ce qui serait bien en deçà de ce qui est possible aujourd’hui.

L’algorithme de Shor a sérieusement remis en question la sécurité des informations basée sur les systèmes de chiffrement à clé publique. Cependant, pour casser le schéma RSA-2048 largement utilisé, il faudrait des millions de qubits physiques, ce qui est bien au-delà des capacités techniques actuelles. Les chercheurs chinois présentent un algorithme quantique universel pour la factorisation des nombres entiers en combinant la méthode classique du treillis et la méthode de l’équation.

Le groupe de chercheurs chinois a présenté ce quils prétendent être un algorithme quantique universel pour la factorisation des nombres entiers. Lalgorithme combinerait la réduction classique du treillis avec un algorithme d’optimisation approximative, le quantum approximate optimization algorithm. Selon les chercheurs, le nombre de qubits requis est O(logN/loglogN), qui est sous-linéaire dans la longueur de bit de l’entier N, ce qui en fait l’algorithme de factorisation le plus économe en qubits à ce jour.

Montage expérimental et circuit QAOA de l’algorithme de la factorisation en nombres entiers à ressources quantiques sous-linéaires

A, les 10 qubits sélectionnés sur un processeur quantique supraconducteur, chaque qubit étant couplé à ses plus proches voisins par l’intermédiaire de coupleurs accordables en fréquence ;
B, topologie d’interaction native de l’hamiltonien du problème pour le cas de factorisation à 10 qubits, mappée dans une topologie de chaîne décrite en A ;
C, schéma de circuit d’un QAOA à p couches. Tous les qubits qubits sont initialisés en |+i, suivis de p couches d’application répétée de l’hamiltonien du problème (orange) et de l’hamiltonien de mélange (vert), terminées par des mesures de population (gris). Notons que les paramètres variationnels {γ, β} sont différents pour toutes les couches ;
D, Circuit de routage pour l’hamiltonien tout-à-tout à 10 qubits dans la topologie linéaire du plus proche voisin, construit par un maillage de deux blocs SWAP similaires avec deux couches de portes de Hardamard (H) appliquées au début et à la fin, suivies d’une couche de portes Rz(θ). Ici, l’angle de rotation est omis. La profondeur du circuit est proportionnelle au nombre de qubits utilisés ;
E, Compilation détaillée du circuit quantique dans les portes natives du processeur quantique supraconducteur.

Les chercheurs démontrent l’algorithme expérimentalement en factorisant des entiers jusqu’à 48 bits avec 10 qubits supraconducteurs, le plus grand entier factorisé sur un dispositif quantique. Les chercheurs chinois estiment qu’un circuit quantique avec 372 qubits physiques et une profondeur de milliers est nécessaire pour défier RSA 2048 en utilisant, le quantum approximate optimization algorithm.

RSA

Le protocole de chiffrement RSA, qui doit son nom à ses auteurs Rivest, Shamir et Adleman, est l’un des schémas de chiffrement les plus utilisés de nos jours. Il est notamment utilisé dans TLS pour échanger en toute sécurité les clés entre le serveur et le client et protège ainsi la communication entre des sites web ou applications web comme ceux de la banque électronique et les appareils des utilisateurs finaux.

RSA est un schéma cryptographique asymétrique, ce qui signifie que deux clés différentes sont utilisées pour le chiffrement et le déchiffrement. La clé qui est utilisée pour chiffrer les données est appelée clé publique. Comme son nom l’indique, la clé publique est publique et peut être partagée avec toute partie avec laquelle on souhaite communiquer. On s’attend à ce que tout attaquant connaisse également la clé publique. La clé utilisée pour le déchiffrement des données est appelée clé privée. La clé privée doit être gardée secrète et ne peut pas tomber dans les mains de l’attaquant ou être calculée par lui.

La sécurité du protocole RSA repose sur l’hypothèse selon laquelle il est difficile de factoriser un nombre N = p*q, qui est le produit de deux nombres premiers p et q, en ces deux facteurs. L’algorithme connu le plus rapide sur un ordinateur classique a besoin de O(2∛n)

Unités de temps pour accomplir cette tâche, où n est le nombre de bits du nombre N. Ainsi, le temps d’exécution de l’algorithme classique qui reçoit N en entrée et renvoie les deux facteurs p et q en sortie est exponentiel dans le nombre de bits n.

L’algorithme de Shor

Les physiciens utilisent couramment la diffusion d’ondes électromagnétiques et les mesures d’interférence pour déterminer la périodicité d’objets physiques tels que les réseaux cristallins. De même, l’algorithme de Shor exploite les interférences pour mesurer la périodicité des objets arithmétiques.

Bien que tout nombre entier ait une décomposition unique en un produit de nombres premiers, la recherche des facteurs premiers est considérée comme un problème difficile. En fait, la sécurité de nos transactions en ligne repose sur l’hypothèse que la factorisation des nombres entiers à mille chiffres ou plus est pratiquement impossible. Cette hypothèse a été remise en question en 1995 lorsque Peter Shor a proposé un algorithme quantique en temps polynomial pour le problème de la factorisation.

L’algorithme de Shor est sans doute l’exemple le plus spectaculaire de la façon dont le paradigme de l’informatique quantique a modifié notre perception des problèmes qui devraient être considérés comme traitables. Dans cette section, nous résumons brièvement certains faits de base concernant la factorisation, nous soulignons les principaux ingrédients de l’algorithme de Shor et nous illustrons son fonctionnement à l’aide d’un problème de factorisation fictif.

Complexité de la factorisation

Supposons que notre tâche consiste à factoriser un nombre entier N avec des chiffres décimaux d. L’algorithme de force brute passe en revue tous les nombres premiers p jusqu’à √N et vérifie si p divise N. Dans le pire des cas, cela prendrait environ √N, ce qui est exponentiel par rapport au nombre de chiffres d. Un algorithme plus efficace, connu sous le nom de crible quadratique, tente de construire des entiers a,b tels que a²-b² est un multiple de N.

Une fois ces entiers trouvés, on vérifie s’ils ont des facteurs communs avec N. La méthode du crible quadratique a un temps d’exécution asymptotique exponentiel en √d. L’algorithme de factorisation classique le plus efficace, connu sous le nom de tamisage général des champs de nombres, a un temps d’exécution asymptotique exponentiel en d^1/3.

La mise à l’échelle exponentielle du temps d’exécution limite l’applicabilité des algorithmes de factorisation classiques aux nombres de quelques centaines de chiffres ; le record mondial est de d=232 (ce qui a pris environ 2 000 années de calcul ). En revanche, l’algorithme de factorisation de Shor a un temps d’exécution polynomial en d. La version de l’algorithme décrite ci-dessous, due à Alexey Kitaev, nécessite environ 10dqubits et a un temps d’exécution d’environ d 3.

Selon le groupe de chercheurs chinois, cest un algorithme quantique universel pour la factorisation des entiers qui ne nécessite que des ressources quantiques sublinéaires qui est proposé dans larticle quils ont publié. L’algorithme est basé sur l’algorithme classique de Schnorr, qui utilise la réduction de treillis pour factoriser les entiers. « Nous profitons de QAOA pour optimiser la partie la plus chronophage de l’algorithme de Schnorr afin d’accélérer le calcul global de la progression de la factorisation », indiquent les chercheurs.

Pour un entier N de m bits, le nombre de qubits nécessaires pour leur algorithme est O(m/logm), qui est sous-linéaire dans la longueur de bits de N. « Cela en fait l’algorithme quantique le plus économe en qubits pour la factorisation des entiers par rapport aux algorithmes existants, y compris l’algorithme de Shor, indiquent-ils. En utilisant cet algorithme, nous avons réussi à factoriser les entiers 1961 (11 bits), 48567227 (26 bits) et 261980999226229 (48 bits), avec respectivement 3, 5 et 10 qubits dans un processeur quantique supraconducteur », déclare le groupe de chercheurs

L’entier de 48 bits, 261980999226229, représente également le plus grand entier factorisé par une méthode générale dans un dispositif quantique réel. Les chercheurs chinois révèlent quils ont procédé à l’estimation des ressources quantiques nécessaires pour factoriser RSA-2048. « Nous trouvons qu’un circuit quantique avec 372 qubits physiques et une profondeur de plusieurs milliers est nécessaire pour factoriser RSA-2048, même dans le système à chaîne 1D le plus simple. Une telle échelle de ressources quantiques est le plus susceptible d’être atteint sur des dispositifs NISQ dans un avenir proche. »

Flux de travail de l’algorithme de factorisation d’entiers quantiques à ressources sous-linéaires (SQIF). L’algorithme adopte un cadre hybride « classique+quantique », où un optimiseur quantique QAOA est utilisé pour optimiser l’algorithme classique de factorisation de Schnorr.

Tout d’abord, le problème est prétraité comme un problème de closest vector problem (CVP) ou vecteur le plus proche sur un treillis. Ensuite, l’ordinateur quantique fonctionne comme un optimiseur pour affiner les vecteurs classiques calculés par l’algorithme de Babai, et cette étape permet de trouver une solution de meilleure qualité (plus proche) du CVP. Les résultats optimisés seront renvoyés à la procédure de l’algorithme de Schnorr. Après le post-traitement, on obtient finalement les facteurs p et q.

Discussion sur les travaux du groupe de recherche chinois

Selon Bruce Schneier, responsable de l’architecture de sécurité chez Inrupt, l’un des problèmes de l’algorithme du groupe de chercheurs chinois est qu’il reposerait sur un article récent de Peter Schnorr sur la factorisation. « Il s’agit d’un article controversé ; et malgré l’affirmation « ceci détruit le système de chiffrement RSA » dans le résumé, il ne fait rien de tel. L’algorithme de Schnorr fonctionne bien avec de petits modules – du même ordre que ceux testés par le groupe chinois »

Pour Bruce Schneier, il faudrait un gros ordinateur quantique, de l’ordre de millions de qbits, pour factoriser quoi que ce soit qui ressemble aux tailles de clés que nous utilisons aujourd’hui. Ce qui, selon lui, ne dispose pas le groupe de chercheurs chinois. Ils auraient pu factoriser des nombres de 48 bits à l’aide d’un ordinateur quantique de 10 qbits. « Honnêtement, la majeure partie de l’article me dépasse, qu’il s’agisse des mathématiques de réduction du treillis ou de la physique quantique. Et il y a la question lancinante de savoir pourquoi le gouvernement chinois n’a pas classifié cette recherche », écrit Bruce Schneier dans un billet de blog publié le 3 janvier sur son blog Schneier on Security.

Bruce Schneier est un technologue de la sécurité de renommée internationale, qualifié de « gourou de la sécurité » par The Economist. Il est l’auteur de plus d’une douzaine de livres, dont son dernier, We Have Root, ainsi que de centaines d’articles, d’essais et de documents universitaires. Sa lettre d’information influente Crypto-Gram et son blog Schneier on Security sont lus par plus de 250 000 personnes.

Schneier est également membre du Berkman Klein Center for Internet & Society de l’université de Harvard, maître de conférences en politique publique à la Harvard Kennedy School, membre du conseil d’administration de l’Electronic Frontier Foundation et d’AccessNow, et membre du conseil consultatif de l’Electronic Privacy Information Center et de VerifiedVoting.org. Il est le responsable de l’architecture de sécurité chez Inrupt, Inc.

Dans des propos attribués à Roger Grimes, CPA, CISSP, CEH, MCSE, CISA, CISM, CNE, auteur de 13 livres et de plus de 1 100 articles de magazines sur la sécurité informatique, spécialisé dans la sécurité des hôtes et la prévention des attaques de pirates et de logiciels malveillants, Bruce Schneier, le maître de conférences écrit.

« Apparemment, ce qui s’est passé, c’est qu’un autre type qui avait précédemment annoncé qu’il était capable de casser les chiffrements asymétriques traditionnel en utilisant des ordinateurs classiques… mais les examinateurs ont trouvé une faille dans son algorithme et ce dernier a dû retirer son article. Mais cette équipe chinoise s’est rendu compte que l’étape qui empêchait tout pouvait être résolue par de petits ordinateurs quantiques. Ils ont donc fait des essais et ça a marché. »

« Aujourd’hui, RSA est l’un des protocoles de chiffrement les plus utilisés au monde et protège diverses applications des regards indiscrets des attaquants – à moins que ces derniers ne disposent d’un ordinateur quantique. Les propriétés de sécurité du RSA reposent sur l’idée que les ordinateurs ont besoin d’un certain temps pour résoudre un problème difficile. Les ordinateurs quantiques peuvent résoudre certains de ces problèmes beaucoup plus efficacement que les ordinateurs classiques, de sorte qu’ils sont capables de briser le protocole RSA », écrit Noah Berner diplômé en informatique et en ingénierie quantique à l’ETH Zurich.

Outre la sécurité de l’information dans les systèmes complexes de traitement des données, les recherches de Noah Berner portent sur les protocoles de distribution de clés quantiques et les architectures de calcul quantique physique. « Des ordinateurs quantiques suffisamment grands briseront en effet les algorithmes et les protocoles utilisés aujourd’hui pour chiffrer les communications sur l’internet. De tels ordinateurs quantiques sont encore loin, mais nous devons commencer à remplacer les algorithmes et protocoles actuels par des alternatives résistantes aux quanta », soutient Noah Berner.

Pour illustrer ce point, Noah Berner prend l’algorithme RSA-2048, largement utilisé. Selon lui, briser le niveau de sécurité offert par RSA-2048 peut être considéré comme briser l’internet aujourd’hui. Au cours des 30 dernières années, les progrès technologiques ont permis de résoudre des problèmes RSA de plus en plus difficiles et de briser les niveaux de sécurité correspondants :

« En se basant sur ces progrès, on peut s’attendre à ce que RSA-1024 soit cassé d’ici une dizaine d’années, tandis que RSA-2048 reste intact », déclare-t-il. « Avec les ordinateurs quantiques, toutefois, la situation peut changer rapidement : si le cassage de RSA-2048 prend aujourd’hui plus de temps que l’âge de l’univers, un grand ordinateur quantique peut le faire en 8 heures », ajoute-t-il. Lors du Quantum Summit 2022, les experts ont présenté létat des lieux et prévoient que des ordinateurs quantiques capables de casser les chiffrements actuels seront disponibles d’ici 15 à 20 ans.

Source : ARXIV

Et vous ?

Quel est votre avis sur le sujet ?