Comment un ordinateur quantique pourrait casser le cryptage RSA 2048 bits en 8 heures

Gros plan sur la puce D-Wave Vesuvius Steve Jurvetson | Flickr

Beaucoup de gens craignent que les ordinateurs quantiques soient capables de déchiffrer certains codes utilisés pour envoyer des messages sécurisés. Les codes en question chiffrent les données à l'aide de fonctions mathématiques à trappe qui fonctionnent facilement dans un sens mais pas dans l'autre. Cela rend le cryptage des données facile mais le décodage extrêmement difficile sans l'aide d'une clé spéciale.

Ces systèmes de cryptage n'ont jamais été incassables. Au lieu de cela, leur sécurité est basée sur l'énorme quantité de temps qu'il faudrait à un ordinateur classique pour faire le travail. Les méthodes de cryptage modernes sont spécialement conçues pour que leur décodage prenne tellement de temps qu'elles soient pratiquement incassables.

Mais les ordinateurs quantiques changent cette façon de penser. Ces machines sont bien plus puissantes que les ordinateurs classiques et devraient être capables de casser ces codes facilement.

Cela soulève une question importante : quand les ordinateurs quantiques seront-ils assez puissants pour faire cela ? Après cette date, toute information protégée par cette forme de cryptage devient non sécurisée.

Les informaticiens ont donc tenté de calculer les ressources dont un tel ordinateur quantique pourrait avoir besoin, puis de déterminer combien de temps il faudra avant qu'une telle machine puisse être construite. Et la réponse a toujours été des décennies.

Aujourd'hui, cette réflexion doit être révisée grâce aux travaux de Craig Gidney de Google à Santa Barbara et de Martin Ekerå au KTH Royal Institute of Technology de Stockholm, en Suède. Ces gars-là ont trouvé un moyen plus efficace pour les ordinateurs quantiques d'effectuer les calculs de rupture de code, réduisant les ressources dont ils ont besoin par des ordres de grandeur.

Par conséquent, ces machines sont beaucoup plus proches de la réalité que quiconque ne le soupçonnait. Le résultat rendra la lecture inconfortable pour les gouvernements, les organisations militaires et de sécurité, les banques et toute autre personne ayant besoin de sécuriser des données pendant 25 ans ou plus.

Tout d'abord un peu de contexte. En 1994, le mathématicien américain Peter Shor a découvert un algorithme quantique qui surpassait son équivalent classique. L'algorithme de Shor factorise de grands nombres et constitue l'élément crucial du processus de craquage des codes basés sur des trappes.

Les fonctions de trappe sont basées sur le processus de multiplication, qui est facile à effectuer dans un sens mais beaucoup plus difficile à faire dans le sens inverse. Par exemple, il est trivial de multiplier deux nombres ensemble : 593 fois 829 font 491 597. Mais il est difficile de commencer avec le nombre 491 597 et de déterminer quels sont les deux nombres premiers qui doivent être multipliés pour le produire.

Et cela devient de plus en plus difficile à mesure que les chiffres augmentent. En effet, les informaticiens considèrent qu'il est pratiquement impossible pour un ordinateur classique de factoriser des nombres supérieurs à 2048 bits, ce qui est à la base de la forme de cryptage RSA la plus couramment utilisée.

Shor a montré qu'un ordinateur quantique suffisamment puissant pouvait le faire facilement, un résultat qui a envoyé des ondes de choc dans l'industrie de la sécurité.

Et depuis, les ordinateurs quantiques sont de plus en plus puissants. En 2012, les physiciens ont utilisé un ordinateur quantique à quatre qubits pour factoriser 143. Puis en 2014, ils ont utilisé un appareil similaire pour factoriser 56 153.

Il est facile d'imaginer qu'à ce rythme de progrès, les ordinateurs quantiques devraient bientôt être en mesure de surpasser les meilleurs classiques.

Pas si. Il s'avère que l'affacturage quantique est beaucoup plus difficile dans la pratique que ce à quoi on pourrait s'attendre autrement. La raison en est que le bruit devient un problème important pour les grands ordinateurs quantiques. Et la meilleure façon actuellement de lutter contre le bruit est d'utiliser des codes de correction d'erreur qui nécessitent eux-mêmes des qubits supplémentaires importants.

En tenir compte augmente considérablement les ressources nécessaires pour factoriser des nombres de 2048 bits. En 2015, des chercheurs ont estimé qu'un ordinateur quantique aurait besoin d'un milliard de qubits pour faire le travail de manière fiable. C'est nettement plus que les 70 qubits des ordinateurs quantiques de pointe d'aujourd'hui.

Sur cette base, les experts en sécurité auraient bien pu justifier l'idée qu'il faudrait des décennies avant que les messages avec un cryptage RSA 2048 bits puissent être brisés par un ordinateur quantique.

Maintenant, Gidney et Ekerå ont montré comment un ordinateur quantique pouvait faire le calcul avec seulement 20 millions de qubits. En effet, ils montrent qu'un tel appareil ne prendrait que huit heures pour effectuer le calcul. [En conséquence], la pire estimation du nombre de qubits nécessaires pour factoriser des entiers RSA de 2048 bits a chuté de près de deux ordres de grandeur, disent-ils.

Leur méthode se concentre sur une manière plus efficace d'effectuer un processus mathématique appelé exponentiation modulaire. C'est le processus de recherche du reste lorsqu'un nombre est élevé à une certaine puissance puis divisé par un autre nombre.

Ce processus est l'opération la plus coûteuse en calcul de l'algorithme de Shor. Mais Gidney et Ekerå ont trouvé différentes façons de l'optimiser, réduisant considérablement les ressources nécessaires pour exécuter l'algorithme.

C'est un travail intéressant qui devrait avoir des implications importantes pour quiconque stocke des informations pour l'avenir. Un ordinateur quantique de 20 millions de qubits semble certainement un rêve lointain aujourd'hui. Mais la question que ces experts devraient se poser est de savoir si un tel dispositif pourrait être possible dans les 25 ans qu'ils souhaitent pour sécuriser les informations. S'ils pensent que c'est le cas, ils ont besoin d'une nouvelle forme de cryptage.

En effet, les experts en sécurité ont développé des codes post-quantiques que même un ordinateur quantique ne pourra pas déchiffrer. Il est donc déjà possible de protéger les données aujourd'hui contre les attaques futures des ordinateurs quantiques. Mais ces codes ne sont pas encore utilisés en standard.

Pour les gens ordinaires, il y a peu de risques. La plupart des gens utilisent un cryptage 2048 bits, ou quelque chose de similaire, pour des tâches telles que l'envoi de détails de carte de crédit sur Internet. Si ces transactions sont enregistrées aujourd'hui et rompues dans 25 ans, peu de choses seront perdues.

Mais pour les gouvernements, il y a plus en jeu. Les messages qu'ils envoient aujourd'hui – entre ambassades ou militaires, par exemple – pourraient bien être significatifs dans 20 ans et donc mériter d'être gardés secrets. Si de tels messages sont toujours envoyés via un cryptage RSA 2048 bits, ou quelque chose de similaire, ces organisations devraient commencer à s'inquiéter rapidement.

Réf : arxiv.org/abs/1905.09749 : Comment factoriser des entiers RSA de 2048 bits en 8 heures en utilisant 20 millions de qubits bruyants

cacher