
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 qubits dans le monde augmente rapidement. IBM a présenté un QPU de 443 qubits à la fin de l'année dernière et prévoit un système de 1 100 qubits en 2023.
La question de savoir dans combien de temps les ordinateurs NISQ (noisy intermediate scale quantum) ou les approches de recuit quantique non basées sur des portes seront capables de déchiffrer les données RSA fait l'objet d'un débat animé.

Elle a récemment annoncé son intention de développer et de déployer un ordinateur quantique de 64 qubits avec Riken en 2023. Le nouvel ordinateur quantique sera basé sur des qubits supraconducteurs à base de semi-conducteurs - similaires aux approches d'autres sociétés comme IBM, Rigetti et Google. Peu de détails sur le nouvel ordinateur ont été divulgués jusqu'à présent.
La société a lancé son simulateur quantique en 2022 et prévoit d'augmenter sa capacité à 40 qubits au premier trimestre 2023. En 2018, Fujitsu a lancé un service de recycleur numérique : « En utilisant une conception de circuit numérique inspirée des phénomènes quantiques, le recycleur numérique se concentre sur la résolution rapide de problèmes d'optimisation combinatoire complexes sans les complications et les coûts supplémentaires généralement associés aux méthodes de calcul quantique. » L'automne dernier, Fujitsu a conclu un accord avec Toyota pour exploiter sa machine numérique dans des applications de production automobile.
En novembre, Fujitsu a annoncé le développement d'une technologie de calcul hybride quantique/HPC pour optimiser la sélection des charges de travail pour les clients. « Le nouveau logiciel basé sur l'IA, qui sert de précurseur à une future technologie de courtage de charge de travail informatique, sélectionne automatiquement parmi différentes plateformes de calcul de prochaine génération pour offrir la solution optimale aux problèmes des clients en fonction de paramètres tels que le temps de calcul, la précision du calcul et les coûts. »
Le National Institute of Standards and Technology (NIST) a recommandé la normalisation de quatre algorithmes cryptographiques afin de garantir la protection des données à mesure que les ordinateurs quantiques deviennent plus performants.
Les véritables ordinateurs quantiques n'existeraient pas encore
Actuellement, les algorithmes cryptographiques de la Suite B sont spécifiés par le NIST et sont utilisés par L’Agence nationale de la sécurité (NSA) dans des solutions approuvées pour la protection des systèmes de sécurité. La NSA a annoncé en 2015 son intention de passer à des algorithmes cryptographiques résistants aux quanta, en prévision au moment où les ordinateurs quantiques permettront d'accéder aux données chiffrées par les algorithmes actuels, tels que l'Advanced Encryption Standard (AES) et le RSA.
Sur la base de l'expérience acquise lors du déploiement de la Suite B, la NSA a décidé de commencer à planifier et à communiquer rapidement sur la transition à venir vers des algorithmes résistants aux quanta. L’objectif ultime est de fournir une sécurité efficace contre un éventuel ordinateur quantique. « Nous travaillons avec des partenaires du gouvernement américain, des fournisseurs et des organismes de normalisation afin de garantir l'existence d'un plan clair pour l'obtention d'une nouvelle suite d'algorithmes développée de manière ouverte et transparente, qui constituera la base de notre prochaine suite d'algorithmes cryptographiques », déclare l’organisme.
Jusqu'à ce que cette nouvelle suite soit développée et que des produits soient disponibles mettant en œuvre la suite résistante au quantique, la NSA s’appuiera sur les algorithmes actuels. Pour les partenaires et les fournisseurs qui n'ont pas encore effectué la transition vers les algorithmes à courbe elliptique de la Suite B, l’Agence nationale de la sécurité recommande de ne pas engager de dépenses importantes à ce stade, mais plutôt de se préparer à la prochaine transition vers des algorithmes résistants aux quanta.
Dans une de ses récentes sorties, le Dr Nikita Gourianov, physicien chercheur à l'Université d'Oxford, s’en est pris à l'industrie de l'informatique quantique, estimant qu'il s'agit d'une escroquerie. Selon Gourianov, malgré les milliards de dollars investis dans...
La fin de cet article est réservée aux abonnés. Soutenez le Club Developpez.com en prenant un abonnement pour que nous puissions continuer à vous proposer des publications.