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.

Corrigé

Corrigé

partie a : chiffrement de hill

À l’étape 1, le mot « HILL » est divisé en deux blocs de deux lettres consécutives. Le premier bloc est « HI », le deuxième bloc est « LL ».

Étapes 2 à 5 pour le bloc « HI ».

À l’étape 2, le bloc « HI » est associé aux deux entiers x1=7 et x2=8.

Gagnez des points !

Vous pouvez vérifier vos résultats à l’aide de la calculatrice  C5 .

La matrice X=(x1x2)=(78) est transformée, à l’étape 3, en la matrice Y:Y=AX=(5   27   7)×(78)=(5×7+2×87×7+7×8)=(51105)=(y1y2).

D’une part y1=51=26×1+25, soit y125  [26] et d’autre part y2=105=26×4+1, soit y21  [26].

Donc la matrice Y est transformée, à l’étape 4, en la matrice R=(251).

À cette matrice R est associé, à l’étape 5, le bloc « ZB ».

Étapes 2 à 5 pour le bloc « LL ».

À l’étape 2, le bloc « LL » est associé aux entiers x1=11 et x2=11.

Gagnez des points !

Vous pouvez vérifier vos résultats à l’aide de la calculatrice  C5 .

La matrice X=(x1x2)=(1111) est transformée, à l’étape 3, en la matrice Y :

Y=AX=(5   27   7)×(1111)=(5×11+2×117×11+7×11)=(77154)=(y1y2).

Comme y1=77=26×2+25, soit y125  [26] et y2=154=26×5+24, soit y224  [26], la matrice Y est transformée, à l’étape 4, en la matrice R=(2524).

À cette matrice R est associé, à l’étape 5, le bloc « ZY ».

Finalement, le bloc « HILL » est chiffré en « ZBZY ».

partie b : quelques outils mathématiques nécessaires au déchiffrement

▶ 1. Établir une relation de congruence

Notez bien

Théorème de Bézout. Si a et b, deux entiers relatifs, sont premiers entre eux, alors il existe deux entiers relatifs u et v tels que au+bv=1.

Comme l’entier relatif a et 26 sont premiers entre eux, d’après le théorème de Bézout, il existe deux entiers relatifs u et v tels que : a×u+26×v=1.

Ce qui s’écrit également u×a=126×v.

Par conséquent, u×a1 [26].

▶ 2. a) Dérouler un algorithme

La valeur 21 a été saisie pour la variable a au début de la phase de traitement. La variable u prend la valeur 0, la variable r également (2e colonne du tableau). Comme r=01, la boule « tant que » s’exécute : u prend la valeur 1 et, comme 1×21=21=0×26+21,r prend la valeur 21 (3e colonne du tableau). Les mises à jour des valeurs prises par les variables u et r sont faites « tant que r est différent de 1 ». Ce que nous pouvons résumer dans le tableau suivant :

u

0

1

2

3

4

5

Calcul intermédiaire

  1×21=0×26+21

  2×21=1×26+16

  3×21=2×26+11

  4×21=3×26+6

  5×21=4×26+1

r

0

21

16

11

6

1

Condition du « tant que »

Vraie

r=01

Vraie

r=211

Vraie

r=161

Vraie

r=111

Vraie

r=61

Fausse

r=1

L’algorithme affiche la valeur 5.

b) Utiliser un algorithme

Dans la phase de sortie, l’algorithme affiche la valeur 5. Nous en déduisons que 1 est le reste de la division euclidienne de 5×21 par 26.5×21 est alors congru à 1 modulo 26 ce qui se note 5×211 [26].

▶ 3. a) Calculer une matrice

Gagnez des points !

Vous pouvez vérifier vos résultats à l’aide de la calculatrice  C5 .

Nous avons :

12AA2=12×(5   27   7)(5   27   7)×(5   27   7)               =(12×5   12×212×7   12×7)(5×5+2×7   5×2+2×77×5+7×7   7×2+7×7)              =(60   2484   84)(39   2484   63)              =(6039   24248484    8463)              =(21   00   21)=21×(1   00   1)=21I.

▶ b) Identifier une matrice

Notez bien

Pour toute matrice carrée D d’ordre 2, I×D=D=D×I.

Par la question précédente, nous avons :

Gagnez des points !

Vous pouvez vérifier vos résultats à l’aide de la calculatrice  C5 .

12AA2=21I12(I×A)A×A=21I(12I)×AA×A=21I(12IA)×A=21I.

En posant B=12IA, nous avons : B=12×(1   00   1)(5   27   7)B=(125   0207   127)B=(7   27   5).

c) Démontrer une implication

Supposons vraie la relation matricielle AX=Y. Alors, en multipliant à gauche par la matrice B, on obtient B(AX)=BY. Par associativité, (BA)X=BY. Or, d’après la question précédente, BA=21I. Ainsi, (21I)×X=BY ou encore 21(I×X)=BY. La matrice I étant la matrice identité d’ordre 2, 21X=BY.

Nous en concluons que si AX=Y, alors 21X=BY.

partie c : déchiffrement

▶ 1. Établir un système d’équations

D’après l’énoncé, nous avons la relation matricielle : Y=AX.

Par la question B 3. c), nous en déduisons que 21X=BY. Pour rappel, d’après la question B 3. b), la matrice B est donnée par B=(7   27   5). Par conséquent :

21X=BY21(x1x2)=(7   27   5)(y1y2)(21x121x2)=(7y12y27y1+5y2).

Ce qui s’écrit également :

{21x1=7y12y221x2=7y1+5y2.

▶ 2. Établir un système d’équations

Multiplions chaque équation du système établi à la question précédente par 5 :

{21x1=7y12y221x2=7y1+5y2{5×21x1=35y110y25×21x2=35y1+25y2.

Or, d’après la question B 2. b), 5×211  [26]. Il en découle alors que :

{x135y110y2  [26]x235y1+25y2  [26].

Comme r1 et r2 sont les restes respectifs de y1 et y2 dans la division euclidienne par 26, ce que nous pouvons noter y1r1  [26] et y2r2  [26], il s’ensuit que :

{x135r110r2  [26]x235r1+25r2  [26].

Notez bien

35=26+99  [26] ; 10=26+1616  [26] ; 35=172×2617  [26].

Ainsi, nous en concluons que : {x19r1+16r2  [26]x217r1+25r2  [26].

▶ 3. Déchiffrer un mot

Le bloc « VL » est codé par la matrice (2111)=(r1r2)=R.

Or, d’après la question précédente, nous avons : x19r1+16r29×21+16×11365  [26] etx217r1+25r217×21+25×11632 [26].

Notez bien

365=26×14+11  [26] et 632=26×24+88  [26].

Ainsi, la matrice X est (x1x2)=(18) et le bloc « VL » est déchiffré en « BI ».

Le bloc « UP » est codé par la matrice (2015)=(r1r2)=R. Or, d’après la question précédente, nous avons : x19r1+16r29×20+16×15420  [26] et x217r1+25r217×20+25×15715 [26].

Notez bien

420=26×16+44  [26] et 715=26×27+1313  [26].

Ainsi, la matrice X est (x1x2)=(413) et le bloc « UP » est déchiffré en « EN ».

Le bloc « VLUP » est, par conséquent, déchiffré en « BIEN ».