Nouvel algorithme quantique : 20 millions de qubits pour casser le RSA 2048 bits en 8 heures

Des chercheurs développent un nouvel algorithme quantique qui utilise moins de ressources pour effectuer des calculs de cassage de code. Un ordinateur quantique à 20 millions de qubits fonctionnant sur cet algorithme ne prendrait que 8 heures pour casser le chiffrement RSA 2 048 bits.

Il est certain que les ordinateurs quantiques pourront casser les codes de chiffrement existants utilisés pour envoyer des messages secrets. Ces techniques de chiffrement n'ont jamais été complètement fiables. Au lieu de cela, elles dépendent de fonctions mathématiques complexes qui ne fonctionnent que dans un sens, ce qui rend facile le chiffrement de l'information.

La sécurité de telles techniques repose sur le temps qu'un ordinateur classique met pour déchiffrer l'information. Les techniques de chiffrement modernes sont presque incassables, car il faudrait des milliers d'années aux ordinateurs d'aujourd'hui pour déchiffrer leur code.

Cependant, les ordinateurs quantiques pourraient casser ces codes facilement, et ces machines sont beaucoup plus proches de la réalité que prévu.

Récemment, des chercheurs de Google et de l'Institut royal de technologie KTH en Suède ont mis au point une technique plus efficace que les ordinateurs quantiques pourraient utiliser pour déchiffrer des messages secrets. Elle permettrait aux ordinateurs quantiques d'utiliser moins de ressources pour effectuer des calculs de cassage de code.

Les ordinateurs quantiques deviennent plus puissants

En 1994, un mathématicien américain, Peter Shor, a développé un algorithme quantique pour factoriser de grands nombres exponentiellement plus vite que les meilleurs algorithmes existants s'exécutant sur un ordinateur classique. Il a suggéré qu'une machine quantique suffisamment puissante pourrait casser les techniques de chiffrement modernes facilement.

Au cours de la dernière décennie, beaucoup de progrès ont été réalisés en informatique quantique. En 2012, des scientifiques ont réussi à utiliser un ordinateur quantique à 4 qubits pour factoriser « 143 ». Deux ans plus tard, ils ont utilisé une machine similaire pour factoriser « 56153 ».

Compte tenu du taux de progression, les ordinateurs quantiques pourront bientôt surpasser les ordinateurs d'aujourd'hui. Du moins, c'est ce que les scientifiques attendaient il y a quelques années.

Il s'avère que la factorisation de grands nombres dans les machines quantiques est beaucoup plus difficile que prévu. Cela est dû au bruit significatif dans les grands ordinateurs quantiques. Le problème pourrait être résolu en utilisant des codes correcteurs d'erreurs, qui nécessitent eux-mêmes des qubits supplémentaires.

Référence : arXiv:1905.09749 | MIT Technology Review

En tenant compte de ce facteur de bruit, un ordinateur quantique aurait besoin d'un milliard de qubits pour factoriser des nombres de 2048 bits (ou pour déchiffrer le chiffrement RSA 2048 bits). Cependant, les ordinateurs quantiques universels d'aujourd'hui ne comportent que 70 qubits.

Exponentiation modulaire

Le nouvel algorithme permet aux ordinateurs quantiques de faire ces calculs avec seulement 20 millions de qubits. En fait, les chercheurs ont montré qu'un dispositif quantique fonctionnant sur ce nouvel algorithme ne prendrait que 8 heures pour casser le chiffrement RSA 2 048 bits.

Theur méthode effectue l'exponentiation modulaire — un type d'exponentiation réalisée sur un module — de manière efficace. Cette opération mathématique est coûteuse en calcul dans l'algorithme de Shor.

Les chercheurs ont trouvé différentes façons d'optimiser cette opération, réduisant considérablement les ressources nécessaires pour exécuter l'algorithme.

Bien qu'un ordinateur quantique à 20 millions de qubits ne soit pas réalisable dans un avenir proche, les experts en sécurité doivent réfléchir à une nouvelle forme de chiffrement que même un ordinateur quantique puissant ne pourra pas casser.