Les ordinateurs quantiques ne menacent pas encore le chiffrement, selon Fujitsu,

Alors que pour certains spécialistes, les véritables ordinateurs quantiques n'existeraient pas encore

Alors que pour certains spécialistes, l'industrie de l'informatique quantique serait une fumisterie, le fabricant mondial d'ordinateurs et de puces Fujitsu a annoncé le 23 janvier qu'une nouvelle étude réalisée sur son simulateur quantique de 39 qubits suggère qu'il restera difficile pour les ordinateurs quantiques de craquer la cryptographie RSA dans les années à venir. Cette annonce est un prélude à la présentation officielle des résultats de l'étude par Fujitsu lors du Symposium 2023 sur la cryptographie et la sécurité de l'information (SCIS 2023) qui se tient cette semaine à Kitakyushu, au Japon.

Rappelons que l'informatique quantique exploite les propriétés communes des états quantiques, telles que la superposition, l'interférence et l'intrication, pour effectuer des calculs. Bien que les ordinateurs quantiques actuels soient trop petits pour surpasser les ordinateurs habituels (classiques) pour des applications pratiques, on pense qu'ils sont capables de résoudre certains problèmes de calcul, tels que la factorisation des nombres entiers (qui sous-tend le chiffrement RSA), beaucoup plus rapidement que les ordinateurs classiques.


En travaillant avec une version de l'algorithme de Shor, les chercheurs de Fujitsu ont indiqué qu'un ordinateur quantique tolérant aux pannes d'une taille d'environ 10 000 qubits et 2,23 trillions de portes quantiques serait nécessaire pour craquer le RSA, ce qui dépasse largement les ordinateurs quantiques les plus avancés du monde actuel. Les chercheurs ont également estimé qu'il serait nécessaire de mener des calculs quantiques tolérants aux pannes pendant environ 104 jours pour réussir à craquer l'ASR.

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.

« Nos recherches démontrent que l'informatique quantique ne constitue pas une menace immédiate pour les méthodes cryptographiques existantes. Toutefois, nous ne pouvons pas non plus nous reposer sur nos lauriers. Le monde doit commencer à se préparer dès maintenant à la possibilité qu'un jour, les ordinateurs quantiques puissent transformer fondamentalement notre façon de penser la sécurité », a déclaré Tetsuya Izu, directeur principal de la recherche sur les données et la sécurité chez Fujitsu.

Un groupe de chercheurs chinois a publié 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. 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.

RSA

Fujitsu a mené les essais en janvier 2023 en utilisant son simulateur quantique de 39 qubits pour évaluer la difficulté pour les ordinateurs quantiques de craquer la cryptographie RSA existante, en utilisant l'algorithme de Shor pour déterminer les ressources nécessaires pour effectuer une telle tâche. Les chercheurs de Fujitsu ont découvert qu'un ordinateur quantique tolérant aux pannes d'une taille d'environ 10 000 qubits et 2,23 trillions de portes quantiques serait nécessaire pour craquer le système RSA, ce qui dépasse largement les capacités des ordinateurs quantiques les plus avancés du monde actuel. Les chercheurs ont en outre estimé qu'il serait nécessaire de mener des calculs quantiques tolérants aux pannes pendant environ 104 jours pour réussir à craquer l'algorithme 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.

Les derniers travaux portant sur l'algorithme de Shor ont été réalisés sur le simulateur quantique de Fujitsu ; ce système s'appuie sur la technologie développée pour le superordinateur japonais Fugaku (numéro deux de la dernière liste Top500) et sur une technologie spécialisée de manipulation des qubits : « En utilisant un système en grappe basé sur le superordinateur PRIMEHPC FX700 à 512 nœuds de Fujitsu, doté de la CPU A64FX, et une nouvelle technologie qui réarrange automatiquement et efficacement les informations d'état des bits quantiques, Fujitsu a obtenu une augmentation de vitesse de plus de 100 fois par rapport à un système sans réarrangement dans 64 nœuds, et a pu effectuer la factorisation de N = 253 en 463 secondes, ce qui prenait auparavant 16 heures », a déclaré Fujitsu. Plus de détails sur la simulation sont présentés à la fin de l'article.

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.

Il est désormais acquis que lorsque des ordinateurs quantiques tolérants aux pannes et de taille suffisante seront disponibles, l'algorithme de Shor sera en mesure de déchiffrer rapidement les systèmes de chiffrement actuels basés sur la factorisation, y compris RSA. L'été dernier, le National Institute of Technology and Standards (NIST) a publié sa première série de nouveaux algorithmes destinés à remplacer les méthodes RSA actuelles. Nombreux sont ceux qui préviennent que les acteurs malveillants sont dorénavant engagés dans des stratégies dites « Stocker maintenant/Déchiffrer plus tard ».

Comme on pouvait s'y attendre, l'élaboration de mesures visant à empêcher les ordinateurs quantiques de casser les méthodes de chiffrement modernes - notamment RSA - fait l'objet de recherches intenses et de débats animés au sein de la communauté quantique. Tout le monde ne pense pas que la menace soit aussi éloignée que le rapporte Fujitsu. Le nombre de...