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, Géométrie dans l'espace, Nombres complexes, Probabilités et statistiques
Spécifique
Mai
2013
Sujet d'annales
.icon_annales.png
Entraînez-vous au concours Geipi-Polytech grâce à 4 exercices issus du concours de 2013.
loi binomiale | fonction exponentielle | suite convergente | algorithmique | vecteur | coordonnée
Tle S
Mathématiques
Algorithmique, Fonctions, Géométrie dans l'espace, Nombres complexes, Suites
Spécifique
Mai
2013
Sujet d'annales
.icon_annales.png
Entraînez-vous au concours Puissance 11 grâce à 16 exercices issus du concours de 2013.
dérivée | limite | fonction | algorithmique exponentielle | intégrale
Tle S
Mathématiques
Algorithmique, Arithmétique, Fonctions, Nombres complexes, Probabilités et statistiques, Suites
Spécifique
Amérique du Nord
Juin
2012
Bac
.icon_annales.png
Entraînez-vous avec 5 exercices, dont un de spécialité, sur les probabilités, les fonctions, les nombres complexes, les suites et l'arithmétique.
variable aléatoire | fonction logarithme népérien | algorithmique | fonction trigonométrique | suite d’intégrales
Tle S
Mathématiques
Algorithmique, Fonctions, Géométrie dans l'espace, Probabilités et statistiques, Suites
Spécifique
Amérique du Nord
Mai
2013
Bac
.icon_annales.png
Entraînez-vous avec 5 exercices, dont un de spécialité, sur la géométrie dans l'espace, l'algorithmique, les probabilités, les fonctions et les suites.
géométrie dans l'espace | algorithmique | probabilité | fonction logarithme népérien | congruence | suite
Tle S
Mathématiques
Algorithmique, Fonctions, Géométrie dans l'espace, Matrices, Nombres complexes, Probabilités et statistiques, Suites
Spécifique
Antilles-Guyane
Juin
2013
Bac
.icon_annales.png
Entraînez-vous avec 5 exercices, dont un de spécialité, grâce à un sujet complet du bac 2013.
suite | géométrie dans l'espace | loi binomiale | fonction exponentielle | nombre complexe