Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
Le 12887ième jour après Epoch, François Boisson écrivait: > PS: A titre indicatif, c'est en gros 1 fois plus que le nombre de > grains de blés sur l'échiquier. Si on met ces adresses dans un annuaire > comme celui de la poste (400 adresses par pages, 3cm pour 1000 pages), > on obtient un annuaire épais de 6,5 billions de km (millions de > millions) soit 43000 fois la distance terre soleil. Bref, c'est > gros. Oui, mais si tu compresses les données et que tu graves ça sur CD, ça prendra peut-être moins de place, non? D'ailleurs, j'aimerais bien savoir combien de temps il faudra pour compresser ça ;) -- Pensez à lire la FAQ de la liste avant de poser une question : http://wiki.debian.net/?DebianFrench Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:" To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
Le Tue, 12 Apr 2005 19:00:34 +0200 Vincent DUVERT <[EMAIL PROTECTED]> a écrit: > > 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=4294967296 > > 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. D'après ce que je viens de calculer, en gros 15 chances sur 1 million qu'il existe 2 adresses ayant la même md5sum en comptant une adresse par personne et 6 milliards d'habitants. En fait, sur un choix de n adresses, la probabilité qu'il y ait une différences 20 premiers caractères de la md5sum est comprise entre exp[-n²/(2N.(N-n))] et exp[-n(n+1)/(2N²)] avec N=16^20. J'obtiens que pour avoir 1 chance sur 100 d'avoir deux adresses avec des md5sum distinctes, il faut prendre entre 1,5.10^23 et 1,7.10^23 adresses, ça monte à 50 fois plus d'adresses pour porter ces chances à 9 chances sur 10 (tant qu'à faire, autant aller jusque là). Bref, je me retire du concours... François Boisson PS: A titre indicatif, c'est en gros 1 fois plus que le nombre de grains de blés sur l'échiquier. Si on met ces adresses dans un annuaire comme celui de la poste (400 adresses par pages, 3cm pour 1000 pages), on obtient un annuaire épais de 6,5 billions de km (millions de millions) soit 43000 fois la distance terre soleil. Bref, c'est gros. -- Pensez à lire la FAQ de la liste avant de poser une question : http://wiki.debian.net/?DebianFrench Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:" To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
Comput unicum 1113334743 (Tue, 12 Apr 2005 21:39:03 +0200), [EMAIL PROTECTED] a écrit : > > Salut, > > Sylvain Sauvage a écrit : > >> > >>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=4294967296 > > > > Tu veux dire 36^20, je suppose. > > Vous êtes vraiment tous mauvais ! :-D > Le hash MD5 qu'on a l'habitude de voir est la représentation > hexadécimale d'un nombre codé sur 128 bits, les caractères ne peuvent > donc prendre que 16 valeurs [0-9a-f]. Si on n'en prend que 20, ça fait > 16^20 = 2^80 ~ 1,2*10^24 combinaisons. Oui, 1208925819614629174706176. J'ai relevé les erreurs de calcul mais pas d'énoncé. (Même quand on ne manipule pas les md5 tous les jours, on devrait savoir que c'est de l'hexa.) Mais, bon, ça ne change pas trop le problème. Même avec une approximation de n!, yacas n'arrive pas à calculer nos chances... -- Sylvain Sauvage
Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
Comput unicum 111197 (Tue, 12 Apr 2005 21:13:17 +0200), mailing-list a écrit : > > LOL, tu m'as fais comprendre à quoi servait les maths :p Sans vouloir t'offenser, j'espère qu'un jour tu comprendras à quoi servent la grammaire et l'orthographe ;o) > Le mardi 12 avril 2005 à 20:48 +0200, Sylvain Sauvage a écrit : >[...] > > 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... > dit le :) c'est impossible :p Ce n'est pas impossible. Il suffit d'un peu de chance et de deux adresses pour que cela arrive. La formule que je donnais donne la probabilité de trouver deux adresses qui donnent le même md5 tronqué dans un paquet de n adresses. Ce qui prend du temps, c'est le calcul de cette proba avec un milliard d'adresses. J'aurais mieux fait de lancer une recherche aléatoire plutôt que le calcul de la proba. [EMAIL PROTECTED] de factorielle qui ne se simplifie pas (en tout cas, je ne sais pas et Yacas non plus). Y a pas un vrai mathématicien dans la salle ? > à par si t'as du bolle mais domage, falait joué au loto car t'avais plus > de chance de gagné :p Je ne sais pas, je n'ai pas fini le calcul de la proba. Je suis sérieux là : tant que je ne connais pas la proba, je ne sais pas si je ferais mieux de jouer au loto. En tout cas je sais que ça ne sert à rien de jouer au loto : les rapports sont meilleurs au casino (au Casino aussi d'ailleurs, comme à Carrouf, Monoprix, Leclerc... ;o). Remarquez que les spammeurs ont tout un lot d'adresses. Si vous leur demandez gentiment, ils pourraient vous les prêter pour le calcul ;o) -- Sylvain Sauvage Décidément, le vendredi tombe tôt en cette saison.
Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
Salut, Sylvain Sauvage a écrit : 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=4294967296 Tu veux dire 36^20, je suppose. Vous êtes vraiment tous mauvais ! :-D Le hash MD5 qu'on a l'habitude de voir est la représentation hexadécimale d'un nombre codé sur 128 bits, les caractères ne peuvent donc prendre que 16 valeurs [0-9a-f]. Si on n'en prend que 20, ça fait 16^20 = 2^80 ~ 1,2*10^24 combinaisons. -- Pensez à lire la FAQ de la liste avant de poser une question : http://wiki.debian.net/?DebianFrench Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:" To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
mailing-list a écrit : LOL, tu m'as fais comprendre à quoi servait les maths :p Le mardi 12 avril 2005 à 20:48 +0200, Sylvain Sauvage a écrit : 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 à 10^4 = 1 -> 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=4294967296 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... dit le :) c'est impossible :p à par si t'as du bolle mais domage, falait joué au loto car t'avais plus de chance de gagné :p Ben c'est assez chouette je devrais pas payé ma bière (je m'en doutais un peu...) -- +-+ | Stephane Witryk | | [EMAIL PROTECTED] | +-+
Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
LOL, tu m'as fais comprendre à quoi servait les maths :p Le mardi 12 avril 2005 à 20:48 +0200, Sylvain Sauvage a Ãcrit : > 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 à > > 10^4 = 1 -> 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=4294967296 > > 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... dit le :) c'est impossible :p à par si t'as du bolle mais domage, falait jouà au loto car t'avais plus de chance de gagnà :p > -- Pensez à lire la FAQ de la liste avant de poser une question : http://wiki.debian.net/?DebianFrench Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:" To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
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 à > 10^4 = 1 -> 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=4294967296 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
Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
Le 12885ième jour après Epoch, Vincent DUVERT écrivait: > 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 à > 10^4 = 1 -> 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=4294967296 Non, 20^36 = 68719476736, c'est à dire 16 fois plus... > 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. Conclusion hâtive, mais bon. > Et puis, je crains ne pas avoir la puissance nécessire pour calculer > tout ça avant vendredi... :-) Et si on s'y mettait à plusieurs: Nouveau challenge pour distributed network. Grande récompense: Une bière. -- Pensez à lire la FAQ de la liste avant de poser une question : http://wiki.debian.net/?DebianFrench Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:" To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: [HS Grand concours] Re: Re: Rép: [HS] fonction de hash
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 à 10^4 = 1 -> 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=4294967296 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. Et puis, je crains ne pas avoir la puissance nécessire pour calculer tout ça avant vendredi... :-) Le réglement complet a été déposé auprès de Maitre Couillard à Issy les moulineaux. Contactez moi pour récupérer le réglement complet. Remboursement du timbre sur simple demande :-) -- Pensez à lire la FAQ de la liste avant de poser une question : http://wiki.debian.net/?DebianFrench Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:" To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
[HS Grand concours] Re: Re: Rép: [HS] fonction de hash
--- Stéphane Witryk <[EMAIL PROTECTED]> wrote: > > pingouin osmolateur a écrit : > > > Le pb c'est que mon condensé n'est plus unique > puisque > > je tronque les derniers caractéres > > Un md5 n'est pas "unique" non plus. Il y a juste que > tu augmentes la > probabilité de collisions en écourtant le md5. Mais > bon si tu me trouves > deux hash md5 d'emails valides qui ont les mêmes 20 > premiers caractères > je te paye une bière :) > 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. Le réglement complet a été déposé auprès de Maitre Couillard à Issy les moulineaux. Contactez moi pour récupérer le réglement complet. Remboursement du timbre sur simple demande :-) > -- > +-+ > | Stephane Witryk | > | [EMAIL PROTECTED] | > +-+ > > __ Découvrez le nouveau Yahoo! Mail : 250 Mo d'espace de stockage pour vos mails ! Créez votre Yahoo! Mail sur http://fr.mail.yahoo.com/ -- Pensez à lire la FAQ de la liste avant de poser une question : http://wiki.debian.net/?DebianFrench Pensez à rajouter le mot ``spam'' dans vos champs "From" et "Reply-To:" To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
