Comment l'algorithme de Shor casse-t-il RSA et ECC ?

Il rend faciles les problèmes difficiles sur lesquels ils reposent. RSA est sûr parce que personne ne sait décomposer un très grand nombre en ses deux facteurs premiers en un temps raisonnable ; la cryptographie sur courbes elliptiques est sûre parce que personne ne sait retrouver le nombre secret derrière un point public de la courbe. Peter Shor a montré en 1994 qu'un ordinateur quantique peut trouver, dans les deux problèmes, un motif répétitif caché, une période, dont le secret se déduit rapidement. Sur une machine assez grande, l'attaque prend un temps praticable au lieu d'un temps impossible. Des clés plus longues ne sauvent ni RSA ni ECC : elles ralentissent seulement un peu l'attaque quantique. C'est pourquoi la réponse passe par de nouvelles mathématiques, comme les problèmes de réseaux euclidiens derrière ML-KEM et ML-DSA, pour lesquels aucun algorithme quantique efficace n'est connu. Les estimations publiées de la machine nécessaire dépassent encore de loin tout ce qui a été construit.

← Les 33 questions sur Cryptographie post-quantiqueTous les thèmes