L'algorithme de Shor casse RSA et ECC

La sécurité de RSA, de Diffie-Hellman et de la cryptographie sur courbes elliptiques (ECC) repose sur des problèmes que nos ordinateurs classiques ne savent pas résoudre rapidement. Un ordinateur quantique assez grand change radicalement la donne.

L'algorithme de Shor

En 1994, Peter Shor publie un algorithme qui, sur un ordinateur quantique, factorise un grand nombre et résout le logarithme discret en temps polynomial.

C'est une rupture. Les meilleurs algorithmes classiques de factorisation sont sous-exponentiels : doubler la taille de la clé rend le problème astronomiquement plus dur. Shor, lui, met à genoux ces problèmes en un temps qui ne croît que comme un polynôme de la taille du nombre.

Or toute la cryptographie asymétrique déployée aujourd'hui repose précisément sur ces deux problèmes :

• RSA repose sur la difficulté de factoriser n = p × q ;
• Diffie-Hellman et ECC reposent sur la difficulté du logarithme discret.

Un ordinateur quantique tolérant aux fautes, de taille suffisante, les casserait tous.

Ce qui survit : le symétrique

La cryptographie symétrique (AES) et les fonctions de hachage (SHA-2, SHA-3) ne sont pas cassées, seulement affaiblies.

L'algorithme de Grover (1996) accélère une recherche par force brute : il trouve une clé de N possibilités en environ racine(N) essais au lieu de N. Cela divise par deux la sécurité effective en bits.

Sécurité effective face à Grover
--------------------------------
AES-128  ->  ~64 bits  (jugé insuffisant)
AES-256  -> ~128 bits  (jugé sûr)

La parade est simple et connue : doubler la taille des clés. Passer d'AES-128 à AES-256 restaure une marge confortable. Grover n'offre qu'un gain quadratique, pas exponentiel : il ne remet pas en cause le principe du symétrique.

Le tableau qui résume la menace

Primitive	Type	Attaque quantique	Verdict
RSA	asymétrique	Shor	cassé
Diffie-Hellman	asymétrique	Shor	cassé
ECC	asymétrique	Shor	cassé
AES-128	symétrique	Grover	affaibli
AES-256	symétrique	Grover	sûr (clés doublées)
SHA-256	hachage	Grover	affaibli
SHA-512	hachage	Grover	sûr

La ligne de fracture est nette : l'asymétrique s'effondre, le symétrique tient en agrandissant les clés.

En résumé

L'algorithme de Shor casserait RSA, Diffie-Hellman et ECC en temps polynomial sur un ordinateur quantique. Le symétrique et les hachages ne sont qu'affaiblis par Grover, qui divise par deux la sécurité effective : AES-256 conserve environ 128 bits et reste sûr. C'est pourquoi la migration urgente concerne l'asymétrique, remplacé par la cryptographie post-quantique.