Cryptographie – Bac S Pondichéry 2016 (spé)
Exercice 3 - 5 points
Candidats ayant suivi l'enseignement de spécialité
Partie A
On considère les matrices $ M $ de la forme $ M = \begin{pmatrix}a&b \\ 5&3\end{pmatrix} $ où $ a $ et $ b $ sont des nombres entiers.
Le nombre $ 3a - 5b $ est appelé le déterminant de $ M $. On le note det$ (M) $.
Ainsi det$ (M) = 3a - 5b $.
Dans cette question on suppose que det$ (M) \ne 0 $ et on pose $ N = \dfrac{1}{\text{det}(M)}\begin{pmatrix}3& - b \\ - 5&a\end{pmatrix} $.
Justifier que $ N $ est l'inverse de $ M $.
On considère l'équation $ (E) :\quad \text{det}(M) = 3 $.
On souhaite déterminer tous les couples d'entiers $ (a~;~b) $ solutions de l'équation $ (E) $.
- Vérifier que le couple $ (6~;~3) $ est une solution de $ (E) $.
Montrer que le couple d'entiers $ (a~;~b) $ est solution de $ (E) $ si et seulement si$ 3(a - 6) = 5(b - 3) $.
En déduire l'ensemble des solutions de l'équation $ (E) $.
Partie B
On pose $ Q = \begin{pmatrix}6 & 3 \\ 5 & 3\end{pmatrix} $.
En utilisant la partie A, déterminer la matrice inverse de $ Q $.
Codage avec la matrice $ Q $
Pour coder un mot de deux lettres à l'aide de la matrice $ Q = \begin{pmatrix}6 &3 \\ 5& 3\end{pmatrix} $ on utilise la procédure ci-après :
Étape 1 : On associe au mot la matrice $ X = \begin{pmatrix}x_1 \\ x_2\end{pmatrix} $ où $ x_1 $ est l'entier correspondant à la première lettre du mot et $ x_2 $ l'entier correspondant à la deuxième lettre du mot selon le tableau de correspondance ci-dessous :
A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Étape 2 : La matrice $ X $ est transformée en la matrice $ Y = \begin{pmatrix}y_1 \\ y_2\end{pmatrix} $ telle que $ Y = QX $.
Étape 3 : La matrice $ Y $ est transformée en la matrice $ R = \begin{pmatrix}r_1 \\ r_2\end{pmatrix} $ telle que $ r_1 $ est le reste de la division euclidienne de $ y_1 $ par 26 et $ r_2 $ est le reste de la division euclidienne de $ y_2 $ par 26.
Étape 4 : À la matrice $ R = \begin{pmatrix}r_1 \\ r_2\end{pmatrix} $ on associe un mot de deux lettres selon le tableau de correspondance de l'étape 1.
Exemple : JE
$ \to X = \begin{pmatrix}9 \\ 4\end{pmatrix} \to Y = \begin{pmatrix}66 \\ 57\end{pmatrix} \to R \begin{pmatrix}14 \\ 5\end{pmatrix} \to $OF.
Le mot JE est codé en le mot OF.
Coder le mot DO.
Procédure de décodage On conserve les mêmes notations que pour le codage.
Lors du codage, la matrice $ X $ a été transformée en la matrice $ Y $ telle que $ Y = QX $.
- Démontrer que $ 3X = 3Q^{ - 1}Y $ puis que $ \begin{cases} 3x_1 \equiv 3r_1 - 3r_2 \quad [26]\\ 3x_2 \equiv - 5r_1+6r_2 \quad [26] \end{cases} $
- En remarquant que $ 9 \times 3 \equiv 1 \quad [26] $, montrer que $ \begin{cases} x_1 \equiv r_1 - r_2 \quad [26] \\ x_2 \equiv 7r_1+2r_2 \quad [26] \end{cases} $
- Décoder le mot SG.
Corrigé
Partie A
On a :
$ NM = \dfrac{1}{\text{det}(M)} \begin{pmatrix} 3 & -b \\ -5 & a \end{pmatrix} \begin{pmatrix} a & b \\ 5 & 3 \end{pmatrix} = \dfrac{1}{3a-5b} \begin{pmatrix} 3a-5b & 3b-3b \\ -5a+5a & -5b+3a \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I $où $ I $ est la matrice unité de dimension $ 2 \times 2 $. On en déduit que $ N = M^{-1} $.
L'équation $(E)$ est $ 3a - 5b = 3 $.
- Le couple $(6~;~3)$ est solution car $ 3 \times 6 - 5 \times 3 = 18 - 15 = 3 $.
$ 3a - 5b = 3 \iff 3a - 5b = 3 \times 6 - 5 \times 3 \iff 3(a-6) = 5(b-3) $.
5 divise $ 3(a-6) $ et $ \text{pgcd}(5, 3) = 1 $, donc d'après le théorème de Gauss, 5 divise $ a-6 $.
Il existe donc un entier relatif $ k $ tel que $ a-6 = 5k $, soit $ a = 6 + 5k $.
En remplaçant dans $ 3(a-6) = 5(b-3) $, on obtient $ 3(5k) = 5(b-3) $, soit $ 3k = b-3 $, donc $ b = 3 + 3k $.
L'ensemble des solutions est l'ensemble des couples $(6 + 5k~;~3 + 3k)$ où $ k \in \mathbb{Z} $.
Partie B
D'après la partie A, si $\text{det}(Q) = 3$, alors :
$ Q^{-1} = \dfrac{1}{3} \begin{pmatrix} 3 & -3 \\ -5 & 6 \end{pmatrix} = \begin{pmatrix} 1 & -1 \\ -\dfrac{5}{3} & 2 \end{pmatrix} $Codage du mot DO
$ D \to 3 $ et $ O \to 14 $. On a $ X = \begin{pmatrix} 3 \\ 14 \end{pmatrix} $.
$ Y = QX = \begin{pmatrix} 6 & 3 \\ 5 & 3 \end{pmatrix} \begin{pmatrix} 3 \\ 14 \end{pmatrix} = \begin{pmatrix} 18+42 \\ 15+42 \end{pmatrix} = \begin{pmatrix} 60 \\ 57 \end{pmatrix} $.
On calcule les restes de la division euclidienne par 26 :
$ 60 = 2 \times 26 + 8 $, donc $ r_1 = 8 \to I $.
$ 57 = 2 \times 26 + 5 $, donc $ r_2 = 5 \to F $.
Le mot DO est codé en IF.
Décodage
$ QX = Y \implies Q^{-1}QX = Q^{-1}Y \implies X = Q^{-1}Y $.
En multipliant par 3 : $ 3X = 3Q^{-1}Y $.
$ 3 \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = 3 \begin{pmatrix} 1 & -1 \\ -\dfrac{5}{3} & 2 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = \begin{pmatrix} 3 & -3 \\ -5 & 6 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = \begin{pmatrix} 3y_1 - 3y_2 \\ -5y_1 + 6y_2 \end{pmatrix} $D'où :
$ \begin{cases} 3x_1 = 3y_1 - 3y_2 \\ 3x_2 = -5y_1 + 6y_2 \end{cases} $Comme $ y_1 \equiv r_1 \pmod{26} $ et $ y_2 \equiv r_2 \pmod{26} $, on en déduit :
$ \begin{cases} 3x_1 \equiv 3r_1 - 3r_2 \pmod{26} \\ 3x_2 \equiv -5r_1 + 6r_2 \pmod{26} \end{cases} $$ 9 \times 3 = 27 \equiv 1 \pmod{26} $.
En multipliant les relations précédentes par 9 :
$ 9 \times 3x_1 \equiv 9(3r_1 - 3r_2) \pmod{26} \implies 27x_1 \equiv 27r_1 - 27r_2 \pmod{26} \implies x_1 \equiv r_1 - r_2 \pmod{26} $.
$ 9 \times 3x_2 \equiv 9(-5r_1 + 6r_2) \pmod{26} \implies 27x_2 \equiv -45r_1 + 54r_2 \pmod{26} $.
Or $ -45 = -2 \times 26 + 7 \equiv 7 \pmod{26} $ et $ 54 = 2 \times 26 + 2 \equiv 2 \pmod{26} $.
D'où $ x_2 \equiv 7r_1 + 2r_2 \pmod{26} $.
Décoder le mot SG
$ S \to 18 $ et $ G \to 6 $. On a $ r_1 = 18 $ et $ r_2 = 6 $.
$ x_1 \equiv 18 - 6 = 12 \to M $.
$ x_2$ est le reste de $ 7 \times 18 + 2 \times 6 = 126 + 12 = 138 $ par 26.
$ 138 = 5 \times 26 + 8 $. Donc $ x_2 = 8 \to I $.
Le mot SG se décode en MI.
(Solution rédigée par Paki)