Paradoxe des anniversaires

Le paradoxe des anniversaires est une étude probabiliste qui calcule les chances que deux objets d'un groupe partagent une même propriété issue d'un ensemble fini.

Illustration

Par exemple, il permet d'affirmer qu'il suffit de rassembler 23 personnes au hasard pour avoir une chance sur deux que deux de ces 23 personnes soient nées le même jour. Etant donné qu'il y a 365 jours dans l'année, on s'attendrait à beaucoup plus.

Ce résultat vient du fait qu'on ne fixe pas de date. Si l'énoncé était "Quelle est la probabilité qu'une personne ait la même date d'anniversaire que moi, alors les probabilités seraient beaucoup plus faibles.

Calcul

La démonstration de ce paradoxe (qui n'en est un que dans le sens où il contredit l'intuition) se fait en calculant la probabilité inverse : celle que toutes les personnes soient nées un jour différent. La démonstration se fait par récurence. Si on a deux personnes, la première peut être née n'importe quand, la seconde n'importe quel autre jour :

P(2) = 364/365 = 1 - 364/365

Si on a trois personnes, alors la troisième peut être née n'importe quand, mis à part les deux jours déjà "pris" :

P(3) = P(2) * ( 1 - 364/365 )

Pour n personnes, on obtient de même :

P(n) = P(2) * P(3) * ... * P(n-1) * ( 1 - (n-1)/365 )

Ce qui donne :

Nombre de personnes	Probabilité
1	1
2	0,99
5	0,97
10	0,88
20	0,58
23	0,59
30	0,29
50	0,03

Applications à la cryptanalyse

Le paradoxe des anniversaires est utilisé en cryptanalyse, notamment pour l'étude des fonctions de hashage, et les calculs de pré-image. En effet, alors qu'il est extrêment complexe de trouver, pour un hash donné, une entrée qui fournira le même hash (complexité de l'ordre de 2^k, où k est la taille en bits du hash, celle-ci est beaucoup réduite (2^(k/2)) lorsqu'on cherche deux entrées fournissant le même hash.

Cela peut paraitre le même problème, mais pourtant, dans le deuxième cas, on laisse libre les deux entrées et le hash, alors que dans le premier le hash est fixé.

C'est exactement la même différence entre "Trouver deux personnes ayant la même date d'anniversaire", et "Trouver une personne née le même jour que moi", c'est-à-dire le paradoxe des anniversaires.

La recherche de seconde pré-image et de collisions voit donc sa complexité fortement diminuée par ce paradoxe. C'est en partie ce qui a coûté la via à MD5.