In [ ]:
import numpy as np

TP1 - Chiffrement par substitution monoalphabétique

2022/2023 - L. Naert, A. Ridard, T. Godin

Le chiffrement par substitution monoalphabétique consiste à remplacer chaque symbole d'un message en clair par un autre symbole (généralement du même alphabet) pour constituer le message chiffré.

Dans ce TP, nous étudierons 2 types de chiffrement par substitution monoalphabétique : le chiffrement par décalage et le chiffrement affine.

Pour chaque type de chiffrement, nous développerons des fonctions pour:

  1. chiffrer un message en clair à l'aide d'une clef
  2. déchiffrer un message (en connaissant la clef)
  3. décrypter un message (ne connaissant pas la clef) en faisant appel à l'analyse de fréquence

Par convention, nous appelerons :

  • $k$ : la clef
  • $E_k$ : la fonction de chiffrement
  • $D_k$ : la fonction de déchiffrement
  • $m$ : le message en clair
  • $m_i$ : la lettre de rang $i$ sur message en clair
  • $c$ : le message chiffré
  • $c_i$ : la lettre de rang $i$ sur message en clair

1 - Chiffrement par décalage, dit "chiffrement de César"

César, pour assurer la confidentialité de sa correspondance, avaient l'habitude de remplacer chaque lettre de ses messages par la lettre qui était située 3 rangs après dans l'alphabet ('a' devenait ainsi 'd', 'b' devenait 'e', etc.).

Il s'agit d'un cas particulier de chiffrement par décalage qui consiste à décaler, dans un sens ou dans l'autre, les lettres de l'alphabet d'un nombre constant de position. Ce nombre constitue la clef du chiffrement par décalage.

Il s'agit évidemment d'un décalage circulaire : 'z' décalé de 3 positions devient ainsi 'c'. Plus généralement, cela revient à travailler dans l'ensemble $\mathbb{Z}/26\mathbb{Z}$ en considérant chaque lettre comme un entier entre $0$ (pour 'a') et $25$ (pour 'z').

Ainsi, en appelant $k$ la clef de décalage, la fonction $E_k$ de chiffrement d'une lettre est :

\begin{align*} E_k \colon \mathbb{Z}/26\mathbb{Z} &\to \mathbb{Z}/26\mathbb{Z}\\ m_i &\mapsto c_i = m_i + k \end{align*}
In [ ]:
# Quelques fonctions utiles (ou pas)
def lettreToEntier(lettre, alphabet = "abcdefghijklmnopqrstuvwxyz"):
    return alphabet.find(lettre)
def entierToLettre(a, alphabet = "abcdefghijklmnopqrstuvwxyz"):
    return alphabet[a]

print("Lettre -> entier : w ->", lettreToEntier('w'))
print("Entier -> Lettre : 22 ->", entierToLettre(22))

1 - a) Chiffrement/Déchiffrement

