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(221, 2526)\) . Justifier.
- Expliquer pourquoi \( (221, 487)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 221\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (221, 487)\) on a obtenu le message 1975-928-1708-1929-1860-76-1140-698-2062-707-947-1496-824-313-2062-1705. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(221, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
221 & 2526 & 221 & 0&1223 & -107 \\ \hline
2526 & 221 & 95 & 11&-107 & 1223 \\ \hline
221 & 95 & 31 & 2&46 & -107 \\ \hline
95 & 31 & 2 & 3&-15 & 46 \\ \hline
31 & 2 & 1 & 15&1 & -15 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 221\) et \( 2526\) est \( 1\) alors \( (221, 487)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 221^{-1}\equiv_{2526}1223\) .
- Pour déchiffrer on fait \( 1223(x-487) \) .
Message : LENFERESTPAVEDEBONNESINTENTIONS
\[
\begin{array}{c|*{8}{c}}&1975&928&1708&1929&1860&76&1140&698
\\\hline x-b&1488&441&1221&1442&1373&-411&653&211
\\\hline a^{-1}(x-b)&1819824&539343&1493283&1763566&1679179&-502653&798619&258053
\\\hline \%2526&1104&1305&417&418&1915&21&403&401
\\\hline Décodage&LE&NF&ER&ES&TP&AV&ED&EB
\end{array}\]
\[
\begin{array}{c|*{8}{c}}&2062&707&947&1496&824&313&2062&1705
\\\hline x-b&1575&220&460&1009&337&-174&1575&1218
\\\hline a^{-1}(x-b)&1926225&269060&562580&1234007&412151&-212802&1926225&1489614
\\\hline \%2526&1413&1304&1808&1319&413&1908&1413&1800
\\\hline Décodage&ON&NE&SI&NT&EN&TI&ON&SA
\end{array}\]