③ Divisibilité dans Z
④ PGCD et applications
⑥ Calcul matriciel
Chiffrement de Hill
En 1929, le mathématicien et cryptologue Hill publie ses travaux concernant une méthode de chiffrement qui porte aujourd’hui son nom.
Le principe repose sur le choix d’une matrice
A vérifiant les conditions suivantes :
- det(A) est non nul ;
- det(A) est premier avec 26.
On travaillera ici avec la matrice
A=(7123).
Partie A : Étude de la matrice A
1. Justifier que la matrice
A vérifie bien les conditions demandées par l’énoncé.
2. À l’aide de la calculatrice, déterminer
A−1.
Partie B : Étude du chiffrement
Le chiffrement de Hill repose uniquement sur le choix de la matrice
A.
Pour coder un mot ayant un nombre pair
n de lettres, on procède de la manière suivante :
- on associe à chaque lettre de l’alphabet un nombre entre 0 et 25 en suivant l’ordre alphabétique ;
- on divise le mot à chiffrer en blocs de deux lettres successives. On obtient donc plusieurs blocs de nombres (x1;x2);…;(xn−1;xn) ;
- on utilise alors la matrice A pour procéder au chiffrement : on calcule, pour tout entier k∈{0;…;2n−2}, (y2k+1y2k+2)=A×(x2k+1x2k+2).
On obtient alors les blocs (y1;y2);…;(yn−1;yn) qu’on juxtapose : le mot initialement choisi est alors codé par une suite de nombres y1y2…yn ;
- on réduit modulo 26 chacun de ces nombres : pour tout entier k∈{1;…;n}, on détermine le reste rk de la division euclidienne de yk par 26 ;
- le mot choisi est donc maintenant codé par une suite de nombres r1r2…rn ;
- on associe à chacun de ces nombres compris entre 0 et 25 une lettre selon le procédé décrit précédemment.
1. En utilisant la matrice
A décrite au début de l’exercice, coder le mot JUIN par ce procédé.
2. Coder un mot de votre choix en utilisant ce procédé.
Compte tenu du processus de codage décrit ici, le mot doit être constitué d’un nombre pair de lettres.
3. Compléter le programme ci‑après afin qu’il transforme la liste initiale de nombres en la suite codée de nombres.
def Hill(L):
n = len(L)
if n%2 != 0:
return 'Il faut un nombre de lettres pair !'
else:
for k in range(int(n/2)):
L[2*k], L[2*k + 1] = ... , ...
L[2*k] = L[2*k]%26
L[2*k + 1] = L[2*k + 1]%26
return L
Partie C : Étude du déchiffrement
On cherche ici à déterminer un moyen de déchiffrer un mot chiffré par le procédé précédent. Sans perte de généralité, on étudie uniquement le bloc codé
(r1;r2) correspondant au couple de nombres
(y1;y2) obtenu après transformation des nombres
(x1;x2) du mot initial.
On note donc
Y=(y1y2) la matrice correspondant aux nombres obtenus suite à la multiplication à gauche de la matrice
X=(x1x2) par
A.
1. Justifier que
(x1;x2) est une solution du système d’équations suivant :
{19x1=3y1−2y219x2=−y1+7y2.
2. Montrer que
(x1;x2) est une solution du système de congruences suivant :
{19x1≡3r1−2r2[26]19x2≡−r1+7r2[26].
3. Déterminer un inverse de
19 modulo
26.
4. En déduire que
x1 et
x2 vérifient le système :
{x1≡7r1+4r2[26]x2≡15r1+25r2[26].
5. Le codage d’un mot a donné OCRR, c’est‑à‑dire la liste
(r1;r2;r1′;r2′)=(14;2;17;17). On cherche à retrouver le mot initial.
En appliquant le résultat de la question
4. à
(142) et
(1717), retrouver le mot initial.
Remarque :
Lorsque le nombre de lettres est divisible par 3, il est possible de coder des blocs de trois lettres de la même manière que ci‑dessus en utilisant une matrice carrée d’ordre 3 vérifiant les mêmes conditions que dans l’énoncé.
Lester S. Hill (1891‑1961) est un mathématicien et cryptologue américain. Ses recherches reposent
principalement sur l’application des mathématiques dans les systèmes de communications et notamment
la cryptographie : le chiffrement de Hill fait partie de ses principales contributions mais il a aussi développé des méthodes pour détecter des erreurs dans les transmissions télégraphiques.