Conforme au programme
Centres étrangers
Juin
2016
Bac
Spécialité
Tle S
Mathématiques
Codage, algorithme, matrice
Algorithmique
Matrices
.icon_annales.png Le but de l'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.

Sujet 4Codage, algorithme, matrice1 heure

Centres étrangers, juin 2016

Enseignement de spécialité

Algorithmique
Matrices

Exercice

5 pts

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 :

img1

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 :

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 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

u

0

1

2

r

0

21

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 – A2.          0,5 pt

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

c. Démontrer que si AXY, alors 21XBY.          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 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=( 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

Voir le corrigé

Cet article est réservé aux abonnés
ou aux acheteurs de livres ABC du Bac

Pour approfondir le thème...

Tle S
Mathématiques
Algorithmique, Fonctions
Spécifique
Polynésie
Juin
2016
Bac
.icon_annales.png
Deux courbes donnent pour deux personnes de corpulences différentes la concentration C d'alcool dans le sang (taux d'alcoolémie) en fonction du temps t après ingestion de la même quantité d'alcool.
fonction exponentielle | algorithme | limite
Tle S
Mathématiques
Algorithmique, Fonctions
Spécifique
Inde
Avril
2016
Bac
.icon_annales.png
On souhaite stériliser une boîte de conserve.
algorithme | fonction exponentielle | fonction logarithme népérien | primitive
Tle S
Mathématiques
Algorithmique
Spécifique
Mai
2016
On considère l'algorithme ALGO n°1.
algorithmique | algorithme | suite
Tle S
Mathématiques
Algorithmique, Géométrie dans le plan, Suites
Spécifique
Mai
2016
On divise chaque côté d'un triangle équilatéral de côté 1 en 3 segments de même longueur.
algorithme | suite | triangle | raison
Tle S
Mathématiques
Algorithmique, Fonctions, Suites
Spécifique
France métropolitaine
Juin
2016
Bac
.icon_annales.png
Montrer que la suite est convergente.
fonction logarithme | algorithme | suite | récurrence | limite