# Activité 5 - Codage d'un message par substitution¶

## Présentation de l'activité¶

- Références au programme :
  - spécialité mathématiques de première générale : Fréquence d’apparition des lettres d’un texte donné, en français, en anglais.
  - spécialité mathématiques de première générale : Calcul de factorielle.
- Description : activité présentant une méthode de déchiffrement de messages chiffrés par substitution.

##### Situation¶

Le chiffrement par substitution simple (ou alphabet désordonné) consiste à remplacer dans un message chacune des lettres de l'alphabet par une autre.

Par exemple, si la lettre m est remplacée par t et la lettre i est remplacée par la lettre o alors le mot mimi est remplacé par toto.

La substitution est définie par une permutation des lettres de l'alphabet. Nous nous intéressons ici au décodage des messages chiffrés par substitution. Nous nous limiterons aux messages écrits en français sans accent, sans majuscule, sans espace et sans ponctuation. L'alphabet utilisé comporte donc 26 lettres minuscules.

## Nombre de chiffrements par substitution¶

Chaque permutation des 26 lettres fournit une possibilité de chiffrement. Pour décoder un message chiffré par substitution, on pourrait lister toutes les permutations possibles.

Le nombre de permutations est égal à $26\times25\times24\times...\times1=26!$.

La fonction suivante permet le calcul de la factorielle d'un entier naturel $n$. Elle prend en paramètre un entier naturel $n$ et renvoie $n!$.

In [1]:

    def factorielle(n):
        fact=1
        for i in range(1,n+1):
            fact=fact*i
        return fact
    print(factorielle(26))

    403291461126605635584000000

Suggestions pédagogiques

- Mathématiques débranchées

  Dans le cas où on ne présente pas un alphabet comme une permutation de l'ensemble $\lbrace a, b, \dots, y, z\rbrace$ , demander aux élèves de calculer directement le nombre de chiffrements possibles.

- Expliquer un programme

  Que fait la ligne 3 ?

- Compléter un programme

  Le programme précédent étant fourni en remplaçant les lignes 2 et 4 par `fact = ...` (dans ces deux lignes), demander aux élèves de compléter les lignes 2 et 4.

- Tester la fonction `factorielle` pour donner le nombre de permutations possibles pour un alphabet de 26 lettres. Conclure sur la faisabilité de la méthode de déchiffrement basée sur l'examen de tous les chiffrements possibles.

## Utilisation de la fréquence d'apparition des lettres¶

Pour déchiffrer un message codé par substitution, il est plus efficace d'utiliser l'analyse fréquentielle. Celle-ci utilise le fait que, dans une langue donnée, la fréquence d'apparition d'une lettre donnée varie peu d'un texte à l'autre.

### Détermination de la fréquence d'une lettre dans un texte¶

La fonction `frequenceLettre` prend en paramètres une lettre et un texte (chaines de caractères) en paramètres et renvoie la fréquence d'apparition de la lettre dans le texte.

On la teste ici pour un texte de 206 caractères extrait de Cyrano de Bergerac (sans majuscule, accent, espace ou ponctuation) et la lettre a.

In [2]:

    texte="ahnoncestunpeucourtjeunehommeonpouvaitdireohdieubiendeschosesensommeenvariantletonparexempletenezagressifmoimonsieursijavaisuntelnezilfaudraitsurlechampquejemelamputasseamicalmaisildoittremperdansvotretasse"

    def frequenceLettre(lettre,texte):
        compteur=0
        for l in texte:
            if l==lettre:
                compteur=compteur+1
        return compteur/len(texte)

    print(frequenceLettre("a",texte))

    0.08737864077669903

Suggestions pédagogiques

- Expliquer un programme

  Quel est le type de la variable `l` dans la ligne 5 ?

- Compléter un programme

  Le programme précédent étant fourni en remplaçant les lignes 4,6 et 7 par `compteur = ...`, `if l==...` et `compteur = ...`, demander aux élèves de compléter les lignes 4, 6 et 7.

### Fluctuation de la fréquence d'apparition d'une lettre en fonction de la longueur du texte¶

Pour des textes longs, la fréquence d’apparition observée est proche d’une valeur qui peut s’interpréter comme fréquence d’apparition de la lettre dans la langue française. On étudie ici un texte comprenant $1917$ caractères.

Remarque

Le code texte[:i] permet d'extraire les i premiers caractères du texte.

