Pourquoi l'ordinateur quantique casse RSA | L'algorithme de Shor expliqué simplement

RSA protège discrètement vos virements bancaires, vos messages et vos mises à jour logicielles depuis près de cinquante ans. Peter Shor l'a coulé sur le papier en 1994, et un ordinateur quantique suffisamment grand le coulera un jour en pratique.

Pour comprendre pourquoi, il faut dépasser la formule habituelle — « factoriser de grands nombres, c'est difficile » — et tendre l'oreille vers tout autre chose : un rythme caché à l'intérieur même du chiffrement.

En résumé :

• La sécurité de RSA repose sur un cycle dont la découverte par tâtonnement coûte astronomiquement cher.

• Un ordinateur quantique ne cherche pas ce cycle. Il le fait interférer avec lui-même et en lit la fréquence.

• Doubler la longueur de clé élève au carré le travail de l'attaquant classique. Cela double à peu près celui de l'attaquant quantique.

Comment RSA protège-t-il un secret ?

Pour un cryptographe, RSA tient du remède universel. L'algorithme repose sur des mathématiques élégantes, tressant arithmétique, théorie des nombres et théorie des groupes (ces mots ne vous diront peut-être pas grand-chose, mais quiconque a eu la chance de les étudier un jour sentira un irrépressible frétillement intellectuel). Il gère à la fois la signature numérique et le transport de clés. Il est efficace, et les objets qu'il produit restent de taille modeste. Et — qualité que l'on apprécie énormément dans un article de vulgarisation — il est relativement simple à expliquer.

On commence d'ordinaire par annoncer que RSA repose sur la difficulté supposée de décomposer de grands nombres en produit de facteurs premiers. C'est vrai, mais bien trop mince pour saisir la mécanique sous-jacente — celle-là même qu'un ordinateur quantique exploite.

Deux secrets, un cadenas public

Supposons qu'Alice et Bob veuillent échanger un message secret. RSA commence par exiger deux grands nombres premiers, appelons-les p et q. Alice s'exécute : elle les tire au hasard et ne les révélera sous aucun prétexte. Ils sont à elle, et à elle seule.

Elle peut en revanche les multiplier l'un par l'autre pour obtenir un troisième nombre, N = p × q. Si, comme nous l'avons supposé, retrouver les facteurs premiers de N est réellement difficile, alors Alice n'a aucun scrupule à publier N — sur internet, par exemple. Par hypothèse, une personne malveillante qui met la main dessus aura toutes les peines du monde à remonter aux deux nombres premiers d'origine. Parfait.

Mais nous n'en avons pas fini.

Chiffrement : élever le message à une puissance

Bob a un message à transmettre en toute sécurité à Alice : « Les sanglots longs des violons de l'automne. » On peut toujours transformer du texte en nombre — en binaire, par exemple, ce que fait précisément votre ordinateur pour stocker un fichier Word (10 Ko signifie que le fichier peut être représenté par dix mille octets, soit quatre-vingt mille bits). Appelons M le message exprimé sous forme d'un grand nombre. Bob a N, Alice a p et q. Et maintenant ?

C'est le moment d'attacher votre ceinture. Un nouveau nombre e fait son apparition. Il est public et, pour de bonnes raisons, on le choisit souvent égal à e = 65537. Pour chiffrer son message, Bob calcule M à la puissance e : M × M × M × … × M, « e fois ». Le résultat est un très grand nombre, parfaitement incompréhensible pour le commun des mortels. Appelons-le C : le chiffré, ce que Bob envoie effectivement sur le réseau et que n'importe quelle oreille indiscrète peut intercepter.

Déchiffrement : tourner jusqu'à ce que M retombe sur ses pieds

