Paradoxe des anniversaires
La notion de collision est importante pour les fonction de hachage cryptographiques. Autrement dit f étant une fonction de hachage on ne doit pas pouvoir calculer en pratique deux messages distincts x et y tels que f(x)=f(y). Or la probabilité quand on prend x et y au hasard d'obtenir une collision est plus grande qu'il pourrait paraître à première vue. Par exemple quand on prend 20 personnes au hasard, il y a une probabilité voisine de ½ qu'au moins deux d'entre elles aient le même jour d'anniversaire. Il n'est donc pas simple de construire des fonctions de hachage, et la taille des messages hachés ne doit pas être trop courte si on veut justement éviter ce phénomène appelé paradoxe des anniversaires. Cette taille doit en pratique être le double de celle des clés d'un circuit de chiffrement par bloc assurant la même résistance aux attaques.