Importation de la bibliothèque graphique.

In [3]:

    %matplotlib inline
    import matplotlib.pyplot as plt

Texte à déchiffrer.

In [4]:

    texte="ahnoncestunpeucourtjeunehommeonpouvaitdireohdieubiendeschosesensommeenvariantletonparexempletenezagressifmoimonsieursijavaisuntelnezilfaudraitsurlechampquejemelamputasseamicalmaisildoittremperdansvotretassepourboirefaitesvousfabriquerunhanapdescriptifcestunroccestunpiccestuncapquedisjecestuncapcestunepeninsulecurieuxdequoisertcetteoblonguecapsuledecritoiremonsieuroudeboiteaciseauxgracieuxaimezvousacepointlesoiseauxquepaternellementvousvouspreoccupatesdetendreceperchoiraleurspetitespattestruculentç ûtesjamaisunatomeetdelettresvousnavezquelestroisquiformentlemotsoteussiezvouseudailleursiinventionquilfautpourpouvoirladevantcesnoblesgaleriesmeservirtoutescesfollesplaisanteriesquevousneneussiezpasarticulelequartdelamoitieducommencementdunecarjemelessersmoimemeavecassezdevervemaisjenepermetspasquunautremelesserve"

Le programme suivant permet de représenter la fréquence d'apparition de la lettre a dans un extrait de ce texte en fonction de la longueur de l'extrait.

In [5]:

    N=len(texte)
    frequences = []
    somme = 0
    for i in range(1,N):
        frequences.append(frequenceLettre("a",texte[:i]))

    plt.title("Fréquence d'apparition de la lettre en fonction de la longueur du texte",color="#1e7fcb",fontsize=14)
    plt.plot(frequences)
    plt.show()
    print(frequenceLettre("a",texte))

    0.07720396452790819

Suggestions pédagogiques

- Expliquer un programme

  Expliquer les paramètres du `range` de la ligne 4.

- Tester ce programme en modifiant la lettre recherchée.

  Estimer la fréquence d'apparition du e et du s.

- Compléter un programme

  Le programme précédent étant fourni en remplaçant la ligne 5 par `frequences.append(...)`, demander aux élèves de compléter la ligne 5.

### Alphabet en Python¶

La fonction `alphabet` ci-dessous permet de générer une liste contenant les 26 lettres de l'alphabet grâce à la fonction `chr`. Cette fonction renvoie la chaîne représentant un caractère dont le code de caractère Unicode est donné. Par exemple, `chr(97)` renvoie la chaîne de caractères 'a'

In [6]:

    def alphabet():
        return [chr(i) for i in range(97,123)]

    print(alphabet())

    ['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']

Suggestions pédagogiques

- Tester la fonction `alphabet` afin de donner les valeurs de `chr(98)` et `chr(97+25)`.

- Expliquer un programme

  Que fait la ligne 2 ?

### Liste des fréquences des lettres de l'alphabet¶

La fonction `listeFrequences` donne la liste des fréquences des 26 lettres de l'alphabet dans un texte. Elle prend en paramètre une chaine de caractères et renvoie une liste contenant la fréquence d'apparition des lettres de l'alphabet (toutes dans l'ordre alphabétique) de la chaine de caractères.

In [7]:

    def listeFrequences(texte):
        alpha=alphabet()
        liste=[]
        for l in alpha:
            liste.append(frequenceLettre(l,texte))
        return liste
    print(listeFrequences(texte))

    [0.07720396452790819, 0.005216484089723527, 0.03547209181011998, 0.026604068857589983, 0.16536254564423578, 0.0099113197704747, 0.00782472613458529, 0.009389671361502348, 0.06677099634846113, 0.0036515388628064684, 0.0, 0.04538341158059468, 0.03547209181011998, 0.0693792383933229, 0.0605112154407929, 0.03495044340114763, 0.016692749087115284, 0.06520605112154408, 0.07511737089201878, 0.0714658320292123, 0.07876890975482524, 0.023995826812728223, 0.0, 0.0036515388628064684, 0.001564945226917058, 0.009389671361502348]

Suggestions pédagogiques

- Compléter un programme

  Le programme précédent étant fourni en remplaçant les lignes 4 et 5 par `for ...` et `liste.append(...)`, demander aux élèves de compléter les lignes 4 et 5.

- Écrire un programme

  Écrire la fonction `listeFrequences`.