Toute la question du déchiffrement revient à retrouver M à partir de M^e. Il se trouve (et nous esquiverons élégamment la démonstration ici) que si l'on continue à multiplier M^e par lui-même, encore et encore — en calculant M^2e, puis M^3e, puis M^4e, et ainsi de suite —, un moment providentiel finit par arriver où l'ensemble retombe sur ses pieds. Il existe une puissance d telle que M^ed = M × M × … × M (« ed fois ») possède une propriété assez intéressante : elle est égale à M plus un multiple de N — ce même N public du tout début. Autrement dit, M^ed peut s'écrire M + (N × un certain nombre).

Et là, l'espoir revient. Parce que soustraire des multiples de N est facile (croyez-moi sur parole). La conclusion : si vous parvenez jusque-là, à exprimer une puissance de M comme la somme de M et d'un multiple de N, vous pouvez retrouver le M d'origine. Vous avez déchiffré le message.

Autrement dit, déchiffrer revient à trouver le tempo de la ronde qui ramène M sur ses pieds lorsqu'on le multiplie par lui-même un nombre suffisant de fois.

La difficulté, évidemment, c'est que chercher ce tempo à tâtons — cet exposant ed — prend du temps. Beaucoup de temps, surtout lorsqu'on choisit de très grands nombres : ed se situe quelque part autour de 2^2048, c'est-à-dire « plus que le nombre d'atomes dans l'univers », selon la formule consacrée. Cela représente une quantité vertigineuse de calculs, hors de portée même d'une armée de superordinateurs.

Le raccourci que seule Alice possède

Extrêmement compliqué, certes — sauf pour Alice. Connaissant p et q, elle peut trouver ce tempo, cet exposant, très facilement, en une poignée d'opérations. Il y a à cela une raison profonde et élégante, mais elle dépasse le cadre de cet article.

Magnifique. Nous disposons d'un chiffrement asymétrique robuste et élégant, qui irrigue de sécurité nos communications à distance depuis près d'un demi-siècle.

Comment un ordinateur quantique casse-t-il RSA ?

Nous avons justifié la robustesse de RSA par la difficulté de trouver la bonne puissance s du message M qui permet de « retomber sur ses pieds » — celle qui exprime M^s comme M plus un multiple de N.

Et c'est précisément cette certitude que Peter Shor a ébranlée en 1994.

Si le schéma RSA est vulnérable à l'algorithme de Shor, et donc à l'ordinateur quantique, c'est parce qu'il dissimule ce rythme, ce cycle — et donc une structure — que le calcul quantique parvient à exploiter. Avec quels ingrédients ?

1. La superposition : le chat de Schrödinger est-il vivant ou mort ?

Un état quantique, c'est la manière dont un qubit a été préparé : un électron, un proton, un photon, un atome, ou autre chose encore. On peut interagir avec ces petits grains de matière (au laser, notamment) pour leur conférer certaines caractéristiques — et dans l'histoire qui nous occupe, on les place dans un état qui donne une chance sur deux de lire 0 à la mesure, et une chance sur deux de lire 1.

Là où un registre de processeur classique ne peut stocker qu'une seule valeur déterministe, les registres quantiques ont l'excellente propriété de stocker quelque chose de bien plus profond : une superposition d'états, une sorte de combinaison de tous les états dans lesquels les qubits sous-jacents ont été placés.

Chaque qubit stocke déjà une superposition de deux états, 0 et 1. À la mesure, un seul état (0 ou 1) sera observé, avec une probabilité de 1/2. Mais tant que la mesure n'a pas été faite, les deux états coexistent.

C'est ce que l'on illustre habituellement par la macabre parabole du chat de Schrödinger (du nom du grand physicien et philosophe autrichien, pionnier de la mécanique quantique) : un chat est enfermé dans une boîte hermétique avec un bol de lait empoisonné. Tant que l'on ne soulève pas le couvercle — la mesure —, le chat est-il vivant ou mort ? Un peu des deux, en un sens. Ses états « vivant » et « mort » sont superposés.

