Adhérer ou faire un don

Autour de la cryptographie, dans une classe de Terminale S.

Françoise Gaydier [1]

Je suis partie de constats :
- La cryptographie actuelle, dont on n’imagine pas toujours à quel point elle concerne tout un chacun dans sa vie quotidienne, utilise des résultats mathématiques fort vieux, dont on a pu penser à certaines époques qu’ils ne serviraient jamais à rien. Je pense par exemple au théorème d’Euler-Fermat.
- La problématique de la cryptographie, simple à comprendre sans schématisation réductrice, permet non seulement de proposer des exercices touchant à de nombreuses parties du programme de TS, ce que je voudrais illustrer ici, mais également d’aborder des problématiques dans des domaines voisins des maths ou nouveaux en maths : programmation et complexité d’algorithmes.
- De plus, dans la mesure où c’est une problématique ouverte (il demeure des questions sans réponses à ce jour concernant la sûreté des cryptages actuels), il est possible de trouver des articles à donner à lire, qui soient mieux que des textes sur mesure pour lycéens éveillés : de vrais textes d’information ; ainsi par exemple, sur le site de la Société Mathématique de France, l’article de Jean-Louis Nicolas de l’Université Claude-Bernard (Lyon 1), mais aussi de temps en temps dans la presse l’annonce d’un record battu concernant la taille d’un entier décomposé en produit de deux facteurs premiers, annonce parfois assortie d’explications sur ce qui est en jeu autour de ces records : la sûreté des cryptages.

1. La problématique

Il faut, au départ, faire réaliser aux élèves qu’il y a dans la langue courante une ambiguïté sur le sens de « code » : l’enfant de 8 ans qui dit qu’il envoie à ses amis un message codé, sous-entend qu’il s’agit d’un message contenant un secret que seuls les destinataires sont censés pouvoir décoder, autrement dit, il s’agit d’un message crypté.

Dans un contexte de classe Terminale, « coder » ne doit plus sous-entendre une idée de secret : les élèves doivent réaliser que beaucoup de choses sont codées, par des codes souvent transparents ; ainsi 2005 est la représentation en base dix d’un nombre : on a utilisé pour ce faire un code qui permet de représenter n’importe quel nombre entier, mais ce code n’est pas secret, tout le monde sait en principe le déchiffrer.

De même l’utilisation du code morse pour envoyer un SOS exige que le message ainsi codé puisse être déchiffré par n’importe quel capitaine de bateau croisant à proximité…

Tout cela paraît évident, mais il n’est pas si facile que cela de faire exprimer cette évidence lorsque l’on pose à un groupe d’élèves de TS, spécialité maths la question :
« codage et cryptage, qu’est-ce que cela évoque pour vous ? ».

Ces questions de terminologie éclaircies, il s’agit alors de dégager la problématique du cryptage : A et B doivent échanger des messages secrets ; pour cela ils conviennent de les crypter.

De façon classique, A et B se rencontraient ou utilisaient un intermédiaire pour convenir des codes secrets qu’ils allaient utiliser pour crypter et décrypter les messages secrets qu’ils voulaient s’envoyer.
Cette manière de procéder posait plusieurs problèmes :

Premier problème : un tiers caché dans les buissons pouvait intercepter ces codes ; c’est le problème de l’échange des clés (de cryptage et, éventuellement, de décryptage).

Deuxième problème : le plus souvent, lorsque l’on connaissait le code pour crypter, on pouvait connaître le code pour décrypter : le codage par translation ou le codage affine (annexe 2) en sont de bons exemples. Non seulement un tiers malveillant pouvait, s’étant procuré la clé de cryptage, envoyer un faux message, mais il pouvait aussi, en s’étant emparé seulement de la clé de cryptage, fabriquer la clé de décryptage et déchiffrer le message secret. Ce problème rendait donc encore plus cruciale la confidentialité de l’échange des clés.

