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(379, 2526)\) . Justifier.
- Expliquer pourquoi \( (379, 1874)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 379\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (379, 1874)\) on a obtenu le message 759-2016-1054-894-2024-1054-2084-1697-2390-1789-2024-1829. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(379, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
379 & 2526 & 379 & 0&-1253 & 188 \\ \hline
2526 & 379 & 252 & 6&188 & -1253 \\ \hline
379 & 252 & 127 & 1&-125 & 188 \\ \hline
252 & 127 & 125 & 1&63 & -125 \\ \hline
127 & 125 & 2 & 1&-62 & 63 \\ \hline
125 & 2 & 1 & 62&1 & -62 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 379\) et \( 2526\) est \( 1\) alors \( (379, 1874)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 379^{-1}\equiv_{2526}-1253\) .
- Pour déchiffrer on fait \( -1253(x-1874) \) .
Message : CROUTEDEPATEVAUTBIENPAIN
\[
\begin{array}{c|*{6}{c}}&759&2016&1054&894&2024&1054
\\\hline x-b&-1115&142&-820&-980&150&-820
\\\hline a^{-1}(x-b)&1397095&-177926&1027460&1227940&-187950&1027460
\\\hline \%2526&217&1420&1904&304&1500&1904
\\\hline Décodage&CR&OU&TE&DE&PA&TE
\end{array}\]
\[
\begin{array}{c|*{6}{c}}&2084&1697&2390&1789&2024&1829
\\\hline x-b&210&-177&516&-85&150&-45
\\\hline a^{-1}(x-b)&-263130&221781&-646548&106505&-187950&56385
\\\hline \%2526&2100&2019&108&413&1500&813
\\\hline Décodage&VA&UT&BI&EN&PA&IN
\end{array}\]