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.