Le professeur propose à la classe de produire un nouveau programme, qui va aider à la cryptanalyse : il s’agit de construire l’histogramme de fréquences d’un texte, de façon automatisée. Ce travail se déroule en 2 temps :

•  Créer un tableau contenant les fréquences de chaque lettre du message. Cette étape ne présente pas de difficulté majeure et fait l’objet de la présente séance.
•  Créer un graphique permettant de visualiser ces fréquences. Cette étape, qui fait l’objet des 2 séances suivantes, est plus difficile (mais fort intéressante, notamment pour travailler les fonctions et leur représentation graphique !). Elle est considérée comme optionnelle.

Note pédagogique
 L’emploi du terme « fréquence » est ici un abus de langage, car ce que l’on calcule, ce sont des nombres d’occurrence plutôt que des fréquences. Nous gardons néanmoins ce terme pour faire le lien avec la méthode de cryptanalyse appelée « analyse fréquentielle ».

Étape 1 : définir les différentes étapes du projet  (15 minutes)

Dans un premier temps, les élèves réfléchissent à l’algorithme permettant de compter la fréquence d’une lettre donnée dans un texte. En fonction de leur aisance, le professeur peut les faire travailler en binôme, en groupe (suivi d’une mise en commun) ou conduire un travail collectif en classe entière.

•  Pour compter le nombre de « A » présents dans un texte, la méthode est :
  •  Parcourir le texte, de la première à la dernière lettre
  •  Pour chaque lettre examinée, tester si cette lettre est un « A ». Si oui, ajouter « 1 » à la variable qui compte les occurrences de cette lettre.
•  Pour compter la fréquence de toutes les lettres d’un texte :
  •  il suffit de généraliser la méthode ci-dessus et de faire une boucle portant sur toutes les lettres du texte.
  •  Les valeurs vont devoir être enregistrées dans un tableau de 26 cases (la première case contiendra la fréquence de la lettre « A », la seconde celle de la lettre « B »…). Le professeur explique que ceci est possible en Scratch, à l’aide d’un type de variable appelé « liste ».

Voici un exemple de découpage du projet en différentes étapes (la réalisation du graphique sera traitée à la séance suivante) :

Étape 2 : calculer la fréquence d’une lettre dans un texte (30 minutes)

Cette étape ne pose pas de difficulté car elle reprend les mêmes notions que les 4 séances de programmation précédentes sur le chiffrement de César.
Un programme qui compte le nombre de « A » présents dans un texte s’écrit :

Note scientifique :
Rappel : Scratch n’est pas sensible à la casse. Les lettres « a » et « A » sont considérées comme identiques dans les opérations faisant intervenir des chaines de caractères.

Exprimé à l’aide d’une fonction, le programme devient :

Note : L’utilisation d’une fonction nécessite que l’on renomme notre variable « frequence_a » en « Var_frequence_a », si l’on souhaite respecter la convention utilisée jusqu’à présent.

Si maintenant on souhaite calculer la fréquence, non pas de la lettre « a », mais de n’importe quelle lettre de l’alphabet, on peut généraliser cette approche en remplaçant « a » par « élément (rang) de alphabet », où rang est un nombre entre 1 et 26 et alphabet une variable contenant les 26 lettres, dans l’ordre.

Pour modifier les propriétés de la fonction (la renommer en « frequence » et lui ajouter une seconde variable d’entrée), il faut effectuer un clic droit sur la définition de cette fonction et choisir « éditer ». On note que la variable « Var_frequence_a » a également été renommée en « Var_frequence ».

Étape 3 : remplir un tableau de fréquences (30 minutes)

Remplir le tableau de fréquence de toutes les lettres de l’alphabet nécessite une variable de type « liste ». Si les élèves n’ont jamais manipulé de listes en Scratch, ne pas hésiter à leur montrer comment créer, initialiser et utiliser de telles variables. C’est l’objet de la Fiche 14, qui propose un petit exercice guidé. Nous conseillons d’effectuer le premier exercice collectivement, puis de faire des mises en commun à chaque étape, de façon à vérifier la bonne appropriation de cette nouvelle notion par les élèves.

Réponses :

•  Programme 1 : ce programme demande à l’utilisateur de taper 3 textes, et stocke ces textes dans une variable de type « liste » (un tableau à une colonne, affiché à l’écran). Par défaut, elle est vide (« empty »), et sa longueur est 0.
•  Programme 2 : l’instruction « supprimer… » ajoutée en début de programme permet de réinitialiser la liste.
•  Programme 3 : le programme ne s’arrête de remplir la liste que lorsque l’utilisateur entre le mot « OK ». La liste contient donc tous les éléments cités par l’utilisateur (dont le « OK » final).
•  Programme 4 : Ce programme supprime le dernier élément de la liste (qui est le « OK » vu précédemment), et affiche la longueur (nombre d’éléments) de cette liste (sans le « OK », qui a été supprimé). Il envoie alors un message, qui peut déclencher un autre programme (cf. ci-dessous).
•  Programme 5 : Ce programme, déclenché à la fin du précédent, récapitule la liste (le chat affiche, un par un, les éléments de la liste).

Les élèves savent désormais comment créer, initialiser et manipuler une liste (ajouter des éléments, en supprimer, afficher la longueur de la liste…). Ils peuvent donc reprendre le programme réalisé à l’étape précédente, et le mettre à jour pour calculer les fréquences de toutes les lettres de l’alphabet (ces fréquences sont stockées dans une variable de type « liste »).

Modification du programme principal pour calculer les fréquences de toutes les lettres de l’alphabet.
Note : nous n’avons pas besoin de modifier la fonction « frequence_de_rang_dans_message ».

Les élèves vérifient le bon fonctionnement du programme en le testant sur des textes courts, sur lesquels ils peuvent calculer rapidement les fréquences à la main.

Note pédagogique :
 Ne pas hésiter à poser de petits défis aux élèves en avance sur le reste de la classe. Ici, par exemple, on peut leur demander d’initialiser la liste avec des 0 puis d’incrémenter la case adéquate chaque fois qu’une lettre est trouvée dans le texte (cf. second algorithme, dans la note scientifique ci-dessous).

Note scientifique
 Pour établir le tableau des fréquences, 2 algorithmes sont possibles :

•  Premier algorithme (celle qui est illustrée ici)
  Pour la lettre A, on parcourt tout le texte, à la recherche de cette lettre, et on incrémente le compteur quand on la trouve. On boucle ensuite sur les 26 lettres de l’alphabet
•  Second algorithme
  Pour la première lettre du texte, on parcourt l’alphabet (pour trouver son rang) et on incrémente le compteur correspondant à ce rang. On boucle ensuite pour toutes les lettres du texte. Cette seconde méthode est légèrement plus efficace, car elle évite d’avoir à parcourir tout le texte pour chaque lettre de l’alphabet, y compris une lettre absente du texte. Cependant, cette méthode ne permet pas d’utiliser la fonction que nous avons introduite à l’étape précédente, intéressante car moins difficile.

Étape 4 (optionnelle) : remplacer les lettres accentuées (15 minutes)

Cette étape ressemble fortement à celle réalisée pour le chiffrement de César ; elle permet donc aux élèves de renforcer leur compréhension des notions impliquées et pose moins de difficulté que la première fois.
Les deux séances qui suivent, optionnelles, permettent de visualiser ce tableau de fréquences sous la forme d’un graphique.