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(433, 2526)\) . Justifier.
- Expliquer pourquoi \( (433, 1305)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 433\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (433, 1305)\) on a obtenu le message 537-1882-2090-1726-2220-427-1178-1426-1149-2356-2387-240-644-2203-1545. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(433, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
433 & 2526 & 433 & 0&-35 & 6 \\ \hline
2526 & 433 & 361 & 5&6 & -35 \\ \hline
433 & 361 & 72 & 1&-5 & 6 \\ \hline
361 & 72 & 1 & 5&1 & -5 \\ \hline
72 & 1 & 0 & 72&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 433\) et \( 2526\) est \( 1\) alors \( (433, 1305)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 433^{-1}\equiv_{2526}-35\) .
- Pour déchiffrer on fait \( -35(x-1305) \) .
Message : QUANDLEVINESTTIREILFAUTLEBOIRE
\[
\begin{array}{c|*{7}{c}}&537&1882&2090&1726&2220&427&1178
\\\hline x-b&-768&577&785&421&915&-878&-127
\\\hline a^{-1}(x-b)&26880&-20195&-27475&-14735&-32025&30730&4445
\\\hline \%2526&1620&13&311&421&813&418&1919
\\\hline Décodage&QU&AN&DL&EV&IN&ES&TT
\end{array}\]
\[
\begin{array}{c|*{8}{c}}&1426&1149&2356&2387&240&644&2203&1545
\\\hline x-b&121&-156&1051&1082&-1065&-661&898&240
\\\hline a^{-1}(x-b)&-4235&5460&-36785&-37870&37275&23135&-31430&-8400
\\\hline \%2526&817&408&1105&20&1911&401&1408&1704
\\\hline Décodage&IR&EI&LF&AU&TL&EB&OI&RE
\end{array}\]