import numpy as np
Certains exemples et textes de ce TP sont tirés de Exercices et Problèmes de cryptographie de Damien Vergnaud, 3ème édition
Dans le chiffrement par substitution monoalphabétique, un symbole du message en clair était toujours remplacé par un même symbole pour constituer le message chiffré et un symbole du chiffré correspondait toujours au même symbole du clair. L'attaque par analyse de fréquence est donc très efficace sur ce type de chiffrement.
Dans le chiffrement par substitution polyalphabétique, plusieurs alphabets de chiffrement sont utilisés. Un symbole du message en clair sera remplacé par un autre symbole en fonction de sa position dans le clair, de l'algorithme de chiffrement utilisé et de la clef choisi. Ainsi, deux occurences d'un même symbole dans le clair peuvent être remplacées par des symboles différents dans le chiffré. Et un même symbole dans le chiffré peut servir à coder des lettres différentes du clair.
Dans ce TP, nous étudierons 2 types de chiffrement par substitution polyalphabétique : le chiffrement de Vigenère et le chiffrement de Hill.
Pour chaque type de chiffrement, nous développerons des fonctions pour:
Par convention, nous appelerons :
Le chiffrement de Vigenère consiste à effectuer de façon périodique plusieurs chiffrements par décalage. La clef utilisée est un mot, bien plus court que le message à chiffrer, qui donne la valeur du décalage à effectuer pour chaque lettre du clair.
Par exemple, chiffrons le mot chiffrement à l'aide de l'algorithme de Vigenère et de la clef clef. Cette clef indique que :
Le mot chiffrement sera donc chiffré esmkhcirgyx. On peut remarquer que les deux "f" du clair sont chiffrés par "k" et "h" respectivement.
# Quelques fonctions utiles (ou pas)
def lettreToEntier(lettre, alphabet = "abcdefghijklmnopqrstuvwxyz"):
return alphabet.find(lettre)
def entierToLettre(a, alphabet = "abcdefghijklmnopqrstuvwxyz"):
return alphabet[int(a)]
print("Lettre -> entier : w ->", lettreToEntier('w'))
print("Entier -> Lettre : 22 ->", entierToLettre(22))
Question 1 (chiffrement) : Définir une fonction
chiffrementVigenere(msgClair, clef, alphabet)qui étant donné un message en clairmsgClair, un motclefet un alphabetalphabet(par défaut, l'alphabet français) renvoie le message chiffré par l'algorithme de Vigenère.
Note : il est bien sûr possible et conseillé de réutiliser les fonctions codées dans le TP précédent.
def chiffrementVigenere(msgClair, clef, alphabet="abcdefghijklmnopqrstuvwxyz"):
return "TODO"
try:
assert chiffrementVigenere("vigenere","truc") == "ozaggvlg"
assert chiffrementVigenere("chiffrement","clef") == "esmkhcirgyx"
print("chiffrementVigenere : OK")
except:
print("chiffrementVigenere : ERREUR")
Partant du message chiffré et connaissant la clef de chiffrement, il est possible de déchiffrer le message en opérant le décalage inverse.
Question 2 (déchiffrement) : Définir une fonction
dechiffrementVigenere(msgChiffre, clef, alphabet)qui étant donné un message chiffrémsgChiffre, la clef qui a servi à construire ce message chiffréclefet un alphabetalphabet(par défaut, l'alphabet français) renvoie le message en clair correspondant.
def dechiffrementVigenere(msgChiffre, clef, alphabet="abcdefghijklmnopqrstuvwxyz"):
return "TODO"
try:
assert dechiffrementVigenere("esmkhcirgyx","clef") == "chiffrement"
assert dechiffrementVigenere("ozaggvlg","truc") == "vigenere"
print("dechiffrementVigenere : OK")
except:
print("dechiffrementVigenere : ERREUR")
----------- Début de la partie optionnelle ---------------
Attention, cette partie n'est à faire que si le reste du TP (dont Chiffrement de Hill en partie 2) est terminé.
Une attaque directe par analyse de fréquence sur l'ensemble du chiffré ne sera pas efficace sur un message chiffré avec l'algorithme de Vigenère car une même lettre du clair peut-être chiffrée par des lettres différentes et une même lettre du chiffré peut représenter des lettres du clair distinctes.
Mais, si l'on connait le nombre de lettres $l$ que comporte la clef, il devient possible d'effectuer des analyses de fréquences efficaces sur chacun des sous-messages chiffrés déterminés en prenant les lettres du message clair espacées de $l$. Il y a donc $l$ sous-messages chiffrés à cryptanalyser.
L'attaque pour décrypter un message codé avec Vigenère consiste donc tout d'abord à déterminer la taille de la clef et à ensuite effectuer une attaque similaire à celle du chiffrement par décalage (analyse de fréquence) sur chaque sous message chiffré.
Exemple : Si le chiffré est :"dbsndqufgdi" et que la clef est de longueur $3$. Il faudra faire 3 analyses de fréquences (il s'agit d'un exemple totalement fictif, le message est trop court pour pouvoir faire une analyse de fréquence, encore moins 3...) :
Le test de Kasiski est une méthode pour déterminer la longueur de la clef. Il repose sur le fait que si plusieurs groupes de lettres sont égaux dans le chiffré, ils correspondent certainement au même groupe de lettre dans le clair chiffré avec la même partie de la clef. La taille de l'intervalle séparant les motifs identiques sera donc probablement un multiple de la taille de la clef. S'il y a plusieurs répétitions de motifs, le plus grand diviseur commun de ces longeurs d'intervalle est possiblement la taille de la clef.
Question 3 (Test de Kasiski) : Définir une fonction
testKasiski(msgChiffre)qui étant donné un message chiffrémsgChiffrerenvoie la taille de clef la plus probable.
def testKasiski(msgChiffre):
return "TODO"
c = "zbpuevpuqsdlzgllksousvpasfpddggaqwptdgptzweemqzrdjtddefekeferdprrcyndgluaowcnbptzzzrbvpssfpashpncotemhaeqrferdlrlwwertlussfikgoeuswotfdgqsyasrlnrzppdhtticfrciwurhcezrpmhtpuwiyenamrdbzyzwelzucamrptzqseqcfgdrfrhrpatsepzgfnaffisbpvdblisrplzgnemswaqoxpdseehbeeksdptdttqsdddgxurwnidbdddplncsd"
try:
assert testKasiski(c) == 4
print("testKasiski : OK")
except:
print("testKasiski : ERREUR")
Question 4 (attaque par analyse de fréquence avec longueur de clef connue) : Définir une fonction
attaqueFrequenceVig(msgChiffre, l, frequenceLangue, alphabet)qui décrypte le message en paramètre en effectuant des analyses de fréquences connaissant la longueurlde la clef ayant servie à chiffrer le message.frequenceLangueest un dictionnaire des fréquences dans la langue du message (le dictionnaire des fréquences de chaque lettre en françaisfrequenceFrancaisvous est fourni).
Note : n'hésitez pas à utiliser des fonctions écrites dans le TP précédent.
frequenceFrancais = {'a': 8.15, 'b': 0.97, 'c': 3.15, 'd': 3.73, 'e': 17.39,
'f': 1.12, 'g': 0.97, 'h': 0.85, 'i': 7.31, 'j': 0.45,
'k': 0.02, 'l': 5.69, 'm': 2.87, 'n': 7.12, 'o': 5.28,
'p': 2.80, 'q': 1.21, 'r': 6.64, 's': 8.14, 't': 7.22,
'u': 6.38, 'v': 1.64, 'w': 0.03, 'x': 0.41, 'y': 0.28,
'z': 0.15}
def attaqueFrequenceVig(msgChiffre, l, frequenceLangue = frequenceFrancais, alphabet="abcdefghijklmnopqrstuvwxyz"):
return "TODO"
c = "zbpuevpuqsdlzgllksousvpasfpddggaqwptdgptzweemqzrdjtddefekeferdprrcyndgluaowcnbptzzzrbvpssfpashpncotemhaeqrferdlrlwwertlussfikgoeuswotfdgqsyasrlnrzppdhtticfrciwurhcezrpmhtpuwiyenamrdbzyzwelzucamrptzqseqcfgdrfrhrpatsepzgfnaffisbpvdblisrplzgnemswaqoxpdseehbeeksdptdttqsdddgxurwnidbdddplncsd"
try:
assert attaqueFrequenceVig(c,4) == "aneufheureslasalledutheatredesvarietesetaitencorevidequelquespersonnesaubalconetalorchestreattendaientperduesparmilesfauteuilsdeveloursgrenatdanslepetitjourdulustreademifeuxuneombrenoyaitlagrandetacherougedurideauetpasunbruitnevenaitdelascenelarampeeteintelespupitresdesmusiciensdebandes"
print("attaqueFrequenceVig : OK")
except:
print("attaqueFrequenceVig : ERREUR")
----------- Fin de la partie optionnelle -----------
Le chiffrement de Hill est un type de chiffrement par substitution polyalphabétique où les lettres du clair sont chiffrées et déchiffrées par paquets et non les unes à la suite des autres. Ce chiffrement est donc mieux protégé contre les attaques par analyse de fréquence.
Pour chiffrer, on commence par choisir une matrice carrée inversible (nous verrons plus tard comment vérifier qu'une matrice est inversible dans $\mathbb{Z}/26\mathbb{Z}$) de taille $p \times p$. Cette matrice constitue la clef de chiffrement. Ensuite, le message en clair est divisé en blocs/vecteurs de longueur $p$. Le dernier bloc est éventuellement complété avec une lettre choisie arbitrairement si sa longueur est différente de $p$. Chaque vecteur est chiffré en le multipliant avec la matrice carré. Evidemment, pour effectuer la multiplication matricielle, les lettres des messages sont converties en nombre entre 0 et 25.
La fonction de chiffrement correspondante pour un bloc de $p$ lettres est :
\begin{align*} E \colon (\mathbb{Z}/26\mathbb{Z})^p &\to (\mathbb{Z}/26\mathbb{Z})^p\\ \begin{pmatrix} m_i\\ m_{i+1}\\ ... \\ m_{i+p-1} \\ \end{pmatrix} & \mapsto \begin{pmatrix} c_i\\ c_{i+1}\\ ... \\ c_{i+p-1} \\ \end{pmatrix} = K \times \begin{pmatrix} m_i\\ m_{i+1}\\ ... \\ m_{i+p-1} \\ \end{pmatrix} \end{align*}où $K$ est une matrice carrée inversible de taille $p \times p$.
Par exemple, Chiffrons le message "TEXTE" avec une matrice $K \in \mathcal{M_{2,2}}$ : $\begin{pmatrix} 3 & 5\\ 6 & 17\\ \end{pmatrix}$.
Nous commençons par faire des blocs de 2 lettres : "TE","XT","EW" (ici, on rajoute un W en fin de message pour avoir un dernier bloc de deux lettres car le message initial n'a pas un nombre pair de lettres).
"TE" correspond au couple de valeurs (19,4).
$ \begin{pmatrix} 3 & 5\\ 6 & 17\\ \end{pmatrix} \times \begin{pmatrix} 19\\ 4\\ \end{pmatrix} = \begin{pmatrix} 77\\ 182\\ \end{pmatrix} $
Il faut ensuite convertir le résultat $\begin{pmatrix} 77\\ 182\\ \end{pmatrix}$ en nombre de $\mathbb{Z}/26\mathbb{Z}$ :$\begin{pmatrix} 25\\ 0\\ \end{pmatrix}$ puis en lettre : $\begin{pmatrix} Z\\ A\\ \end{pmatrix}.$ "TE" sera donc chiffré "ZA". En recommançant le processus pour les autres couples de lettres, le clair "TEXTE" devient le chiffré "ZAITSI".
Question 5 (chiffrement) : Définir une fonction
chiffrementHill(msgClair, clef, lettreRemplacement, alphabet)qui étant donné un message en clairmsgClair, une clef de chiffrementclefsous forme de matrice carré $p \times p$, une lettre de "padding" (par défaut "w") s'il n'est pas possible de diviser le message clair en blocs de taille p et un alphabetalphabet(par défaut, l'alphabet français), renvoie le message chiffré correspondant.
def chiffrementHill(msgClair, clef, lettrePadding = 'w', alphabet = "abcdefghijklmnopqrstuvwxyz") :
return "TODO"
try:
assert chiffrementHill("texte",np.array([[3,5],[6,17]])) == "zaitsi"
assert chiffrementHill("chiffredehill",np.array([[1,3,1],[1,1,0],[2,9,3]])) == "fjnlkcrhvqppvha"
print("chiffrementHill : OK")
except:
print("chiffrementHill : ERREUR")
Partant du message chiffré $c$ et connaissant la matrice de chiffrement de taille $p \times p $, il est possible de déchiffrer le message pour obtenir le clair $m$.
Il s'agit de diviser le message chiffré en vecteurs de $p$ lettres et de multiplier ces vecteurs par l'inverse de la matrice de chiffrement.
La fonction de déchiffrement d'un bloc de $p$ lettres est ainsi :
\begin{align*} D \colon (\mathbb{Z}/26\mathbb{Z})^p &\to (\mathbb{Z}/26\mathbb{Z})^p\\ \begin{pmatrix} c_i\\ c_{i+1}\\ ... \\ c_{i+p-1} \\ \end{pmatrix} & \mapsto \begin{pmatrix} m_i\\ m_{i+1}\\ ... \\ m_{i+p-1} \\ \end{pmatrix} = K^{-1} \times \begin{pmatrix} c_i\\ c_{i+1}\\ ... \\ c_{i+p-1} \\ \end{pmatrix} \end{align*}où $ K^{-1}$ est l'inverse de la matrice de chiffrement K dans $\mathbb{Z}/26\mathbb{Z}$.
Pour déchiffrer le message, nous avons donc besoin d'inverser la matrice K dans $\mathbb{Z}/26\mathbb{Z}$.
La matrice K est inversible dans $\mathbb{Z}/n\mathbb{Z}$ si son déterminant est inversible dans $\mathbb{Z}/n\mathbb{Z}$.
Question 6 : Faire une fonction
estInversibleMat(k, n)qui renvoieTruesi la matrice carrée $k$ est inversible sur $\mathbb{Z}/n\mathbb{Z}$ etFalsesinon.
def estInversibleMat(k,n):
"""
k est une matrice carree
"""
return "TODO"
try:
assert estInversibleMat(np.array([[3,5],[6,17]]),26) == True
assert estInversibleMat(np.array([[1,3,1],[1,1,0],[2,9,3]]),26) == True
assert estInversibleMat(np.array([[1,2],[3,4]]),26) == False
print("estInversibleMat : OK")
except:
print("estInversibleMat : ERREUR")
Pour inverser K, il faut multiplier la transposée de la comatrice de K par un inverse modulaire de son déterminant.
Question 7 : A partir de la fonction
comatricefournie, faire une fonctioninverseMat(k, n)qui teste si k est inversible. Si oui, renvoie la matrice inverse de k dans $\mathbb{Z}/n\mathbb{Z}$ et sinon, renvoie -1. N'hésitez pas à réutiliser des fonctions du TP précédent.
def comatrice(mat):
det = np.linalg.det(mat)
if(det!=0):
return np.linalg.inv(mat).T * det
else:
return "Matrice non inversible"
print("Matrice des cofacteurs/Comatrice :\n", comatrice([[1, 2], [3, 4]]))
def inverseMat(k,n):
return "TODO"
try:
assert (inverseMat([[9,4],[5,7]],26) == np.array([[ 5, 12],[15, 25]])).all
assert (inverseMat([[3,7],[5,8]],26) == np.array([[ 4, 3],[17, 21]])).all
assert (inverseMat(np.array([[1,3,1],[1,1,0],[2,9,3]]),26) == np.array([[ 3,0,25],[23,1,1],[ 7,23,24]])).all
print("inverseMat : OK")
except:
print("inverseMat : ERREUR")
Question 8 (déchiffrement) : Définir une fonction
dechiffrementHill(msgChiffre, clef, alphabet)qui étant donné un message chiffrémsgChiffre, la matrice de chiffrementclefqui a servi à construire ce message chiffré et un alphabetalphabet(par défaut, l'alphabet français) renvoie le message en clair correspondant.
def dechiffrementHill(msgChiffre, clef, alphabet = "abcdefghijklmnopqrstuvwxyz"):
return "TODO"
try:
assert dechiffrementHill("zaitsi",np.array([[3,5],[6,17]])) == "textew"
assert dechiffrementHill("fjnlkcrhvqppvha",np.array([[1,3,1],[1,1,0],[2,9,3]])) == "chiffredehillww"
print("dechiffrementHill : OK")
except:
print("dechiffrementHill : ERREUR")