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(197, 2526)\) . Justifier.
- Expliquer pourquoi \( (197, 2138)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 197\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (197, 2138)\) on a obtenu le message 476-2211-1520-1281-344-2100-113-2501-1388-227-6-10-1360-1402-1602-1080-2404. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(197, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
197 & 2526 & 197 & 0&-577 & 45 \\ \hline
2526 & 197 & 162 & 12&45 & -577 \\ \hline
197 & 162 & 35 & 1&-37 & 45 \\ \hline
162 & 35 & 22 & 4&8 & -37 \\ \hline
35 & 22 & 13 & 1&-5 & 8 \\ \hline
22 & 13 & 9 & 1&3 & -5 \\ \hline
13 & 9 & 4 & 1&-2 & 3 \\ \hline
9 & 4 & 1 & 2&1 & -2 \\ \hline
4 & 1 & 0 & 4&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 197\) et \( 2526\) est \( 1\) alors \( (197, 2138)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 197^{-1}\equiv_{2526}-577\) .
- Pour déchiffrer on fait \( -577(x-2138) \) .
Message : QUIVEUTTUERSONCHIENLACCUSEDELARAGE
\[
\begin{array}{c|*{8}{c}}&476&2211&1520&1281&344&2100&113&2501
\\\hline x-b&-1662&73&-618&-857&-1794&-38&-2025&363
\\\hline a^{-1}(x-b)&958974&-42121&356586&494489&1035138&21926&1168425&-209451
\\\hline \%2526&1620&821&420&1919&2004&1718&1413&207
\\\hline Décodage&QU&IV&EU&TT&UE&RS&ON&CH
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&1388&227&6&10&1360&1402&1602&1080&2404
\\\hline x-b&-750&-1911&-2132&-2128&-778&-736&-536&-1058&266
\\\hline a^{-1}(x-b)&432750&1102647&1230164&1227856&448906&424672&309272&610466&-153482
\\\hline \%2526&804&1311&2&220&1804&304&1100&1700&604
\\\hline Décodage&IE&NL&AC&CU&SE&DE&LA&RA&GE
\end{array}\]