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(259, 2526)\) . Justifier.
- Expliquer pourquoi \( (259, 987)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 259\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (259, 987)\) on a obtenu le message 1251-924-337-1519-1348-1763-2013-1603-1310-890-273-1896-517. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(259, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
259 & 2526 & 259 & 0&829 & -85 \\ \hline
2526 & 259 & 195 & 9&-85 & 829 \\ \hline
259 & 195 & 64 & 1&64 & -85 \\ \hline
195 & 64 & 3 & 3&-21 & 64 \\ \hline
64 & 3 & 1 & 21&1 & -21 \\ \hline
3 & 1 & 0 & 3&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 259\) et \( 2526\) est \( 1\) alors \( (259, 987)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 259^{-1}\equiv_{2526}829\) .
- Pour déchiffrer on fait \( 829(x-987) \) .
Message : QUITROPEMBRASSEMALETREINT
\[
\begin{array}{c|*{6}{c}}&1251&924&337&1519&1348&1763
\\\hline x-b&264&-63&-650&532&361&776
\\\hline a^{-1}(x-b)&218856&-52227&-538850&441028&299269&643304
\\\hline \%2526&1620&819&1714&1504&1201&1700
\\\hline Décodage&QU&IT&RO&PE&MB&RA
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&2013&1603&1310&890&273&1896&517
\\\hline x-b&1026&616&323&-97&-714&909&-470
\\\hline a^{-1}(x-b)&850554&510664&267767&-80413&-591906&753561&-389630
\\\hline \%2526&1818&412&11&419&1704&813&1900
\\\hline Décodage&SS&EM&AL&ET&RE&IN&TA
\end{array}\]