Cryptons avec M. Hill

Merci !

Annales corrigées
Classe(s) : Tle S | Thème(s) : Matrices et applications
Type : Exercice | Année : 2016 | Académie : Afrique

Afrique • Juin 2016

Exercice 4 • 5 points

Cryptons avec M. Hill

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=(5   27   7).

Partie A : Chiffrement de Hill

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

Étape 1. On divise le mot en blocs de deux lettres consécutives puis, pour chaque bloc, on effectue chacune des étapes suivantes.

Étape 2. On associe aux deux lettres du bloc les deux entiers x1 et x2, tous deux compris entre 0 et 25, qui correspondent aux deux lettres dans le même ordre, dans le tableau suivant :

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 3. On transforme la matrice X=(x1x2) en la matrice Y=(y1y2) vérifiant Y = AX.

Étape 4. On transforme la matrice Y=(y1y2) en la matrice R=(r1r2), où r1 est le reste de la division euclidienne de y1 par 26 et r2 celui de la division euclidienne de y2 par 26.

Étape 5. On associe aux entiers r1 et r2 les deux lettres correspondantes du tableau de l’étape 2. Le bloc chiffré est le bloc obtenu en juxtaposant ces deux lettres.

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 × a 1 modulo 26.

▶ 2. On considère l’algorithme suivant :

Variables

a, u et r sont des nombres (a est naturel et premier avec 26)

Traitement

Lire a

u prend la valeur 0 et r prend la valeur 0

Tant que r ≠ 1

u prend la valeur u + 1

r prend la valeur du reste de la division euclidienne de u × a par 26

Fin du Tant que

Sortie

Afficher u

On entre la valeur = 21 dans cet algorithme.

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

u

0

1

2

r

0

21

b) En déduire que 5 × 21 1 modulo 26.

▶ 3. On rappelle que A est la matrice A=(5   27   7) et on note I la matrice I=(1   00   1).

a) Calculer la matrice 12A A2.

b) En déduire la matrice B telle que B A = 21I.

c) Démontrer que si AX = Y, alors 21= BY.

Partie C : Déchiffrement

On veut déchiffrer le mot VLUP.

On note X=(x1x2) la matrice associée, selon le tableau de correspondance, à un bloc de deux lettres avant chiffrement, et Y=(y1y2) la matrice définie par l’égalité Y=AX=(5   27   7)X.

Si r1 et r2 sont les restes respectifs de y1 et y2 dans la division euclidienne par 26, le bloc de deux lettres après chiffrement est associé à la matrice R=(r1r2).

▶ 1. Démontrer que {21x1=7y12y221x2=7y1+5y2.

▶ 2. En utilisant la question B 2., établir que :

{x19r1+16r2 modulo26x217r1+25r2 modulo26

▶ 3. Déchiffrer le mot VLUP, associé aux matrices (2111) et (2015).

Les clés du sujet

Durée conseillée : 65 minutes.

Les thèmes clés

Matrices • Arithmétique.

Les outils dont vous avez besoin

Les références en rouge renvoient à la boîte à outils en fin d’ouvrage.

Calcul matriciel  C5  Partie A  Partie B, 3. a) et 3. b)

Nos coups de pouce

Partie B

▶ 1. Pensez à utiliser le théorème de Bézout.

Pour lire la suite :