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...