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(401, 2526)\) . Justifier.
- Expliquer pourquoi \( (401, 911)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 401\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (401, 911)\) on a obtenu le message 1565-2356-89-2195-316-1667-2171-1070-2173. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(401, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
401 & 2526 & 401 & 0&863 & -137 \\ \hline
2526 & 401 & 120 & 6&-137 & 863 \\ \hline
401 & 120 & 41 & 3&41 & -137 \\ \hline
120 & 41 & 38 & 2&-14 & 41 \\ \hline
41 & 38 & 3 & 1&13 & -14 \\ \hline
38 & 3 & 2 & 12&-1 & 13 \\ \hline
3 & 2 & 1 & 1&1 & -1 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 401\) et \( 2526\) est \( 1\) alors \( (401, 911)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 401^{-1}\equiv_{2526}863\) .
- Pour déchiffrer on fait \( 863(x-911) \) .
Message : LERREURESTHUMAINE
\[
\begin{array}{c|*{4}{c}}&1565&2356&89&2195
\\\hline x-b&654&1445&-822&1284
\\\hline a^{-1}(x-b)&564402&1247035&-709386&1108092
\\\hline \%2526&1104&1717&420&1704
\\\hline Décodage&LE&RR&EU&RE
\end{array}\]
\[
\begin{array}{c|*{5}{c}}&316&1667&2171&1070&2173
\\\hline x-b&-595&756&1260&159&1262
\\\hline a^{-1}(x-b)&-513485&652428&1087380&137217&1089106
\\\hline \%2526&1819&720&1200&813&400
\\\hline Décodage&ST&HU&MA&IN&EA
\end{array}\]