Ces derniers mois, j’ai vu se multiplier les articles de presse plus ou moins sérieux à propos de l’informatique quantique et du problème qu’elle pose aux fondements de la sécurité sur l’Internet. On trouve bien entendu des articles honnêtes cherchant à informer, mais surtout des articles cherchant à faire le buzz et à inquiéter. On comprend aisément l’intérêt pour le sujet: déjà, c’est quantique, donc ça fascine les foules ; et en plus, ça concerne la sécurité sur internet, c’est à dire la protection de nos échanges électroniques, y compris bancaires.

Disclaimer
Les informations réunies ici sont le résultat de mes lectures de multiples sources en ligne. Chaque fois que possible, je citerai les publications scientifiques permettant d’étayer mes propos. Cela dit, je ne suis ni physicien, ni mathématicien : je suis un informaticien intéressé par les implications de l’informatique quantique pour la sécurité informatique. De fait, si cet article se veut fidèle à l’état de l’art actuel, ma compréhension profonde des sujets est limitée et certains détails peuvent se révéler inexacts à cause d’une mauvaise interprétation des publications scientifiques citées.

Il existe donc pléthore d’articles sur le sujet qui mettent en avant le danger posé et son imminence, remettent en question la capacité d’anticipation de nos élites ou leur clairvoyance, détaillent par le menu tous les domaines impactés et l’ampleur de l’apocalypse mondiale qui nous attend. Récemment, une limite a même été franchie par Siècle Digital, qui titre carrément “Un ordinateur quantique casse le chiffrement RSA sur 2048 bits en 8 heures”, rien que ça ! Si je lis correctement, je comprend que ça y est, RSA-2048 est cassé, dépassé, obsolète… Ce n’est plus le futur inquiétant décrit jusque là par la presse, c’est le présent. L’apocalypse est là, elle a commencé. Mais est-ce vrai ?

Mais déjà, c’est quoi RSA ?

RSA est l’algorithme de chiffrement asymétrique le plus utilisé au monde. Comme tous les algorithmes de chiffrement asymétrique, il repose sur deux clés: une clé publique, connue de tous, et une clé privée, connue uniquement de son propriétaire. L’algorithme est dit “asymétrique” car une clé est utilisée pour chiffrer un message et l’autre est utilisée pour le déchiffrer. Un algorithme de chiffrement asymétrique permet notamment deux cas d’usage ultra-classiques et utiles en informatique:

1. S’assurer que seul le destinataire d’un message sera capable de le lire. Si je veux envoyer un message à Bob, je peux chiffrer le message avec la clé publique de Bob. Le message ne pourra alors être déchiffré que par la clé privée de Bob, connue de lui seul.
2. Garantir à mes destinataires l’intégrité et l’authenticité d’un message que j’envoie. C’est la notion de signature électronique. Sans rentrer dans les détails, j’utilise ma clé privée pour signer mon message et mes destinataires peuvent utiliser ma clé publique pour vérifier que je suis bien l’émetteur du message et que le message n’a pas été modifié pendant son transit.

Le second cas d’usage, la signature, est un des principaux fondements de la sécurité sur l’Internet. C’est typiquement cet usage qui est au coeur du fonctionnement des certificats électroniques, qui à leur tour garantissent que le site de votre banque est bien l’authentique site de votre banque et permettent à vos navigateurs web d’afficher l’icône cadenas qui vous garantit que votre navigation est sécurisée. Il y a également bien d’autres usages, notamment pour l’authentification des transactions entre différentes entités, y compris les transactions bancaires.

Bref, pour résumer, sans algorithme de chiffrement asymétrique tel que RSA, on ne pourrait jamais savoir qui est qui sur le net, ni faire confiance à aucune information. On en serait encore à l’échange secret d’enveloppe physique, en mains propres sur un pont inquiétant en pleine nuit.

D’accord et pourquoi l’informatique quantique change quelque chose ?

Tous les algorithmes de chiffrement asymétrique reposent sur un problème mathématique difficile à résoudre pour un ordinateur classique.

Dans le cas de RSA, ce problème est la factorisation des nombres. Un ordinateur peut assez facilement calculer deux très grands nombres premiers et les multiplier. En revanche, essayer de retrouver les facteurs d’origine (la décomposition en facteurs premiers) du résultat est impossible à faire en pratique, il faudrait tout simplement des siècles (on parle ici de nombres extrêmement grands, de l’ordre de 500 chiffres).

Il existe d’autres algorithmes asymétriques qui reposent sur d’autres problèmes, par exemple ECC (Elliptic-Curve Cryptography) repose sur la difficulté de calcul d’un logarithme discret. Ce qu’il faut retenir en essence, c’est que la cryptographie asymétrique repose sur des opérations faciles à faire dans un sens pour un ordinateur classique mais impossibles à faire dans l’autre sens en un temps raisonnable.

Les possibilités de l’informatique quantique changent tout. En 1994, Peter Shor décrit pour la première fois l’algorithme qui porte son nom. En exploitant les propriétés étranges des particules quantiques, l’algorithme de Shor permettrait de factoriser des nombres extrêmement grands en un temps raisonnable. Son algorithme pourrait donc complètement remettre en question la sécurité de RSA, qui est justement basée sur la difficulté de ce problème (à noter que ECC est également concerné car l’algorithme de Shor permet aussi d’accélérer le calcul de logarithmes discrets. Il est même généralement admis qu’ECC est encore plus facile à casser “quantiquement” que RSA). Mais à l’époque, les ordinateurs quantiques sont encore de la science-fiction, l’algorithme n’est pas implémentable, et donc ça n’inquiète pas grand monde.

