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(211, 2526)\) . Justifier.
- Expliquer pourquoi \( (211, 150)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 211\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (211, 150)\) on a obtenu le message 225-1642-900-1894-702-2044-702-1472-430-1770-388-1409-1894-961-702. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(211, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
211 & 2526 & 211 & 0&-419 & 35 \\ \hline
2526 & 211 & 205 & 11&35 & -419 \\ \hline
211 & 205 & 6 & 1&-34 & 35 \\ \hline
205 & 6 & 1 & 34&1 & -34 \\ \hline
6 & 1 & 0 & 6&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 211\) et \( 2526\) est \( 1\) alors \( (211, 150)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 211^{-1}\equiv_{2526}-419\) .
- Pour déchiffrer on fait \( -419(x-150) \) .
Message : ONNAPASELEVELESCOCHONSENSEMBLE
\[
\begin{array}{c|*{7}{c}}&225&1642&900&1894&702&2044&702
\\\hline x-b&75&1492&750&1744&552&1894&552
\\\hline a^{-1}(x-b)&-31425&-625148&-314250&-730736&-231288&-793586&-231288
\\\hline \%2526&1413&1300&1500&1804&1104&2104&1104
\\\hline Décodage&ON&NA&PA&SE&LE&VE&LE
\end{array}\]
\[
\begin{array}{c|*{8}{c}}&1472&430&1770&388&1409&1894&961&702
\\\hline x-b&1322&280&1620&238&1259&1744&811&552
\\\hline a^{-1}(x-b)&-553918&-117320&-678780&-99722&-527521&-730736&-339809&-231288
\\\hline \%2526&1802&1402&714&1318&413&1804&1201&1104
\\\hline Décodage&SC&OC&HO&NS&EN&SE&MB&LE
\end{array}\]