Le paradoxe des anniversaires



  Dans une classe, quelle est la probabilité pour que 2 élèves fêtent leurs anniversaires le même jour? Avec 365 jours par an, une trentaine d'élèves dans la classe, on se dit qu'elle doit être faible...

  Détrompez-vous! On va calculer la probabilité pour que, dans un groupe de k personnes, ces personnes aient toutes un jour d'anniversaire différent.
  • Qd on a 2 personnes, la première peut avoir son anniversaire n'importe quand, la seconde n'importe quel autre jour. On a donc :
  • Quand on a 3 personnes, la troisième doit avoir son anniversaire un jour différent des 2 autres :
  • On peut réitérer le raisonnement. Pour un groupe de k personnes, on obtient :
Une petite application numérique donne :

Nombre de personnes Probabilité pour que les anniversaires tombent tous un jour différent
11
20.99
5 0.97
10 0.88
20 0.58
22 0.52
23 0.49
30 0.29
50 0.03
Il ne faut donc que 23 personnes pour qu'il y ait plus d'une chance sur 2 pour que 2 personnes aient leur anniversaire le même jour, contrairement à ce que l'intuition laisse présumer. A partir de 50 personnes, il n'y a que 3% de chances que tous les anniversaires diffèrent!

  Ce paradoxe a son importance en cryptographie, lorsqu'on étudie les fonctions de hachage. Une telle fonction calcule le résumé d'un texte, en vue de le signer. Pour que cette méthode soit fiable, il ne faut pas que quelqu'un puisse produire 2 textes aux sens très différents, mais donnant le même résumé (ex : l'attaquant produit 2 textes, et introduit de ci, de là, des espaces jusqu'à obtenir le même résumé).

  Si le haché (= le résumé) est codé sur b bits, il y a 2b résumés possibles. Si l'on prend k textes différents, la probabilité pour que 2 textes aient le même haché est donc :
Combien l'attaquant doit-il essayer de textes avant de trouver le même résumé avec une probabilité d'au moins un demi? On va faire quelques approximations, et d'abord, en vue de l'égalité de Taylor :
On a alors :
Il faut donc que :
Une application numérique donne :

Taille du haché (en bits) Nombre de textes à essayer
813
16213
32 54562
64 9,6×109
128 1,5×1019
160 1,0×1024
256 2,8×1038
On considère en général, pour obtenir un niveau de sécurité correct, qu'il faut prendre une taille de résumé d'au moins 128 bits!

Et encore, dans la cryptographie expliquée...


Sommaire de la Cryptographie Expliquée - Plan du site - Retour à la BibM@th - Nous écrire - Tous droits réservés - Frédéric Bayart -