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(119, 2526)\) . Justifier.
- Expliquer pourquoi \( (119, 627)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 119\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (119, 627)\) on a obtenu le message 481-2471-262-749-1780-1529-651-1545-1579-857-1090-1185-1717-117. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(119, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
119 & 2526 & 119 & 0&467 & -22 \\ \hline
2526 & 119 & 27 & 21&-22 & 467 \\ \hline
119 & 27 & 11 & 4&5 & -22 \\ \hline
27 & 11 & 5 & 2&-2 & 5 \\ \hline
11 & 5 & 1 & 2&1 & -2 \\ \hline
5 & 1 & 0 & 5&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 119\) et \( 2526\) est \( 1\) alors \( (119, 627)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 119^{-1}\equiv_{2526}467\) .
- Pour déchiffrer on fait \( 467(x-627) \) .
Message : AUXINNOCENTSLESMAINSPLEINES
\[
\begin{array}{c|*{7}{c}}&481&2471&262&749&1780&1529&651
\\\hline x-b&-146&1844&-365&122&1153&902&24
\\\hline a^{-1}(x-b)&-68182&861148&-170455&56974&538451&421234&11208
\\\hline \%2526&20&2308&1313&1402&413&1918&1104
\\\hline Décodage&AU&XI&NN&OC&EN&TS&LE
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&1545&1579&857&1090&1185&1717&117
\\\hline x-b&918&952&230&463&558&1090&-510
\\\hline a^{-1}(x-b)&428706&444584&107410&216221&260586&509030&-238170
\\\hline \%2526&1812&8&1318&1511&408&1304&1800
\\\hline Décodage&SM&AI&NS&PL&EI&NE&SA
\end{array}\]