Il y a une série de 5 articles sur RSA :

  1. Démarrer les défis contenant des clés RSA
  2. Comment chiffrer (et déchiffrer avec RSA
  3. RSA : Attention à vos P et à vos Q
  4. RSA : Même message, même module, exposants différents (celui-ci)
  5. RSA : Même message, même exposant, modules différents

On rappelle qu’une clé publique RSA est formée d’un exposant public $e$ et d’un module $n$, produit de deux nombres premiers $p$ et $q$. L’exposant public doit être premier avec $(p-1)(q-1)$.

Nous allons voir ce qui se produit si on chiffre le même message $M$ avec deux clés publiques ayant le même module $(e_1,n)$ et $(e_2, n)$

Les deux message chiffrés sont $C_1$ et $C_2$ :

$$\left\{\begin{array}{l} C_1 = M^{e_1} [n]\\ C_2 = M^{e_2} [n]\\ \end{array}\right.$$

Comme les 2 exposants $e_1$ et $e_2$ sont choisis très souvent premiers, il est particulièrement probables qu’ils soient premiers entre eux. Le théorème de bezout indique que dans ce cas, il existe deux autres entiers relatifs $a$ et $b$ tels que : $a.e_1 + b.e_2 = 1$.

En admettant qu’on trouve ces deux nombres. Calculons :

$C_1^a \times C_2^b = M^{e_1.a} \times M^{e_2.b} [n] = M^{a.e_1+b.e_2} [n] = M [n]$

Et l’affaire est réglée. Il reste donc à calculer les coefficients de Bezout $a$ et $b$. C’est encore une fois l’algorithme d’Euclide étendu que nous avons rencontré dans un billet similaire, qui permet de faire ça.