Re: [gull] Petit problème d =?UTF-8?Q?e_maths, _pour_cr=C3=A9er_de_liens?=

[Marc Mongenet]

Bonsoir,

Le 30 avril 2008 22:58, Félix Hauri <felix at f-hauri.ch> a écrit :
>
> Ma question:
> Si plutot que de comparer l'intégrité des fichiers lors de la deuxième passe,
> à partir de quel pourcentage de fichier comparé, je peux considérer que les
> deux fichiers sont identique, s'ils ont le même md5?
>
> Question subsidiaire:
> Est-ce qu'une combinaison différente offrerait des perspectives à étudier?
> Je m'essplike: En admettant que si j'utilise md5, je dois comparer 50%
> pour être à peu près tranquille, mais qu'en utilisant md160 je pourrais
> me contenter de comparer 25% pour le même niveau de ``certitude'',
> alors je planifierais une série de tests afin de déterminer le processus
> le plus rapide.
>
>
> --
>  Félix Hauri  -  <felix at f-hauri.ch>  -  http://www.f-hauri.ch

MD5 étant cracké, s'il faut se protéger contre des collisions
malicieuses, alors il faut comparer l'intégralité des fichiers.

S'il ne faut se protéger que contre des collisions accidentelles,
alors les maths derrière me semblent être celles de
http://en.wikipedia.org/wiki/Birthday_attack
en faisant l'hypothèse qu'un hashage MD5 peut donner
2^128 hashes équiprobables.
L'article contient toute une table qui se conclut par :
    Table shows number of hashes n(p) needed to achieve the
given probability of success, assuming all hashes are equally
likely. For comparison, 10−18 to 10−15 is the uncorrectable
bit error rate of a typical hard disk [1]. In theory, MD5, 128
bits, should stay within that range until about 820 billion
documents, even if its possible outputs are many more.

-- 
Marc Mongenet
Creator of the Web 2 Markup Language
http://w2ml.com