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(311, 2526)\) . Justifier.
- Expliquer pourquoi \( (311, 711)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 311\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (311, 711)\) on a obtenu le message 1005-596-1801-1729-2232-1261-1277-983-1891-1857-2270-1937-1175-2248-779-851. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(311, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
311 & 2526 & 311 & 0&731 & -90 \\ \hline
2526 & 311 & 38 & 8&-90 & 731 \\ \hline
311 & 38 & 7 & 8&11 & -90 \\ \hline
38 & 7 & 3 & 5&-2 & 11 \\ \hline
7 & 3 & 1 & 2&1 & -2 \\ \hline
3 & 1 & 0 & 3&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 311\) et \( 2526\) est \( 1\) alors \( (311, 711)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 311^{-1}\equiv_{2526}731\) .
- Pour déchiffrer on fait \( 731(x-711) \) .
Message : CESTLAPOELEQUISEMOQUEDUCHAUDRON
\[
\begin{array}{c|*{8}{c}}&1005&596&1801&1729&2232&1261&1277&983
\\\hline x-b&294&-115&1090&1018&1521&550&566&272
\\\hline a^{-1}(x-b)&214914&-84065&796790&744158&1111851&402050&413746&198832
\\\hline \%2526&204&1819&1100&1514&411&416&2008&1804
\\\hline Décodage&CE&ST&LA&PO&EL&EQ&UI&SE
\end{array}\]
\[
\begin{array}{c|*{8}{c}}&1891&1857&2270&1937&1175&2248&779&851
\\\hline x-b&1180&1146&1559&1226&464&1537&68&140
\\\hline a^{-1}(x-b)&862580&837726&1139629&896206&339184&1123547&49708&102340
\\\hline \%2526&1214&1620&403&2002&700&2003&1714&1300
\\\hline Décodage&MO&QU&ED&UC&HA&UD&RO&NA
\end{array}\]