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(115, 2526)\) . Justifier.
- Expliquer pourquoi \( (115, 1738)\) est une clef de chiffrement du cryptosystème affine.
- Déterminer l'inverse de \( 115\) modulo \( 2526\) . Vous pourrez vous servir de la première question. Justifier.
- Par un chiffrement affine de clef \( (115, 1738)\) on a obtenu le message 1114-2461-1820-404-923-210-1150-1124-477-1929-670-1771-476. Quel est le message clair ? Justifier.
Cliquer ici pour afficher la solution
Exercice
- D'après l'algorithme d'Euclide on a \( PGCD(115, 2526)=1\) :
\[\begin{array}{|c|c|c|c||c|c|}\hline
a&b&r&q&u&v \\ \hline
115 & 2526 & 115 & 0&637 & -29 \\ \hline
2526 & 115 & 111 & 21&-29 & 637 \\ \hline
115 & 111 & 4 & 1&28 & -29 \\ \hline
111 & 4 & 3 & 27&-1 & 28 \\ \hline
4 & 3 & 1 & 1&1 & -1 \\ \hline
3 & 1 & 0 & 3&0 & 1 \\ \hline
\end{array}\]
- Puisque le PGCD entre \( 115\) et \( 2526\) est \( 1\) alors \( (115, 1738)\) est une clef de chiffrement valide du cryptosystème affine.
- D'apres l'algorithme d'Euclide étendu (voir plus haut), on a \( 115^{-1}\equiv_{2526}637\) .
- Pour déchiffrer on fait \( 637(x-1738) \) .
Message : QUITROPEMBRASSEMALETREINT
\[
\begin{array}{c|*{6}{c}}&1114&2461&1820&404&923&210
\\\hline x-b&-624&723&82&-1334&-815&-1528
\\\hline a^{-1}(x-b)&-397488&460551&52234&-849758&-519155&-973336
\\\hline \%2526&1620&819&1714&1504&1201&1700
\\\hline Décodage&QU&IT&RO&PE&MB&RA
\end{array}\]
\[
\begin{array}{c|*{7}{c}}&1150&1124&477&1929&670&1771&476
\\\hline x-b&-588&-614&-1261&191&-1068&33&-1262
\\\hline a^{-1}(x-b)&-374556&-391118&-803257&121667&-680316&21021&-803894
\\\hline \%2526&1818&412&11&419&1704&813&1900
\\\hline Décodage&SS&EM&AL&ET&RE&IN&TA
\end{array}\]