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(53, 2526)\) . Justifier.
- Expliquer pourquoi \( (53, 1908)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 53\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (53, 1908)\) on a obtenu le message 1532-2399-1903-1328-2002-2368-302-2322-2009-480-1118-398-1063-2045-18-2332-1479-495-2320. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(53, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
53 & 2526 & 53 & 0&143 & -3 \\ \hline
2526 & 53 & 35 & 47&-3 & 143 \\ \hline
53 & 35 & 18 & 1&2 & -3 \\ \hline
35 & 18 & 17 & 1&-1 & 2 \\ \hline
18 & 17 & 1 & 1&1 & -1 \\ \hline
17 & 1 & 0 & 17&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 53\) et \( 2526\) est \( 1\) alors \( (53, 1908)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 53^{-1}\equiv_{2526}143\) .
- Pour déchiffrer on fait \( 143(x-1908) \) .
Message : SEULSLESIMBECILESNECHANGENTJAMAISDAVIS
\[
\begin{array}{c|*{9}{c}}&1532&2399&1903&1328&2002&2368&302&2322&2009
\\\hline x-b&-376&491&-5&-580&94&460&-1606&414&101
\\\hline a^{-1}(x-b)&-53768&70213&-715&-82940&13442&65780&-229658&59202&14443
\\\hline \%2526&1804&2011&1811&418&812&104&208&1104&1813
\\\hline Décodage&SE&UL&SL&ES&IM&BE&CI&LE&SN
\end{array}\]
\[
\begin{array}{c|*{10}{c}}&480&1118&398&1063&2045&18&2332&1479&495&2320
\\\hline x-b&-1428&-790&-1510&-845&137&-1890&424&-429&-1413&412
\\\hline a^{-1}(x-b)&-204204&-112970&-215930&-120835&19591&-270270&60632&-61347&-202059&58916
\\\hline \%2526&402&700&1306&413&1909&12&8&1803&21&818
\\\hline Décodage&EC&HA&NG&EN&TJ&AM&AI&SD&AV&IS
\end{array}\]