Question 1 (chiffrement) : Définir une fonction chiffrementDecalage(msgClair, clef, alphabet) qui étant donné un message en clair msgClair, un certain décalage clef et un alphabet alphabet (par défaut, l'alphabet français) renvoie le message chiffré correspondant.

In [ ]:
def chiffrementDecalage(msgClair, clef, alphabet="abcdefghijklmnopqrstuvwxyz"):
    return "TO DO"

try:
    assert chiffrementDecalage("messageenclair",3) == "phvvdjhhqfodlu"
    assert chiffrementDecalage("venividivici",-3) == "sbkfsfafsfzf"
    print("chiffrementDecalage : OK")
except:
    print("chiffrementDecalage : ERREUR")

Partant du message chiffré et connaissant la clef de chiffrement (la valeur du décalage), il est aisé de déchiffrer le message en opérant le décalage inverse. Ainsi :

\begin{align*} D_k \colon \mathbb{Z}/26\mathbb{Z} &\to \mathbb{Z}/26\mathbb{Z}\\ c_i &\mapsto m_i = c_i - k \end{align*}

Question 2 (déchiffrement) : Définir une fonction dechiffrementDecalage(msgChiffre, clef, alphabet) qui étant donné un message chiffré msgChiffre, la clef qui a servi à construire ce message chiffré clef et un alphabet alphabet (par défaut, l'alphabet français) renvoie le message en clair correspondant.

In [ ]:
def dechiffrementDecalage(msgChiffre, clef, alphabet="abcdefghijklmnopqrstuvwxyz"):
    return "TO DO"

try:
    assert dechiffrementDecalage("phvvdjhhqfodlu",3) == "messageenclair"
    assert dechiffrementDecalage("sbkfsfafsfzf",-3) == "venividivici"
    print("dechiffrementDecalage : OK")
except:
    print("dechiffrementDecalage : ERREUR")

1 - b) Attaques : Force brute et analyse de fréquence

Mais que faire si nous tombons sur un message chiffré par décalage mais que nous ne connaissons pas la clef ?

La grande faille du chiffrement par décalage est le faible nombre de clefs possibles : $26$ en français (et même $25$ car un décalage de 0 n'en est pas un). Une attaque par force brute, en testant toutes les clefs possibles est donc très efficace sur ce genre de chiffrement

Question 3 (attaque par force brute) : Définir une fonction attaqueForceBruteDec(msgChiffre, alphabet) qui étant donné un message chiffré msgChiffre, et un alphabet alphabet (par défaut, l'alphabet français) affiche tous les messages en clair possibles avec la clef correspondante.

In [ ]:
def attaqueForceBruteDec(msgChiffre, alphabet="abcdefghijklmnopqrstuvwxyz"):
    return "TO DO"

attaqueForceBruteDec("phvvdjhhqfodlu")

Même si l'attaque par force brute fonctionne très bien dans le cas du chiffrement par décalage du fait du très petit nombre de clefs disponibles, l'attaque la plus courante dans le cas des chiffrements par substitution monoalphabétique est l'analyse de fréquence. Connaissant la langue dans laquelle a été écrit le message en clair initial et la fréquence d'apparition de chaque lettre dans cette langue, il est possible de retrouver, en calculant la fréquence de chaque lettre dans le message chiffré, la correspondance entre les lettres du message chiffré et celles du message en clair.

En fait, dans le cas d'un chiffrement par décalage, la connaissance de la correspondance entre une unique lettre du chiffré et une lettre de l'alphabet d'origine suffit à calculer le pas de décalage (la clef) et donc à décrypter le message.

Il s'agit en effet de trouver la valeur de $k$ dans l'équation : $x_c - k = x_m \mod 26$ avec $x_c$ la lettre du message chiffré correspondant à la lettre $x_m$ de l'alphabet d'origine.

L'analyse de fréquence nous permet de tester directement des candidats pertinents pour $x_m$ et $x_c$. En effet, il est probable pour que la lettre la plus fréquente dans le message chiffré serve à coder la lettre la plus fréquente dans la langue étudiée. Par exemple, en français, la lettre la plus utilisée est le "e". Si, dans le message chiffré, la lettre la plus utilisée est le "v", il y a de grandes chances pour que "v" serve à coder "e". Cette méthode sera d'autant plus efficace que le message à déchiffrer est long.

Question 3 (attaque par analyse de fréquence) :

  • Définir une fonction frequenceLettre(lettre, txt) qui calcule la fréquence en pourcentages du caractère lettre dans la chaine de caractere txt.
  • Définir une fonction frequenceTouteLettre(txt, alphabet) qui calcule la fréquence en pourcentages de chaque lettre de alphabet dans txt. Cette fonction renvoie un dictionnaire ayant pour clef chaque lettre et pour valeur la fréquence correspondante.
  • Définir une fonction triFreq(freqs) qui, étant donné un dictionnaire de fréquence freqs, les éléments triées par fréquence décroissante.
  • Définir une fonction getNiemelettre(freqs, n) qui renvoie la n-ième lettre la plus fréquente (par exemple, si n = 1, la fonction renverra la lettre la plus frequente) d'après freqs.
  • Définir une fonction calculeDecalage(lettre1, lettre2, alphabet) qui renvoie la valeur du décalage entre les deux lettres en paramètre étant donné un alphabet. Ce décalage sera exprimé dans $\mathbb{Z}/n\mathbb{Z}$ avec $n$ la longueur de l'alphabet considéré.
  • Définir une fonction attaqueFrequenceDec (msgChiffre, frequenceLangue, alphabet) qui utilise les fonctions précédentes pour décrypter le message en paramètre en comparant la lettre la plus fréquente dans le message chiffré et dans la langue considérée. frequenceLangue est un dictionnaire des fréquences dans la langue du message (le dictionnaire des fréquences de chaque lettre en français frequenceFrancais vous est fourni).

Note : si le message n'est pas assez long ou pas assez représentatif de la langue considéré, une analyse de fréquence ne se basant que sur la lettre la plus fréquente risque de ne pas aboutir. Il peut dans ce cas être interessant de tester plusieurs possibilités (par exemple en calculant le décalage entre la deuxième lettre la plus fréquente dans le chiffré et la lettre la plus fréquente du français).

In [ ]:
def frequenceLettre(lettre, txt):
    return "TODO"

chiffre ="abhffbzzrfpbzzrqrfanvafnffvffheqrfrcnhyrfqrtrnagffvabhfiblbafcyhfqrpubfrfrgcyhfrybvtarrfdhrhkprarfgcnfnpnhfrqryncrefcvpnpvgrqrabgerihravqrabgertenaqrheprfgcneprdhrabhffbzzrfryrirfcnerhk"

try:
    assert round(frequenceLettre('f',chiffre),2) == 15.68
    assert round(frequenceLettre('a',chiffre),2) == 7.03
    print("frequenceLettre : OK")
except:
    print("frequenceLettre : ERREUR")
In [ ]:
def frequenceTouteLettre(txt, alphabet="abcdefghijklmnopqrstuvwxyz"):
    return "TODO"

print("Frequence de chaque lettre dans le chiffre : ", frequenceTouteLettre(chiffre))
In [ ]:
def triFreq(freqs):
    return "TODO"

def getNiemeLettre(freqs, n):
    return "TODO"


# Frequence des lettres en français
# Source : https://www.apprendre-en-ligne.net/crypto/stat/francais.html
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}
print(triFreq(frequenceFrancais))
print(getNiemeLettre(frequenceFrancais,15))
try:
    assert getNiemeLettre(frequenceTouteLettre(chiffre),1) == 'r'
    assert getNiemeLettre(frequenceFrancais,1) == 'e'
    assert getNiemeLettre(frequenceFrancais,2) == 'a'
    assert getNiemeLettre(frequenceFrancais,3) == 's'
    print("getNiemeLettre : OK")
except:
    print("getNiemeLettre : ERREUR")
In [ ]:
def calculDecalage(lettre1, lettre2, alphabet="abcdefghijklmnopqrstuvwxyz"):
    return "TODO"

try:
    assert calculDecalage('a','d') == 3
    assert calculDecalage('d','a') == 23
    assert calculDecalage('z','c') == 3
    assert calculDecalage('r','a') == 9
    print("calculDecalage : OK")
except:
    print("calculDecalage : ERREUR")
In [ ]:
def attaqueFrequenceDec(msgChiffre, frequenceLangue = frequenceFrancais, alphabet="abcdefghijklmnopqrstuvwxyz"):
    return "TODO"

print(attaqueFrequenceDec(chiffre))
#chiffre2="vcfgrwqwoizcuwgtowbsobhgoizcuwgsghqseisqsghoixcifrviwxcifrstshsqcaasbhsghqseisjcigbsgojsndogeishobhrsgofhwgobgjcigbsrsjsndogjcigacbhfsfibxcifcijfwsfgobgojcwfzsgwbgwubsgrsjcgdfctsggwcbgdofzshcweiszsghhcbashwsf"
#print(attaqueFrequenceDec(chiffre2))

2 - Chiffrement Affine

Le chiffrement affine est un autre type de chiffrement par substitution monoalphabétique. Ici, la clef de chiffrement $k$ est composée d'un couple d'entiers $(a,b)$ avec $a \in (\mathbb{Z}/n\mathbb{Z})^*$ (l'ensemble des éléments inversibles de $\mathbb{Z}/n\mathbb{Z}$) et $b \in \mathbb{Z}/n\mathbb{Z}$

La fonction de chiffrement correspondante est :

\begin{align*} E_k \colon \mathbb{Z}/26\mathbb{Z} &\to \mathbb{Z}/26\mathbb{Z}\\ m_i & \mapsto c_i = am_i + b \end{align*}

Ainsi, si k = (3,4), la lettre codée 6 (donc 'g') sera chiffrée avec la lettre codée $(3*6+4)\mod 26 = 22$ (donc 'w').

2 - a) Chiffrement/Déchiffrement

Question 4 (chiffrement) : Définir une fonction chiffrementAffine(msgClair, a, b, alphabet) qui étant donné un message en clair msgClair, une clef de chiffrement clef$=[a,b]$ et un alphabet alphabet (par défaut, l'alphabet français) renvoie le message chiffré correspondant.

In [ ]:
def chiffrementAffine(msgClair, clef, alphabet = "abcdefghijklmnopqrstuvwxyz") :
    return "TODO"

try:
    assert chiffrementAffine("messageenclair",[3,4]) == "oqggewqqrklecd"
    assert chiffrementAffine("messageenclair",[23,6]) == "wueegouutazgih"
    print("chiffrementAffine : OK")
except:
    print("chiffrementAffine : ERREUR")

Partant du message chiffré et connaissant la clef de chiffrement (les valeurs de a et b), il est possible de déchiffrer le message.

La fonction de déchiffrement peut s'écrire :

\begin{align*} D_k \colon \mathbb{Z}/26\mathbb{Z} &\to \mathbb{Z}/26\mathbb{Z}\\ c_i &\mapsto m_i = \alpha c_i + \beta \end{align*}

avec $\alpha = a^{-1}$ et $\beta = (-a^{-1}b) \mod n$

où $a^{-1}$ désigne l'inverse modulaire de $a$

Avant de faire la fonction permettant de déchiffrer un message chiffré connaissant sa clef, il est donc nécessaire de faire une parenthèse plus mathématique sur les inverses modulaires !

Inversibilité dans $\mathbb{Z}/n\mathbb{Z}$

S'il existe un entier $b$ de $\mathbb{Z}/n\mathbb{Z}$ tel que $a*b \mod n = 1$ alors b est appelé inverse de a dans $\mathbb{Z}/n\mathbb{Z}$ et est noté $a^{-1}$.

$a$ est inversible dans $\mathbb{Z}/n\mathbb{Z}$ ssi $a$ et $n$ sont premiers entre eux, c'est à dire qu'ils n'ont aucun diviseur commun (i.e. $pgcd(a,n) = 1$).

Question 5 :

  • Faire une fonction estInversible(a, n) qui renvoie True si $a$ est inversible sur $\mathbb{Z}/n\mathbb{Z}$ et Falsesinon.
  • Faire une fonction listeInversibles(n) qui renvoie la liste de tous les éléments inversibles de $\mathbb{Z}/n\mathbb{Z}$
In [ ]:
def estInversible(a,n):
    return "TODO"


try:
    assert estInversible(0,180) == False
    assert estInversible(1,180) == True
    assert estInversible(4,180) == False
    assert estInversible(5,180) == False
    assert estInversible(179,180) == True
    assert estInversible(11,180) == True
    assert estInversible(131,180) == True
    assert estInversible(13,26) == False
    assert estInversible(4,26) == False
    assert estInversible(5,26) == True
    print("estInversible : OK")
except:
    print("estInversible : ERREUR")
In [ ]:
def listeInversibles(n):
    return "TODO"

try:
    assert listeInversibles(26) == [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
    assert listeInversibles(5) == [1, 2, 3, 4]
    assert listeInversibles(6) == [1, 5]
    print("listeInversibles : OK")
except:
    print("listeInversibles : ERREUR")

Maintenant que nous savons si un nombre est inversible dans $\mathbb{Z}/n\mathbb{Z}$, il nous faut pouvoir calculer son inverse. Une méthode consiste à trouver les coefficients de Bezout entre $a$ et $n$.

De manière générale, les coefficients de Bezout de $a$ et $b$ sont les entiers relatifs $s$ et $t$ tels que $sa + tb = pgcd(a,b) $

Si $a$ est inversible, il s'agit donc de trouver les entiers relatifs $s$ et $t$ tels que $sa + tn = 1 $ car a et n sont premiers entre eux (donc $pgcd(a,n) = 1$)

Comme $tn = 0$ dans $\mathbb{Z}/n\mathbb{Z}$ ($tn$ est un multiple de n), on a $sa=1$ donc $a^{-1} = s\mod n$ (définition de l'inverse).

Question 6 : A partie de la fonction coeffBezout(a, b) qui renvoie les valeurs de $pgcd(a,b)$, $s$ et $t$ dans une liste, faire une fonction inverse(a, n) qui teste si $a$ est inversible et, si oui, renvoie sont inverse. Sinon, renvoie -1.

In [ ]:
# sources : cette [vidéo](https://www.youtube.com/watch?v=7o79t2KAKxE&list=PLE8WtfrsTAinMMyQkK_CzXhXU_LHRNXy_&index=3) 
# et [celle-ci](https://www.youtube.com/watch?v=BkK1_FspgYQ).
def coeffBezout(a, b) :
    l1 = np.array([a, 1, 0])
    l2 = np.array([b, 0, 1])
    
    while( l2[0] != 0):
        mult = l1[0]//l2[0]
        ltmp = l2
        l2 = l1 - mult*l2
        l1 = ltmp
    if(l1[0]<0):
        l1 = -l1
        
    return l1.tolist()

try:
    assert coeffBezout(180, 11) == [1, 3,-49]
    assert coeffBezout(23,26) == [1, -9, 8]
    assert coeffBezout(26, 3) == [1, -1, 9]
    print("coeffBezout : OK")
except:
    print("coeffBezout : ERREUR")
In [ ]:
def inverse(a, n) :
    return "TODO"
try:
    assert inverse(11, 180) == 131
    assert inverse(3, 26) == 9
    assert inverse(23, 26) == 17
    print("inverse : OK")
except:
    print("inverse : ERREUR")

Nous avons maintenant toutes les cartes en main pour définir la fonction de déchiffrement affine. Pour rappel :

\begin{align*} D_k \colon \mathbb{Z}/26\mathbb{Z} &\to \mathbb{Z}/26\mathbb{Z}\\ c_i &\mapsto m_i = \alpha c_i + \beta \end{align*}

avec $\alpha = a^{-1}$ et $\beta = (-a^{-1}b) \mod n$

où $a^{-1}$ désigne l'inverse modulaire de $a$.

Question 7 (déchiffrement) : Définir une fonction dechiffrementAffine(msgChiffre, clef, alphabet) qui étant donné un message chiffré msgChiffre, la clef qui a servi à construire ce message chiffré composée de a et b et un alphabet alphabet (par défaut, l'alphabet français) renvoie le message en clair correspondant.

In [ ]:
def dechiffrementAffine(msgChiffre, clef, alphabet = "abcdefghijklmnopqrstuvwxyz"):
    return "TODO"

try:
    assert dechiffrementAffine("oqggewqqrklecd",[3, 4]) == "messageenclair"
    assert dechiffrementAffine("wueegouutazgih",[23,6]) == "messageenclair"
    print("dechiffrementAffine : OK")
except:
    print("dechiffrementAffine : ERREUR")

2 - b) Attaque : Analyse de fréquence

Nous allons maintenant coder une attaque par analyse de fréquence dans le cas du chiffrement affine. Dans le chiffrement par décalage, il n'y avait qu'une seule inconnue : le pas de décalage $k$. Dans le chiffrement affine, il s'agit de trouver les valeurs de $a$ et $b$, ou plus exactement, de $\alpha$ et $\beta$. Il nous faut donc résoudre deux équations à deux inconnues :

$$ \left\{ \begin{array}{ll} x_c\alpha + \beta & = x_m \mod 26 \\ y_c\alpha + \beta & = y_m \mod 26 \\ \end{array} \right. $$

où $x_c$ (resp. $y_c$) désigne la lettre qui code $x_m$ (resp. $y_m$) dans le message chiffré.

Note : L'attaque par force brute est toujours très faisable. Il n'y aurait que $Card((\mathbb{Z}/n\mathbb{Z})^*)*Card(\mathbb{Z}/n\mathbb{Z}) = 12 * 26 = 312$ clefs à tester.

Question 8 (attaque par analyse de fréquence) : Résolution de deux équations à deux inconnues.

  • Faire une fonction resEquations(xc,xm,yc,ym,alphabet) qui renvoie les valeurs de $\alpha$ et $\beta$ par résolution du système d'équation donné ci-dessus.
  • Faire une fonction attaqueFrequenceAff(msgCrypte, frequenceLangue, alphabet) qui utilise les fonctions précédentes pour décrypter le message en paramètre en comparant les lettres les plus fréquentes dans le message chiffré et dans la langue considérée. frequenceLangue est un dictionnaire des fréquences dans la langue du message (le dictionnaire des fréquences de chaque lettre en français frequenceFrancais vous est fourni plus haut). Il faudra certainement tester plusieurs possibilités...
In [ ]:
"""
resolution des equations
xc * alpha + beta = xm mod 26
yc * alpha + beta = ym mod 26
"""
def resEquations(xc,xm,yc,ym, alphabet = "abcdefghijklmnopqrstuvwxyz"):
    return "TODO"

try:
    assert resEquations('a','d','d','e') == (9,3)
    assert resEquations('t','e','m','t') == (9,15)
    assert resEquations('t','e','m','a') == (8,8)
    assert resEquations('r','e','f','a') == (9,7)
    print("resEquations : OK")
except:
    print("resEquations : ERREUR")
In [ ]:
def attaqueFrequenceAff(msgCrypte, frequenceLangue = frequenceFrancais, alphabet = "abcdefghijklmnopqrstuvwxyz"):
    return "TODO"

#Passer de alpha/beta à a/b
#n = len(alphabet)
#a = inverse(alpha,n)
#b = (-beta*a)%26
#print("a, b",a,b)




c1 = "svnhfmmvshpfdskrsfsklvorensrfkkfbnryfefsfmzhroruerbnrslrofshmrlfhonladuuerprskfuudsrfkkrskdvsdmufnkmfdhhrnsyrnorgrnmfyerpdrermrkkeronladuuersrlveerhyvsoyfhuvelrprskfmfyerpdrermrkkeronuefslfdhdorpyvnemfornwdrpr"
print(attaqueFrequenceAff(c1))

print("\nUn peu plus complique...")
c2 = "ntjmpumgxpqtstgqpgtxpnchumtputgfsftgthnngxnchumwxootrtumhpyctgktjqtjchfooxujqhgztumxpotjxotfoqtohrxumhzutwftgtopfmntjmpuatmfmshodpfrxpjjtqtghbxuj"
print(attaqueFrequenceAff(c2))