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 rduction de treillis avec un algorithme d’optimisation approximative quantique, le quantum approximate optimization algorithm (QAOA). De lavis de certains spcialistes, cela signifie qu’ils n’ont 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 srieusement remis en question la scurit des informations base sur les systmes de chiffrement cl publique. Cependant, pour casser le schma RSA-2048 largement utilis, il faudrait des millions de qubits physiques, ce qui est bien au-del des capacits techniques actuelles. Les chercheurs chinois prsentent un algorithme quantique universel pour la factorisation des nombres entiers en combinant la mthode classique du treillis et la mthode de l’quation.
Le groupe de chercheurs chinois ont prsent ce quils prtendent tre un algorithme quantique universel pour la factorisation des nombres entiers. Lalgorithme combinerait la rduction 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-linaire 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 exprimental et circuit QAOA de l’algorithme de la factorisation en nombres entiers ressources quantiques sous-linaires
- A, les 10 qubits slectionns sur un processeur quantique supraconducteur, chaque qubit tant coupl ses plus proches voisins par l’intermdiaire de coupleurs accordables en frquence ;
- B, topologie d’interaction native de l’hamiltonien du problme pour le cas de factorisation 10 qubits, mappe dans une topologie de chane dcrite en A ;
- C, schma de circuit d’un QAOA p couches. Tous les qubits qubits sont initialiss en |+i, suivis de p couches d’application rpte de l’hamiltonien du problme (orange) et de l’hamiltonien de mlange (vert), termines par des mesures de population (gris). Notons que les paramtres variationnels {γ, β} sont diffrents pour toutes les couches ;
- D, Circuit de routage pour l’hamiltonien tout–tout 10 qubits dans la topologie linaire du plus proche voisin, construit par un maillage de deux blocs SWAP similaires avec deux couches de portes de Hardamard (H) appliques au dbut 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 utiliss ;
- E, Compilation dtaille du circuit quantique dans les portes natives du processeur quantique supraconducteur.
Les chercheurs dmontrent l’algorithme exprimentalement 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 ncessaire pour dfier 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 schmas de chiffrement les plus utiliss de nos jours. Il est notamment utilis dans TLS pour changer en toute scurit les cls entre le serveur et le client et protge 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 schma cryptographique asymtrique, ce qui signifie que deux cls diffrentes sont utilises pour le chiffrement et le dchiffrement. La cl qui est utilise pour chiffrer les donnes est appele cl publique. Comme son nom l’indique, la cl publique est publique et peut tre partage avec toute partie avec laquelle on souhaite communiquer. On s’attend ce que tout attaquant connaisse galement la cl publique. La cl utilise pour le dchiffrement des donnes est appele cl prive. La cl prive doit tre garde secrte et ne peut pas tomber dans les mains de l’attaquant ou tre calcule par lui.
La scurit du protocole RSA repose sur l’hypothse 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)
Units de temps pour accomplir cette tche, o n est le nombre de bits du nombre N. Ainsi, le temps d’excution de l’algorithme classique qui reoit N en entre 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 lectromagntiques et les mesures d’interfrence pour dterminer la priodicit d’objets physiques tels que les rseaux cristallins. De mme, l’algorithme de Shor exploite les interfrences pour mesurer la priodicit des objets arithmtiques.
Bien que tout nombre entier ait une dcomposition unique en un produit de nombres premiers, la recherche des facteurs premiers est considre comme un problme difficile. En fait, la scurit de nos transactions en ligne repose sur l’hypothse que la factorisation des nombres entiers mille chiffres ou plus est pratiquement impossible. Cette hypothse a t remise en question en 1995 lorsque Peter Shor a propos un algorithme quantique en temps polynomial pour le problme de la factorisation.
L’algorithme de Shor est sans doute l’exemple le plus spectaculaire de la faon dont le paradigme de l’informatique quantique a modifi notre perception des problmes qui devraient tre considrs comme traitables. Dans cette section, nous rsumons brivement certains faits de base concernant la factorisation, nous soulignons les principaux ingrdients de l’algorithme de Shor et nous illustrons son fonctionnement l’aide d’un problme de factorisation fictif.
Complexit de la factorisation
Supposons que notre tche consiste factoriser un nombre entier N avec des chiffres dcimaux d. L’algorithme de force brute passe en revue tous les nombres premiers p jusqu’ √N et vrifie 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 a2-b2 est un multiple de N.
Une fois ces entiers trouvs, on vrifie s’ils ont des facteurs communs avec N. La mthode du crible quadratique a un temps d’excution asymptotique exponentiel en √d. L’algorithme de factorisation classique le plus efficace, connu sous le nom de tamisage gnral des champs de nombres, a un temps d’excution asymptotique exponentiel en d1/3.
La mise l’chelle exponentielle du temps d’excution 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 annes de calcul ). En revanche, l’algorithme de factorisation de Shor a un temps d’excution polynomial en d. La version de l’algorithme dcrite ci-dessous, due Alexey Kitaev, ncessite environ 10dqubits et a un temps d’excution d’environ d 3.
Selon le groupe de chercheurs chinois, cest un algorithme quantique universel pour la factorisation des entiers qui ne ncessite que des ressources quantiques sublinaires qui est propos dans larticle quils ont publi. L’algorithme est bas sur l’algorithme classique de Schnorr, qui utilise la rduction de treillis pour factoriser les entiers. Nous profitons de QAOA pour optimiser la partie la plus chronophage de l’algorithme de Schnorr afin d’acclrer le calcul global de la progression de la factorisation , indiquent les chercheurs.
Pour un entier N de m bits, le nombre de qubits ncessaires pour leur algorithme est O(m/logm), qui est sous-linaire 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 russi 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 , dclare le groupe de chercheurs
L’entier de 48 bits, 261980999226229, reprsente galement le plus grand entier factoris par une mthode gnrale dans un dispositif quantique rel. Les chercheurs chinois rvlent quils ont procd l’estimation des ressources quantiques ncessaires pour factoriser RSA-2048. Nous trouvons qu’un circuit quantique avec 372 qubits physiques et une profondeur de plusieurs milliers est ncessaire pour factoriser RSA-2048, mme dans le systme chane 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-linaires (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 problme est prtrait comme un problme 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 calculs par l’algorithme de Babai, et cette tape permet de trouver une solution de meilleure qualit (plus proche) du CVP. Les rsultats optimiss seront renvoys la procdure de l’algorithme de Schnorr. Aprs 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 scurit chez Inrupt, l’un des problmes de l’algorithme du groupe de chercheurs chinois est qu’il reposerait sur un article rcent de Peter Schnorr sur la factorisation. Il s’agit d’un article controvers ; et malgr l’affirmation ceci dtruit le systme de chiffrement RSA dans le rsum, il ne fait rien de tel. L’algorithme de Schnorr fonctionne bien avec de petits modules – du mme ordre que ceux tests 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 cls 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. Honntement, la majeure partie de l’article me dpasse, qu’il s’agisse des mathmatiques de rduction 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 scurit de renomme internationale, qualifi de gourou de la scurit 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, matre de confrences 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 scurit chez Inrupt, Inc.
Dans des propos attribus Roger Grimes, CPA, CISSP, CEH, MCSE, CISA, CISM, CNE, auteur de 13 livres et de plus de 1 100 articles de magazines sur la scurit informatique, spcialis dans la scurit des htes et la prvention des attaques de pirates et de logiciels malveillants, Bruce Schneier, le matre de confrences crit :
Apparemment, ce qui s’est pass, c’est qu’un autre type qui avait prcdemment annonc qu’il tait capable de casser les chiffrements asymtriques 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 empchait tout pouvait tre rsolue 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 utiliss au monde et protge diverses applications des regards indiscrets des attaquants – moins que ces derniers ne disposent d’un ordinateur quantique. Les proprits de scurit du RSA reposent sur l’ide que les ordinateurs ont besoin d’un certain temps pour rsoudre un problme difficile. Les ordinateurs quantiques peuvent rsoudre certains de ces problmes beaucoup plus efficacement que les ordinateurs classiques, de sorte qu’ils sont capables de briser le protocole RSA , crit Noah Berner diplm en informatique et en ingnierie quantique l’ETH Zurich.
Outre la scurit de l’information dans les systmes complexes de traitement des donnes, les recherches de Noah Berner portent sur les protocoles de distribution de cls quantiques et les architectures de calcul quantique physique. Des ordinateurs quantiques suffisamment grands briseront en effet les algorithmes et les protocoles utiliss 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 rsistantes aux quanta , soutient Noah Berner.
Pour illustrer ce point, Noah Berner prend l’algorithme RSA-2048, largement utilis. Selon lui, briser le niveau de scurit offert par RSA-2048 peut tre considr comme briser l’internet aujourd’hui. Au cours des 30 dernires annes, les progrs technologiques ont permis de rsoudre des problmes RSA de plus en plus difficiles et de briser les niveaux de scurit correspondants :
En se basant sur ces progrs, on peut s’attendre ce que RSA-1024 soit cass d’ici une dizaine d’annes, tandis que RSA-2048 reste intact , dclare-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 prsent ltat des lieux et prvoient 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 ?
Accordez-vous du crdit aux conclusions des travaux du groupe de recherche chinois ?
Voir aussi :