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(407, 2526)\) . Justifier.
- Expliquer pourquoi \( (407, 2316)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 407\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (407, 2316)\) on a obtenu le message 843-1194-1801-435-1856-2247-2016-1194-1004-465-581-134. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(407, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
407 & 2526 & 407 & 0&-391 & 63 \\ \hline
2526 & 407 & 84 & 6&63 & -391 \\ \hline
407 & 84 & 71 & 4&-13 & 63 \\ \hline
84 & 71 & 13 & 1&11 & -13 \\ \hline
71 & 13 & 6 & 5&-2 & 11 \\ \hline
13 & 6 & 1 & 2&1 & -2 \\ \hline
6 & 1 & 0 & 6&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 407\) et \( 2526\) est \( 1\) alors \( (407, 2316)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 407^{-1}\equiv_{2526}-391\) .
- Pour déchiffrer on fait \( -391(x-2316) \) .
Message : APRESLEFFORTLERECONFORT
\[
\begin{array}{c|*{6}{c}}&843&1194&1801&435&1856&2247
\\\hline x-b&-1473&-1122&-515&-1881&-460&-69
\\\hline a^{-1}(x-b)&575943&438702&201365&735471&179860&26979
\\\hline \%2526&15&1704&1811&405&514&1719
\\\hline Décodage&AP&RE&SL&EF&FO&RT
\end{array}\]
\[
\begin{array}{c|*{6}{c}}&2016&1194&1004&465&581&134
\\\hline x-b&-300&-1122&-1312&-1851&-1735&-2182
\\\hline a^{-1}(x-b)&117300&438702&512992&723741&678385&853162
\\\hline \%2526&1104&1704&214&1305&1417&1900
\\\hline Décodage&LE&RE&CO&NF&OR&TA
\end{array}\]