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, 767)\) 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, 767)\) on a obtenu le message 2413-1120-1030-1876-629-2184-35-184-1294-379-80-1030-1876-629-2184-975-2103. 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, 767)\) 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-767) \) .
Message : DESHABILLERPIERREPOURHABILLERPAUL
\[
\begin{array}{c|*{8}{c}}&2413&1120&1030&1876&629&2184&35&184
\\\hline x-b&1646&353&263&1109&-138&1417&-732&-583
\\\hline a^{-1}(x-b)&679798&145789&108619&458017&-56994&585221&-302316&-240779
\\\hline \%2526&304&1807&1&811&1104&1715&804&1717
\\\hline Décodage&DE&SH&AB&IL&LE&RP&IE&RR
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&1294&379&80&1030&1876&629&2184&975&2103
\\\hline x-b&527&-388&-687&263&1109&-138&1417&208&1336
\\\hline a^{-1}(x-b)&217651&-160244&-283731&108619&458017&-56994&585221&85904&551768
\\\hline \%2526&415&1420&1707&1&811&1104&1715&20&1100
\\\hline Décodage&EP&OU&RH&AB&IL&LE&RP&AU&LA
\end{array}\]