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(487, 2526)\) . Justifier.
- Expliquer pourquoi \( (487, 572)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 487\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (487, 572)\) on a obtenu le message 778-974-906-1314-1479-2149-865-2331-103-1960-1851-341-597-182-237-1571-572. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(487, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
487 & 2526 & 487 & 0&1027 & -198 \\ \hline
2526 & 487 & 91 & 5&-198 & 1027 \\ \hline
487 & 91 & 32 & 5&37 & -198 \\ \hline
91 & 32 & 27 & 2&-13 & 37 \\ \hline
32 & 27 & 5 & 1&11 & -13 \\ \hline
27 & 5 & 2 & 5&-2 & 11 \\ \hline
5 & 2 & 1 & 2&1 & -2 \\ \hline
2 & 1 & 0 & 2&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 487\) et \( 2526\) est \( 1\) alors \( (487, 572)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 487^{-1}\equiv_{2526}1027\) .
- Pour déchiffrer on fait \( 1027(x-572) \) .
Message : TELQUIRITVENDREDIDIMANCHEPLEURERA
\[
\begin{array}{c|*{8}{c}}&778&974&906&1314&1479&2149&865&2331
\\\hline x-b&206&402&334&742&907&1577&293&1759
\\\hline a^{-1}(x-b)&211562&412854&343018&762034&931489&1619579&300911&1806493
\\\hline \%2526&1904&1116&2008&1708&1921&413&317&403
\\\hline Décodage&TE&LQ&UI&RI&TV&EN&DR&ED
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&103&1960&1851&341&597&182&237&1571&572
\\\hline x-b&-469&1388&1279&-231&25&-390&-335&999&0
\\\hline a^{-1}(x-b)&-481663&1425476&1313533&-237237&25675&-400530&-344045&1025973&0
\\\hline \%2526&803&812&13&207&415&1104&2017&417&0
\\\hline Décodage&ID&IM&AN&CH&EP&LE&UR&ER&AA
\end{array}\]