BAC S 2016 de Mathématiques : Centres Étrangers 8 juin 2016 - Spécialité
Spécialité 5 points
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
- 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$.
- 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}$$ On entre la valeur $ a = 21$ dans cet algorithme.
-
- Reproduire et compléter le tableau suivant jusqu’à l’arrêt de l’algorithme.
- En déduire que $5 \times 21 \equiv 1 \:\text{modulo}\: 26$
- 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}$
- Calculer la matrice $12A - A^2$.
- En déduire la matrice $B$ telle que $BA = 21I$.
- 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}$.
- 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.$
- 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.$
- Déchiffrer le mot VLUP, associé aux matrices $\begin{pmatrix}21\\11\end{pmatrix}$ et $\begin{pmatrix}20\\15\end{pmatrix}$.
- Vues: 23591