Plaçons-nous maintenant au niveau du registre : superposez Q qubits (dont chacun est lui-même la superposition des états 0 et 1) et la probabilité de mesurer n'importe quel nombre entre 0 (tous les qubits mesurés dans leur état 0) et 2^Q^−1 (tous les qubits mesurés à 1) est uniforme, égale à 1/2^Q. Pour mesurer 1010…1010, par exemple, il faut que le premier qubit sorte à 1 (une chance sur deux), le deuxième à 0 (une chance sur deux), le troisième à 1 (une chance sur deux), et ainsi de suite.

Bien utile, direz-vous, de construire un registre qui vous livre un nombre aléatoire entre 0 et 2^Q^−1 quand on le mesure… Patience. Cela vient.

2. L'intrication : le grand mariage des registres

Dans un second registre, nous plaçons Q−1 qubits dans l'état 0 et un qubit dans l'état 1. Mesurer ce registre donne invariablement la valeur 1 (en binaire : Q−1 zéros suivis d'un unique 1).

Mesurons à présent l'état des deux registres dans leur ensemble. La mesure globale se compose d'un nombre aléatoire entre 0 et 2^Q^−1 (registre 1) et d'un état 1 (registre 2). Autrement dit : une sorte de produit cartésien (on l'appelle produit tensoriel) d'un état du registre 1 et d'un état du registre 2. On peut séparer à volonté ce qui vient du registre 1 (une somme d'états uniformément répartis) et ce qui vient du registre 2 (un état à Q qubits qui donne toujours 1).

Dans cet état global, les contributions des registres 1 et 2 sont indépendantes. Ils mènent deux heureuses vies de célibataires.

Marions-les.

Tourne, tourne, le manège

Par distributivité du produit tensoriel entre les états du registre 1 et les états du registre 2, on peut aussi écrire l'état global des deux registres comme la superposition de [chaque état possible de R1, apparié à l'état 1 porté par R2].

En effet : j'avais auparavant 2^Q prétendants dans le registre 1. Photographier ce registre me livrait un prétendant tiré au hasard parmi les 2^Q, que je mariais invariablement à la promise « 1 » du registre 2. J'affirme que cela équivaut à sélectionner au hasard l'un des 2^Q couples (état 0 ≤ x ≤ 2^Q^−1 du registre 1, promise « 1 » du registre 2). Ce sont désormais les couples qui sont superposés, et non plus les prétendants d'un côté et la promise de l'autre.

Comme chacun sait, le mariage change le caractère des tendres époux.

C'est ce qui va arriver à l'épouse de chaque couple superposé. Au lieu de valoir 1 avec une probabilité de 1, nous appliquons une seule opération à l'ensemble de la noce, d'un seul geste. L'épouse du mari x prend alors une valeur qui dépend de x — une fonction de x.

Et c'est là que se cache la magie de la chose. On pourrait croire qu'agir sur 2^Q couples exige 2^Q calculs, un par valeur de x, ce qui ne nous ferait rien gagner sur un ordinateur classique. Rien de tel : la machine ne manipule pas les 2^Q valeurs une à une, elle manipule les Q qubits, une fois et une seule. Parce que le registre est une superposition et que l'opération est la même pour tous, elle s'applique simultanément à toutes les branches. Un seul passage dans le circuit, et les 2^Q épouses sont calculées d'un coup.

Pourquoi cela fonctionne-t-il ? Parce que la nature est ainsi faite.

Poursuivons.

Chaque mari a désormais une épouse qui lui est exclusivement liée. L'état de chaque promise étant fonction de la valeur de l'état de son mari, il n'est plus possible de revenir en arrière et d'écrire l'état global des deux registres comme un produit indépendant d'un état du registre 1 et d'un état du registre 2. Les deux états sont intrinsèquement liés. Ou plutôt : ils sont intriqués.

