IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Les ordinateurs quantiques pourraient craquer le chiffrement d'Internet plus rapidement que prévu grâce à un nouvel algorithme
Supposément plus efficace que l'algorithme de Shor vieux de 30 ans

Le , par Mathis Lucas

29PARTAGES

13  0 
Un algorithme quantique menace de rendre inutiles nos principaux systèmes cryptographiques plus rapidement que prévu. Dans un article de recherche publié récemment, un informaticien à l'université de New York décrit un nouvel algorithme quantique qui serait une version améliorée de l'algorithme de Shor, un algorithme quantique qui factorise un entier naturel n en temps O((\log N)^{3}) et en espace O(\log N). Une analyse préliminaire estime que l'algorithme découvert par le chercheur de l'université de New York propose un schéma qui pourrait réduire considérablement le nombre de portes, ou d'étapes logiques, nécessaires pour factoriser de très grands nombres.

Un nouvel algorithme quantique menace les systèmes de chiffrement actuels sur Internet

L'informatique quantique fait l'objet d'un battage médiatique constant, mais des points d'interrogation importants subsistent quant à l'utilité réelle des ordinateurs quantiques. L'on espère que l'informatique quantique va contribuer aux processus de recherche de données volumineuses, ainsi qu'au développement rapide de l'IA et de l'apprentissage automatique. L'informatique quantique pourrait même révolutionner nos sources d'énergie domestique, en fournissant de l'énergie électrique basée sur les processus de fusion nucléaire. Cependant, on ne sait toujours pas dans quelle mesure les ordinateurs quantiques seront plus pratiques et plus rapides.


Les chercheurs semblent toutefois unanimes sur un point : un ordinateur quantique suffisamment puissant pourrait craquer les algorithmes de chiffrement existants. Il remettrait ainsi en cause la sécurité des données en ligne et exposerait des systèmes hautement sensibles à toute sorte de violation. Les énigmes mathématiques qui sous-tendent les principaux systèmes cryptographiques actuels sont pratiquement insolubles pour les ordinateurs classiques, mais elles seraient tout à fait accessibles à un ordinateur quantique suffisamment puissant. Toutefois, les processeurs quantiques d'aujourd'hui sont loin d'atteindre l'échelle requise pour les craquer.

En 1994, Peter Shor, chercheur en mathématiques appliquées au MIT, s'est lancé sur cette voie et a proposé un algorithme révolutionnaire pour y parvenir. Connu pour son travail sur le calcul quantique, Shor a montré comment un ordinateur quantique pouvait être exponentiellement plus rapide qu'un ordinateur classique pour trouver les facteurs premiers de grands nombres. Ces nombres premiers composent les clés secrètes utilisées pour sécuriser la plupart des informations chiffrées envoyées sur Internet. Depuis sa découverte, il y a 30 ans, l'algorithme de Shor est considéré comme un exemple des promesses des ordinateurs quantiques.

Aujourd'hui, Oded Regev, un informaticien de l'université de New York, a révélé un nouvel algorithme quantique qui pourrait être meilleur que celui de Shor. Dans un article publié sur le serveur arXiv le 12 août, Regev propose un schéma qui pourrait réduire considérablement le nombre de portes, ou d'étapes logiques, nécessaires pour factoriser de très grands nombres. En principe, cela pourrait permettre à un ordinateur quantique plus petit de découvrir les clés de cryptage secrètes ou à une machine plus grande de les décoder plus rapidement. « Cela aura-t-il un effet réel ? Mon sentiment est que oui, cela pourrait avoir une chance », a-t-il déclaré.

Les cryptographes indépendants ayant évalué le travail semblent intrigués. « Dans le monde de l'informatique quantique, deux ou trois nouvelles idées sont apparues au cours des 30 dernières années, depuis Shor. On ne voit pas ces nouvelles idées tous les jours, et c'est ce qui nous donne de l'espoir », note Vinod Vaikuntanathan, informaticien au MIT. Kenneth Brown, chercheur en informatique quantique à l'université de Duke, affirme : « comme tout le monde étudie l'algorithme de Shor depuis longtemps, ce résultat est surprenant et super cool ». Il s'attend à une salle comble le mois prochain lorsque Regev présentera son nouvel algorithme en novembre.

Les chercheurs affirment qu'une amélioration de l'algorithme de Shor serait une prouesse

Comme tous les algorithmes quantiques, l'algorithme de Shor repose sur les propriétés mystérieuses des bits quantiques (qubits) qui peuvent être réglés sur des valeurs non seulement 0 et 1, mais également sur une superposition de 0 et 1 en même temps. De petits nombres de ces qubits peuvent être assemblés pour former des portes, qui exécutent les opérations logiques d'un algorithme. Pour factoriser un nombre de n bits, l'algorithme de Shor nécessite un circuit quantique de n2 portes. Selon un récent article de Science, la plupart des chiffrements sur Internet reposent désormais sur des nombres d'au moins 2 048 bits.