Troisième problème : il fallait faire un code secret suffisamment robuste pour qu’un tiers interceptant le message crypté ne puisse pas, bien que ne connaissant ni le procédé de cryptage ni celui de décryptage, déchiffrer quand même le message (voir l’activité 7 de décryptage par analyse fréquentielle).

Deux personnes donc, A et B, veulent se communiquer une information que de tierces personnes ne doivent pas connaître. Plus précisément, A doit envoyer à B une information qui doit rester secrète.

L’avancée dans la cryptographie moderne se situe dans la « dé-symétrisation » des rôles de A et de B : A est l’émetteur et B le récepteur du message.
Le coup de génie dans le cryptage moderne est de rendre publique, par le récepteur B, la clé de cryptage. Évidemment cela exige que la clé de décryptage ne puisse pas se déduire de la clé de cryptage : elle reste privée, c’est-à-dire connue du seul récepteur B.

Le livre de Simon Singh (J.-C. Lattès) : Histoire des codes secrets, détaille les étapes de cette invention du cryptage à clé publique qui a abouti à la fin des années 1970 ( » 1977).

La solution aujourd’hui le plus souvent retenue, le cryptage R.S.A., est fondée sur le théorème d’Euler-Fermat (annexe 3).

Résumons la situation actuelle : on utilise un cryptage à clé publique (par exemple le cryptage RSA) : le récepteur B diffuse sans se cacher la clé avec laquelle les émetteurs doivent crypter les messages confidentiels qu’ils veulent lui envoyer. Le procédé de cryptage est tel que lorsque l’on connaît seulement la clé de cryptage, on peut crypter (plus ou moins facilement) mais on ne peut pas décrypter (voir cependant l’activité 8).
Seul B dispose de la clé de décryptage qui est sa clé privée.

En fait, de tels cryptages sont coûteux en temps. Pour réduire les temps de codage/décodage du message, on utilise un procédé en deux étapes : le cryptage à clé publique évoqué ci-dessus est utilisé pour crypter un second code secret avec lequel sera crypté le message, ce second code étant tout à la fois moins gourmand en temps de codage, et cependant assez sophistiqué pour que le décryptage du message ainsi codé soit laborieux, ce qui doit protéger le secret suffisamment longtemps. Le premier cryptage, qui permet la distribution des clés, doit, lui, être inviolable. Ce procédé permet de répondre au premier problème évoqué : celui de la distribution des clés.

2. Diverses activités menées avec les élèves sur le thème de la cryptographie.

- 1°) lecture d’un article scientifique (cité plus haut ) en début d’année : j’ai eu peu de retour de la part des élèves, à part la difficulté du paragraphe concernant les courbes elliptiques que j’avais suggéré de survoler. J’entends par « peu de retour » le fait que les élèves ont dit avoir globalement compris le texte et n’ont pas posé de question en dehors du paragraphe sur les courbes elliptiques.

- 2°) programmation sur calculatrice d’un test : un nombre est-il premier ? (annexe 1). Le problème de la difficulté de la décomposition d’un nombre en produit de nombres premiers a été abordé lors du chapitre sur les nombres premiers : où sont les nombres premiers ? comment savoir si un nombre est premier ? comment faire avec une machine ? enregistrer tous les nombres premiers n’est pas possible, etc.

Mon objectif était de montrer que le temps de calcul pour tester la primalité d’un nombre augmente vite lorsqu’on augmente la taille du nombre, afin d’introduire l’idée de complexité d’algorithme.

Résultats obtenus : quelques élèves ont fait un programme, mais ils ne semblaient pas trouver le temps de calcul long. J’ai fini par réaliser que nous n’avions pas le même outil de calcul : avec ma vieille TI 89, il faut être patient… Avec une TI 83 ou équivalent, ce n’est en fait pas très spectaculaire : une dizaine de minutes pour déclarer premier un nombre de 10 chiffres.

Il me faudra l’an prochain faire la manipulation avec une calculatrice formelle pour que la manipulation soit parlante (voir aussi annexe 4).

- 3°) Devoir à la maison pour l’enseignement de spécialité : codage de César, codage affine : sujet inspiré, avec son aimable autorisation, d’un travail de Martine Bühler (annexe 2). Le devoir a été réussi, mise à part la dernière question (voir plus loin).

- 4°) Travail en tronc commun :

  • a) Dénombrement des codages caractères par caractères ( ou monographiques) : il y en a 26 ! Puis, calcul de durées quand on essaye tous les codages (le pire des cas) en supposant qu’on ait besoin de deux secondes par essai.
    J’ai mené ce calcul de durées car il m’est apparu, lors de la correction du devoir évoqué en 3°), que les élèves pensaient que la fragilité d’un codage monographique résidait dans le fait que l’on pouvait trouver facilement la clé : « il y en a peu, donc avec un ordinateur … ».
    J’ai alors découvert que l’ordre de grandeur de 26 ! ne saute pas aux yeux : ce n’est après tout qu’un entier qui s’écrit avec 3 signes…

    Remarque : j’ai constaté également un peu plus tard que prendre x grand sur calculatrice, c’est prendre x = 50 par exemple… Je voulais mettre en défaut la calculatrice pour conjecturer la limite à l’infini de $ (1+\frac{1}{x})^{x}$ . J’ai obtenu timidement x = 1 000 ou x = 10 000. Ma proposition $x = 10^{48}$ les a surpris…
  • b) Exercice de probabilités :
    Sachant qu’un message a été codé caractères par caractères, que le code a été choisi au hasard et que l’on a besoin d’une durée $\Delta t$ pour essayer un code, quelle est la durée moyenne pour décrypter le message ?

- 5°) Devoir en classe de spécialité : le théorème de Fermat-Euler (annexe 3). Je n’ai malheureusement gardé de ce devoir (d’une durée d’une heure) que la note globale obtenue par chaque élève pour le DS de quatre heures dont cet exercice était une composante. En tout cas, lors de l’exposé évoqué plus loin, les élèves se souvenaient bien du résultat démontré.

6°) Introduction à la notion de bijectivité sur la base du devoir à la maison (annexe 2).

Ce fut ma transition tout à fait inattendue entre l’arithmétique et les similitudes… J’avais à revenir sur la question 1°) du Cas général. Je me suis alors aperçue que certains élèves n’avaient pas vu l’importance pour le décryptage que TOTO et TATA ne soient pas codés de la même manière.
En faisant un schéma pour expliquer le problème du décodage, je me suis rendu compte que j’étais en train de faire les diagrammes que j’avais l’intention de faire l’heure suivante pour commencer mon cours sur les similitudes : « une similitude est une bijection qui conserve les rapports de longueurs ».
J’ai fait mes diagrammes et j’ai enchaîné sur la feuille polycopiée que j’avais préparée sur la notion de bijectivité. J’ai pu illustrer mon propos non seulement avec les transformations déjà connues et leurs bijections réciproques, les fonctions « carré » et ln, « racine carrée » et exp, mais aussi les fonctions de codage et décodage que nous venions d’étudier.

- 7°) Décryptage par analyse fréquentielle d’un texte crypté caractères par caractères : ce texte est le texte proposé en première étape d’un concours par Simon Singh dans son livre déjà évoqué (p. 382).
J’ai vidéoprojeté le texte à décrypter préalablement scanné et transformé en fichier Word par un logiciel de reconnaissance de caractères. Les élèves l’ont décrypté en utilisant des données statistiques sur la fréquence des caractères dans la langue française, et quelques commandes Word (« rechercher » et « remplacer ») avec un petit problème technique à résoudre quand on remplace un caractère par un autre…
Ce fut rapide, plaisant et probant quant à la faiblesse du cryptage monographique. Pour être honnête, les espaces étant en place, l’outil informatique était utile mais non nécessaire…

