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(17, 2526)\) . Justifier.
- Expliquer pourquoi \( (17, 1520)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 17\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (17, 1520)\) on a obtenu le message 1274-321-1082-1305-400-1237-1031-1891-400-982. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(17, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
17 & 2526 & 17 & 0&743 & -5 \\ \hline
2526 & 17 & 10 & 148&-5 & 743 \\ \hline
17 & 10 & 7 & 1&3 & -5 \\ \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 \( 17\) et \( 2526\) est \( 1\) alors \( (17, 1520)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 17^{-1}\equiv_{2526}743\) .
- Pour déchiffrer on fait \( 743(x-1520) \) .
Message : QUIVEUTTOUTPERDTOUT
\[
\begin{array}{c|*{5}{c}}&1274&321&1082&1305&400
\\\hline x-b&-246&-1199&-438&-215&-1120
\\\hline a^{-1}(x-b)&-182778&-890857&-325434&-159745&-832160
\\\hline \%2526&1620&821&420&1919&1420
\\\hline Décodage&QU&IV&EU&TT&OU
\end{array}\]
\[
\begin{array}{c|*{5}{c}}&1237&1031&1891&400&982
\\\hline x-b&-283&-489&371&-1120&-538
\\\hline a^{-1}(x-b)&-210269&-363327&275653&-832160&-399734
\\\hline \%2526&1915&417&319&1420&1900
\\\hline Décodage&TP&ER&DT&OU&TA
\end{array}\]