Le 23 octobre 2019, Google annonce que leur processeur quantique Sycamore a réussi à résoudre un problème en 3 minutes qui aurait nécessité plus de 10 000 ans de calcul à un superordinateur. C’était le premier cas déclaré de suprématie quantique.
Cette technologie promet d’ouvrir le champ des possibles dans de nombreux domaines. Cependant, elle vient également faire peser un nouveau risque sur la cryptographie moderne, dont la sécurité repose sur des problèmes mathématiques difficiles à résoudre. Que se passe-t-il lorsque cette difficulté de calcul n'est plus un obstacle ?
Dans cette nouvelle série d’articles, nous explorons le potentiel de l'informatique quantique et nous analysons ses éventuels impacts sur Bitcoin.
C’est quoi un ordinateur quantique ?
En parcourant cet article, vous vous servez probablement d'un ordinateur classique ou peut-être d'un smartphone. Ces appareils ont la capacité d'exécuter des opérations de calcul, bien qu'ils aient des limites. En effet, face à certains calculs complexes, il faudrait que la machine tourne pendant des millions d’années avant de trouver une solution. L’intérêt d’un ordinateur quantique est de pouvoir réaliser certains calculs spécifiques beaucoup plus rapidement qu’un ordinateur classique.
Pour arriver à ce résultat, le fonctionnement de l’ordinateur quantique n’a strictement rien à voir avec le fonctionnement de l’ordinateur classique. L'ordinateur traditionnel manipule des bits qui peuvent incarner deux états distincts - 0 ou 1 – et qui se combinent pour créer du code et réaliser des tâches. L’informatique classique s’établit donc sur les principes fondamentaux de l’électricité, alors que l’informatique quantique s'articule autour des principes de la physique quantique.
Au lieu de traiter les informations avec des bits, les ordinateurs quantiques utilisent des bits quantiques, également appelés « qubits ». Ces qubits peuvent valoir soit 0, soit 1, soit une superposition du 0 et du 1. En utilisant cette superposition d'états avec d'autres phénomènes quantiques tels que l'intrication et l'interférence quantique, un ordinateur quantique peut paralléliser les tâches de calculs, et donc résoudre certains problèmes beaucoup plus rapidement.
Le défi réside dans le fait que la cryptographie repose sur des problèmes mathématiques considérés comme insolubles par les ordinateurs traditionnels. Or, il est possible qu’à l’avenir, ces problèmes mathématiques puissent être résolus dans des temps acceptables par des ordinateurs quantiques, ce qui viendrait casser nos standards cryptographiques actuels.
Quels sont les risques pour la cryptographie ?
À ce jour, il existe principalement deux algorithmes quantiques qui pourraient menacer certaines primitives cryptographiques modernes. Ce sont les algorithmes de Shor (1994) et de Grover (1996).
L'algorithme de Shor a été conçu pour décomposer les nombres entiers en leurs facteurs premiers en temps polynomial. Cela implique que le temps de calcul nécessaire s'accroît de manière acceptable avec la taille du nombre à factoriser. À l'opposé, les algorithmes classiques les plus performants en la matière présentent une complexité qualifiée de « sous-exponentielle ».
Or, certaines des méthodes cryptographiques les plus utilisées au monde sont justement établies sur ce problème de la factorisation de grands entiers. C’est le cas de l’algorithme RSA par exemple.
Pour le dire plus simplement, si des ordinateurs traditionnels réussissent à casser le chiffrement RSA, il est possible de rétablir la sécurité de l’algorithme en augmentant la taille des clés utilisées. On est ensuite tranquilles pour un moment, puisque la complexité augmente de manière sous-exponentielle avec la taille de la clé. Cependant, avec l’utilisation de l'algorithme quantique de Shor, cette complexité croît beaucoup moins vite, ce qui pourrait, à terme, compromettre l'usage sécurisé de méthodes de chiffrement telles que RSA.
Cet algorithme de Shor peut être modifié afin de traiter également le problème du logarithme discret en temps polynomial. C’est le problème mathématique utilisé dans le cadre de Diffie-Hellman ou de la cryptographie sur les courbes elliptiques.
L'algorithme de Grover, quant à lui, peut être utilisé pour résoudre des problèmes de recherche non structurés. Autrement dit, il a été conçu pour rechercher un élément spécifique dans une base de données non organisée, et il le fait beaucoup plus vite que ne le ferait un algorithme classique. Il peut notamment être utile pour trouver des collisions sur une fonction de hachage.
Grover et Shor sont deux algorithmes qui pourraient mettre à mal certaines primitives cryptographiques modernes. Cependant, même s'ils existent depuis longtemps, il est encore impossible à ce jour de les exécuter sur un ordinateur quantique.
Les raisons de cette impossibilité sont multiples. Tout d’abord, il nous faudrait pouvoir disposer d’un ordinateur quantique avec un très grand nombre de qubits. Ensuite, il faudrait que ces qubits disposent d’un taux d’erreur infime. Seulement, les techniques de correction d’erreurs sont encore en cours de développement à l’heure actuelle. Enfin, pour effectuer des calculs si complexes, les qubits doivent pouvoir maintenir leur état quantique suffisamment longtemps. Les temps actuels sont trop courts et l’information est perdue avant de pouvoir effectuer toutes les opérations requises.
À court et à moyen terme, il ne semble donc pas y avoir de menace pour la cryptographie. C’est en tout cas ce qui ressort des avis des experts, comme le démontre un sondage EvolutionQ réalisé en 2022 auprès de 40 professionnels du secteur.
Dans cette étude, on leur a demandé quelle était la probabilité qu’un ordinateur quantique soit capable de casser une clé RSA de 2 048 bits en 24 heures, par rapport à différents horizons temporels en partant de l’an 2022. Dans un horizon de 5 ans, un seul expert estime qu'il y a plus de 50 % de chance que la situation décrite se produise. À un horizon de 15 ans, plus de la moitié des experts considèrent que la probabilité dépasse les 50 %. À 30 ans, presque tous sont d'accord, et près d'un tiers croient même qu'il y a 99 % de chance qu'une clé RSA soit cassée.
Ce sondage nous montre qu'à court et à moyen terme, les menaces que l'informatique quantique pourrait faire peser sur la cryptographie ne suscitent guère de préoccupations auprès des experts. En revanche, sur le long terme, ces derniers sont beaucoup plus pessimistes.
Conclusion
Dans ce premier chapitre, vous avez découvert pourquoi l’informatique quantique fait peser un risque sur la cryptographie. Les principales menaces sont les algorithmes de Shor et de Grover. Toutefois, on est encore loin de pouvoir les exécuter avec succès sur une machine. C’est tout simplement dû au fait que l’on ne dispose pas encore d’un ordinateur quantique suffisamment stable et puissant.
Selon les experts de ce secteur, cette menace doit être prise au sérieux. Cependant, c’est un risque qui ne devrait pas arriver avant plusieurs années, voire plusieurs dizaines d’années.
Dans le second chapitre de cette série, nous étudierons plus spécifiquement les risques qui pèsent sur le protocole Bitcoin. Nous verrons si les ordinateurs quantiques peuvent avoir des répercussions sur l’invention de Satoshi Nakamoto.
.png)
.png)
