Étape 1
Pour déchiffrer le message $C = 57$, il convient de déterminer la clé privée $d$, puis de calculer le reste de $C^d$ modulo $77$.
Étape 2
Étape 1 : Factorisation et indicateur d'Euler
Le nombre $n = 77$ se décompose en produit de deux nombres premiers : $$77 = 7 \times 11$$ L'indicateur d'Euler associé est égal à : $$\phi(77) = (7 - 1)(11 - 1) = 6 \times 10 = 60$$
Étape 3
Étape 2 : Recherche de la clé privée $d$
La clé privée $d$ est l'inverse de l'exposant public $e = 13$ modulo $60$, c'est-à-dire l'entier $d \in \{1, \dots, 59\}$ vérifiant : $$13d \equiv 1 \pmod{60}$$ En appliquant l'algorithme d'Euclide à $60$ et $13$ : $$60 = 4 \times 13 + 8$$ $$13 = 1 \times 8 + 5$$ $$8 = 1 \times 5 + 3$$ $$5 = 1 \times 3 + 2$$ $$3 = 1 \times 2 + 1$$ En remontant les égalités, on obtient l'identité de Bézout : $$5 \times 60 - 23 \times 13 = 1$$ On en déduit que $-23 \times 13 \equiv 1 \pmod{60}$. Comme $-23 \equiv 37 \pmod{60}$, la clé de déchiffrement est : $$d = 37$$
Étape 4
Étape 3 : Calcul du message clair $M \equiv 57^{37} \pmod{77}$
Pour calculer $57^{37} \pmod{77}$, on étudie la congruence modulo $7$ et modulo $11$.
Étape 5
Modulo $7$ : Comme $57 = 7 \times 8 + 1 \equiv 1 \pmod 7$, on a : $$M \equiv 1^{37} \equiv 1 \pmod 7$$
Étape 6
Modulo $11$ : Comme $57 = 11 \times 5 + 2 \equiv 2 \pmod{11}$, on applique le petit théorème de Fermat. Puisque $11$ est premier et ne divise pas $2$, on a $2^{10} \equiv 1 \pmod{11}$. Comme $37 = 3 \times 10 + 7$, il vient : $$M \equiv 2^{37} \equiv (2^{10})^3 \times 2^7 \equiv 1^3 \times 128 \pmod{11}$$ Or $128 = 11 \times 11 + 7 \equiv 7 \pmod{11}$, d'où : $$M \equiv 7 \pmod{11}$$
Étape 7
Étape 4 : Résolution du système de congruences
Le message clair $M$ vérifie le système : $$\begin{cases} M \equiv 1 \pmod 7 \\ M \equiv 7 \pmod{11} \end{cases}$$ De la seconde congruence, il existe un entier $k$ tel que $M = 11k + 7$. En substituant dans la première congruence : $$11k + 7 \equiv 1 \pmod 7$$ $$4k \equiv 1 \pmod 7$$ En multipliant par $2$, car $2 \times 4 = 8 \equiv 1 \pmod 7$, on obtient : $$k \equiv 2 \pmod 7$$ Ainsi, $k = 2 + 7m$ pour un entier $m$. Comme $0 \le M < 77$, la seule valeur possible s'obtient pour $m = 0$, soit $k = 2$. On trouve finalement : $$M = 11 \times 2 + 7 = 29$$
Méthode clé
Pour déchiffrer un message RSA $C$, on cherche la clé privée $d$ vérifiant $e \cdot d \equiv 1 \pmod{\phi(n)}$. Le message clair s'obtient via $M \equiv C^d \pmod n$, calculé efficacement en résolvant un système de congruences modulo les facteurs premiers de $n$.
Piège à éviter
Chercher à calculer directement la puissance $57^{37}$ sur un entier global au lieu de décomposer le problème modulo $7$ et modulo $11$ à l'aide du petit théorème de Fermat.
