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(371, 2526)\) . Justifier.
- Expliquer pourquoi \( (371, 1123)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 371\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (371, 1123)\) on a obtenu le message 1411-2476-1099-692-489-2476-9-1640-489-479. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(371, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
371 & 2526 & 371 & 0&1103 & -162 \\ \hline
2526 & 371 & 300 & 6&-162 & 1103 \\ \hline
371 & 300 & 71 & 1&131 & -162 \\ \hline
300 & 71 & 16 & 4&-31 & 131 \\ \hline
71 & 16 & 7 & 4&7 & -31 \\ \hline
16 & 7 & 2 & 2&-3 & 7 \\ \hline
7 & 2 & 1 & 3&1 & -3 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 371\) et \( 2526\) est \( 1\) alors \( (371, 1123)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 371^{-1}\equiv_{2526}1103\) .
- Pour déchiffrer on fait \( 1103(x-1123) \) .
Message : TOUTNOUVEAUTOUTBEAU
\[
\begin{array}{c|*{5}{c}}&1411&2476&1099&692&489
\\\hline x-b&288&1353&-24&-431&-634
\\\hline a^{-1}(x-b)&317664&1492359&-26472&-475393&-699302
\\\hline \%2526&1914&2019&1314&2021&400
\\\hline Décodage&TO&UT&NO&UV&EA
\end{array}\]
\[
\begin{array}{c|*{5}{c}}&2476&9&1640&489&479
\\\hline x-b&1353&-1114&517&-634&-644
\\\hline a^{-1}(x-b)&1492359&-1228742&570251&-699302&-710332
\\\hline \%2526&2019&1420&1901&400&2000
\\\hline Décodage&UT&OU&TB&EA&UA
\end{array}\]