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(235, 2526)\) . Justifier.
- Expliquer pourquoi \( (235, 2412)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 235\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (235, 2412)\) on a obtenu le message 734-1756-1620-278-2271-1355-1164-953-1810-2358-403-1686-140-483-307-953-1223-2445. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(235, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
235 & 2526 & 235 & 0&43 & -4 \\ \hline
2526 & 235 & 176 & 10&-4 & 43 \\ \hline
235 & 176 & 59 & 1&3 & -4 \\ \hline
176 & 59 & 58 & 2&-1 & 3 \\ \hline
59 & 58 & 1 & 1&1 & -1 \\ \hline
58 & 1 & 0 & 58&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 235\) et \( 2526\) est \( 1\) alors \( (235, 2412)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 235^{-1}\equiv_{2526}43\) .
- Pour déchiffrer on fait \( 43(x-2412) \) .
Message : LAVENIRAPPARTIENTACEUXQUISELEVENTTOT
\[
\begin{array}{c|*{9}{c}}&734&1756&1620&278&2271&1355&1164&953&1810
\\\hline x-b&-1678&-656&-792&-2134&-141&-1057&-1248&-1459&-602
\\\hline a^{-1}(x-b)&-72154&-28208&-34056&-91762&-6063&-45451&-53664&-62737&-25886
\\\hline \%2526&1100&2104&1308&1700&1515&17&1908&413&1900
\\\hline Décodage&LA&VE&NI&RA&PP&AR&TI&EN&TA
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&2358&403&1686&140&483&307&953&1223&2445
\\\hline x-b&-54&-2009&-726&-2272&-1929&-2105&-1459&-1189&33
\\\hline a^{-1}(x-b)&-2322&-86387&-31218&-97696&-82947&-90515&-62737&-51127&1419
\\\hline \%2526&204&2023&1620&818&411&421&413&1919&1419
\\\hline Décodage&CE&UX&QU&IS&EL&EV&EN&TT&OT
\end{array}\]