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.
Exercice
On considère dans le système RSA, la clef publique \( (3953, 3511)\) .
- Déterminer deux entiers \( p\) et \( q\) tel que \( p {<} q\) et \( 3953=pq\) .
- Justifier que \( (3953, 3511)\) est une clef publique valide du cryptosystème RSA.
-
- Déterminer la décomposition de \( 3511\) en binaire.
- Calculer \( 66^{3511}\) modulo \( 3953\) .
- Quel est le message chiffré de \( M=66\) .
Déterminer la clef privé associée à la clef publique \( (3953, 3511)\) .
Déchiffrer le message \( M'=3899\)
Cliquer ici pour afficher la solution
Exercice
- On observe que \( 3953=59\times 67\) .
- Pour vérifier que \( (3953, 3511)\) est une clef publique valide du cryptosystème RSA, il faut d'une part que \( 3953\) soit le produit de deux nombres premiers, ce que nous avons vérifier à la question précédente. Il faut d'autre part que \( 3511\) soit inversible modulo \( \phi=(p-1)(q-1)=58\times66=3828\) . 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
3828 & 3511 & 317 & 1&731 & -797 \\ \hline
3511 & 317 & 24 & 11&-66 & 731 \\ \hline
317 & 24 & 5 & 13&5 & -66 \\ \hline
24 & 5 & 4 & 4&-1 & 5 \\ \hline
5 & 4 & 1 & 1&1 & -1 \\ \hline
4 & 1 & 0 & 4&0 & 1 \\ \hline
\end{array}\]
-
- Le nombre \( 3511\) en binaire s'écrit \( 110110110111\) .
- On appliquel'algorithme d'exponentiation modulaire :
\[
\begin{array}{r|*{12}{|c}}
k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\\hline66^{2^k} & 66 & 4356 & 162409 & 112896 & 4892944 & 9504889 & 3523129 & 1012036 & 4624 & 450241 & 12616704 & 7187761\\mod\ 3953 & \fbox{66} & \fbox{403} & \fbox{336} & 2212 & \fbox{3083} & \fbox{1877} & 1006 & \fbox{68} & \fbox{671} & 3552 & \fbox{2681} & \fbox{1207}
\end{array}
\]
Finalement \( 66^{3511}=1406\)
- Lorsque l'on applique le processus de chiffrement RSA avec \( (3953, 3511)\) comme clef publique a un message \( M\) , il faut réaliser l'opération \( M^e\% n\) soit ici \( M=66\) soit \( 66^{3511}\) modulo \( 3953\) que nous avons fait à la question précédente. Le chiffrement de \( M=66\) est donc \( 1406\) .
Pour déterminer la clef privé associée à \( (3953, 3511)\) , il suffit de déterminer l'inverse de \( 3511\) modulo \( 3828\) . Nous avons précédement appliquer l'algorithme d'Euclide étendue. Nous observons donc que la clef privé est \( (3953, 3031)\) .
Comme précédement on va appliquer l'algorithme d'exponentiation modulaire rapide pour calculer \( 3899^{3031}\) modulo \( 3953\) .
\[
\begin{array}{r|*{12}{|c}}
k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\\hline3899^{2^k} & 3899 & 15202201 & 8503056 & 23409 & 13278736 & 370881 & 10575504 & 1510441 & 156025 & 3452164 & 1428025 & 984064\\mod\ 3953 & \fbox{3899} & \fbox{2916} & \fbox{153} & 3644 & \fbox{609} & 3252 & \fbox{1229} & \fbox{395} & \fbox{1858} & \fbox{1195} & 992 & \fbox{3720}
\end{array}
\]
Finalement le déchiffrement de \( 3899\) est \( 51\) .