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(79, 2526)\) . Justifier.
- Expliquer pourquoi \( (79, 104)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 79\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (79, 104)\) on a obtenu le message 792-1729-2340-736-2475-446-1386-2446-1120-1181. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(79, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
79 & 2526 & 79 & 0&-1247 & 39 \\ \hline
2526 & 79 & 77 & 31&39 & -1247 \\ \hline
79 & 77 & 2 & 1&-38 & 39 \\ \hline
77 & 2 & 1 & 38&1 & -38 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 79\) et \( 2526\) est \( 1\) alors \( (79, 104)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 79^{-1}\equiv_{2526}-1247\) .
- Pour déchiffrer on fait \( -1247(x-104) \) .
Message : JEUDEMAINJEUDEVILAIN
\[
\begin{array}{c|*{5}{c}}&792&1729&2340&736&2475
\\\hline x-b&688&1625&2236&632&2371
\\\hline a^{-1}(x-b)&-857936&-2026375&-2788292&-788104&-2956637
\\\hline \%2526&904&2003&412&8&1309
\\\hline Décodage&JE&UD&EM&AI&NJ
\end{array}\]
\[
\begin{array}{c|*{5}{c}}&446&1386&2446&1120&1181
\\\hline x-b&342&1282&2342&1016&1077
\\\hline a^{-1}(x-b)&-426474&-1598654&-2920474&-1266952&-1343019
\\\hline \%2526&420&304&2108&1100&813
\\\hline Décodage&EU&DE&VI&LA&IN
\end{array}\]