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(145, 2526)\) . Justifier.
- Expliquer pourquoi \( (145, 1879)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 145\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (145, 1879)\) on a obtenu le message 2082-2013-2010-1984-1140-1720-23-1509-2143-175. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(145, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
145 & 2526 & 145 & 0&331 & -19 \\ \hline
2526 & 145 & 61 & 17&-19 & 331 \\ \hline
145 & 61 & 23 & 2&8 & -19 \\ \hline
61 & 23 & 15 & 2&-3 & 8 \\ \hline
23 & 15 & 8 & 1&2 & -3 \\ \hline
15 & 8 & 7 & 1&-1 & 2 \\ \hline
8 & 7 & 1 & 1&1 & -1 \\ \hline
7 & 1 & 0 & 7&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 145\) et \( 2526\) est \( 1\) alors \( (145, 1879)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 145^{-1}\equiv_{2526}331\) .
- Pour déchiffrer on fait \( 331(x-1879) \) .
Message : PROMETTRENERUINEPAS
\[
\begin{array}{c|*{5}{c}}&2082&2013&2010&1984&1140
\\\hline x-b&203&134&131&105&-739
\\\hline a^{-1}(x-b)&67193&44354&43361&34755&-244609
\\\hline \%2526&1517&1412&419&1917&413
\\\hline Décodage&PR&OM&ET&TR&EN
\end{array}\]
\[
\begin{array}{c|*{5}{c}}&1720&23&1509&2143&175
\\\hline x-b&-159&-1856&-370&264&-1704
\\\hline a^{-1}(x-b)&-52629&-614336&-122470&87384&-564024
\\\hline \%2526&417&2008&1304&1500&1800
\\\hline Décodage&ER&UI&NE&PA&SA
\end{array}\]