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
Vous recevez un message de la part de votre prof de math :
J'ai utilisé ta clef publique \( (3293, 437)\) du protocole RSA. Voici le message que je te transmets :
93-1233
Quel est le message claire ?
Vous détaillerez toutes les étapes de votre raisonnement et de vos calculs. Les éléments de réponse donnés sans justification seront considérées comme fausses.
Cliquer ici pour afficher la solution
Exercice
Commençons par déterminer deux entiers \( p\) et \( q\) tel que \( p\times q=3293\) . La racine carré de ce nombre est, arrondi inférieurement, \( 57\) . En cherchant à diviser par tous les nombres premiers jusqu'à cette valeur, on trouve rapidement que \( 3293\) est divisible par \( 37\) , précisément \( 3293=37\times89\) .
Cela signifie que \( \varphi=(p-1)(q-1)=3168\) . Nous pouvons donc déterminer la clef privé en cherchant l'inverse de \( e=437\) modulo \( \varphi=3168\) .
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
3168 & 437 & 109 & 7&-4 & 29 \\ \hline
437 & 109 & 1 & 4&1 & -4 \\ \hline
109 & 1 & 0 & 109&0 & 1 \\ \hline
\end{array}\]
En conclusion, la clef privée est \( (3293, 29)\) . Pour déchiffrer ce message, il suffit d'appliquer l'algorithme d'exponentiation modulaire rapide pour calculer \( x^{29} \) modulo \( n=3293\) . L'écriture binaire de \( d=29\) est \( 11101\) . Dans les tableaux nous encadrons alors les valeurs considérées.
\[
\begin{array}{r|*{5}{|c}}
k & 0 & 1 & 2 & 3 & 4\\\hline93^{2^k} & 93 & 8649 & 4255969 & 1996569 & 1022121\\mod\ 3293 & \fbox{93} & 2063 & \fbox{1413} & \fbox{1011} & \fbox{1291}
\end{array}
\]
Et on trouve que \( 93^{29}\equiv_{3293}720\)
Ce qui correspond aux caractères \( HU\) .
\[
\begin{array}{r|*{5}{|c}}
k & 0 & 1 & 2 & 3 & 4\\\hline1233^{2^k} & 1233 & 1520289 & 4910656 & 628849 & 10106041\\mod\ 3293 & \fbox{1233} & 2216 & \fbox{793} & \fbox{3179} & \fbox{3117}
\end{array}
\]
Et on trouve que \( 1233^{29}\equiv_{3293}1920\)
Ce qui correspond aux caractères \( TU\) .
En conclusion, le message claire est \( HUTU\)