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(415, 2526)\) . Justifier.
- Expliquer pourquoi \( (415, 2351)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 415\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (415, 2351)\) on a obtenu le message 63-1007-1386-639-1547-188-2211-649-1978-28-2315-571-6. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(415, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
415 & 2526 & 415 & 0&-1193 & 196 \\ \hline
2526 & 415 & 36 & 6&196 & -1193 \\ \hline
415 & 36 & 19 & 11&-17 & 196 \\ \hline
36 & 19 & 17 & 1&9 & -17 \\ \hline
19 & 17 & 2 & 1&-8 & 9 \\ \hline
17 & 2 & 1 & 8&1 & -8 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 415\) et \( 2526\) est \( 1\) alors \( (415, 2351)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 415^{-1}\equiv_{2526}-1193\) .
- Pour déchiffrer on fait \( -1193(x-2351) \) .
Message : PETITPOISSONDEVIENDRAGRAND
\[
\begin{array}{c|*{6}{c}}&63&1007&1386&639&1547&188
\\\hline x-b&-2288&-1344&-965&-1712&-804&-2163
\\\hline a^{-1}(x-b)&2729584&1603392&1151245&2042416&959172&2580459
\\\hline \%2526&1504&1908&1915&1408&1818&1413
\\\hline Décodage&PE&TI&TP&OI&SS&ON
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&2211&649&1978&28&2315&571&6
\\\hline x-b&-140&-1702&-373&-2323&-36&-1780&-2345
\\\hline a^{-1}(x-b)&167020&2030486&444989&2771339&42948&2123540&2797585
\\\hline \%2526&304&2108&413&317&6&1700&1303
\\\hline Décodage&DE&VI&EN&DR&AG&RA&ND
\end{array}\]