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(239, 2526)\) . Justifier.
- Expliquer pourquoi \( (239, 2371)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 239\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (239, 2371)\) on a obtenu le message 547-845-2176-114-1713-1084-625-1623-1279-606-41-1831-1968-1233-426-2401-2325-994. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(239, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
239 & 2526 & 239 & 0&-613 & 58 \\ \hline
2526 & 239 & 136 & 10&58 & -613 \\ \hline
239 & 136 & 103 & 1&-33 & 58 \\ \hline
136 & 103 & 33 & 1&25 & -33 \\ \hline
103 & 33 & 4 & 3&-8 & 25 \\ \hline
33 & 4 & 1 & 8&1 & -8 \\ \hline
4 & 1 & 0 & 4&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 239\) et \( 2526\) est \( 1\) alors \( (239, 2371)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 239^{-1}\equiv_{2526}-613\) .
- Pour déchiffrer on fait \( -613(x-2371) \) .
Message : QUISINSTRUITSANSAGIRLABOURESANSSEMER
\[
\begin{array}{c|*{9}{c}}&547&845&2176&114&1713&1084&625&1623&1279
\\\hline x-b&-1824&-1526&-195&-2257&-658&-1287&-1746&-748&-1092
\\\hline a^{-1}(x-b)&1118112&935438&119535&1383541&403354&788931&1070298&458524&669396
\\\hline \%2526&1620&818&813&1819&1720&819&1800&1318&6
\\\hline Décodage&QU&IS&IN&ST&RU&IT&SA&NS&AG
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&606&41&1831&1968&1233&426&2401&2325&994
\\\hline x-b&-1765&-2330&-540&-403&-1138&-1945&30&-46&-1377
\\\hline a^{-1}(x-b)&1081945&1428290&331020&247039&697594&1192285&-18390&28198&844101
\\\hline \%2526&817&1100&114&2017&418&13&1818&412&417
\\\hline Décodage&IR&LA&BO&UR&ES&AN&SS&EM&ER
\end{array}\]