Situation initiale

La classe fait le point sur ce qu’elle a appris en matière de cryptographie :

•  le chiffrement de César est très facile à casser, à la fois car le nombre de clés possibles est très faible (donc on peut les tester toutes très rapidement) et parce qu’il ne résiste pas à l’analyse fréquentielle ;
•  le chiffrement par substitution mono-alphabétique possède un nombre de clés très élevé, mais il est facile à casser (pour des messages de longueur suffisante) à l’aide de l’analyse fréquentielle ;
•  Il existe des méthodes de chiffrement qui résistent à l’analyse fréquentielle (ceux pour lesquelles une même lettre peut être chiffrée en plusieurs lettres différentes).

Le professeur fait remarquer que toutes ces méthodes de chiffrement possèdent un point faible : la transmission de la clé. Pour que le destinataire du message puisse le déchiffrer, il faut qu’il possède la clé de chiffrement. Le professeur demande aux élèves comment il est possible de se mettre d’accord sur une clé avec son interlocuteur, et la classe examine les points faibles des méthodes proposées par les élèves :

•  Noter la clé sur un papier, que l’on transmet à l’interlocuteur : si le papier est intercepté, c’est fichu ! (On peut évoquer les « cabinets noirs » qui, dans chaque pays, interceptaient les courriers postaux pour espionner les communications, en particulier venant ou allant à des ambassades).
•  Transmettre la clé oralement à son interlocuteur, qui l’apprend par cœur : cela nécessite de pouvoir rencontrer son interlocuteur. Aujourd’hui, on veut communiquer rapidement avec des personnes à l’autre bout de la planète. Comment justifier de prendre un billet d’avion juste pour communiquer la clé d’un futur échange ? Ce système peut fonctionner en théorie, mais sera très lent et couteux. C’est comme cela que fonctionne le téléphone rouge : avant chaque nouvelle communication, une nouvelle clé est générée aléatoirement, puis échangée par voie diplomatique (ce qui prend du temps et nécessite un acheminement hautement sécurisé). L'important étant que la clé soit très longue (à peu près aussi longue que le message à chiffrer) et qu’elle soit nouvelle pour chaque nouveau message. Ce chiffrement est inviolable, mais très couteux : seules les communications les plus importantes peuvent justifier un tel coût.
•  Changer souvent de clé. Avantage : si quelqu’un découvre une clé, il ne pourra décoder que les messages du jour, et pas ceux du lendemain). Inconvénient : il faut noter les différentes clés et se les transmettre… et l’on retombe sur les difficultés rencontrées précédemment.
•  …

Recherche (par groupes)

Le professeur propose aux élèves de modéliser la communication entre 2 personnes à l’aide d’une boîte (qui renferme le message que l’on veut transmettre) et de cadenas (qui symbolisent des méthodes de chiffrement). On peut mettre en place plusieurs méthodes de chiffrement (i.e. utiliser plusieurs cadenas). Chaque groupe reçoit une boîte, 2 cadenas, chacun des cadenas ayant sa propre clé.

La situation est la suivante : Alice cherche à envoyer un message à Bob, sans qu’Ève puisse intercepter ce message.

Les élèves doivent chercher quelles sont les opérations à réaliser (et dans quel ordre) par Alice et par Bob pour que le message puisse être correctement déchiffré à l’arrivée, sans jamais voyager en clair.

Note scientifique :
Alice, Bob et Ève sont des figures inventées par Ron Rivest en 1978 dans un article décrivant le système RSA (dont il est question sur la Fiche 9). Depuis, ces 3 prénoms sont couramment utilisées pour illustrer les méthodes de cryptographie.

Notes pédagogiques

•  Il est peu probable que les élèves parviennent, seuls, à trouver l’algorithme. Ce petit temps de tâtonnement nous semble cependant important pour leur faire réfléchir avant de les guider (légèrement) vers la solution.
•  Une façon de les guider peut être de les faire jouer au jeu « loup/chèvre/chou » : Un batelier doit faire traverser une rivière à un loup, une chèvre et un chou. Attention : il n’y a qu’une place sur le bateau. De plus, si le loup et la chèvre sont ensemble sur la même rive lorsque le batelier s’éloigne, le loup mange la chèvre. Même chose avec la chèvre et le chou. Comment faire ? Il s’agit d’un problème similaire, avec une contrainte sur le voyage. Ici, il s’agit de ne jamais laisser seuls le loup et la chèvre, ou la chèvre et la laitue ; tandis que dans notre problème d’origine, il s’agit de ne jamais faire voyager le coffre sans aucun cadenas.

Après une dizaine de minutes de tâtonnement, le professeur les met sur la voie : il explique que le problème de l’échange de clé vient du fait que les 2 interlocuteurs utilisent la même clé.
Il propose d’explorer ce qui se passe si chacun possède son propre cadenas et sa propre clé. Les élèves tâtonnent à nouveau une dizaine de minutes en explorant cette configuration :

•  Alice possède un cadenas, et une clé (qui n’ouvre que son propre cadenas)
•  Idem pour Bob
•  Ils doivent se communiquer la boîte en faisant en sorte qu’elle soit toujours fermée par un cadenas, et qu’elle puisse être ouverte à la fin (par Bob).

Mise en commun

Le professeur organise la mise en commun au cours de laquelle quelques groupes viennent présenter leur méthode. Chacune est discutée.

La méthode qui fonctionne (ou plutôt, qui  semble fonctionner, comme on le verra à la séance suivante) est :  Étape 1 : situation initiale : Alice veut envoyer un message à Bob. Chacun possède un cadenas et une clé privée (son propre algorithme de chiffrement)  Étape 2 : Alice pose son cadenas et envoie ce message chiffré à Bob  Étape 3 : Bob ne peut pas ouvrir le cadenas d’Alice (il n’a pas la clé d’Alice) : il pose son propre cadenas et renvoie le message (chiffré à la fois par Alice et par Bob) à Alice  Étape 4 : Alice retire son cadenas (elle déchiffre le message à l’aide de sa clé) et le renvoie à Bob  Étape 5 : cette fois, Bob peut retirer le dernier cadenas (puisque c’est le sien : il a la clé !) et lire ainsi le message contenu dans la boîte.

Le professeur fait remarquer aux élèves qu’Alice et Bob ont réussi à communiquer secrètement… et ce, sans jamais communiquer leur clé !

Exercice

Chaque groupe répète la manœuvre plusieurs fois de manière à ce qu’elle soit bien comprise par tous les élèves.

Notes scientifiques

•  Cette méthode possède un point faible, qui est discuté (et résolu) dans la séance suivante.
•  Les cadenas représentent des fonctions mathématiques de chiffrement (et les clés les valeurs qui permettent de déchiffrer). Cette méthode de communication sans échange de clé suppose donc que les méthodes de chiffrement utilisées (donc les fonctions mathématiques) soit commutatives.