Situation déclenchante

Le professeur rappelle ce qui a été vu à la séance précédente : le chiffrement de César consiste à décaler les lettres de l’alphabet d’un certain rang (la « clé »), toujours le même. Ce chiffrement est très facile à casser, car il n’y a que 25 clés possibles.
Il propose de raffiner ce chiffrement, en faisant correspondre à chaque lettre une autre lettre, mais sans s’obliger à respecter le même décalage à chaque fois. En pratique, cela revient à faire correspondre 2 alphabets : un alphabet « clair » (dans l’ordre) et un alphabet « chiffré » (mélangé).

Exercice (individuellement)

Le professeur distribue la Fiche 5 à chaque élève et leur demande d’effectuer les 2 premiers exercices.
La solution de l’exercice 1 est :

•  Message clair :        bonne chance  pour    casser  ce code
•  Message crypté :     TCUUI KMJUKI HCYW KJVVIW KI KCJI

La solution de l’exercice 2 est :

•  Message crypté :     D JB EBUB
•  Message clair :        j  ai fini

Les élèves apprennent ainsi à utiliser la table de correspondance dans les 2 sens (pour chiffrer et déchiffrer).

Combien de clés possibles ? (collectivement)

Après avoir corrigé les 2 premiers exercices de la Fiche 5, le professeur explique qu’il s’agit d’un chiffrement par substitution mono-alphabétique : à chaque lettre de l’alphabet, on en substitue une autre (et une seule). Il fait remarquer que le chiffrement de César est une version très simplifiée du chiffrement mono-alphabétique.

Note scientifique
Le chiffrement de César est bien un cas particulier de chiffrement par substitution mono-alphabétique. On peut appréhender ceci de 2 façons :

•  Parmi tous les chiffrements mono-alphabétiques possibles, le chiffrement de César s’obtient en réalisant une permutation circulaire sur l’alphabet clair, ce qui est bien un sous-ensemble de tous les mélanges possibles.
•  Autre manière de considérer le problème : le chiffrement de César est un chiffrement mono-alphabétique dont la clé est un mot à 1 seule lettre. Par exemple, le chiffrement de César de rang 3 est un chiffrement mono-alphabétique dont la clé est « D » (« A » décalé de 3 rangs). La notion de clé sera approfondie plus loin dans cette séance.

Il pose plusieurs questions de manière à guider les élèves, collectivement, dans le calcul du nombre de clés possibles dans un chiffrement mono-alphabétique.

•  Question 1 : combien de possibilités a-t-on pour chiffrer la lettre « A » ? Réponse : 26.
•  Question 2 : une fois que l’on a choisi une lettre qui correspond à « A » (par exemple, « K »), combien de possibilités reste-t-il pour chiffrer la lettre « B » ? Réponse : 25 (car « K » est déjà prise).
•  Question 3 : une fois qu’on a choisi la correspondance pour A et pour B, combien de possibilités a-t-on pour la lettre C ? Réponse : 24
•  Question 4 : combien de correspondances peut-on fabriquer entre l’alphabet de départ (« clair ») et l’alphabet d’arrivée (« crypté ») ? Réponse : 26x25x24x23…x2x1.

Note pédagogique :
En cas de difficulté à comprendre l’usage de la multiplication dans la question 4, ne pas hésiter à utiliser une représentation en arbre.

Le professeur explique que ce nombre peut également s’écrire « 26 ! » et se prononce « factorielle 26 ». Les élèves calculent (à l’aide de la calculatrice scientifique ou d’un tableur) :

•  1 ! = 1
•  2 ! = 1 x 2 = 2
•  3 ! = 1 x 2 x 3 = 6
•  4 ! = 1 x 2 x 3 x 4 = 24
•  5 ! = 1 x 2 x 3 x 4 x 5 = 120
•  6 ! = 720
•  7 ! = 5 040
•  8 ! = 40 320
•  9 ! = 362 880
•  10 ! = 3 628 800
•  …
•  26 ! ≈ 4x10²⁶, c’est-à-dire 400 000 000 000 000 000 000 000 000

Le nombre de clés possibles n’est plus 26 (comme dans le chiffrement de César), mais 400 millions de milliards de milliards !

Exercice (individuellement)

Le professeur donne aux élèves l’exercice 3 de la Fiche 5 qui permet, par ailleurs, de travailler sur les puissances de 10.

Corrigé :

