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(229, 2526)\) . Justifier.
- Expliquer pourquoi \( (229, 1264)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 229\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (229, 1264)\) on a obtenu le message 2512-1025-2167-1971-1891-1257-922-1662-2150-2200-448-152-2396-2041-1433-1646-866-1928. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(229, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
229 & 2526 & 229 & 0&1081 & -98 \\ \hline
2526 & 229 & 7 & 11&-98 & 1081 \\ \hline
229 & 7 & 5 & 32&3 & -98 \\ \hline
7 & 5 & 2 & 1&-2 & 3 \\ \hline
5 & 2 & 1 & 2&1 & -2 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 229\) et \( 2526\) est \( 1\) alors \( (229, 1264)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 229^{-1}\equiv_{2526}1081\) .
- Pour déchiffrer on fait \( 1081(x-1264) \) .
Message : CESTLHOPITALQUISEMOQUEDELINFIRMERIE
\[
\begin{array}{c|*{9}{c}}&2512&1025&2167&1971&1891&1257&922&1662&2150
\\\hline x-b&1248&-239&903&707&627&-7&-342&398&886
\\\hline a^{-1}(x-b)&1349088&-258359&976143&764267&677787&-7567&-369702&430238&957766
\\\hline \%2526&204&1819&1107&1415&819&11&1620&818&412
\\\hline Décodage&CE&ST&LH&OP&IT&AL&QU&IS&EM
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&2200&448&152&2396&2041&1433&1646&866&1928
\\\hline x-b&936&-816&-1112&1132&777&169&382&-398&664
\\\hline a^{-1}(x-b)&1011816&-882096&-1202072&1223692&839937&182689&412942&-430238&717784
\\\hline \%2526&1416&2004&304&1108&1305&817&1204&1708&400
\\\hline Décodage&OQ&UE&DE&LI&NF&IR&ME&RI&EA
\end{array}\]