La fonction de x portée par chaque épouse ne doit rien au hasard. Elle vaut f(x) = C^x (mod N), où C = M^e est le chiffré intercepté — tiens donc, nous reconnaissons la forme du problème « supposé difficile » de la section précédente, avec le message M chiffré par exponentiation. Le « (mod N) » indique simplement que l'on ignore les multiples de N dans le calcul de f(x) : si C^x₁ et C^x₂ diffèrent d'un multiple de N, on considère que f(x₁) et f(x₂) sont égaux.

Polygamie quantique

Une question utile : toutes les épouses sont-elles différentes ? Ou bien existe-t-il des épouses liées à plusieurs maris différents ?

Imaginons que nous trouvions un nombre r tel que C^r = 1 (mod N) — nous savons qu'il en existe un. Alors, si x est un mari du registre 1 marié à son épouse f(x), nous avons f(x+r) = C^x+r = C^x · C^r = C^x · 1 = C^x (mod N) = f(x). Donc f(x) est aussi l'épouse de x+r — et, du reste, de tout mari de la forme x + kr, avec k un entier. Appelons cela la propriété de polygamie, dans laquelle l'épouse règne en maîtresse absolue.

Conséquence immédiate et plutôt saisissante : toute mesure du registre 2 affecte la mesure du registre 1. Si nous mesurons une certaine épouse y = f(x) dans le registre 2, nous mesurerons nécessairement la superposition des états des maris x tels que y = f(x). C'est-à-dire des maris de la forme x, x+r, x+2r, x+3r…

Vous pourriez croire que nous sommes arrivés au bout du raisonnement. Après tout, trouver ce fichu r, c'est mettre la main sur le rythme secret du système. Et ce rythme ouvre exactement la même porte que le raccourci qu'Alice tirait de p et q : vous vous souvenez de d, l'exposant magique de la première partie, celui qu'un attaquant classique mettrait des milliards d'années à deviner ? Une fois r connu, d suit en un clin d'œil, et avec lui le message M est retrouvé. Peu importe l'arithmétique exacte — ce qui compte, c'est que r joue le rôle des nombres premiers d'Alice.

Mais nous n'avons pas encore accès à r. Nous pourrions être tentés de mesurer le registre 1 tout de suite — sauf que nous obtiendrions alors une valeur x+kr, avec x et k tous deux inconnus. La chasse à r reste ouverte.

3. La dualité onde-corpuscule : « et pourtant elle vibre »

On vous avait dit que les qubits contenaient une particule de matière ? On vous a menti. À moitié menti, en tout cas.

La beauté de la chose, c'est que l'on ne peut pas trancher lequel des deux modèles, onde ou particule, décrit le mieux la matière élémentaire. On appelle cela la dualité onde-corpuscule.

Ce qui signifie que nous pouvons choisir la représentation qui nous arrange.

Faire vibrer le bassin

Imaginez des rides à la surface de l'eau. Nous envoyons une ride à t = x, une autre à t = x+r, une autre à t = x+2r, et ainsi de suite : nous obtenons un ensemble d'ondes espacées de r.

De l'autre côté du bassin, nous envoyons d'autres rides espacées de s = 1, puis 2, puis 3, et ainsi de suite jusqu'à N. Tentez l'expérience et deux scénarios se dérouleront sous vos yeux :

• s diffère de r : votre bassin devient un chaos de petites vagues qui se brisent les unes sur les autres.

• s égale r : les creux des rides envoyées depuis la gauche s'alignent sur les creux de celles envoyées depuis la droite, creusant des creux plus profonds encore ; et leurs crêtes coïncident aussi, élevant des crêtes plus hautes.

Ce que nous venons de décrire, c'est le phénomène d'interférence constructive. Lorsque vous jouez un la à la guitare et que vous fredonnez un la en même temps, le son semble gagner en volume — parce que les ondes sonores de la guitare et de la voix s'additionnent et se soustraient aux bons endroits, rendant la vibration plus intense.

Le rythme retrouvé

