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(31, 2526)\) . Justifier.
- Expliquer pourquoi \( (31, 1960)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 31\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (31, 1960)\) on a obtenu le message 96-1461-2133-391-2102-1394-1384-1862-1761-1624-1999-233-2288-732-1058-406-26-1730. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(31, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
31 & 2526 & 31 & 0&163 & -2 \\ \hline
2526 & 31 & 15 & 81&-2 & 163 \\ \hline
31 & 15 & 1 & 2&1 & -2 \\ \hline
15 & 1 & 0 & 15&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 31\) et \( 2526\) est \( 1\) alors \( (31, 1960)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 31^{-1}\equiv_{2526}163\) .
- Pour déchiffrer on fait \( 163(x-1960) \) .
Message : SOUVENTFEMMEVARIEBIENFOLESTQUISYFIE
\[
\begin{array}{c|*{9}{c}}&96&1461&2133&391&2102&1394&1384&1862&1761
\\\hline x-b&-1864&-499&173&-1569&142&-566&-576&-98&-199
\\\hline a^{-1}(x-b)&-303832&-81337&28199&-255747&23146&-92258&-93888&-15974&-32437
\\\hline \%2526&1814&2021&413&1905&412&1204&2100&1708&401
\\\hline Décodage&SO&UV&EN&TF&EM&ME&VA&RI&EB
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&1624&1999&233&2288&732&1058&406&26&1730
\\\hline x-b&-336&39&-1727&328&-1228&-902&-1554&-1934&-230
\\\hline a^{-1}(x-b)&-54768&6357&-281501&53464&-200164&-147026&-253302&-315242&-37490
\\\hline \%2526&804&1305&1411&418&1916&2008&1824&508&400
\\\hline Décodage&IE&NF&OL&ES&TQ&UI&SY&FI&EA
\end{array}\]