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(59, 2526)\) . Justifier.
- Expliquer pourquoi \( (59, 13)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 59\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (59, 13)\) on a obtenu le message 2131-458-662-1646-1205-321-2054-139-1301-2035-321-2054-2000-139-63-2512. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(59, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
59 & 2526 & 59 & 0&-685 & 16 \\ \hline
2526 & 59 & 48 & 42&16 & -685 \\ \hline
59 & 48 & 11 & 1&-13 & 16 \\ \hline
48 & 11 & 4 & 4&3 & -13 \\ \hline
11 & 4 & 3 & 2&-1 & 3 \\ \hline
4 & 3 & 1 & 1&1 & -1 \\ \hline
3 & 1 & 0 & 3&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 59\) et \( 2526\) est \( 1\) alors \( (59, 13)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 59^{-1}\equiv_{2526}-685\) .
- Pour déchiffrer on fait \( -685(x-13) \) .
Message : QUIVALENTEMENTVASUREMENTETVALOIN
\[
\begin{array}{c|*{8}{c}}&2131&458&662&1646&1205&321&2054&139
\\\hline x-b&2118&445&649&1633&1192&308&2041&126
\\\hline a^{-1}(x-b)&-1450830&-304825&-444565&-1118605&-816520&-210980&-1398085&-86310
\\\hline \%2526&1620&821&11&413&1904&1204&1319&2100
\\\hline Décodage&QU&IV&AL&EN&TE&ME&NT&VA
\end{array}\]
\[
\begin{array}{c|*{8}{c}}&1301&2035&321&2054&2000&139&63&2512
\\\hline x-b&1288&2022&308&2041&1987&126&50&2499
\\\hline a^{-1}(x-b)&-882280&-1385070&-210980&-1398085&-1361095&-86310&-34250&-1711815
\\\hline \%2526&1820&1704&1204&1319&419&2100&1114&813
\\\hline Décodage&SU&RE&ME&NT&ET&VA&LO&IN
\end{array}\]