PGCD : Plus Grand Commun Diviseur
Cryptographie
PGCD : Plus Grand Commun Diviseur, le plus grand entier qui divise à la fois deux nombres donnés. « Le calcul d'école primaire qui casse des clés RSA générées sans hasard », par analogie avec la ressemblance entre deux frères, qui trahit aussitôt le nom du père qu'ils voulaient tenir secret.
Calcul : L'algorithme d'Euclide, vieux de plus de deux mille ans, calcule le PGCD de deux nombres de plusieurs milliers de bits en une fraction de seconde. En anglais, on parle de GCD (Greatest Common Divisor). L'ancienneté de l'algorithme n'a d'égale que l'imprudence de ceux qui ont rendu son emploi rentable.
Attaque contre RSA : Un module RSA est le produit de deux nombres premiers secrets p et q. Si deux clés partagent un même facteur premier, parce que le générateur de nombres aléatoires manquait d'entropie au moment de leur création, le PGCD des deux modules publics donne ce facteur, et la division donne l'autre : les deux clés privées sont reconstituées sans aucun accès aux équipements.
Constat à grande échelle : En 2012, deux équipes (Heninger et al., « Mining Your Ps and Qs », et Lenstra et al.) ont collecté des millions de clés publiques sur Internet et en ont factorisé des dizaines de milliers par calcul de PGCD par lots, surtout sur des équipements embarqués générant leur clé au premier démarrage.
Ce qui arrive si on s'en passe
Un équipement qui génère sa clé RSA au premier démarrage, avant d'avoir accumulé assez d'entropie, produit des facteurs premiers que d'autres exemplaires du même modèle produisent aussi. Un attaquant qui collecte les certificats publics du parc n'a plus qu'à calculer des PGCD deux à deux pour retrouver les clés privées partagées, puis à usurper ou déchiffrer ces équipements à distance. Aucune intrusion n'est nécessaire, aucune alerte ne se déclenche : la faille est publiée par la victime elle-même, à chaque poignée de main TLS.
Explication de la marmotte
Le PGCD de deux nombres est le plus grand nombre qui les divise tous les deux, notion vue au collège. Une clé RSA repose sur un grand nombre obtenu en multipliant deux nombres premiers secrets. Si deux clés ont été fabriquées avec un mauvais tirage au hasard et partagent par malchance un de ces nombres secrets, un simple calcul de PGCD entre leurs parties publiques le révèle. À partir de là, il devient facile de retrouver les deux clés privées.
Où ce terme est utilisé
- Créer, vérifier et utiliser les clés dès le départ (1 occurrence)
- Produire de l’aléa utilisable en cryptographie (1 occurrence)
- RNG matériel ou PRNG dans un HSM (1 occurrence)