Ainsi, trouver leurs facteurs premiers avec l'algorithme de Shor nécessiterait donc des ordinateurs quantiques dotés d'au moins 4 millions de portes. Or, les plus puissants ordinateurs quantiques à ce jour ne possèdent que quelques centaines de qubits. « Aucun d'entre eux n'atteint la puissance nécessaire pour factoriser des nombres qui nous intéressent », explique Brown. En outre, le bruit ambiant détruit souvent les délicats états de superposition des qubits, ruinant ainsi l'opération. Selon Vaikuntanathan, il est possible de remédier au bruit en corrigeant les erreurs, mais cela nécessite encore plus de qubits - des millions, voire des milliards.

« La correction d'erreurs fait vraiment exploser le système. C'est pourquoi nous sommes encore loin de pouvoir factoriser des nombres à 1 000 chiffres. L'amélioration de la correction des erreurs serait utile, mais l'amélioration de l'algorithme de Shor le serait tout autant », explique-t-il. Dans son rapport, Regev affirme avoir trouvé un moyen d'y parvenir. L'algorithme de Shor est 1D. Il recherche les facteurs premiers en élevant un seul nombre à des puissances élevées. Plusieurs grands nombres doivent être multipliés ensemble avant d'obtenir un résultat. Regev a réalisé qu'il pouvait multiplier plusieurs nombres dans différentes dimensions.

Les puissances d'un même nombre ne sont pas aussi élevées. Selon une analyse préliminaire, bien que les algorithmes de Shor et de Regev nécessitent à peu près le même nombre total de multiplications, le caractère multidimensionnel de celui de Regev signifie que les nombres multipliés ne sont pas aussi grands avant d'obtenir un résultat. Finalement, il a constaté qu'il n'avait besoin que de n1,5 portes pour factoriser un entier de n bits. « Il s'agit de la première amélioration substantielle de l'algorithme de Shor depuis 30 ans. Personne n'a vraiment réussi à faire mieux que de réduire un peu la taille de l'algorithme », affirme Vaikuntanathan.

Le nouvel algorithme quantique de Regev présente également quelques inconvénients

Martin Ekerå, chercheur en informatique quantique auprès du gouvernement suédois, explique que l'algorithme de Regev présente aussi des inconvénients. Regev dit avoir consulté le chercheur Ekerå pour comprendre les implications pratiques de son travail. « Sa structure semble nécessiter une mémoire quantique pour stocker les valeurs intermédiaires pendant le calcul, ce qui signifie qu'il faut davantage de ces qubits si délicats. Cela augmente le coût de l'algorithme », explique Ekerå. Regev reconnaît que les exigences en matière de mémoire posent problème, mais il estime que l'algorithme pourrait tout de même s'avérer utile.

« Cet algorithme pourrait s'avérer très utile lorsque la mémoire sera moins chère et que nous nous préoccuperons plutôt du nombre d'opérations », a déclaré Regev. Il est difficile de prédire le moment où cela arrivera en raison des progrès relativement lents dans le domaine de l'informatique quantique. Selon le rapport Science, lorsque les ordinateurs quantiques seront prêts à trouver les facteurs premiers en appliquant l'algorithme de Regev ou de Shor, le chiffrement d'Internet aura peut-être évolué. Conscients de la menace, les experts en cryptographie se dépêchent pour mettre au point de nouveaux algorithmes qui seront à l'épreuve des quanta.

Certains chercheurs se tournent déjà vers des solutions telles que la cryptographie dite en treillis, qui serait à l'abri du piratage quantique. La cryptographie basée sur les treillis utilise une simple algèbre linéaire pour chiffrer les données. Elle comprend des treillis, des vecteurs et des bases qui sont utilisés pour construire un modèle difficile. Le National Institute of Standards and Technology (NIST) des États-Unis travaille également sur le sujet et a recommandé l'année dernière la normalisation de nouveaux algorithmes cryptographiques afin de garantir la protection des données à mesure que les ordinateurs quantiques deviennent plus performante.

Mais les chercheurs en informatique quantique affirment que cela n'écarte pas totalement les risques que posent les ordinateurs quantiques. « Des algorithmes comme ceux de Regev et Shor pourraient être appliqués rétroactivement, pour déchiffrer le trafic enregistré dans le présent et le passé récent », explique Ekerå. Sans les ordinateurs quantiques, l'un des quatre algorithmes de chiffrement recommandés par le NIST comme étant susceptibles de résister aux quanta a été craqué en une heure par des chercheurs utilisant un seul cœur d'un processeur Intel Xeon, sorti en 2013. Ils se sont appuyés sur les mathématiques pures pour le craquer.