Aujourd’hui, on a démontré amplement la faisabilité de l’informatique quantique.

Ah, donc on est en danger ?

Non.

De multiples groupes de recherche et entreprises ont produit des implémentations réelles d’ordinateurs quantiques et de l’algorithme de Shor en particulier. Ce n’est plus de la science fiction. On peut fièrement annoncer que nous sommes désormais capables de factoriser des nombres grâce à l’algorithme de Shor. Le plus grand nombre jamais factorisé demandez-vous ? 21. C’est notre record. On sait factoriser 21 en 3×7. C’est un accomplissement scientifique majeur, une démonstration de la faisabilité de l’idée, mais pour l’instant on est très, très, très loin de menacer RSA. Le record absolu de “factorisation quantique” a été accompli via une autre technique en 2018 : on a factorisé 4088459, soit un nombre à 7 chiffres, et ça a pris beaucoup plus de temps que sur un ordinateur classique (qui peut factoriser un nombre aussi bas en à peine une microseconde).

Les faits souvent “oubliés” par la presse

L’obsession du nombre de qubits

Les annonces de presse se résument souvent à “il suffirait de X qubit pour…”, “un ordinateur quantique à X qubit construit par…”, “l’algorithme de Shor optimisé pour ne nécessiter que X qubit…”. Mais le nombre de qubits ne fait pas tout.

Imaginez un instant que vous me demandiez la puissance de mon processeur, et je vous réponds fièrement  “Ah ! C’est un 64 bits !”. Ca vous fait une belle jambe. C’est la capacité de mon processeur à manipuler ces 64 bits qui fait sa puissance, les opérations qu’il peut faire dessus, la vitesse à laquelle il les fait. Mon processeur est avant tout un amas de portes logiques, des milliards de portes logiques réalisées à l’aide de transistors.

Pour un ordinateur quantique, c’est un peu pareil. Ce n’est pas le tout d’aligner des milliers de qubits, si vous n’avez pas un circuit pour les manipuler, des “portes logiques quantiques”, ils ne vous serviront pas à grand chose. L’article de Siècle Digital simplifie les choses et ne cite même pas sa source, mais en la cherchant on la trouve. C’est en effet impressionnant, pour factoriser un nombre de n bits, il faut 3*n+0.002*n*log(n) qubits, 0.3*n³ + 0.005*n³*log(n) portes logiques, bien mieux que ce que j’avais pu voir précédemment. Pour RSA-2048, ça reste quand même la bagatelle de 6189 qubits et 2.7 milliards de portes logiques (la différence avec l’annonce de 20 millions s’explique par la différence entre qubit logique et qubit physique, voir ici) . Les auteurs eux-même ne voient pas ça arriver avant des décennies.

Le temps de calcul

L’autre problème délicat, c’est le temps. Aujourd’hui, nous avons beaucoup de peine à maintenir l’état quantique de nos qubits pendant plus de quelques secondes au mieux, c’est le problème de la décohérence. Là, on parle d’heures de calcul. Ce n’est pas pour demain non plus.

Le taux d’erreurs

Les fameuses “portes logiques quantiques” sont pour l’instant loin d’être aussi fiables que nos bons vieux transistors. Le papier cité au dessus, sur lequel s’appuie Siècle Digital, suppose un taux d’erreur inférieur à 10^-3 qui n’est pas du tout atteint aujourd’hui ( Il semble qu’on était à ~13% d’erreurs en 2015).

C’est entre autres à cause du temps et du taux d’erreur qu’on est obligé d’utiliser beaucoup plus de qubit physiques que ce qu’il faudrait normalement pour implémenter un algorithme : on essaie ainsi d’améliorer le temps disponible et de faciliter la correction des erreurs.

Pour faire un parallèle, c’est comme si vous aviez un robot auquel vous pouvez poser une question mais il ne donne la bonne réponse que 6 fois sur 10 et, la plupart du temps, il ne donne pas de réponse du tout parce qu’il crash en essayant de la trouver. Pour compenser, vous posez votre question à 1000 robots en même temps, et vous faites des stats sur leurs réponses pour connaître la bonne réponse.

Conclusion, qu’est-ce qui nous attend ?

Probablement rien de spécial. Depuis déjà quelques années, le NIST (National Institute of Standards Technology) a lancé un concours visant à sélectionner un algorithme asymétrique post-quantique, c’est à dire qui ne serait pas vulnérable même face à un ordinateur quantique (oui, ça existe !). C’est un concours du même type que celui qui avait permis en 2001 d’aboutir à AES, l’algorithme de chiffrement symétrique utilisé partout dans le monde (qui n’est pas en danger, lui). Nous allons donc, dans les prochaines années, sélectionner un nouvel algorithme asymétrique, puis petit à petit il remplacera les algorithmes actuels. En toute probabilité, le déploiement sera achevé bien avant qu’un ordinateur quantique atteigne la complexité nécessaire pour casser RSA.

Précisions à propos d’AES

AES n’est pas en danger d’extinction (contrairement à RSA), mais il est impacté : l’algorithme de Grover, un autre algorithme quantique, permettra de diviser sa sécurité par deux.Pour en savoir plus, Stay Tuned ! Un autre article est en préparation pour en parler un peu plus en détails.