Exercice

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 américain 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=( 52 77 ) .

Partie A Chiffrement de Hill

Voici les différentes étapes de chiffrement pour un mot comportant un nombre pair de lettres :

Question : utiliser la méthode de chiffrement exposée pour chiffrer le mot « HILL ».          0,5 pt

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 × a ≡ 1 modulo 26.          0,5 pt

2 On considère l’algorithme suivant :

On entre la valeur a = 21 dans cet algorithme.

a. Reproduire sur la copie et compléter le tableau suivant, jusqu’à l’arrêt de l’algorithme.          0,5 pt

b. En déduire que 5 × 21 ≡ 1 modulo 26.          0,5 pt

3 On rappelle que A est la matrice A=( 52 77 ) et on note I la matrice :

I=( 10 01 ).

a. Calculer la matrice 12A – A².          0,5 pt

b. En déduire la matrice B telle que BA = 21I.          0,5 pt

c. Démontrer que si AX = Y, alors 21X = BY.          0,5 pt

Partie C  Déchiffrement

On veut déchiffrer le mot VLUP.

On note X=( x 1 x 2 ) la matrice associée, selon le tableau de correspondance, à un bloc de deux lettres avant chiffrement, et Y=( y 1 y 2 ) la matrice définie par l’égalité :

Y=AX=( 52 77 )X.

Si r₁ et r₂ sont les restes respectifs de y₁ et y₂ dans la division euclidienne par 26, le bloc de deux lettres après chiffrement est associé à la matrice :

R=( r 1 r 2 ).

1 Démontrer que { 21 x 1 =7 y 1 –2 y 2 21 x 2 =–7 y 1 +5 y 2           0,5 pt

2 En utilisant la question Partie B 2, établir que :

{ x 1 ≡9 r 1 +16 r 2 modulo26 x 2 ≡17 r 1 +25 r 2 modulo26          0,5 pt

3 Déchiffrer le mot VLUP, associé aux matrices ( 21 11 ) et ( 20 15 ) .          0,5 pt