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(271, 2526)\) . Justifier.
- Expliquer pourquoi \( (271, 873)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 271\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (271, 873)\) on a obtenu le message 1303-2137-1870-585-481-1195-210-1468-481-1864-752-655. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(271, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
271 & 2526 & 271 & 0&-755 & 81 \\ \hline
2526 & 271 & 87 & 9&81 & -755 \\ \hline
271 & 87 & 10 & 3&-26 & 81 \\ \hline
87 & 10 & 7 & 8&3 & -26 \\ \hline
10 & 7 & 3 & 1&-2 & 3 \\ \hline
7 & 3 & 1 & 2&1 & -2 \\ \hline
3 & 1 & 0 & 3&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 271\) et \( 2526\) est \( 1\) alors \( (271, 873)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 271^{-1}\equiv_{2526}-755\) .
- Pour déchiffrer on fait \( -755(x-873) \) .
Message : MEFIANCEESTMEREDESURETE
\[
\begin{array}{c|*{6}{c}}&1303&2137&1870&585&481&1195
\\\hline x-b&430&1264&997&-288&-392&322
\\\hline a^{-1}(x-b)&-324650&-954320&-752735&217440&295960&-243110
\\\hline \%2526&1204&508&13&204&418&1912
\\\hline Décodage&ME&FI&AN&CE&ES&TM
\end{array}\]
\[
\begin{array}{c|*{6}{c}}&210&1468&481&1864&752&655
\\\hline x-b&-663&595&-392&991&-121&-218
\\\hline a^{-1}(x-b)&500565&-449225&295960&-748205&91355&164590
\\\hline \%2526&417&403&418&2017&419&400
\\\hline Décodage&ER&ED&ES&UR&ET&EA
\end{array}\]