Jacques BAUDRON  –  février 2023

Menace sur la cryptographie : la Chine annonce être sur le point de casser « RSA », l’algorithme garant de vos secret !

Alors, danger ? En deux mots, non, car la toute puissance du quantique achoppe sur une réalité physique : la quantité d’éléments binaires quantiques à faire cohabiter est incompatible avec le maintien dans l’état quantique.

Commençons par un rapide retour sur les calculateurs quantiques.

Calculateur quantique

La mécanique quantique repose sur un ensemble de postulats auxquels sont arrivés les physiciens du début du XXème siècle pour expliquer des phénomènes physiques sinon incompréhensibles. La précision des prévisions et ses capacités explicatives de la physique la rendent indéniable, les applications depuis les composants électroniques jusqu’au laser ou aux IRM et aux systèmes informatiques la rendent incontournable.

Problème : il ne faut pas chercher à se raccrocher à un quelconque “bon sens” voire à son intuition.  La physique qui nous est familière au niveau macroscopique n’a plus cours au niveau quantique.

Superposition

L’état quantique révèle sa face contre intuitive quand on se penche par exemple sur la trajectoire d’un photon qui rejoint un écran à partir de sa source alors que deux chemins lui sont proposés. Alors qu’on s’attendrait à ce que le photon suive une trajectoire ou l’autre, on se rend compte qu’il n’y a plus de trajectoire du tout. Le photon part de la source et arrive sur l’écran, ce sont deux états de la physique classique ; entre les deux on est dans l’état quantique et la position de la particule n’est pas déterminée, un petit peu comme si elle n’avait pas  de réalité physique dans l’état quantique. L’impact du photon sur l’écran se fait au hasard selon une combinaison de l’intégralité des chemins possibles. Toutes les possibilités sont prises en compte, elles sont comme superposées. Les équations de la physique quantique ne permettent pas de savoir où l’impact va se produire, indétermination oblige. Cependant elles fournissent une cartographie extrêmement précise de la probabilité de présence en tout point et génère par exemple de splendides figures d’interférence. 

Parallélisme

Les calculateurs quantiques utilisent cette faculté de superposition de deux états. Un paramètre nommé spin, par exemple, peut prendre deux valeurs qui vont être associées aux « 0 » et « 1 » logiques. On parle alors de qubits.

Vérifier une propriété sur un registre de quatre bits en informatique classique demande seize tests  ; cette même vérification avec quatre qubits quantiques se contente d’un seul test. La puissance du quantique provient de ce parallélisme.

Ainsi en simplifiant le calculateur quantique est formé de portes logiques situées entre un registre d’entrée et un registre de sortie. 

Gardons toujours en tête que le quantique suit sa propre logique en interdisant le « copier-coller », en fournissant des résultats au hasard, en étant dédié qu’à un type de calcul et en quittant son travail à la moindre interaction. Il n’est définitivement pas de la même lignée que nos « laptops » familiers. 

Qubits physiques, qubits logiques

L’état quantique est très fragile, à la merci de la moindre vibration, du moindre rayonnement. Il faut isoler au maximum les particules en étant proche du zéro absolu par exemple mais sans porter atteinte à l’interconnexion des qubits. Des codes correcteurs d’erreurs permettent de contenir les erreurs. Problème : les qubits utilisés pour ce calcul doivent eux-mêmes être corrigés, d’où un gros surcoût en qubits physiques pour chaque qubit logique. Combien ? À défaut de recul suffisant pour établir une règle, on rencontre aussi bien un facteur multiplicateur de 15.000 pour chaque qubit logique que le nombre de qubits élevés au carré. D’autres notions comme le volume quantique cherchent à cerner ce surcoût en intégrant les portes logiques situées entre les registres d’entrée et de sortie. 

… et le chaton revint

L’ensemble formé par les registres d’entrée, de sortie et les portes logiques doit rester dans un état quantique le temps du calcul. Hélas, ce temps avant retour au monde classique est d’autant plus court que le nombre de particules en interaction est élevé. Plus la quantité de qubits augmente, plus le maintien en état quantique un temps suffisant relève du défi. 

Nous sommes dans la cas de figure illustré avec humour par Erwin Schrödinger et son chat : il est illusoire de chercher à maintenir un système macroscopique en état quantique. 

Voilà qui bride l’horizon des calculateurs quantiques de grande taille.

La menace quantique

Que sont les vulnérabilités potentielles de RSA ?

RSA tient sa force d’une asymétrie mathématique : il est aisé d’obtenir le produit de deux nombres mais très compliqué de retrouver ces deux nombres à partir du seul produit. À ce jour les siècles voire les millénaires de force brute requis pour y arriver nous laissent un certain répit. 

Mais une double épée de Damoclès entache notre sérénité : qu’un petit génie mette au jour un principe mathématique capable de factoriser sans effort un nombre quelconque ou qu’un saut technologique offre la puissance de calcul suffisante pour tester exhaustivement toutes les combinaisons en un temps raisonnable. 

Shor

