© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
Dans cette activité, on étend la notion de congruence modulo $n$ ( $n \geqslant 2$ ) à des matrices à coefficients entiers.
On dira que deux matrices $A$ et $B$ à coefficients entiers sont congrues modulo $n$ si leurs coefficients correspondants sont deux à deux congrus modulo $n$.
On notera alors $A \equiv B \;[n]$.
Ainsi, pour des matrices de dimension $2 \times 2$ à coefficients entiers, on a :
$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \equiv \begin{pmatrix} a' & b' \\ c' & d' \end{pmatrix} [n]$ si et seulement si $\begin{Bmatrix} a \equiv a' [n] \\ b \equiv b' [n] \\ c \equiv c' [n] \\ d \equiv d' [n] \end{Bmatrix}$
0.0. On considère des matrices $A$; $B$ et $C$ de dimension $2 \times 2$ à coefficients entiers, telles que $A \equiv B \;[n]$.
$\;\;\;\;\;\;$Démontrer que $CA \equiv CB \;[n]$.
Deux détectives, Archibald et Balthazar, souhaitent échanger des messages secrets, de telle sorte qu'ils soient difficilement déchiffrables s'ils tombaient en de mauvaises mains. Pour simplifier, on supposera que les messages à coder sont écrits en majuscules, sans accents, et ne comportent pas d'espaces.
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Par exemple:
Archibald souhaite coder le mot "EUREKA". Les premières lettres "EU" correspondent à la matrice $ X=\begin{pmatrix} 4 \\ 20 \end{pmatrix} $ qui donne la matrice codée $ HX= \begin{pmatrix} 9 & 4 \\ 5 & 7 \end{pmatrix} \begin{pmatrix} 4 \\ 20 \end{pmatrix}=\begin{pmatrix} 116 \\ 160 \end{pmatrix} \equiv \begin{pmatrix} 12 \\ 4 \end{pmatrix} [26]$. On obtient donc les lettres codées "ME".
1.1. Coder complètement le mot "EUREKA".
Le mot "EUREKA" est codé en "MENJMY".1.2. On donne la fonction Python codage_Hill ci-dessous, qui permet de coder un message à l'aide d'une matrice de chiffrement H.
$\;\;\;\;\;\;$Exécuter les deux cellules pour vérifier le résultat de la question 1.1.
import numpy as np
#Mise en mémoire de l'alphabet
Alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def codage_Hill(message,H):
"""
fonction réalisant le codage du message
à l'aide de la matrice de chiffrement H
"""
code=""
if len(message)%2 !=0: message += "A" # s'il n'y a pas un nombre pair de lettres, on complète le message avec un A
for k in range(len(message)//2): # pour chaque couple de lettres:
X = np.array([[ Alphabet.index(message[2*k])], # on crée la matrice X
[ Alphabet.index(message[2*k+1])]])
Y = np.dot( H , X ) %26 # on calcule la matrice Y
code += Alphabet[Y[0][0]]+Alphabet[Y[1][0]] # on complète le code avec les deux lettres obtenues
return code
#définition de la matrice de chiffrement H
H = np.array([ [ 9 , 4 ],
[ 5 , 7 ] ])
#Appel à la fonction codage_Hill pour la construction du message codé
code = codage_Hill("EUREKA",H)
code
Archibald et Balthazar ont convenu d'une matrice $H$ pour coder leurs messages, mais il leur faut maintenant aussi une méthode pour déchiffrer les messages. On cherche à déterminer une matrice $D$ qui, utilisée comme précédemment, permette ce décodage.
1.3. Vérifier que la matrice $H$ a pour déterminant $43$. En déduire que $H$ est une matrice inversible et calculer $H^{-1}$.
$\;\;\;\;\;$Pourquoi la matrice $H^{-1}$ ne peut-elle pas être la matrice $D$ cherchée ?
1.4. a. Sans chercher à déterminer sa valeur, justifier qu'il existe un unique $m$ tel que $1 \leqslant m \leqslant 25$ et $43m \equiv 1 [26]$.
$\;\;\;\;\;\;\;\;\;$On dit que $m$ est l'inverse de $43$ modulo $26$
$\;\;\;\;\;\;\;\;\;$(pour démontrer l'existence, on pourra appliquer le théorème de Bézout)
$\;\;\;\;\;$b. Ecrire une fonction Python inv qui renvoie une valeur $m$ qui convient.
$\;\;\;\;\;\;\;\;$(on pourra écrire une boucle qui teste un à un les candidats pour la valeur de $m$ à partir de $1$)
#Ecrire ici la fonction inv
def inv():
"""
renvoie l'inverse de 43 modulo 26
"""
for m in range(1,26):
if 43*m %26 == 1:
return m
return None
$\;\;\;\;\;$c. A l'aide d'un appel à la fonction Python inv, déterminer une valeur de $m$ qui convient.
#Effectuer ici l'appel à la fonction inv
inv()
1.5. a. Vérifier que la matrice $D_0=43H^{-1}$ est à coefficients entiers.
$\;\;\;\;\;$b. Déterminer une matrice $D$, dont les coefficients sont entiers compris entre $0$ et $25$, telle que $D \equiv m D_0[26]$.
$\;\;\;\;\;$c. On considère deux matrices colonnes $X=\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}$ et $Y=\begin{pmatrix} y_1 \\ y_2 \end{pmatrix}$. Démontrer que $Y \equiv HX [26]$ est équivalent à $X \equiv DY [26]$.
La matrice $D$ ainsi construite est donc la matrice de déchiffrement cherchée.
1.6. Définir ci-dessous la matrice $D$ en langage Python (s'inspirer de la syntaxe utilisée pour $H$ dans la question 1.2).
# définir ici la matrice de déchiffrement D
D = np.array([ [ 5 , 12 ],
[ 15 , 25 ] ])
D
1.7. Effectuer un appel à la fonction Python codage_Hill pour décoder le message qui a été codé à la question 1.2.
$\;\;\;\;\;$Vérifier qu'on retrouve bien le mot "EUREKA".
# Effectuer ici l'appel à la fonction codage_Hill
decode = codage_Hill("MENJMY",D)
decode
1.8. Balthazar a reçu de la part d'Archibald le message suivant: "IWVZHSGENJSSMQMVSIINAJ". Décoder ce message.
# Utiliser cette zone de saisie pour décoder le message
decode = codage_Hill("IWVZHSGENJSSMQMVSIINAJ",D)
decode
On considère une matrice $H$ de dimension $2 \times 2$ à coefficients entiers, de déterminant $d=det(H)$.
On suppose que $d$ est non nul et premier avec $26$.
2.1. Justifier qu'il existe un entier $m$ tel que $dm \equiv 1[26]$ ($m$ est inverse de $d$ modulo $26$)
$\;\;\;\;\;\;$(on pourra utiliser le théorème de Bézout)
2.2. Adapter la fonction inv de la question 1.4 pour qu'elle reçoive en argument une valeur d et renvoie son inverse m modulo $26$.
#Ecrire ici la fonction inv modifiée
def inv(d):
"""
renvoie l'inverse de d modulo 26
"""
for m in range(1,26):
if d*m %26 == 1:
return m
return None
2.3. a. Justifier que la matrice $D_0=dH^{-1}$ est à coefficients entiers.
$\;\;\;\;\;$b. On considère une matrice $D$ à coefficients entiers telle que $D \equiv mD_0 [26]$.
$\;\;\;\;\;\;\;\;$On considère deux matrices colonnes $X=\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}$ et $Y=\begin{pmatrix} y_1 \\ y_2 \end{pmatrix}$ à coefficients entiers.
$\;\;\;\;\;\;\;\;$Démontrer que $Y \equiv HX [26]$ est équivalent à $X \equiv DY [26]$.
2.4. Convenir avec une autre personne d'une matrice de chiffrement $H$ (dont le déterminant est premier avec $26$).
$\;\;\;\;\;$Chacun code alors un message à l'aide de la fonction Python codage_Hill en utilisant cette matrice, et le donne à l'autre.
$\;\;\;\;\;$Enfin, après avoir déterminé la matrice de décodage $D$, chacun décode le message reçu à l'aide de la fonction Python codage_Hill.
#Utiliser les zones de saisie ci-dessous
#définition de la matrice de chiffrement H
H = np.array([ [ 7 , 15 ],[ 13 , 4 ] ])
H
#Codage d'un message
code = codage_Hill("ONARRIVEAUBOUTDELACTIVITE",H)
code
# LES CALCULS SUIVANTS PEUVENT ETRE FAIT A PART, SANS PYTHON
# LES SYNTAXES D'UTILISATION DES MATRICES SONT EXPERTES
# ET IL Y A DES PRECAUTIONS A PRENDRE SUR LE TYPE DES VARIABLES (int)
#calcul du déterminant de H
#(attention, l'utilisation de la fonction np.linalg.det de numpy ne renvoie pas un int)
d = H[0][0]*H[1][1]-H[0][1]*H[1][0]
d
#calcul de m (inverse de d)
m = inv(d)
m
#calcul des matrices D0 et D
#(attention, le calcul ne donne pas des valeurs int)
D0 = d*np.linalg.inv(H)
D0 = D0.astype(int)
D = m*D0
D
decodage = codage_Hill(code,D)
decodage
© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Dernière modification de l'activité : Juillet 2022