Il y a une série de 5 articles sur RSA :
- Démarrer les défis contenant des clés RSA
- Comment chiffrer (et déchiffrer avec RSA
- RSA : Attention à vos P et à vos Q (celui-ci)
- RSA : Même message, même module, exposants différents
- RSA : Même message, même exposant, modules différents
En 2012, Nadia Heninger, Zakir Durumeric, Eric Wustrow et J. Alex Halderman ont publié un article intitulé : Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices (jeu de mots avec l’expression Mind your Ps and Qs)
Cet article illustre d’une certaine façon le paradoxe des anniversaires : notre intuition nous dit que dans un groupe de 25 personnes, il est improbable que deux d’entre elles fêtent leur anniversaire le même jour. Pourtant, un simple calcul montre que cela se produit dans plus de 50% des cas.
Le module d’une clé RSA, $n$, est obtenu en faisant le produit de 2 nombres premiers
$p$ et $q$. En récupérant sur Internet un grand nombre de clés (plus de 10 millions),
ils ont pu constater que plusieurs clés publiques partageaient le même module :
- parfois parce que c’était le module par défaut à l’installation et qu’il n’avait pas été changé
- parfois parce que le générateur de nombres aléatoires permettant de choisir les deux valeurs
$p$et$q$était de mauvaise qualité.
Une autre constatation est que dans environ 0.5% des cas, deux clés publiques, bien qu’elles soient différentes, partagent un des deux facteurs communs $p$ ou $q$. Ce défaut est grave. En effet, si on dispose de deux nombres $n_1=pq$ et $n_2=pr$ qui sont deux modules appartenant à deux clés publiques, alors il devient très facile de factoriser ces deux modules. Nous n’avons plus à rechercher les décompositions en facteurs premiers (ce qui est lent), mais nous pouvons simplement calculer leur pgcd (ce qui est très rapide). Une fois le pgcd $p$ connu, calculer l’autre facteur premier est une simple division.
Et comme nous l’avons vu précédemment, une fois que les deux facteurs premiers sont connus, il est facile de calculer l’exposant privé (et donc la clé privée) à partir de l’exposant public.
En conséquence, si on a deux modules publics non premiers entre eux, ce qui se produit parfois, on les factorise en quelques secondes :
import math
p = math.gcd(n1, n2)
q1 = n1 // p
q2 = n2 // p