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(113, 2526)\) . Justifier.
- Expliquer pourquoi \( (113, 936)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 113\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (113, 936)\) on a obtenu le message 1643-1514-218-48-1462-1244-1964-1378-2124-513-1914-1764-668. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(113, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
113 & 2526 & 113 & 0&1073 & -48 \\ \hline
2526 & 113 & 40 & 22&-48 & 1073 \\ \hline
113 & 40 & 33 & 2&17 & -48 \\ \hline
40 & 33 & 7 & 1&-14 & 17 \\ \hline
33 & 7 & 5 & 4&3 & -14 \\ \hline
7 & 5 & 2 & 1&-2 & 3 \\ \hline
5 & 2 & 1 & 2&1 & -2 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 113\) et \( 2526\) est \( 1\) alors \( (113, 936)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 113^{-1}\equiv_{2526}1073\) .
- Pour déchiffrer on fait \( 1073(x-936) \) .
Message : ILNYAQUELAVERITEQUIBLESSE
\[
\begin{array}{c|*{6}{c}}&1643&1514&218&48&1462&1244
\\\hline x-b&707&578&-718&-888&526&308
\\\hline a^{-1}(x-b)&758611&620194&-770414&-952824&564398&330484
\\\hline \%2526&811&1324&16&2004&1100&2104
\\\hline Décodage&IL&NY&AQ&UE&LA&VE
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&1964&1378&2124&513&1914&1764&668
\\\hline x-b&1028&442&1188&-423&978&828&-268
\\\hline a^{-1}(x-b)&1103044&474266&1274724&-453879&1049394&888444&-287564
\\\hline \%2526&1708&1904&1620&801&1104&1818&400
\\\hline Décodage&RI&TE&QU&IB&LE&SS&EA
\end{array}\]