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(409, 2526)\) . Justifier.
- Expliquer pourquoi \( (409, 334)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 409\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (409, 334)\) on a obtenu le message 2242-690-1464-2142-131-134-359-1873-16-431-527-2463-2270. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(409, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
409 & 2526 & 409 & 0&877 & -142 \\ \hline
2526 & 409 & 72 & 6&-142 & 877 \\ \hline
409 & 72 & 49 & 5&25 & -142 \\ \hline
72 & 49 & 23 & 1&-17 & 25 \\ \hline
49 & 23 & 3 & 2&8 & -17 \\ \hline
23 & 3 & 2 & 7&-1 & 8 \\ \hline
3 & 2 & 1 & 1&1 & -1 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 409\) et \( 2526\) est \( 1\) alors \( (409, 334)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 409^{-1}\equiv_{2526}877\) .
- Pour déchiffrer on fait \( 877(x-334) \) .
Message : LEPOISSONPOURRITPARLATETE
\[
\begin{array}{c|*{6}{c}}&2242&690&1464&2142&131&134
\\\hline x-b&1908&356&1130&1808&-203&-200
\\\hline a^{-1}(x-b)&1673316&312212&991010&1585616&-178031&-175400
\\\hline \%2526&1104&1514&818&1814&1315&1420
\\\hline Décodage&LE&PO&IS&SO&NP&OU
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&359&1873&16&431&527&2463&2270
\\\hline x-b&25&1539&-318&97&193&2129&1936
\\\hline a^{-1}(x-b)&21925&1349703&-278886&85069&169261&1867133&1697872
\\\hline \%2526&1717&819&1500&1711&19&419&400
\\\hline Décodage&RR&IT&PA&RL&AT&ET&EA
\end{array}\]