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(179, 2526)\) . Justifier.
- Expliquer pourquoi \( (179, 168)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 179\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (179, 168)\) on a obtenu le message 1857-506-192-892-1445-2273-261-1538-1320-2184-483-756-1993-1043-2500. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(179, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
179 & 2526 & 179 & 0&-127 & 9 \\ \hline
2526 & 179 & 20 & 14&9 & -127 \\ \hline
179 & 20 & 19 & 8&-1 & 9 \\ \hline
20 & 19 & 1 & 1&1 & -1 \\ \hline
19 & 1 & 0 & 19&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 179\) et \( 2526\) est \( 1\) alors \( (179, 168)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 179^{-1}\equiv_{2526}-127\) .
- Pour déchiffrer on fait \( -127(x-168) \) .
Message : CHAQUEPOULEVITDECEQUELLEGRATTE
\[
\begin{array}{c|*{7}{c}}&1857&506&192&892&1445&2273&261
\\\hline x-b&1689&338&24&724&1277&2105&93
\\\hline a^{-1}(x-b)&-214503&-42926&-3048&-91948&-162179&-267335&-11811
\\\hline \%2526&207&16&2004&1514&2011&421&819
\\\hline Décodage&CH&AQ&UE&PO&UL&EV&IT
\end{array}\]
\[
\begin{array}{c|*{8}{c}}&1538&1320&2184&483&756&1993&1043&2500
\\\hline x-b&1370&1152&2016&315&588&1825&875&2332
\\\hline a^{-1}(x-b)&-173990&-146304&-256032&-40005&-74676&-231775&-111125&-296164
\\\hline \%2526&304&204&1620&411&1104&617&19&1904
\\\hline Décodage&DE&CE&QU&EL&LE&GR&AT&TE
\end{array}\]