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
- Déterminer \( PGCD(355, 2526)\) . Justifier.
- Expliquer pourquoi \( (355, 2329)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 355\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (355, 2329)\) on a obtenu le message 193-708-1496-353-311-1554-2436-1240-2436-2206-1874-347. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(355, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
355 & 2526 & 355 & 0&-185 & 26 \\ \hline
2526 & 355 & 41 & 7&26 & -185 \\ \hline
355 & 41 & 27 & 8&-3 & 26 \\ \hline
41 & 27 & 14 & 1&2 & -3 \\ \hline
27 & 14 & 13 & 1&-1 & 2 \\ \hline
14 & 13 & 1 & 1&1 & -1 \\ \hline
13 & 1 & 0 & 13&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 355\) et \( 2526\) est \( 1\) alors \( (355, 2329)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 355^{-1}\equiv_{2526}-185\) .
- Pour déchiffrer on fait \( -185(x-2329) \) .
Message : LESRATSQUITTENTLENAVIRE
\[
\begin{array}{c|*{6}{c}}&193&708&1496&353&311&1554
\\\hline x-b&-2136&-1621&-833&-1976&-2018&-775
\\\hline a^{-1}(x-b)&395160&299885&154105&365560&373330&143375
\\\hline \%2526&1104&1817&19&1816&2008&1919
\\\hline Décodage&LE&SR&AT&SQ&UI&TT
\end{array}\]
\[
\begin{array}{c|*{6}{c}}&2436&1240&2436&2206&1874&347
\\\hline x-b&107&-1089&107&-123&-455&-1982
\\\hline a^{-1}(x-b)&-19795&201465&-19795&22755&84175&366670
\\\hline \%2526&413&1911&413&21&817&400
\\\hline Décodage&EN&TL&EN&AV&IR&EA
\end{array}\]