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(383, 2526)\) . Justifier.
- Expliquer pourquoi \( (383, 1223)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 383\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (383, 1223)\) on a obtenu le message 2213-569-778-1335-1200-1459-1335-2147-1138-2213-1025. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(383, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
383 & 2526 & 383 & 0&-277 & 42 \\ \hline
2526 & 383 & 228 & 6&42 & -277 \\ \hline
383 & 228 & 155 & 1&-25 & 42 \\ \hline
228 & 155 & 73 & 1&17 & -25 \\ \hline
155 & 73 & 9 & 2&-8 & 17 \\ \hline
73 & 9 & 1 & 8&1 & -8 \\ \hline
9 & 1 & 0 & 9&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 383\) et \( 2526\) est \( 1\) alors \( (383, 1223)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 383^{-1}\equiv_{2526}-277\) .
- Pour déchiffrer on fait \( -277(x-1223) \) .
Message : LESMURSONTDESOREILLES
\[
\begin{array}{c|*{5}{c}}&2213&569&778&1335&1200
\\\hline x-b&990&-654&-445&112&-23
\\\hline a^{-1}(x-b)&-274230&181158&123265&-31024&6371
\\\hline \%2526&1104&1812&2017&1814&1319
\\\hline Décodage&LE&SM&UR&SO&NT
\end{array}\]
\[
\begin{array}{c|*{6}{c}}&1459&1335&2147&1138&2213&1025
\\\hline x-b&236&112&924&-85&990&-198
\\\hline a^{-1}(x-b)&-65372&-31024&-255948&23545&-274230&54846
\\\hline \%2526&304&1814&1704&811&1104&1800
\\\hline Décodage&DE&SO&RE&IL&LE&SA
\end{array}\]