L'exercice suivant est automatiquement et aléatoirement généré par ataraXy.
Si vous regénérez la page (F5) les valeurs seront changées.
La correction se trouve en bas de page.
On considère dans le système RSA, la clef publique $ (5917, 4463)$ .
- Déterminer deux entiers $ p$ et $ q$ tel que $ p {<} q$ et $ 5917=pq$ .
- Justifier que $ (5917, 4463)$ est une clef publique valide du cryptosystème RSA.
-
- Déterminer la décomposition de $ 4463$ en binaire.
- Calculer $ 173^{4463}$ modulo $ 5917$ .
- Quel est le message chiffré de $ M=173$ .
Déterminer la clef privé associée à la clef publique $ (5917, 4463)$ .
Déchiffrer le message $ M'=841$
Cliquer ici pour afficher la solution
- On observe que $ 5917=97\times 61$ .
- Pour vérifier que $ (5917, 4463)$ est une clef publique valide du cryptosystème RSA, il faut d'une part que $ 5917$ soit le produit de deux nombres premiers, ce que nous avons vérifier à la question précédente. Il faut d'autre part que $ 4463$ soit inversible modulo $ \phi=(p-1)(q-1)=96\times60=5760$ . Ce qui se vérifie avec l'algorithme d'Euclide :
$$\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
5760 & 4463 & 1297 & 1&-1896 & 2447 \\ \hline
4463 & 1297 & 572 & 3&551 & -1896 \\ \hline
1297 & 572 & 153 & 2&-243 & 551 \\ \hline
572 & 153 & 113 & 3&65 & -243 \\ \hline
153 & 113 & 40 & 1&-48 & 65 \\ \hline
113 & 40 & 33 & 2&17 & -48 \\ \hline
40 & 33 & 7 & 1&-14 & 17 \\ \hline
33 & 7 & 5 & 4&3 & -14 \\ \hline
7 & 5 & 2 & 1&-2 & 3 \\ \hline
5 & 2 & 1 & 2&1 & -2 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}$$
-
- Le nombre $ 4463$ en binaire s'écrit $ 1000101101111$ .
- On appliquel'algorithme d'exponentiation modulaire :
$$
\begin{array}{r|*{13}{|c}}
k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\\hline173^{2^k} & 173 & 29929 & 118336 & 34963569 & 256 & 65536 & 201601 & 178929 & 2013561 & 3171961 & 201601 & 178929 & 2013561\\mod\ 5917 & \fbox{173} & \fbox{344} & \fbox{5913} & \fbox{16} & 256 & \fbox{449} & \fbox{423} & 1419 & \fbox{1781} & 449 & 423 & 1419 & \fbox{1781}
\end{array}
$$
Finalement $ 173^{4463}=5178$
- Lorsque l'on applique le processus de chiffrement RSA avec $ (5917, 4463)$ comme clef publique a un message $ M$ , il faut réaliser l'opération $ M^e\% n$ soit ici $ M=173$ soit $ 173^{4463}$ modulo $ 5917$ que nous avons fait à la question précédente. Le chiffrement de $ M=173$ est donc $ 5178$ .
Pour déterminer la clef privé associée à $ (5917, 4463)$ , il suffit de déterminer l'inverse de $ 4463$ modulo $ 5760$ . Nous avons précédement appliquer l'algorithme d'Euclide étendue. Nous observons donc que la clef privé est $ (5917, 2447)$ .
Comme précédement on va appliquer l'algorithme d'exponentiation modulaire rapide pour calculer $ 841^{2447}$ modulo $ 5917$ .
$$
\begin{array}{r|*{12}{|c}}
k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\\hline841^{2^k} & 841 & 707281 & 9972964 & 7946761 & 52900 & 30958096 & 123904 & 30958096 & 123904 & 30958096 & 123904 & 30958096\\mod\ 5917 & \fbox{841} & \fbox{3158} & \fbox{2819} & \fbox{230} & 5564 & 352 & 5564 & \fbox{352} & \fbox{5564} & 352 & 5564 & \fbox{352}
\end{array}
$$
Finalement le déchiffrement de $ 841$ est $ 197$ .