### Diagramme en bâtons des fréquences d'apparition des lettres de l'alphabet¶

Le programme suivant permet de représenter les fréquences des lettres apparaissant dans le texte sous la forme d'un diagramme en bâtons.

In [8]:

    ep = 0.5
    lettres = [lettre for lettre in alphabet()]
    plt.bar(lettres, listeFrequences(texte), ep, color='b' )
    plt.xlabel('Lettres')
    plt.ylabel('Fréquences')
    plt.title("Fréquences d'apparition des lettres dans le texte.")
    plt.show()

### Fréquences d'apparition des lettres dans la langue française¶

Le programme suivant représente la fréquence d'apparition des lettres dans les textes en langue française. Il ne s'agit ici que d'estimations. La nature du texte peut en effet faire varier légérement ces fréquences. La liste donnant ces fréquences pourra être donnée ou remplacée par une autre (Wikipedia).

L'objectif est ici de comparer cette représentation à la précédente.

In [9]:

    frequencesFrance=[0.077,0.013,0.033,0.042,0.174,0.012,0.013,0.011,0.071,0.003,0.005,0.061,0.029,0.064,0.051,0.029,0.007,0.061,0.092,0.071,0.057,0.013,0.001,0.004,0.005,0.001]
    ep = 0.5
    lettres = [lettre for lettre in alphabet()]
    plt.bar(lettres, frequencesFrance, ep, color='r' )
    plt.xlabel('Lettres')
    plt.ylabel('Fréquences')
    plt.title("Fréquences d'apparition des lettres dans les textes de la langue française.")
    plt.show()

### Message chiffré¶

Le message ci-dessous a été chiffré à l'aide d'une substitution simple à partir d'un message écrit en français.

rertepadmneppobewogexaemefopwtvvdpexeaweaxdtxeofxepwerzwobe

Suggestions pédagogiques

- Déchiffrer le message en étudiant les fréquences d'apparition des lettres du message.

### Fiche enseignant¶

Correction de la dernière question.

In [10]:

    message="rertepadmneppobewogexaemefopwtvvdpexeaweaxdtxeofxepwerzwobe"
    ep = 0.5
    lettres = [lettre for lettre in alphabet()]

    plt.bar(lettres, listeFrequences(message), ep, color='b' )
    plt.xlabel('Lettres')
    plt.ylabel('Fréquences')
    plt.title("Fréquences d'apparition des lettres dans le texte.")

Out[10]:

    Text(0.5,1,"Fréquences d'apparition des lettres dans le texte.")

L'alphabet de substitution est ['o', 'i', 'r', 'w', 'e', 'v', 'b', 'u', 't', 'h', 'y', 'g', 'n', 'm', 'z', 'f', 'l', 'x', 'p', 'a', 'd', 'k', 'j', 'c', 'q', 's'] le message est le suivant :

ceciestunmessagedalertenepasdiffuseretdetruireapresdecodage .

On pourra remarquer que les fréquences aident au déchiffrement mais ne suffisent pas dans le cas d'un message court. En effet, la fluctuation liée à la taille de l'échantillon est importante.

Le programme ci-dessous n'est pas destiné aux élèves. Il permet de faire le chiffrement d'un message par substitution en utilisant un alphabet de substitution aléatoire. L'enseignant pourra l'utiliser pour proposer d'autres messages chiffrés.

In [16]:

    from random import shuffle
    texte="ceciestunmessagedalertenepasdiffuseretdetruireapresdecodage"
    texteChiffre=""
    alpha=alphabet()
    #création de l'alphabet à l'aide de la fonction shuffle effectuant une permutation aléatoire
    alphabetSubstitution=alphabet()
    shuffle(alphabetSubstitution)
    #Affichage de l'alphabet de substitution
    print(alphabetSubstitution)
    #Création du message chiffré
    for x in texte:
        for i in range(26):
            if x==alpha[i]:
                texteChiffre+=alphabetSubstitution[i]
    print(texteChiffre)

    ['e', 'p', 'x', 'l', 'f', 'm', 'r', 'n', 'j', 'b', 'd', 'y', 'o', 'i', 'w', 'a', 'z', 'h', 'v', 'u', 'k', 't', 'g', 's', 'q', 'c']
    xfxjfvukiofvverfleyfhufifaevljmmkvfhfulfuhkjhfeahfvlfxwlerf