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(263, 2526)\) . Justifier.
- Expliquer pourquoi \( (263, 1104)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 263\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (263, 1104)\) on a obtenu le message 1412-2485-842-682-1835-420-224-2314-2440-213. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(263, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
263 & 2526 & 263 & 0&413 & -43 \\ \hline
2526 & 263 & 159 & 9&-43 & 413 \\ \hline
263 & 159 & 104 & 1&26 & -43 \\ \hline
159 & 104 & 55 & 1&-17 & 26 \\ \hline
104 & 55 & 49 & 1&9 & -17 \\ \hline
55 & 49 & 6 & 1&-8 & 9 \\ \hline
49 & 6 & 1 & 8&1 & -8 \\ \hline
6 & 1 & 0 & 6&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 263\) et \( 2526\) est \( 1\) alors \( (263, 1104)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 263^{-1}\equiv_{2526}413\) .
- Pour déchiffrer on fait \( 413(x-1104) \) .
Message : JEUDEMAINJEUDEVILAIN
\[
\begin{array}{c|*{5}{c}}&1412&2485&842&682&1835
\\\hline x-b&308&1381&-262&-422&731
\\\hline a^{-1}(x-b)&127204&570353&-108206&-174286&301903
\\\hline \%2526&904&2003&412&8&1309
\\\hline Décodage&JE&UD&EM&AI&NJ
\end{array}\]
\[
\begin{array}{c|*{5}{c}}&420&224&2314&2440&213
\\\hline x-b&-684&-880&1210&1336&-891
\\\hline a^{-1}(x-b)&-282492&-363440&499730&551768&-367983
\\\hline \%2526&420&304&2108&1100&813
\\\hline Décodage&EU&DE&VI&LA&IN
\end{array}\]