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(431, 2526)\) . Justifier.
- Expliquer pourquoi \( (431, 1864)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 431\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (431, 1864)\) on a obtenu le message 104-2245-1222-382-351-66-274-1392-1234-2362-1383-2044-2216-152-1380. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(431, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
431 & 2526 & 431 & 0&-463 & 79 \\ \hline
2526 & 431 & 371 & 5&79 & -463 \\ \hline
431 & 371 & 60 & 1&-68 & 79 \\ \hline
371 & 60 & 11 & 6&11 & -68 \\ \hline
60 & 11 & 5 & 5&-2 & 11 \\ \hline
11 & 5 & 1 & 2&1 & -2 \\ \hline
5 & 1 & 0 & 5&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 431\) et \( 2526\) est \( 1\) alors \( (431, 1864)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 431^{-1}\equiv_{2526}-463\) .
- Pour déchiffrer on fait \( -463(x-1864) \) .
Message : PIERREQUIROULENAMASSEPASMOUSSE
\[
\begin{array}{c|*{7}{c}}&104&2245&1222&382&351&66&274
\\\hline x-b&-1760&381&-642&-1482&-1513&-1798&-1590
\\\hline a^{-1}(x-b)&814880&-176403&297246&686166&700519&832474&736170
\\\hline \%2526&1508&417&1704&1620&817&1420&1104
\\\hline Décodage&PI&ER&RE&QU&IR&OU&LE
\end{array}\]
\[
\begin{array}{c|*{8}{c}}&1392&1234&2362&1383&2044&2216&152&1380
\\\hline x-b&-472&-630&498&-481&180&352&-1712&-484
\\\hline a^{-1}(x-b)&218536&291690&-230574&222703&-83340&-162976&792656&224092
\\\hline \%2526&1300&1200&1818&415&18&1214&2018&1804
\\\hline Décodage&NA&MA&SS&EP&AS&MO&US&SE
\end{array}\]