Multiplier deux nombres premiers très grands est facile pour un ordinateur classique ; retrouver ces facteurs à partir de leur produit peut, en revanche, exiger un calcul hors de portée. Cette asymétrie soutient la sécurité de RSA, un système de cryptographie largement étudié.
L’algorithme de Shor change la perspective : il montre comment un ordinateur quantique pourrait accélérer la factorisation de certains nombres gigantesques. Comprendre son mécanisme permet de distinguer une avancée théorique d’une menace déjà concrète pour la sécurité informatique.
A retenir :
- La factorisation classique devient rapidement coûteuse pour les grands entiers
- L’algorithme de Shor transforme le problème en recherche de période
- Les ordinateurs quantiques actuels ne cassent pas RSA à grande échelle
- La cryptographie postquantique prépare des protections contre cette évolution
Pourquoi la factorisation de grands nombres résiste aux ordinateurs classiques
Cette difficulté arithmétique explique pourquoi la multiplication et son opération inverse n’ont pas le même coût pratique. La complexité algorithmique dépend fortement de la méthode employée et de la taille du nombre étudié.
Multiplier est simple, retrouver les facteurs est difficile
Pour fabriquer un entier composé, un ordinateur multiplie deux nombres premiers en un temps relativement court. Retrouver ces nombres à partir du produit demande beaucoup plus de travail, même si le calcul reste possible pour des valeurs modestes.
Un exemple souvent utilisé est un nombre de 200 chiffres formé par deux facteurs premiers de taille comparable. Une recherche naïve devrait tester des diviseurs jusqu’à environ 10100 ; à 1012 opérations par seconde, l’estimation atteint 1088 secondes.
Ce calcul simplifié ne décrit pas les meilleures méthodes classiques, qui sont bien plus efficaces qu’une vérification successive. Il illustre néanmoins l’écart immense entre une recherche élémentaire et les ressources disponibles.
Selon les travaux de Peter Shor, la factorisation peut être ramenée à la recherche de l’ordre d’un nombre modulo un entier donné. Cette reformulation ouvre la voie au calcul quantique.
Les facteurs premiers et leur taille déterminent ainsi le niveau d’effort nécessaire pour attaquer un système fondé sur cette asymétrie.
Échelle des méthodes de factorisation :
- Petits entiers : essais de division adaptés aux exercices
- Entiers moyens : algorithmes classiques plus élaborés
- Grands produits de premiers : calcul distribué et ressources importantes
Approche
Principe
Usage pertinent
Division successive
Tester des diviseurs candidats
Petits nombres
Méthodes classiques avancées
Exploiter la structure arithmétique
Entiers plus grands
Algorithme de Shor
Rechercher une période sur un calculateur quantique
Ordinateur quantique suffisamment fiable
Test de primalité
Déterminer si un entier est premier
Vérification, sans décomposition complète
Comment l’algorithme de Shor exploite le calcul quantique
Une fois la difficulté classique posée, l’algorithme de Shor propose une autre route, fondée sur les propriétés des nombres et des états quantiques. Le cœur de cette méthode n’est pas l’essai direct de chaque facteur.
La recherche de période révèle des facteurs
Pour factoriser un entier N, l’algorithme choisit un nombre a et étudie les puissances successives de a modulo N. La suite finit par se répéter ; la longueur de cette répétition est appelée son ordre.
Selon l’analyse de Shor, si cet ordre satisfait certaines conditions, des calculs fondés sur le plus grand commun diviseur peuvent révéler des facteurs non triviaux de N. Des cas comme 15 montrent le mécanisme sans représenter la difficulté des clés modernes.
Un ordinateur quantique peut préparer une superposition de possibilités, puis utiliser l’interférence et la transformée de Fourier quantique pour extraire de l’information sur la période. La mesure ne livre pas directement tous les facteurs : elle fournit un résultat qu’il faut interpréter classiquement.
La partie quantique accélère donc une étape centrale, tandis que l’arithmétique classique encadre le calcul et vérifie les résultats obtenus.
Des qubits fiables sont indispensables
Cette accélération théorique suppose un matériel capable d’exécuter de nombreux calculs quantiques sans que les erreurs détruisent le résultat. Les qubits sont sensibles au bruit, et la correction d’erreurs exige des ressources importantes.
Selon le National Institute of Standards and Technology, la préparation à la cryptographie postquantique vise à protéger les systèmes contre de futures capacités quantiques. Cette démarche de précaution ne signifie pas que les machines disponibles factorisent déjà les clés RSA usuelles.
La performance ne se mesure donc pas au seul nombre de qubits annoncé. La durée des opérations, leur fidélité et la correction d’erreurs comptent aussi pour évaluer une capacité réelle.
Facteurs techniques à surveiller :
- Qualité des qubits pendant les opérations
- Correction des erreurs accumulées
- Nombre d’opérations quantiques réalisables
- Capacité à maintenir un calcul cohérent
Ce que Shor change pour RSA et la sécurité informatique
Le mécanisme quantique prend une portée pratique lorsqu’on le relie aux systèmes utilisés pour protéger les échanges numériques. RSA s’appuie précisément sur la difficulté de retrouver les facteurs premiers d’un grand produit.
RSA face à une menace encore conditionnelle
Un ordinateur quantique suffisamment puissant pourrait appliquer l’algorithme de Shor à la factorisation d’un grand entier RSA. Il pourrait alors compromettre certaines clés, ce qui mettrait en péril des communications protégées par des dispositifs vulnérables.
Selon le NIST, l’adoption de solutions postquantiques constitue une préparation nécessaire à l’évolution des capacités informatiques. Le risque concerne aussi les données interceptées aujourd’hui puis conservées pour être déchiffrées plus tard, si des moyens suffisants deviennent disponibles.
Les organisations peuvent commencer par repérer où RSA est utilisé, inventorier la durée de vie des données sensibles et prévoir des mécanismes de remplacement. Cette démarche réduit la dépendance à une seule famille de protections.
| Élément | Fonction actuelle | Enjeu quantique |
|---|---|---|
| RSA | Échange de clés et signatures numériques | Vulnérable en principe à Shor à grande échelle |
| Données archivées | Conservation d’informations sensibles | Risque de déchiffrement ultérieur |
| Inventaire cryptographique | Repérage des protections déployées | Étape de préparation au remplacement |
| Cryptographie postquantique | Protection conçue pour résister aux attaques quantiques connues | Migration à planifier selon les besoins |
Préparer la migration sans céder à l’alarmisme
La menace théorique appelle une planification sérieuse, pas l’abandon immédiat de tous les outils actuels. Les équipes informatiques doivent suivre les recommandations des organismes spécialisés et privilégier les solutions standardisées.
Pour une entreprise, un premier exercice consiste à dresser la liste des certificats, équipements et échanges reposant sur RSA. Elle peut ensuite identifier les systèmes difficiles à mettre à jour et tester progressivement des mécanismes postquantiques.
Ce travail demande du temps, notamment lorsque des appareils restent déployés pendant de longues années. L’enjeu est de rendre la sécurité informatique adaptable avant que la puissance quantique ne transforme une possibilité mathématique en capacité opérationnelle.
Source : Peter W. Shor, « Algorithms for quantum computation: discrete logarithms and factoring », Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.