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(253, 2526)\) . Justifier.
- Expliquer pourquoi \( (253, 1459)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 253\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (253, 1459)\) on a obtenu le message 496-1939-1144-1627-376-1880-265-1734-1819-1939-1281-665-2516. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(253, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
253 & 2526 & 253 & 0&-629 & 63 \\ \hline
2526 & 253 & 249 & 9&63 & -629 \\ \hline
253 & 249 & 4 & 1&-62 & 63 \\ \hline
249 & 4 & 1 & 62&1 & -62 \\ \hline
4 & 1 & 0 & 4&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 253\) et \( 2526\) est \( 1\) alors \( (253, 1459)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 253^{-1}\equiv_{2526}-629\) .
- Pour déchiffrer on fait \( -629(x-1459) \) .
Message : UNMALHEURNEVIENTJAMAISSEUL
\[
\begin{array}{c|*{6}{c}}&496&1939&1144&1627&376&1880
\\\hline x-b&-963&480&-315&168&-1083&421
\\\hline a^{-1}(x-b)&605727&-301920&198135&-105672&681207&-264809
\\\hline \%2526&2013&1200&1107&420&1713&421
\\\hline Décodage&UN&MA&LH&EU&RN&EV
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&265&1734&1819&1939&1281&665&2516
\\\hline x-b&-1194&275&360&480&-178&-794&1057
\\\hline a^{-1}(x-b)&751026&-172975&-226440&-301920&111962&499426&-664853
\\\hline \%2526&804&1319&900&1200&818&1804&2011
\\\hline Décodage&IE&NT&JA&MA&IS&SE&UL
\end{array}\]