Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
Comput unicum 1113325234 (Tue, 12 Apr 2005 19:00:34 +0200),
Vincent DUVERT a écrit :
>
> pingouin osmolateur a écrit :
>
> > Attention : en suivant la bonne idée de Stephane,
> > Je propose pour vendredi (jour du Troll) de trouver de
> > 2 emails "valides" ayant les memes 20 premiers
> > caratéres du condensé md5 identiques.
> > Stéphane m'offre la biere et moi j'offre la biere aux
> > deux adresses email.
> >
> > A vos marques !!!
> > Je sens que les machines vont tourner à bloque pour
> > trouver les deux adresses.
>
> Bon, alors :
> Nombre de possibilités d'une combinaison = (Nombre de possibilités par
> signe)^(Nombre de signes)
>
> Exemple : Un compteur de 0000 à 9999
> 10^4 = 10000 -> correct.
>
> MD5 : 32 caractères (on ramène à 20, vu que pour le concours les 12
> derniers sont ignorés), avec chacun 36 possibilités (a-z 0-9)
> 20^32=429496729600000000000000000000000000000000
Tu veux dire 36^20, je suppose.
Soit 13 367 494 538 843 734 067 838 845 976 576.
(Ce qui est beaucoup moins que 32 chiffres à 20 possibilités par chiffre.)
> Légèrement plus que le nombre d'internautes dans le monde... Donc c'est
> pas sûr qu'il y ait 2 adresses dans le monde qui aient la même somme
> md5.
Il n'est pas nécessaire d'avoir plus de 365 personnes dans un groupe pour
avoir des chances suffisamment grandes d'en avoir deux avec le même
anniversaire (jour et mois, pas année). Dès qu'on dépasse 23 personnes, la
probabilité dépasse 50 % !
La probabilité pour que deux adresses donnent le même md5 tronqué est la
probabilité complémentaire du cas où les md5 diffèrent. Donc 1 - (N-1)/N.
Pour 3 adresses : 1 - (N-1)(N-2)/N².
Donc, si je ne me trompe pas, avec n adresses : 1 - N! / [N^n . (N-n)!]
Si on pose n = 1e9 (ce qui est peu), la proba est de : ...
euh, je vous le redirai quand le calcul sera terminé...
ou peut-être même _si_ le calcul termine...
--
Sylvain Sauvage
Reply to: