Combien de clés secrètes faut-il pour que cent personnes puissent toutes communiquer deux à deux en secret ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En réfléchissant à la messagerie chiffrée que j'utilise avec mes amis, je me suis demandé comment elle gérait les clés : chaque conversation doit avoir sa propre clé secrète. J'ai calculé combien de clés il faudrait pour une classe, puis pour un lycée, et j'ai compris pourquoi la cryptographie à clé publique a été une révolution pour internet.

L'enjeu et les notions du programme

Dénombrer des paires par les combinaisons et comparer une croissance quadratique à une croissance linéaire.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Un chiffrement symétrique utilise la même clé pour chiffrer et déchiffrer. Deux personnes qui veulent se parler doivent donc partager une clé, inconnue des autres. Problématique : combien de clés faut-il dans un groupe, et comment ce nombre évolue-t-il ?

2. 2. Mathématiques : compter les paires

   4 min

   Chaque paire de personnes a besoin de sa propre clé. Le nombre de paires dans un groupe de $n$n personnes est $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$binom n2=(n(n-1))/2.

   Pour $n=100$n=100 : $\frac{100\times 99}{2}=4950$100×99/2=4 950 clés. Pour $n=1000$n=1 000 : $499500$499 500. Multiplier le groupe par 10 multiplie le nombre de clés par environ 100 : croissance quadratique. On retrouve aussi ce nombre par une somme : la première personne partage une clé avec 99 autres, la deuxième avec 98 nouvelles, etc. : $99+98+\cdots +1=4950$99+98+…+1=4 950.

   Avec la cryptographie à clé publique, chaque personne a une paire de clés (publique et privée) : $2n$2n clés en tout, soit 200 pour cent personnes. C'est une croissance linéaire. Le rapport $\frac{n(n-1)/2}{2n}=\frac{n-1}{4}$(n(n-1)/2)/2n=(n-1)/4 montre que l'écart grandit sans limite.

3. 3. NSI : graphe complet et solutions réelles

   3 min

   On représente le groupe par un graphe : un sommet par personne, une arête par clé. Le chiffrement symétrique demande le graphe complet, dont le nombre d'arêtes est $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$binom n2. Chaque sommet a $n-1$n-1 voisins, et la somme des degrés $n(n-1)$n(n-1) vaut le double du nombre d'arêtes.

   En pratique, on combine les deux : chaque utilisateur publie sa clé publique, et une conversation commence par l'échange, à l'aide de ces clés, d'une clé symétrique temporaire. Le nombre de clés à stocker durablement reste linéaire, tandis que le chiffrement des messages reste rapide.

4. 4. Conclusion

   1,5 min

   Le chiffrement symétrique seul demande $\frac{n(n-1)}{2}$(n(n-1))/2 clés, ingérable à l'échelle d'internet ; la clé publique ramène ce nombre à $2n$2n. Un simple dénombrement explique une révolution technique. J'ouvre sur le problème de l'authenticité des clés publiques, résolu par les certificats.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Oublier de diviser par 2.
• Dire que le nombre de clés double quand le groupe double : il est multiplié par environ 4.
• Confondre clé publique et clé partagée.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Graphes et marches aléatoires (Terminale maths expertes) →

Autres questions : cryptographie et sécurité

• Comment peut-on chiffrer un message avec une clé que tout le monde connaît ?
• Deux personnes peuvent-elles fabriquer un secret commun en ne s'échangeant que des messages publics ?
• Pourquoi une clé de 128 bits est-elle considérée comme incassable par force brute ?
• Combien de fichiers faut-il pour que deux d'entre eux aient la même empreinte numérique ?

Toutes les questions maths-nsi →