Probleme – Le paradoxe des anniversaires, démontré et mesuré

1. La formule. On tire $k$ clés, indépendamment et uniformément, dans $m$ cases. Notons $A_k$ l'événement « les $k$ hachés sont deux à deux distincts ». On conditionne : sachant que les $i$ premières clés sont distinctes, la $(i+1)$-ième évite les $i$ cases déjà prises avec probabilité $(m-i)/m=1-i/m$. D'où, par la formule des probabilités composées,

$$\mathbb{P}(A_k)=\prod _{i=0}^{k-1}(1-\frac{i}{m}).$$

Le premier facteur vaut $1$ — la première clé ne peut entrer en collision avec personne —, et le produit est nul dès $k>m$, ce qui redonne le principe des tiroirs.

2. L'ordre de grandeur. On passe au logarithme et l'on emploie $\ln (1-x)\approx -x$ pour $x$ petit :

$$\ln \mathbb{P}(A_k)=\sum _{i=0}^{k-1}\ln (1-\frac{i}{m})\approx -\sum _{i=0}^{k-1}\frac{i}{m}=-\frac{k(k-1)}{2m},$$

soit $\mathbb{P}(A_k)\approx e^{-k^2/(2m)}$. Cette quantité vaut $1/2$ pour

$$k\approx \sqrt{2\ln 2}\sqrt{m}\approx 1,1774\sqrt{m}.$$

Le seuil est en $\sqrt{m}$, et c'est tout le paradoxe : l'intuition attend un seuil proportionnel à $m$ — « il faut à peu près autant de clés que de cases » —, et la réalité en demande la racine. Pour $m=365$, cela fait $22,5$ au lieu de $183$.

L'explication tient en un comptage : il n'y a pas $k$ occasions de collision mais $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\approx k^2/2$ paires de clés, chacune entrant en collision avec probabilité $1/m$. Le nombre moyen de collisions vaut donc $k^2/(2m)$, et il atteint $1$ dès $k\approx \sqrt{2m}$. On raisonne sur les paires, pas sur les clés.

3. Les calculs. Mesuré par évaluation exacte du produit :

L'approximation est exacte à l'unité près dès $m=1024$. Et pour $m=365$, $k=23$ : mesuré, $\mathbb{P}(A_{23})=0,4927$, donc une collision avec probabilité $0,5073$ — le chiffre du chapitre est confirmé.

Vérification par simulation, $200000$ tirages de $23$ clés dans $365$ cases : fréquence observée d'au moins une collision $0,5070$, contre $0,5073$ prédits. On ne se contente pas d'une formule : on la met à l'épreuve d'un tirage.

4. Les empreintes de $64$ bits. Avec $m=2^{64}\approx 1,8\cdot 10^{19}$, le seuil est $1,1774\sqrt{m}\approx 5,1\cdot 10^9$ — cinq milliards. Une empreinte de $64$ bits entre en collision, plus probablement qu'autrement, dès qu'on en calcule cinq milliards : c'est atteignable par une machine moderne en quelques heures. Une empreinte de $32$ bits, elle, cède à $77000$ valeurs — quelques secondes.

C'est pourquoi les empreintes cryptographiques font $256$ bits et non $64$ : contre une attaque qui exploite le paradoxe des anniversaires, un condensat de $b$ bits n'offre que $b/2$ bits de sécurité. La longueur d'une empreinte se lit toujours divisée par deux.