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(199, 2526)\) . Justifier.
- Expliquer pourquoi \( (199, 523)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 199\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (199, 523)\) on a obtenu le message 2101-1840-599-1751-2078-339-1087-1679-186-546-1135-646-2249. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(199, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
199 & 2526 & 199 & 0&787 & -62 \\ \hline
2526 & 199 & 138 & 12&-62 & 787 \\ \hline
199 & 138 & 61 & 1&43 & -62 \\ \hline
138 & 61 & 16 & 2&-19 & 43 \\ \hline
61 & 16 & 13 & 3&5 & -19 \\ \hline
16 & 13 & 3 & 1&-4 & 5 \\ \hline
13 & 3 & 1 & 4&1 & -4 \\ \hline
3 & 1 & 0 & 3&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 199\) et \( 2526\) est \( 1\) alors \( (199, 523)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 199^{-1}\equiv_{2526}787\) .
- Pour déchiffrer on fait \( 787(x-523) \) .
Message : QUITROPEMBRASSEMALETREINT
\[
\begin{array}{c|*{6}{c}}&2101&1840&599&1751&2078&339
\\\hline x-b&1578&1317&76&1228&1555&-184
\\\hline a^{-1}(x-b)&1241886&1036479&59812&966436&1223785&-144808
\\\hline \%2526&1620&819&1714&1504&1201&1700
\\\hline Décodage&QU&IT&RO&PE&MB&RA
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&1087&1679&186&546&1135&646&2249
\\\hline x-b&564&1156&-337&23&612&123&1726
\\\hline a^{-1}(x-b)&443868&909772&-265219&18101&481644&96801&1358362
\\\hline \%2526&1818&412&11&419&1704&813&1900
\\\hline Décodage&SS&EM&AL&ET&RE&IN&TA
\end{array}\]