Tests de primalité et cryptographie
Savoir si un nombre de trois cents chiffres est premier prend une fraction de seconde. Retrouver ses facteurs quand il est composé semble prendre des milliards d'années. Toute la cryptographie à clé publique repose sur ce déséquilibre : on fabrique facilement de grands nombres premiers, et on ne sait pas défaire leur produit. Cinq planches pour comprendre comment on teste, comment on certifie, comment on chiffre, et jusqu'où vont les attaques.
Vue d'ensemble
La page sur Fermat, Euler et les restes chinois a présenté le principe de RSA sur de petits nombres. Ici, on passe à l'échelle réelle. Quatre problèmes ont des difficultés très différentes :
| Problème | Méthode | Pour 300 chiffres |
|---|---|---|
| n est-il premier ? (réponse « probablement ») | Miller-Rabin | quelques millisecondes |
| n est-il premier ? (avec preuve) | certificats, ECPP, AKS (2002) | quelques secondes |
| trouver les facteurs de n = pq | crible algébrique (GNFS) | hors de portée (record : 250 chiffres) |
| logarithme discret modulo p | pas de bébé, pas de géant ; crible | hors de portée aussi |
Le crible et la division d'essai : sûrs, mais lents
Les méthodes de l'école sont exactes. Leur défaut, c'est leur durée.
Le crible d'Ératosthène (IIIᵉ siècle av. J.-C.) raye les multiples de 2, puis de 3, de 5, de 7… Ce qui reste est premier. Pour un seul nombre n, on essaie de le diviser par tous les entiers jusqu'à √n : si aucun ne convient, n est premier. C'est rapide pour n = 1 000 003, mais le nombre d'essais, environ √n/2, double quand n est multiplié par 4. Pour un nombre de 300 chiffres, il faudrait environ 10150 divisions. Avec un milliard de divisions par seconde, cela prendrait 10133 ans, alors que l'Univers a 1,4 × 1010 ans.
Fermat et Miller-Rabin : chercher un témoin
Un seul nombre a suffit à prouver que n est composé, sans connaître ses facteurs.
Si n est premier, an−1 ≡ 1 (mod n) pour tout a non multiple de n (Fermat). Un a qui ne vérifie pas cette égalité est donc un témoin : il prouve que n est composé. Les bases qui « mentent » sont les menteurs de Fermat ; pour les nombres de Carmichael, comme 561, presque toutes les bases mentent. Miller (1976) et Rabin (1980) renforcent le test. On écrit n − 1 = 2sd avec d impair, et l'on regarde la suite ad, a2d, …, an−1. Si n est premier, elle commence par 1 ou passe par −1. Rabin a démontré qu'au plus un quart des bases peuvent mentir à ce test renforcé. Avec 20 bases, la probabilité d'erreur est donc inférieure à 4−20 ≈ 10−12.
Certifier un nombre premier : le certificat de Pratt
Une preuve courte, que n'importe qui peut vérifier en quelques calculs.
Miller-Rabin dit « probablement premier ». Pour une preuve, on utilise la réciproque de Fermat due à Lucas (1876) : s'il existe a tel que an−1 ≡ 1 (mod n) et a(n−1)/q ≢ 1 (mod n) pour chaque facteur premier q de n − 1, alors a est d'ordre n − 1 modulo n, et n est premier. Encore faut-il être sûr que les q sont premiers : on les certifie de la même façon. On obtient un arbre, le certificat de Pratt (1975), dont la vérification est rapide même si sa construction demande de factoriser n − 1. Les records actuels utilisent les courbes elliptiques (ECPP) ; en 2002, Agrawal, Kayal et Saxena ont trouvé un test déterministe en temps polynomial (AKS).
RSA à taille réelle
Deux grands premiers, un produit public, un exposant secret.
Bob tire deux nombres premiers p et q au hasard : on prend un nombre de la taille voulue et on avance jusqu'au premier qui passe Miller-Rabin. Près de 10k, un nombre sur 2,3·k environ est premier, donc il en trouve vite. Il publie n = pq et e = 65 537 ; il garde d, l'inverse de e modulo (p − 1)(q − 1). Alice chiffre son message m en c = me mod n ; Bob retrouve m = cd mod n. Bob peut aussi signer : s = md mod n, et tout le monde vérifie se ≡ m. Connaître p et q permet de déchiffrer environ trois fois plus vite, grâce aux restes chinois.
Signature : Diffie-Hellman, les attaques et les records
La sécurité n'est pas démontrée : elle se mesure au coût des meilleures attaques connues.
Alice et Bob veulent une clé commune sans s'être jamais rencontrés. Ils choisissent publiquement un premier p et une racine primitive g. Alice tire un secret a et envoie A = ga mod p ; Bob tire b et envoie B = gb. Chacun calcule alors la même clé : Ba = Ab = gab. Un espion voit p, g, A et B. Pour retrouver a, il doit résoudre ga ≡ A, le logarithme discret. La méthode « pas de bébé, pas de géant » (Shanks, 1971) le fait en environ √p opérations : c'est faisable ici, mais pas pour p de 600 chiffres.
Pour casser RSA, il suffit de factoriser n. La méthode rho de Pollard (1975) fait tourner une suite x ↦ x² + 1 modulo n. Modulo le petit facteur p, la suite retombe forcément sur une valeur déjà vue au bout d'environ √p pas (paradoxe des anniversaires), et un PGCD révèle alors p. La page la lance ici sur des produits de deux premiers de même taille. L'effort est multiplié par environ √10 à chaque chiffre de p. Pour des premiers de 155 chiffres, il faudrait de l'ordre de 1077 pas. Le crible algébrique (GNFS) fait beaucoup mieux, mais reste sous-exponentiel.
En 1977, Martin Gardner publie dans Scientific American le défi RSA-129, un nombre de 129 chiffres, avec un message chiffré que ses auteurs estimaient indéchiffrable avant 40 millions de milliards d'années. Il tombe en 1994, grâce à 600 volontaires. Les défis lancés par RSA Laboratories ont ensuite servi d'étalon. Le record actuel, RSA-250 (829 bits), a demandé en 2020 environ 2 700 années de calcul d'un cœur de processeur. Les clés recommandées aujourd'hui font au moins 2 048 bits (617 chiffres). Un ordinateur quantique assez grand les casserait (algorithme de Shor, 1994) : c'est pourquoi des algorithmes « post-quantiques », fondés sur les réseaux euclidiens, ont été normalisés en 2024.
Une brève histoire
En résumé
Tester est facile
Miller-Rabin cherche un témoin ; trois quarts au moins des bases en sont pour un composé. Quelques bases suffisent pour une certitude pratique.
Prouver est possible
Le certificat de Pratt, ou ECPP pour les grands nombres, donne une preuve vérifiable par n'importe qui ; AKS montre que c'est polynomial.
Factoriser est difficile
RSA et Diffie-Hellman reposent sur des problèmes sans algorithme rapide connu : leur sécurité est une conjecture, mesurée par les records.
Pour aller plus loin
Courbes elliptiques. Les mêmes idées s'appliquent sur le groupe des points d'une courbe elliptique modulo p. Le logarithme discret y est plus difficile, ce qui permet des clés de 256 bits au lieu de 3 072 pour une sécurité comparable.
Les grands premiers de Mersenne se testent par le critère de Lucas-Lehmer, bien plus rapide que Miller-Rabin pour ces nombres particuliers (voir la page sur les nombres de Mersenne).
Liens. Fermat, Euler et restes chinois ; résidus quadratiques ; décomposition en facteurs premiers ; répartition des nombres premiers.