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(235, 2526)\) . Justifier.
- Expliquer pourquoi \( (235, 1957)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 235\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (235, 1957)\) on a obtenu le message 580-1811-768-2349-1757-817-1294-1673-1809-65-681-589-1301-1668-2004-1036-1311-444-2495. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(235, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
235 & 2526 & 235 & 0&43 & -4 \\ \hline
2526 & 235 & 176 & 10&-4 & 43 \\ \hline
235 & 176 & 59 & 1&3 & -4 \\ \hline
176 & 59 & 58 & 2&-1 & 3 \\ \hline
59 & 58 & 1 & 1&1 & -1 \\ \hline
58 & 1 & 0 & 58&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 235\) et \( 2526\) est \( 1\) alors \( (235, 1957)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 235^{-1}\equiv_{2526}43\) .
- Pour déchiffrer on fait \( 43(x-1957) \) .
Message : ONNATTRAPEPASDESMOUCHESAVECDUVINAIGRE
\[
\begin{array}{c|*{9}{c}}&580&1811&768&2349&1757&817&1294&1673&1809
\\\hline x-b&-1377&-146&-1189&392&-200&-1140&-663&-284&-148
\\\hline a^{-1}(x-b)&-59211&-6278&-51127&16856&-8600&-49020&-28509&-12212&-6364
\\\hline \%2526&1413&1300&1919&1700&1504&1500&1803&418&1214
\\\hline Décodage&ON&NA&TT&RA&PE&PA&SD&ES&MO
\end{array}\]
\[
\begin{array}{c|*{10}{c}}&65&681&589&1301&1668&2004&1036&1311&444&2495
\\\hline x-b&-1892&-1276&-1368&-656&-289&47&-921&-646&-1513&538
\\\hline a^{-1}(x-b)&-81356&-54868&-58824&-28208&-12427&2021&-39603&-27778&-65059&23134
\\\hline \%2526&2002&704&1800&2104&203&2021&813&8&617&400
\\\hline Décodage&UC&HE&SA&VE&CD&UV&IN&AI&GR&EA
\end{array}\]