BAC S 2016 de Mathématiques : Centres Étrangers 8 juin 2016: Spécialité

oui
S
Année 2016
Centres étrangers
Spécialité
Arithmétique

Spécialité 5 points


Candidats AYANT SUIVI l'enseignement de spécialité mathématiques


Le but de cet exercice est d'étudier, sur un exemple, une méthode de chiffrement publiée en 1929 par le mathématicien et cryptologue Lester Hill. Ce chiffrement repose sur la donnée d'une matrice \(A\), connue uniquement de l'émetteur et du destinataire. Dans tout l'exercice, on note \(A\) la matrice définie par : \(A = \begin{pmatrix}5&2\\7&7\end{pmatrix}\).

Partie A -- Chiffrement de Hill


Voici les différentes étapes de chiffrement pour un mot comportant un nombre pair de lettres : \[\begin{array} {|l|l|}\hline \text{ Étape 1 }&\text{ On divise le mot en blocs de deux lettres consécutives puis, pour chaque bloc, on effectue chacune des étapes suivantes.}\\ \hline \text{ Étape 2}&\text{ On associe aux deux lettres du bloc les deux entiers } x_1 \text{ et } x_2 \text{tous deux compris entre 0 et 25, qui correspondent aux deux lettres dans le même ordre, dans le tableau suivant :}\\ & \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline A &B &C &D &E &F &G &H &I &J &K &L &M\\ \hline 0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12\\ \hline\hline N &O &P &Q &R &S &T &U &V &W &X &Y &Z\\ \hline 13 &14 &15 &16 &17 &18 &19 &20 &21 &22 &23 &24 &25\\ \hline \end{array} \\ \hline \text{Étape 3 }& \text{On transforme la matrice } X = \begin{pmatrix}x_1\\x_2\end{pmatrix} \text{ en la matrice } Y = \begin{pmatrix}y_1\\y_2\end{pmatrix} \text{ vérifiant } Y = A X .\\ \hline \text{Étape 4 }&\text{On transforme la matrice } Y = \begin{pmatrix}y_1\\y_2\end{pmatrix} \text{ en la matrice } R = \begin{pmatrix}r_1\\r_2\end{pmatrix} \text{, où } r_1 \text{ est le reste de la division euclidienne de } y_1 \text{ par 26 et} r_2 \text{ celui de la division euclidienne de } y_2 \text{ par } 26.\\ \hline \text{Étape 5 }&\text{ On associe aux entiers } r_1 \text{ et } r_2 \text{ les deux lettres correspondantes du tableau de l'étape 2. }\\ &\text{ Le bloc chiffré est le bloc obtenu en juxtaposant ces deux lettres.}\\ \hline \end{array} \]
Question : utiliser la méthode de chiffrement exposée pour chiffrer le mot « HILL ».

Partie B - Quelques outils mathématiques nécessaires au déchiffrement

 

  1. Soit \(a\) un entier relatif premier avec 26. Démontrer qu'il existe un entier relatif \(u\) tel que \(u \times a \equiv 1 \:\text{modulo}\: 26\).
  2. On considère l'algorithme suivant : \[ \begin{array}{|c|lX|}\hline \text{VARIABLES :} & a, u , \text{ et } r \text{ sont des nombres ( } a \text{ est naturel et premier avec 26)}\\ \text{TRAITEMENT :}& \text{Lire } a \\ & u \text{ prend la valeur 0, et } r \text{ prend la valeur 0 } \\ &\text{Tant que } r \neq 1 \\ &\hspace{0,8cm} u \text{ prend la valeur }u + 1\\ & \hspace{0,8cm}r \text{ prend la valeur du reste de la division euclidienne de } u \times a \text{ par } 26 \\ &\text{ Fin du Tant que } \\ \text{ SORTIE } &\text{Afficher } u \\ \hline \end{array}\]
  3. On entre la valeur \( a = 21\) dans cet algorithme.
    1. Reproduire et compléter le tableau suivant jusqu’à l’arrêt de l’algorithme.
    2. En déduire que \(5 \times 21 \equiv 1 \:\text{modulo}\: 26\)
  4. On rappelle que \(A = \begin{pmatrix}5&2\\7&7\end{pmatrix}\) et on note \(I = Id_2 = \begin{pmatrix}1&0\\0&1\end{pmatrix}\)
    1. Calculer la matrice \(12A - A^2\).
    2. En déduire la matrice \(B\) telle que \(BA = 21I\).
    3. Démontrer que si \(AX = Y\) alors \(21X = BY\) .
Partie C : Déchiffrement

On veut déchiffrer le mot V LUP.

On note \(X = \begin{pmatrix}x_1\\x_2\end{pmatrix}\) la matrice associée, selon le tableau de correspondance, à un bloc de deux lettres avant chiffrement, et \(Y = \begin{pmatrix}y_1\\y_2\end{pmatrix}\) la matrice définie par l'égalité : \(Y = A X = \begin{pmatrix}5&2\\7&7\end{pmatrix}X\).
Si \(r_1\) et \(r_2\) sont les restes respectifs de \(y_1\) et \(y_2\) dans la division euclidienne par 26, le bloc de deux lettres après chiffrement est associé à la matrice \(R = \begin{pmatrix}r_1\\r_2\end{pmatrix}\).

  1. Démontrer que : \(\left\{\begin{array}{l c l} 21x_1 &=& \phantom{-}7y_1 - 2y_2\\ 21x_2 &=&- 7y_1 + 5 y_2 \end{array}\right.\)
  2. En utilisant la question B .2., établir que: \(\left\{\begin{array}{l c l r} x_1 &\equiv&9r_1 + 16r_2 \:\:&\text{modulo}\: 26\\ x_2 &\equiv&17r_1 + 25r_2 \:\:&\text{modulo}\: 26 \end{array}\right.\)
  3. Déchiffrer le mot VLUP, associé aux matrices \(\begin{pmatrix}21\\11\end{pmatrix}\) et \(\begin{pmatrix}20\\15\end{pmatrix}\).
 

Correction de l'exercice de Spécialité 5 points


Candidats AYANT SUIVI l'enseignement de spécialité mathématiques


Le but de cet exercice est d'étudier, sur un exemple, une méthode de chiffrement publiée en 1929 par le mathématicien et cryptologue Lester Hill. Ce chiffrement repose sur la donnée d'une matrice \(A\), connue uniquement de l'émetteur et du destinataire. Dans tout l'exercice, on note \(A\) la matrice définie par : \(A = \begin{pmatrix}5&2\\7&7\end{pmatrix}\).

Partie A -- Chiffrement de Hill


Voici les différentes étapes de chiffrement pour un mot comportant un nombre pair de lettres : \[\begin{array} {|l|l|}\hline \text{ Étape 1 }&\text{ On divise le mot en blocs de deux lettres consécutives puis, pour chaque bloc, on effectue chacune des étapes suivantes.}\\ \hline \text{ Étape 2}&\text{ On associe aux deux lettres du bloc les deux entiers } x_1 \text{ et } x_2 \text{tous deux compris entre 0 et 25, qui correspondent aux deux lettres dans le même ordre, dans le tableau suivant :}\\ & \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline A &B &C &D &E &F &G &H &I &J &K &L &M\\ \hline 0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12\\ \hline\hline N &O &P &Q &R &S &T &U &V &W &X &Y &Z\\ \hline 13 &14 &15 &16 &17 &18 &19 &20 &21 &22 &23 &24 &25\\ \hline \end{array} \\ \hline \text{Étape 3 }& \text{On transforme la matrice } X = \begin{pmatrix}x_1\\x_2\end{pmatrix} \text{ en la matrice } Y = \begin{pmatrix}y_1\\y_2\end{pmatrix} \text{ vérifiant } Y = A X .\\ \hline \text{Étape 4 }&\text{On transforme la matrice } Y = \begin{pmatrix}y_1\\y_2\end{pmatrix} \text{ en la matrice } R = \begin{pmatrix}r_1\\r_2\end{pmatrix} \text{, où } r_1 \text{ est le reste de la division euclidienne de } y_1 \text{ par 26 et} r_2 \text{ celui de la division euclidienne de } y_2 \text{ par } 26.\\ \hline \text{Étape 5 }&\text{ On associe aux entiers } r_1 \text{ et } r_2 \text{ les deux lettres correspondantes du tableau de l'étape 2. }\\ &\text{ Le bloc chiffré est le bloc obtenu en juxtaposant ces deux lettres.}\\ \hline \end{array} \]
Question : utiliser la méthode de chiffrement exposée pour chiffrer le mot « HILL ».

On décompose HILL en HI et LL
Ainsi dans un premier temps \(X=\begin{pmatrix}7\\8\end{pmatrix}\)
\(Y=AX=\begin{pmatrix}51\\105\end{pmatrix}\)
Or \(51\equiv 25\quad [26]\) et \(105\equiv 1 \quad [26]\).
Donc HI est codé par ZB
\(\quad\)
On prend maintenant le couple de lettre LL \(X=\begin{pmatrix}11\\11\end{pmatrix}\)
\(Y=AX=\begin{pmatrix}77\\154\end{pmatrix}\)
Or \(77\equiv 25\quad [26]\) et \(154\equiv 24 \quad [26]\).
Donc HI est codé par ZY

Donc HILL est codé par ZBZY
\(\quad\)

Partie B - Quelques outils mathématiques nécessaires au déchiffrement

 

  1. Soit \(a\) un entier relatif premier avec 26. Démontrer qu'il existe un entier relatif \(u\) tel que \(u \times a \equiv 1 \:\text{modulo}\: 26\).
  2. \(a\) et \(26\) sont premiers entre eux.
    D’après le théorème de Bézout il existe donc deux entiers relatifs \(u\) et \(v\) tels que
    \(u\times a+26 \times v=1\)
    En passant au modulo \(26\) on a alors \(v \times 26\equiv 1\quad [26]\).
  3. On considère l'algorithme suivant : \[ \begin{array}{|c|lX|}\hline \text{VARIABLES :} & a, u , \text{ et } r \text{ sont des nombres ( } a \text{ est naturel et premier avec 26)}\\ \text{TRAITEMENT :}& \text{Lire } a \\ & u \text{ prend la valeur 0, et } r \text{ prend la valeur 0 } \\ &\text{Tant que } r \neq 1 \\ &\hspace{0,8cm} u \text{ prend la valeur }u + 1\\ & \hspace{0,8cm}r \text{ prend la valeur du reste de la division euclidienne de } u \times a \text{ par } 26 \\ &\text{ Fin du Tant que } \\ \text{ SORTIE } &\text{Afficher } u \\ \hline \end{array}\]
    1. Reproduire et compléter le tableau suivant jusqu’à l’arrêt de l’algorithme.
    2. \[\begin{array}{|c|c|c|c|c|c|c|}
      \hline
      u&0&1&2&3&4&5 \\
      \hline
      r&0&21&16&11&6&1\\
      \hline
      \end{array}\]
      L’algorithme permet de fournir un entier naturel \(u\) tel que \(u\times a \equiv 1\quad [26]\)
    3. En déduire que \(5 \times 21 \equiv 1 \:\text{modulo}\: 26\)
    4. L’algorithme affiche \(5\) pour \(a=21\) donc \(5\times 21 \times 5 \equiv 1\quad [26]\).
  4. On rappelle que \(A = \begin{pmatrix}5&2\\7&7\end{pmatrix}\) et on note \(I = Id_2 = \begin{pmatrix}1&0\\0&1\end{pmatrix}\)
    1. Calculer la matrice \(12A - A^2\).
    2. \(12A=\begin{pmatrix} 60&24\\84&84\end{pmatrix}\)
      \(A^2=\begin{pmatrix} 39&24\\84&63\end{pmatrix}\)
      Donc \(12A-A^2=\begin{pmatrix}21&0\\0&21\end{pmatrix}\)
      Soit \(12A-A^2=21I\).
    3. En déduire la matrice \(B\) telle que \(BA = 21I\).
    4. \(12A-A^2=21I \iff (12I-A)\times A =21I\)
      Donc \(B=12I-A\).
      \(\quad\)
    5. Démontrer que si \(AX = Y\) alors \(21X = BY\) .
    6. Si \(AX=Y\) alors \(BAX=BY\) soit \(21IA=BY\) et donc \(21X=BY\).
      \(\quad\)
Partie C : Déchiffrement

On veut déchiffrer le mot VLUP.

On note \(X = \begin{pmatrix}x_1\\x_2\end{pmatrix}\) la matrice associée, selon le tableau de correspondance, à un bloc de deux lettres avant chiffrement, et \(Y = \begin{pmatrix}y_1\\y_2\end{pmatrix}\) la matrice définie par l'égalité : \(Y = A X = \begin{pmatrix}5&2\\7&7\end{pmatrix}X\).
Si \(r_1\) et \(r_2\) sont les restes respectifs de \(y_1\) et \(y_2\) dans la division euclidienne par 26, le bloc de deux lettres après chiffrement est associé à la matrice \(R = \begin{pmatrix}r_1\\r_2\end{pmatrix}\).

  1. Démontrer que : \(\left\{\begin{array}{l c l} 21x_1 &=& \phantom{-}7y_1 - 2y_2\\ 21x_2 &=&- 7y_1 + 5 y_2 \end{array}\right.\)
  2. \(B=12I-A=\begin{pmatrix} 7&-2\\-7&5\end{pmatrix}\)
    Donc \(21X=BY \iff \begin{cases} 21x_1=7y_1-2y_2 \\21x_2=-7y_1+5y_2\end{cases}\)
    \(\quad\)
  3. En utilisant la question B .2., établir que: \(\left\{\begin{array}{l c l r} x_1 &\equiv&9r_1 + 16r_2 \:\:&\text{modulo}\: 26\\ x_2 &\equiv&17r_1 + 25r_2 \:\:&\text{modulo}\: 26 \end{array}\right.\)
  4. On multiplie les deux lignes de ce système par \(5\).
    \(\begin{cases} 5\times 21x_1=35y_1-10y_2\\5\times 21x_2=-35y_1+25y_2\end{cases}\)
    On passe au modulo \(26\) et on utilise le fait que \(5\times 21 \equiv 1 \quad[26]\)
    Donc \(\begin{cases} x_1\equiv 9r_1+16r_2 \quad [26] \\x_2=17r_1+25r_2 \quad [26] \end{cases}\)
    \(\quad\)
  5. Déchiffrer le mot VLUP, associé aux matrices \(\begin{pmatrix}21\\11\end{pmatrix}\) et \(\begin{pmatrix}20\\15\end{pmatrix}\).
  6. On prend dans un premier temps \(r_1=21\) et \(r_2=11\)
    Donc \(x_1\equiv 9\times 21+16\times 11\equiv 365 \equiv 1\quad [26]\)
    et \(x_2 \equiv 17 \times 21+25\times 11 \equiv 632 \equiv 8\quad [26]\)
    \(\quad\)
    On prend ensuite \(r_1=20\) et \(r_2=15\)
    Donc \(x_1\equiv 9\times 20+16\times 15\equiv 420\equiv 4\quad [26]\)
    et \(x_2 \equiv 17 \times 20+25\times 15 \equiv 715 \equiv 13\quad [26]\)
    \(\quad\)
    Ainsi VLUP est la version codé de BIEN.
 

ImprimerE-mail

Statistiques

Visiteurs
173
Articles
1392
Compteur d'affichages des articles
8042085