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(187, 2526)\) . Justifier.
- Expliquer pourquoi \( (187, 1310)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 187\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (187, 1310)\) on a obtenu le message 626-2326-2354-235-1857-1265-311-723-2150-60-2326-858-1284. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(187, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
187 & 2526 & 187 & 0&-851 & 63 \\ \hline
2526 & 187 & 95 & 13&63 & -851 \\ \hline
187 & 95 & 92 & 1&-32 & 63 \\ \hline
95 & 92 & 3 & 1&31 & -32 \\ \hline
92 & 3 & 2 & 30&-1 & 31 \\ \hline
3 & 2 & 1 & 1&1 & -1 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 187\) et \( 2526\) est \( 1\) alors \( (187, 1310)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 187^{-1}\equiv_{2526}-851\) .
- Pour déchiffrer on fait \( -851(x-1310) \) .
Message : LESCHIENSNEFONTPASDESCHATS
\[
\begin{array}{c|*{6}{c}}&626&2326&2354&235&1857&1265
\\\hline x-b&-684&1016&1044&-1075&547&-45
\\\hline a^{-1}(x-b)&582084&-864616&-888444&914825&-465497&38295
\\\hline \%2526&1104&1802&708&413&1813&405
\\\hline Décodage&LE&SC&HI&EN&SN&EF
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&311&723&2150&60&2326&858&1284
\\\hline x-b&-999&-587&840&-1250&1016&-452&-26
\\\hline a^{-1}(x-b)&850149&499537&-714840&1063750&-864616&384652&22126
\\\hline \%2526&1413&1915&18&304&1802&700&1918
\\\hline Décodage&ON&TP&AS&DE&SC&HA&TS
\end{array}\]