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(79, 2526)\) . Justifier.
- Expliquer pourquoi \( (79, 1242)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 79\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (79, 1242)\) on a obtenu le message 48-1986-721-1874-1980-882-1725-651-1426-1637-326-109-1426. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(79, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
79 & 2526 & 79 & 0&-1247 & 39 \\ \hline
2526 & 79 & 77 & 31&39 & -1247 \\ \hline
79 & 77 & 2 & 1&-38 & 39 \\ \hline
77 & 2 & 1 & 38&1 & -38 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 79\) et \( 2526\) est \( 1\) alors \( (79, 1242)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 79^{-1}\equiv_{2526}-1247\) .
- Pour déchiffrer on fait \( -1247(x-1242) \) .
Message : LESAFFAIRESSONTLESAFFAIRES
\[
\begin{array}{c|*{6}{c}}&48&1986&721&1874&1980&882
\\\hline x-b&-1194&744&-521&632&738&-360
\\\hline a^{-1}(x-b)&1488918&-927768&649687&-788104&-920286&448920
\\\hline \%2526&1104&1800&505&8&1704&1818
\\\hline Décodage&LE&SA&FF&AI&RE&SS
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&1725&651&1426&1637&326&109&1426
\\\hline x-b&483&-591&184&395&-916&-1133&184
\\\hline a^{-1}(x-b)&-602301&736977&-229448&-492565&1142252&1412851&-229448
\\\hline \%2526&1413&1911&418&5&500&817&418
\\\hline Décodage&ON&TL&ES&AF&FA&IR&ES
\end{array}\]