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(247, 2526)\) . Justifier.
- Expliquer pourquoi \( (247, 399)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 247\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (247, 399)\) on a obtenu le message 279-695-646-279-697-756-2072-2375-1289-1829-267-1705-2397-1279-279-952-2375-338. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(247, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
247 & 2526 & 247 & 0&-767 & 75 \\ \hline
2526 & 247 & 56 & 10&75 & -767 \\ \hline
247 & 56 & 23 & 4&-17 & 75 \\ \hline
56 & 23 & 10 & 2&7 & -17 \\ \hline
23 & 10 & 3 & 2&-3 & 7 \\ \hline
10 & 3 & 1 & 3&1 & -3 \\ \hline
3 & 1 & 0 & 3&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 247\) et \( 2526\) est \( 1\) alors \( (247, 399)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 247^{-1}\equiv_{2526}-767\) .
- Pour déchiffrer on fait \( -767(x-399) \) .
Message : LEDIABLENAPPARAITQUACELUIQUILECRAINT
\[
\begin{array}{c|*{9}{c}}&279&695&646&279&697&756&2072&2375&1289
\\\hline x-b&-120&296&247&-120&298&357&1673&1976&890
\\\hline a^{-1}(x-b)&92040&-227032&-189449&92040&-228566&-273819&-1283191&-1515592&-682630
\\\hline \%2526&1104&308&1&1104&1300&1515&17&8&1916
\\\hline Décodage&LE&DI&AB&LE&NA&PP&AR&AI&TQ
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&1829&267&1705&2397&1279&279&952&2375&338
\\\hline x-b&1430&-132&1306&1998&880&-120&553&1976&-61
\\\hline a^{-1}(x-b)&-1096810&101244&-1001702&-1532466&-674960&92040&-424151&-1515592&46787
\\\hline \%2526&2000&204&1120&816&2008&1104&217&8&1319
\\\hline Décodage&UA&CE&LU&IQ&UI&LE&CR&AI&NT
\end{array}\]