RSA : Même message, même exposant, modules différents

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

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)$ . N’importe quel nombre premier fait a priori l’affaire, et il est arrivé que 3 soit utilisé (à un époque dans les cartes bancaires je crois). Actuellement, l’exposant $e$ souvent choisi est 65537.

L’exposant 3 pose un problème particulier, lorsqu’il est utilisé comme exposant public de trois clés qui servent à chiffrer trois fois le même message (on aurait la même chose avec l’exposant 5, si on chiffre cinq fois le même message).

Pour comprendre ce qui se passe, il faut utiliser le théorième des restes chinois, documenté par exemple sur wikipedia ou bibmath.

Sans entrer dans les détails (vous les trouverez dans les références ci-dessus), le théorème des restes chinois permet, si on a un système d’équation de congruences (en $x$ ) de type :

$$\left\{\begin{array}{l} x \equiv C1 [n1]\\ x \equiv C2 [n2]\\ x \equiv C3 [n3]\\ \end{array}\right.$$

de trouver $x$ modulo $[n1.n2.n3]$ .

Cette solution est donnée par : $x= C1.n2.n3.m1 + C2.n1.n3.m2 + C3.n1.n2.m3$ avec $m1$ l’inverse de $n2.n3$ modulo $n1$ , $m2$ l’inverse de $n1.n3$ modulo $n2$ … Pour trouver les inverses, on pourra utiliser l'algorithme d’euclide étendu.

Partons du principe qu’on peut donc résoudre le système d’équations ci dessous, si on dispose des bons outils (théorème des restes chinois, et algorithme d’Euclide étendu) et revenons à RSA.

Si on chiffre le même message $M$ , avec 3 clés $(e,n1)$ , $(e, n2)$ , $(e, n3)$ , on obtient les trois messages $C_1$ , $C_2$ , $C_3$ :

$$\left\{\begin{array}{l} C_1 = M^3 [n_1]\\ C_2 = M^3 [n_2]\\ C_3 = M^3 [n_3]\\ \end{array}\right.$$

Ce système est identique à celui exposé précédemment : il s’agit d’un système de congruences, $a \equiv b [n]$ signifie que $a$ et $b$ ont le même reste si on les divise par $n$ , c’est donc identique à $b \equiv a [n]$ . Nous disposons donc d’un moyen pour trouver $M^3$ modulo $n_1.n_2.n_3$ .

C’est maintenant qu’il est utile que l’exposant soit égal à 3. Puisque $M$ est le message à chiffrer par RSA, il est strictement plus petit que $n_1$ , $n_2$ ou $n_3$ . En conséquence, $M^3$ est plus petit que $n_1.n_2.n_3$ . La valeur que l’on va trouver : $M^3\, [n_1.n_2.n_3]$ sera donc exactement le cube de $M$.

Calculer $M$ en connaissant $M^3$ modulo $n1.n2.n3$ revient donc à calculer une racine cubique.

Ce n’est pas très compliqué avec les bons algorithmes (les nombres sont en général très grand, et les librairies mathématiques usuelles calculent les racines avec des flottants, et non des entiers). Pour l’occasion, on peut se confectionner un petit algo de recherche de racine cubique en utilisant par exemple la méthode de Héron.

Exemple

Ouf… un exemple.

Voici les trois clés :

>>> (e, n1) = (3, 589)
>>> (e, n2) = (3, 493)
>>> (e, n3) = (3, 481)

On chiffre un certain message $M$ :

>>> C1 = M**e % n1
>>> C2 = M**e % n2
>>> C3 = M**e % n3
>>> C1, C2, C3
(388, 405, 285)

Le système à résoudre est donc :

$$\left\{\begin{array}{l} M^3 = 388 [589]\\ M^3 = 405 [493]\\ M^3 = 285 [481]\\ \end{array}\right.$$

On applique le théorème des restes chinois pour calculer $M^3$ . Il faut d’abord calculer $m_1$ l’inverse de $n_2.n_3$ modulo $n_1$ . L’algorithme d’Euclide étendu nous donne :

>>> m1 = inverse_modulo(n2*n3, n1)
>>> m2 = inverse_modulo(n1*n3, n2)
>>> m3 = inverse_modulo(n1*n2, n3)
>>> m1, m2, m3
(516, 98, 445)

Il faudra vous faire la fonction inverse_modulo :)

Le théorème des restes chinois donne :

>>> mcube = (C1 * n2 * n3 * m1 + C2 * n1 * n3 * m2 + C3 * n1 * n2 * m3) % (n1 * n2 * n3)
12326391

Il ne reste plus qu’à extraire la racine carrée de ce résultat pour trouver 231, qui est effectivement le message en clair utilisé (vous pouvez le vérifiant chiffrant 231 avec les 3 clés).