- 8°) Exposé de trois élèves sur le cryptage RSA (annexe 5). J’avais proposé assez tôt dans l’année à quatre bons (voire très bons) élèves de faire un exposé sur le cryptage. Ils en étaient d’accord, puis une élève trop prise par ses activités extra scolaires s’est dédite.
Plus tard j’ai fixé avec eux une date : après les soutenances de TPE et le Bac Blanc. Je les ai laissés travailler en autonomie.
La compréhension de cet exposé par l’ensemble de la classe devait être facilitée par le travail entrepris avec le DS cité plus haut. J’avais, dans le même but, proposé aux élèves de traduire sur leur calculatrice un algorithme permettant la détermination de solutions entières particulières pour l’équation au + bv = 1 lorsque a et b sont premiers entre eux (un élève avait essayé tout seul sans aboutir, et je voulais pousser les autres à programmer).
L’exposé a été remarquable :
- Un bon plan.
- Les trois élèves ont parlé, sans cabotinage.
- Le contenu était solide et amené de manière plaisante. Le groupe a donné la preuve du décryptage dans le cas général (cf. annexe 5). Il a été jusqu’à évoquer le problème de la génération de grands nombres premiers (ou qui ont une forte probabilité de l’être), et a su expliquer ce qui faisait la solidité de RSA, mais aussi peut-être sa fragilité : on ne sait pas actuellement « casser » n en sa décomposition n = pq en un temps raisonnable, mais on n’a pas prouvé que c’est impossible.
- Les autres élèves ont bien participé et posé de bonnes questions (par exemple : et si p et q ne sont pas premiers ? comment fait-on pour avoir de grands nombres premiers ?).
Le point faible a été la complexité d’algorithme : ils ont essayé de parler de calculs en temps polynomial ou en temps exponentiel, mais sans conviction.
Je me suis moi-même « plantée » en tentant d’improviser sur le sujet. Les élèves qui faisaient l’exposé étant demandeurs, j’ai essayé de préparer un travail sur la question (cf. annexe 4), mais, en dehors des convergences de suites, bien qu’ayant plus de dix ans de pratique de l’enseignement de l’algorithmique, je ne trouve pas facilement d’algorithmes abordables dans ce cadre pour évaluer des temps de calcul : les algorithmes de tri ou de résolution de systèmes me paraissent difficiles dans ce contexte.

9°) Travail sur la complexité d’algorithme avec calculatrice
en tronc commun par une étude de rapidité de convergences de suite ou d’algorithme :
- calcul de $\sqrt{2}$ par la méthode de Héron : $u_0 = 2 $ et, pour tout n, $ u_{n+1} =\frac{1}{2}(u_{n} + \frac{2}{u_n}) $ ;
- calcul de p par la méthode de Monte-Carlo en DM : simulation avec la calculatrice de gouttes de pluie tombant aléatoirement sur un disque inscrit dans un carré ;
- calcul de $\pi $ par la méthode des polygones inscrits et exinscrits en DM.

En conclusion

ce thème de la cryptographie m’a permis de donner la possibilité à de bons élèves d’aller plus loin en restant dans le cadre du programme de l’année en cours et sans déflorer celui de l’année suivante.
Je pense (j’espère) que ce travail sur la cryptographie a permis aussi à l’ensemble du groupe de voir des applications des mathématiques dans un champ où on ne les imagine pas. Il m’a permis également, en évoquant (sommairement certes) les problèmes de complexité d’algorithme et la conjecture $P\neq ­ NP$ de leur suggérer que les mathématiques sont bien vivantes et pas seulement prestataires de service.
Je n’ai aucun moyen pour mesurer l’impact de ce travail : je pense qu’il fait partie de ce travail de fourmis que nous devons mener quotidiennement pour éveiller des curiosités, relancer des motivations et parfois susciter des enthousiasmes en mathématiques.

Lire l'article et SES ANNEXES dans leur intégralité


[1] Lycée Claude Monet, Paris 13°.