Peter Shor propose en 1995 un algorithme miraculeux : la complexité qui croissait de manière exponentielle avec la taille du nombre à factoriser devient linéaire (polynomial). L’algorithme exploite des phénomènes périodiques et la résolution à base d’ordinateur classique fait appel à un calculateur quantique pour exécuter un module de la famille de la transformée de Fourier.

Cela dit, la taille N des clefs de chiffrement de 2048 bits rend la tâche particulièrement rude. Il faut en entrée un registre à la taille de la clef (en pratique, c’est même entre N2 et 2N2) et en sortie √N. Ces registres en entrée et en sortie sont intriqués, comprenez qu’ils faut additionner les qubits en entrée et en sortie. Ajoutons les portes logiques entre les deux ainsi que le surcoût lié aux calculs d’erreur et le (voire les) million de qubits arrive vite en bas de la facture. 

Une telle concentration de particules peine à rester en mode quantique. Le retour dans le mode classique est immédiat. À défaut d’une avancée majeure en physique quantique, il n’y a pas d’évolution prévisible. On ne sait pas comment faire. Ce type de situation, que l’on rencontre  par exemple également dans l’Intelligence Artificielle forte, se repère facilement : l’échéance affichée se chiffre en dizaines d’années, un petit peu comme « quarante » dans Ali Baba signifie « beaucoup ».

Schnorr

Le très récent (2021) algorithme de Claus-Peter Schnorr clamait dans une première version pouvoir casser RSA : ”This destroyes the RSA cryptosystem’’, propos qui est devenu « It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA » dans une version ultérieure. 

Autrement dit, tout compte fait, ce ne sera pas suffisamment rapide. Ajoutons que ni l’algorithme de Schnorr ni la technique d’optimisation « QAOA » (Quantum Approximate Optimization Algorithm) qui y est associée ne sont clairement validés aujourd’hui.

Avancée chinoise

Quant aux annonces chinoises, on ne dispose que de peu de détails. Elles sont construites sur un dérivé de Schnorr et se targuent de n’avoir besoin que de 372 qubits (hors portes logiques internes) pour une clef de 2048 bits. Cette valeur est extrapolée de la factorisation (théorique ?) avec seulement 10 qubits du nombre 261 980 999 226 229 qui lui est sur 48 bits. 

Peut-être. Ce chiffre semble étonnant, mais mes maigres connaissances en mathématique me rendent illégitime pour porter un jugement. Deux points sont quand même à souligner : d’une part 372 qubits logiques supposent une quantité rédhibitoire de qubits physiques et d’autre part ce papier, loin d’être validé, est fortement décrié par les spécialistes de la chose. Le doute est permis. 

En bref : Feynman dans le texte

Feynman a rapidement eu l’intuition que la simulation des phénomènes quantiques poseraient des problèmes aux ordinateurs classiques : « Ne serait-il pas plus facile de simuler la physique quantique si les ordinateurs étaient eux-mêmes quantiques ? »

Mon ressenti est que autant il y a un sens de faire de la simulation quantique avec un système quantique, autant vouloir aligner des bits quantiques comme on aligne des bits informatique frise l’aporie. Les dures lois de la physique quantique se rappellent à nous dès que l’on cherche à faire un copier-coller de notre informatique familière. 

Sources et bonnes lectures

  –  Parmi les sources de références on trouve bien entendu les papiers académiques de Peter Shor, (https://arxiv.org/pdf/quant-ph/9508027.pdf), Claus-Peter Schnorr (https://eprint.iacr.org/2021/933.pdf) ainsi que l’étude chinoise (https://arxiv.org/pdf/2212.12372.pdf) mais ils sont sans ambiguïté à l’intention d’un public averti. 

Les sources citées ci-dessous sont avant tout des lectures de vulgarisation relativement accessibles.

  –  Fonctionnement de l’algorithme de Shor : 

https://www.geeksforgeeks.org/shors-factorization-algorithm/

  –  Le surcoût en qubits de la correction d’erreur

National Academies of Sciences, Engineering, and Medicine. 2019. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. https://doi.org/10.17226/25196.

  –  Temps de cohérence d’un état intriqué en fonction du nombre de qubits.

https://www.cea.fr/comprendre/Pages/nouvelles-technologies/essentiel-sur-ordinateur-quantique.aspx

  –  Nombre de qubits 

https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/Studien/Quantencomputer/P283_QC_Studie-V_1_2.pdf?__blob=publicationFile&v=1

  –  Calcul d’erreur

https://www.sciencesetavenir.fr/high-tech/reduire-les-erreurs-au-sein-de-l-ordinateur-quantique_156531

  –  Incontournables :

Richard FEYNMAN, Lumière et Matière, collection Points Sciences

Olivier EZRATTI, Understanding Quantum Technologies Fifth edition 2022 

Étienne KLEIN, toute vidéo, tout écrit et toute audio

  –  Mon préféré du moment :

Carlo ROVELLI, Et si le temps n’existait pas ? Dunod 2014, collection Quai des Sciences