Des chercheurs chinois prétendent avoir craqué une clé de chiffrement RSA de 22 bits à l'aide d'un ordinateur quantique D-Wave,

Mais les clés utilisées dans la réalité sont d'une longueur de 2048 à 4096 bits

« 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 l’avis 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 qu’ils prétendent être un algorithme quantique universel pour la factorisation des nombres entiers. L’algorithme 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, c’est un algorithme quantique universel pour la factorisation des entiers qui ne nécessite que des ressources quantiques sublinéaires qui est proposé dans l’article qu’ils 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 qu’ils 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...