Quoi qu'il en soit, Brown estime que la nouveauté même des travaux de Regev est susceptible d'inspirer et de générer d'autres idées nouvelles dans le domaine de la cryptographie quantique, qui a eu du mal à faire des percées significatives. « J'essaie moi-même de réfléchir à des moyens d'aller plus loin », a déclaré Brown.

Source : rapport de l'étude

Et vous ?

Quel est votre avis sur le sujet ?
Que pensez-vous de l'algorithme de factorisation quantique décrit ci-dessus ?
Que représente cette découverte pour les systèmes de chiffrement classiques ?
Les ordinateurs quantiques capables d'exploiter ces algorithmes sont-ils pour bientôt ?
Pensez-vous que les algorithmes de chiffrement actuels résisteront encore longtemps aux quanta ?

Voir aussi

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

Un algorithme candidat au chiffrement post-quantique est craqué par un PC utilisant un seul cœur et en 1 heure, les chercheurs se sont appuyés sur les mathématiques pures pour le craquer

Les véritables ordinateurs quantiques n'existeraient pas encore, mais le chiffrement pour les déjouer pourrait déjà exister

Une erreur dans cette actualité ? Signalez-nous-la !

Avatar de UrbainV
Futur Membre du Club https://www.developpez.com
Le 21/01/2024 à 21:03
Contrairement au XXe siècle où les avancées scientifiques et technologiques étaient perçues comme un chemin vers le progrès et le bien-être de l'humanité (à part la bombe atomique), au XXIe siècle, nombre d'évolutions technologiques sont sources d'angoisse. A juste titre ou pas selon les cas. Par exemple, les vaccins à ARN, l'AI, l'informatique quantique. On a l'impression d'une fuite en avant qui mériterait une pause pour réfléchir aux conséquences de nos actes et prendre les mesures nécessaires pour n'en garder que le meilleur et réduire les risques systémiques.
4  0 
Avatar de petitours
Membre émérite https://www.developpez.com
Le 21/01/2024 à 21:25
Cet article serait à montrer à tous les responsables SI qui mettent tout sur le cloud parce que c'est à la mode.
Les seuls qui ne se feront pas exploser par les prières attaques seront ceux qui ont tout fermé en local et qui auront ainsi le temps de passer au papier et crayon avant d'être en panne puisque 100% des échanges basés sur la confiance (https and co) perdront la confiance en un rien de temps.

Comme l'IA, le quantique ne fait rêver que les passionnés qui oublient le sens de la vie.
Aujourd'hui la puissance de calcul on ne l'utilise qu'à faire des jeux ou priver des gens d'activité. Ce n'est pas simple d'admettre qu'un truc est inutile ou nuisible et ceux qui ont la force de le voir et l'admettre ne sont pas visibles à coté des illuminés.
3  0 
Avatar de calvaire
Expert éminent https://www.developpez.com
Le 21/01/2024 à 22:32
faut relativiser quand meme, c'est du marketing de la peur pour vendre des ordinateurs quantique jusqu'a la petite pme paumé dans les montagnes.

il existe déja plusieurs algos capable de résister au (théorique) quantique, comme kyber.
théorique car les ordi quantique pour l'heure ca reste de vague poc tres loins d'ordi utilisable par une puissance étrangere.

par contre ca fait de belle levé de fond avec l'ia.

et enfin, les usa n'ont pas besoin du quantique, il y'a surrement assez de backdoor dans l'os windows, le cpu intel, le routeur cisco et le cloud azure pour récupérer les données en clair.
3  0 
Avatar de pierre.E
Membre confirmé https://www.developpez.com
Le 30/01/2024 à 19:51
pour le moment un ordinateur quantique c'est surtout un gros congélateur.
3  0 
Avatar de petitours
Membre émérite https://www.developpez.com
Le 12/10/2023 à 15:26
ouais, super, vive l'IA et le quantique qui vont beaucoup nous apporter parait il.
2  0 
Avatar de Christ D
Membre régulier https://www.developpez.com
Le 26/01/2024 à 11:42
IA, ordinateurs quantiques, block chains :

Ces domaines sont difficiles à comprendre pour les "non spécialistes" hors, ils nécessite des investissements important.

