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(17, 2526)\) . Justifier.
- Expliquer pourquoi \( (17, 489)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 17\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (17, 489)\) on a obtenu le message 1431-1100-2458-1649-1705-2237-178-243-1776-605-961-2458-36-1844-653-1841-2381. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(17, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
17 & 2526 & 17 & 0&743 & -5 \\ \hline
2526 & 17 & 10 & 148&-5 & 743 \\ \hline
17 & 10 & 7 & 1&3 & -5 \\ \hline
10 & 7 & 3 & 1&-2 & 3 \\ \hline
7 & 3 & 1 & 2&1 & -2 \\ \hline
3 & 1 & 0 & 3&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 17\) et \( 2526\) est \( 1\) alors \( (17, 489)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 17^{-1}\equiv_{2526}743\) .
- Pour déchiffrer on fait \( 743(x-489) \) .
Message : CESTENFORGEANTQUONDEVIENTFORGERON
\[
\begin{array}{c|*{8}{c}}&1431&1100&2458&1649&1705&2237&178&243
\\\hline x-b&942&611&1969&1160&1216&1748&-311&-246
\\\hline a^{-1}(x-b)&699906&453973&1462967&861880&903488&1298764&-231073&-182778
\\\hline \%2526&204&1819&413&514&1706&400&1319&1620
\\\hline Décodage&CE&ST&EN&FO&RG&EA&NT&QU
\end{array}\]
\[
\begin{array}{c|*{9}{c}}&1776&605&961&2458&36&1844&653&1841&2381
\\\hline x-b&1287&116&472&1969&-453&1355&164&1352&1892
\\\hline a^{-1}(x-b)&956241&86188&350696&1462967&-336579&1006765&121852&1004536&1405756
\\\hline \%2526&1413&304&2108&413&1905&1417&604&1714&1300
\\\hline Décodage&ON&DE&VI&EN&TF&OR&GE&RO&NA
\end{array}\]