•  Exercice 3a : on mettra 5 x 4x10²⁶ secondes, soit 1,5x10²¹ ans (ou encore 100 milliards de fois l’âge de l’univers) à tester toutes les clés.
•  Exercice 3b : si tous les êtres humains coopèrent, on mettra 8 milliards de fois moins de temps, soit encore 12 fois l’âge de l’univers.
•  Exercice 3c : le plus puissant des supercalculateurs actuels mettra 4x10¹¹ secondes, soit 300 000 ans, pour tester toutes les clés possibles.

Après avoir corrigé l’exercice 3, la classe réalise que le nombre vertigineux de clés possibles a rendu cette méthode de chiffrement incassable pendant des siècles (du moins si on supprime les espaces, car sinon on peut se servir des mots courts pour deviner certaines lettres). C’est l’invention par Al-Kindi, au 9^e siècle après J.-C., de l’analyse fréquentielle qui a rendu ce chiffrement obsolète. Cette méthode fait l’objet de la séance suivante.

Chiffrement à l’aide d’un mot-clé ou d’une phrase-clé (collectivement)

Cependant, dans la pratique, il faut que l’émetteur et le destinataire du message s’accordent à trouver quel alphabet utiliser, ce qui peut être compliqué :

•  Prendre un alphabet mélangé aléatoirement nécessite que chacun apprenne par cœur cet alphabet aléatoire, ce qui est très difficile, et facilement source d’erreur ;
•  La solution consistant à noter cet alphabet  (table de correspondance de la Fiche 5) n’est pas non plus satisfaisante : il suffit qu’un espion trouve le papier sur lequel on l’a noté pour avoir la clé permettant de déchiffrer tous les messages.

Une solution possible consiste à ne pas utiliser un alphabet aléatoire, mais un mot-clé, ou une phrase-clé. Le professeur explique la méthode à l’aide d’un exemple. Si la clé est « JULES CESAR », on remplit l’alphabet chiffré par les lettres de la clé, en ignorant les espaces… et en ignorant les lettres qui ont déjà été utilisées ! (c’est indispensable si l’on veut que chaque lettre soit substituée par une seule lettre possible).
« JULES CESAR » devient alors « JULESCAR »

Étape 1 : on remplit le tableau avec les lettres de la phrase-clé « nettoyée ».

Étape 2 : on complète l’alphabet en démarrant là où s’arrête la phrase-clé, et en omettant les lettres déjà utilisées.

Ainsi, il est très facile de reconstruire l’alphabet chiffré, et l’on n’a plus qu’à retenir un mot ou une phrase, ce qui est bien plus facile que d’apprendre un enchaînement aléatoire de 26 lettres !
Avec la clé « JULES CESAR », le texte « VENI VIDI VICI » devient donc MSZT MTET MTLT.

Note pédagogique
 La méthode décrite ci-dessus est celle qui est communément adoptée en cryptographie, c’est pourquoi nous l’utiliserons par la suite. Il faut néanmoins comprendre que cette méthode est une convention et qu’il est parfaitement possible de créer un autre alphabet chiffré. Par exemple, à la fin du mot-clé, plutôt que de continuer l’alphabet comme expliqué ci-dessus, on pourrait décider de le reprendre du début (par la lettre A, sauf si elle a été utilisée…). À noter que dans ce cas, la fin de l'alphabet sera inchangée : ce qui rend le texte chiffré en partie lisible… et donc bien plus facile à cryptanalyser.

Entrainement (par binôme)

Chaque binôme utilise l’exercice 4 de la Fiche 5 pour s’exercer au chiffrement par substitution mono-alphabétique. Il s’agit, dans un premier temps, de trouver une clé de chiffrement, puis de générer l’alphabet chiffré, et enfin de chiffrer un message court. Ce message est transmis au voisin, qui doit le déchiffrer (attention, il faut transmettre le message chiffré, mais aussi la clé !)

Note scientifique :
L’usage du chiffrement par substitution mono-alphabétique est en réalité bien antérieur à Jules César : on le voit apparaître dans le Kama Sutra (écrit au 5^e après J.-C.… mais sur la base d’un manuscrit datant du 4^e siècle avant J.-C.). Parmi les nombreux arts que devait maîtriser une concubine, le numéro 45 (mlecchita-vikalpà) consistait à savoir communiquer secrètement avec son amant !

Conclusion

La classe définit collectivement les concepts-clés cités dans l’en-tête de cette séance : chiffrement mono-alphabétique, clé, alphabet chiffré.