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(227, 2526)\) . Justifier.
- Expliquer pourquoi \( (227, 1797)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 227\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (227, 1797)\) on a obtenu le message 1496-1627-378-1837-2252-434-332-809-1627-332-695-809-236-509-1219. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(227, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
227 & 2526 & 227 & 0&-523 & 47 \\ \hline
2526 & 227 & 29 & 11&47 & -523 \\ \hline
227 & 29 & 24 & 7&-6 & 47 \\ \hline
29 & 24 & 5 & 1&5 & -6 \\ \hline
24 & 5 & 4 & 4&-1 & 5 \\ \hline
5 & 4 & 1 & 1&1 & -1 \\ \hline
4 & 1 & 0 & 4&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 227\) et \( 2526\) est \( 1\) alors \( (227, 1797)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 227^{-1}\equiv_{2526}-523\) .
- Pour déchiffrer on fait \( -523(x-1797) \) .
Message : ILFAUTSOUFFRIROUFAIRESOUFFRIR
\[
\begin{array}{c|*{7}{c}}&1496&1627&378&1837&2252&434&332
\\\hline x-b&-301&-170&-1419&40&455&-1363&-1465
\\\hline a^{-1}(x-b)&157423&88910&742137&-20920&-237965&712849&766195
\\\hline \%2526&811&500&2019&1814&2005&517&817
\\\hline Décodage&IL&FA&UT&SO&UF&FR&IR
\end{array}\]
\[
\begin{array}{c|*{8}{c}}&809&1627&332&695&809&236&509&1219
\\\hline x-b&-988&-170&-1465&-1102&-988&-1561&-1288&-578
\\\hline a^{-1}(x-b)&516724&88910&766195&576346&516724&816403&673624&302294
\\\hline \%2526&1420&500&817&418&1420&505&1708&1700
\\\hline Décodage&OU&FA&IR&ES&OU&FF&RI&RA
\end{array}\]