Combien de fichiers faut-il pour que deux d'entre eux aient la même empreinte numérique ?

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.

Quand je télécharge un logiciel, le site affiche parfois une « empreinte SHA-256 » pour vérifier le fichier. Je me suis demandé comment une suite de 64 caractères pouvait identifier n'importe quel fichier, alors qu'il existe bien plus de fichiers que d'empreintes. Il y a forcément des collisions : la question est de savoir quand on risque d'en rencontrer une.

L'enjeu et les notions du programme

Calculer une probabilité par le complémentaire et un produit, puis l'approcher par l'exponentielle pour dimensionner un outil informatique.

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

1. 1. Introduction

   1 min

   Une fonction de hachage associe à tout fichier une empreinte de taille fixe. Comme il y a plus de fichiers que d'empreintes, deux fichiers ont parfois la même : c'est une collision. Problématique : à partir de combien de fichiers une collision devient-elle probable ?

2. 2. Mathématiques : le paradoxe des anniversaires généralisé

   4 min

   On suppose les empreintes réparties au hasard parmi $N$N valeurs. La probabilité que $k$k fichiers aient des empreintes toutes différentes est $\left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right)\cdots \left(1-\frac{k-1}{N}\right)$(1-1/N)(1-2/N)…(1-(k-1)/N).

   En passant au logarithme et en utilisant $\ln (1-x)\approx -x$ln(1-x)≈-x pour $x$x petit : $\ln P\approx -\frac{1+2+\cdots +(k-1)}{N}=-\frac{k(k-1)}{2N}\approx -\frac{k^2}{2N}$ln P≈-(1+2+…+(k-1))/N=-(k(k-1))/2N≈-k²/2N. Donc $P\approx e^{-k^2/(2N)}$P≈ e^(-k²/(2N)).

   Une collision a une chance sur deux quand $P=\frac{1}{2}$P=1/2 : $\frac{k^2}{2N}=\ln 2$k²/2N=ln2, soit $k=\sqrt{2\ln 2\cdot N}\approx 1,18\sqrt{N}$k=√(2ln2· N)≈1,18 √N. Pour $N=365$N=365, on retrouve 23 personnes. Pour une empreinte de 64 bits, $N=2^{64}$N=2⁶⁴ et $k\approx 1,18\times 2^{32}\approx 5$k≈1,18×2³²≈5 milliards : un nombre atteint par les grandes bases de données.

3. 3. NSI : choisir la taille de l'empreinte

   3 min

   Une empreinte de $n$n bits n'offre donc qu'environ $n/2$n/2 bits de sécurité contre les collisions. Pour SHA-256, il faudrait environ $2^{128}$2¹²⁸ fichiers : hors de portée. La fonction MD5 (128 bits) n'est plus utilisée pour la sécurité, car on sait fabriquer des collisions bien plus vite que $2^{64}$2⁶⁴ essais.

   En NSI, le même phénomène existe dans les tables de hachage des dictionnaires Python : les collisions sont fréquentes et gérées par le programme, qui compare ensuite les clés. Pour la sécurité, en revanche, une collision permettrait de remplacer un fichier par un autre sans que l'empreinte change.

4. 4. Conclusion

   1,5 min

   Les collisions apparaissent bien plus tôt qu'on ne le croit : vers la racine carrée du nombre d'empreintes. C'est pourquoi les empreintes de sécurité font 256 bits. J'ouvre sur le stockage des mots de passe, qui utilise aussi le hachage.

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

• Croire qu'il faut N/2 fichiers pour une collision.
• Confondre trouver une collision quelconque et trouver un fichier ayant une empreinte donnée (2ⁿ essais).
• Oublier que l'approximation suppose k petit devant N.

Revoir les notions

• Probabilités conditionnelles et indépendance (Terminale spé maths) →
• Fonction exponentielle (Terminale spé maths) →

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 ?
• Pourquoi un site ne doit-il jamais stocker nos mots de passe, et à quoi sert le « sel » ?

Toutes les questions maths-nsi →