De nombreux riches investisseurs y voient donc la nouvelle bulle dans laquelle il faut absolument investir (à l'image de la folie des années 90-2000 qui ont donné naissances aux GAFA)

Qui dit investissement dit bluff, buzz : c'est le nerf de la guerre : forcer son concurrent à investir fortement en le faisant tomber dans tel ou tel bluff juste pour qu'il y laisse des plumes. C'est ainsi que les USA ont gagné la guerre froide !

Et comme les gouvernements s'appuient de plus en plus sur le privé. Des malins montent de belles supercheries pour obtenir des fonds de l'état sous la forme de millions d'euros.

On ne compte plus les supercherie en la matière. La dernière en date (eco taxe) a coûté des milliard à l'état Français.

De la même manière, nombreux sont ceux qui ont investi dans les crypto-monnaies (qui utilise les blockchain, expression très à la mode alors que 1% des utilisateurs de cette expression savent de quoi il retourne) et qui y ont laissé beaucoup de plumes.

Alors de tout cela, quelle techno est une arlésienne, laquelle est une supercherie, et dans laquelle faut-il vraiment investir ? Et pour nous, professionnels, dans laquelle devons nous nous investir pour ne pas devenir des "nold" bon pour la casse ?

On s'y perd totalement.
2  0 
Avatar de _toma_
Membre confirmé https://www.developpez.com
Le 24/10/2024 à 1:21
encore une fausse annonce chinoise. qui fait que maintenant ca va gacher toutes les futures vraies annonces.
Encore une vraie annonce scientifique tournée en épingle par les médias.

Chinois ou pas chinois.

Le titre du premier article est assez explicite : ils ont cassé du RSA 22bits.
C'est juste un PoC. Le premier article était à mon avis suffisamment explicite et moins sujet à polémique.

Dit autrement :
- le premier article est factuel et s'adresse à des plus-ou-moins techniciens
- le deuxième article est la conséquence d'une phase de vulgarisation/sensationnalisme outrancière et les gens qui n'ont pas compris ce qu'ils lisaient ont cru que RSA était mort

Tant pis pour eux. ils restent a mes yeux dans leur status de copieur de talent du coup.
Je t'invite à te renseigner un peu sur notre histoire. Et sur l'histoire des autres pays/civilisations.
Je suis pas sûr que ce soit la bonne vidéo vu que leur site est hors ligne pour l'instant :
https://archive.org/details/LuxeColbert
Si c'est pas la bonne vidéo, tu peux taper "louis xv espionnage industriel" ou "louis xvi espionnage industriel" dans un moteur de recherche et tu verras qu'on était plutôt performants.
En gros, pour résumer : la balance commerciale française était négative. Pour l'équilibrer, nos dirigeants lancent une campagne d'espionnage industriel pour voler des techniques de fabrication, les rapatrier en France, ouvrir des manufactures puis produire sur place (donc faire moins d'export donc rééquilibrer la balance)
Laque de chine, porcelaine, verrerie, mirroirs et sans doute plein d'autres choses y sont passées. En priorité des produits de luxe, donc des produits avec un fort savoir-faire (les tabourets on savait faire donc on n'en importait pas ).

Pour en revenir à nos petits chinois, ils n'ont qu'un statut de "copieur" parce que c'est la seule chose que l'économie mondiale leur laissait comme place. Maintenant qu'ils ont travaillé à la chaîne pour pas cher et qu'on a acheté tout ce qu'on leur avait demandé de fabriquer, leur économie leur permet de faire autre chose que de l'agriculture et de la production de masse.

Ne soit pas trop impatient, le retour de bâton arrivera bien avant que tu ne le veuilles .
2  0 
Avatar de Flodelarab
Expert éminent sénior https://www.developpez.com
Le 28/10/2024 à 14:29
Citation Envoyé par _toma_ Voir le message
Encore une vraie annonce scientifique tournée en épingle par les médias..
"Montée en épingle" ou "tournée en dérision", mais "tournée en épingle", cela ne veut rien dire.
2  0 
Avatar de _toma_
Membre confirmé https://www.developpez.com
Le 02/10/2024 à 13:08
<troll>
Informatique quantique : pourquoi les gouvernements attendent cette technologie, un domaine qui pourrait permettre le déchiffrement massif de données volées
</troll>
2  1 
Avatar de floyer
Membre éclairé https://www.developpez.com
Le 15/10/2024 à 18:19
« Les techniques SPN sont au cœur des normes telles que RSA (Rivest-Shamir-Adleman) et AES (Advanced Encryption Standard). ».

Euh… RSA utiliserait des substitutions ? Non juste de l’arithmétique.

Par ailleurs AES est un algorithme symétrique. On ne peut déchiffrer un message que si on en connaît des caractéristiques (comme on fait les anglais avec Enigma). Ce n’est pas aussi simple que RSA où la clé publique est connue par définition. Ainsi, la portée d’une attaque peut être limitée en pratique.

D’ailleurs dans l’article source, les mots clés incluent RSA mais pas AES ni SPN. Le titre de l’article parle de « public key cryptography ». Ceci-dit on trouve d’autres sources avec des attaques de SPN (nota, la page Wikipedia de AES indique des attaques réussies sur des versions simplifiées… donc entre casser un algorithme de type SPN et casser AES-256, il peut y avoir in gros pas).
1  0