C'est à peu près ce qui se produit lorsque nous partons à la recherche de r dans le problème qui nous occupe : nous tentons de retrouver la fréquence de « vibration » de notre système par interférence. (Dans les manuels, cette étape porte le nom de transformée de Fourier quantique.)

r est obtenu. Le message M est déchiffré, via le petit calcul d'exposant décrit plus haut.

Voilà — c'est le moment où il faut croire l'auteur sur parole : l'ensemble des calculs qui permet de retrouver r, cette période cachée, est ridiculement petit comparé à l'effort titanesque du calcul de toutes les puissances de M dans le cas classique.

Mieux encore, tout tient à la manière dont l'attaque est menée. L'ordinateur classique n'a aucun rythme à exploiter. Il est condamné à essayer les puissances une à une, à fouiller une botte de foin dont la taille double à chaque bit ajouté à la clé. Doubler la longueur de clé (2048 → 4096 bits) élève donc cette botte de foin au carré, la multiplie par elle-même : le travail explose. L'ordinateur quantique, lui, ne fouille rien du tout. Il écoute directement le rythme r par interférence, et le coût de cette écoute ne dépend que du nombre de chiffres à manipuler. Deux fois plus de bits, deux fois plus de qubits, et c'est à peu près tout.

Questions fréquentes

L'algorithme de Shor factorise-t-il réellement N ? Pas directement. L'étape quantique, c'est la recherche de période — retrouver le r ci-dessus. La factorisation de N, comme la récupération du message, découlent toutes deux de r moyennant un peu d'arithmétique classique. La factorisation qui fait les gros titres est une conséquence, pas le mécanisme.

Les ordinateurs quantiques actuels peuvent-ils casser RSA-2048 ? Non. Casser une clé de 2048 bits réclame des milliers de qubits logiques corrigés d'erreurs exécutant des circuits très profonds, alors que les meilleures machines n'en alignent aujourd'hui que quelques dizaines. Ce qui bouge vite, c'est l'estimation, pas le matériel : une analyse de Google Quantum AI publiée en 2025 a ramené le besoin sous le million de qubits physiques bruités, soit environ vingt fois moins que le chiffre de 2019, et des préprints de 2026 portant sur des architectures alternatives de correction d'erreurs plaident pour moins encore. Le seuil ne cesse de baisser avant même qu'un seul qubit supplémentaire ne soit construit.

Une clé plus longue me protège-t-elle ? Elle achète du temps, pas de la sécurité. Le coût d'une attaque classique croît exponentiellement avec la longueur de clé ; le coût quantique croît à peu près linéairement. C'est toute l'asymétrie de cet article en une phrase.

RSA est-il la seule victime ? Non. Diffie-Hellman et la cryptographie sur courbes elliptiques tombent sous la même attaque, pour la même raison : elles dissimulent une structure périodique. Les courbes elliptiques tomberont probablement en premier, puisque leur meilleure sécurité classique a conduit à adopter des clés bien plus courtes — et l'algorithme de Shor se soucie surtout de la taille des clés. Les chiffrements symétriques comme AES sont bien moins exposés.

Qu'est-ce qui remplace RSA ? Le NIST a standardisé ses premiers algorithmes post-quantiques en août 2024 : ML-KEM (FIPS 203) pour l'échange de clés, ML-DSA (FIPS 204) et SLH-DSA (FIPS 205) pour les signatures, avec HQC ajouté en secours en mars 2025. RSA et ECC doivent être dépréciés autour de 2030 et proscrits d'ici 2035.

Pourquoi migrer maintenant si aucune machine n'existe ? À cause du harvest now, decrypt later : un adversaire peut enregistrer du trafic chiffré aujourd'hui et le déchiffrer le jour où une machine capable arrivera. Tout secret qui doit le rester une décennie est déjà exposé.

Avertissement

Certaines difficultés ont été sciemment contournées tout au long de cet article. Les puristes trouveront certainement quelques points de détail à redire, et j'implore leur clémence au nom de la vulgarisation.