On 20 Sie, 16:41, "prorok" <p...@t...nie.adres> wrote:
> Użytkownik "hubert depesz lubaczewski" <d...@d...com> napisał w
> wiadomościnews:7e92k7-ffc.ln1@depesz.com...
>
> > nie za bardzo chce mi się liczyć dla 50%, ale 40% prawdopodobieństwo
> > jest przy 2^64 plików.
>
> Skąd taka mała ilość? Przypuszczałbym że skoro dla dwóch plików jest rzędu
> 1/2^128 to prawdopodobieństwo 50% byłoby jeśli nie dla ilości 2^128, to
> przynajmniej 2^127, skąd nagle wychodzi spierwiastkowana liczba?

No wasnei, nie chcemy uniknac tego, ze ostatni md5 nie powtarza
sie z innymi, ale, ze zadne dwie sumy nie sa takie same.

http://pl.wikipedia.org/wiki/Paradoks_dnia_urodzin

Jakie jest prawdopodobienstwo, ze n probkach kazda trafi
w inna liczbe. niech m = 2^128.

Pierwsza moze byc dowolna, 1. Druga moze przyjac wartosc
dowolna poza juz przybrana, trzecia - poza dwoma juz zajetymi
wiec (1-1/m) i (1-2/m)

Lacznie p=iloczyn_{i=1..n} ( 1 - i/m )

liczenie na piechote zajeloby troche komputerowi,
wiec trzeba kombinować. Zalozmy ze n<<m.

Nazwijmy nasza wielkosc przez p i zlogarytmujmy,
oraz skorzystajmy z log(1+x)=x (tu przydatne zalozenie)

log p = - (1/m + 2/m + ...+ n/m) = - [n(n+1)/m]/ m=~= -n^2/(2m)

p=exp(-n^2/2m)

Nasz interesuje prawdopodobienstwo, ze wystapi co najmniej
jedna kolizja, czyli 1-p

1-exp (-n^2/2m) = a. a=1/2, 1/10, 1/100

exp(-n^2/2m) = 1-a
n=sqrt( -2m*log(1-a) )

a=1/2, n= 2.17e19 [hmm, mniej niz obok podawane, moze sie
gdzies kopnalem, moze juz przyblizenie za grube]
a=1/10 n=8e18
1/100 n= 2e18

dla malych a mozna uzyc [modulo ewentualny blad w rachunkach]
n=sqrt( 2m*a ) = 2.6e19 *sqrt(a)

pozdrawiam
bartekltg

do góry

On Fri, 20 Aug 2010 07:15:13 +0100, ptoki <s...@g...com> wrote:

> Mam duzy zestaw plikow.
> Jak ksztaltuje sie prawdopodobienstwo wystapienia kolizji md5-ek tych
> plikow w funkcji ich ilosci?
>
> Podchodząc do sprawy liniowo wiem ze skoro md5 jest 128 bitowe to
> 2^128 plikow+1 wygeneruje kolizje.
> Ale nie wiem jak md5 sie zachowuje dla plikow ktore sa do siebie
> troche podobne (np formularze wypelnione podobnymi danymi).

Żeby mieć 50% szansy na kolizję musiał byś hashować 6 miliardów plików na
sekundę, każdej sekundy, przez 100 lat.

--
http://pornel.net
this.author = new Geek("porneL");

do góry

On 20 Sie, 17:26, bartekltg <b...@g...com> wrote:
> On 20 Sie, 16:41, "prorok" <p...@t...nie.adres> wrote:
>
> > Użytkownik "hubert depesz lubaczewski" <d...@d...com> napisał w
> > wiadomościnews:7e92k7-ffc.ln1@depesz.com...
>
> > > nie za bardzo chce mi się liczyć dla 50%, ale 40% prawdopodobieństwo
> > > jest przy 2^64 plików.
>
> > Skąd taka mała ilość? Przypuszczałbym że skoro dla dwóch plików jest rzędu
> > 1/2^128 to prawdopodobieństwo 50% byłoby jeśli nie dla ilości 2^128, to
> > przynajmniej 2^127, skąd nagle wychodzi spierwiastkowana liczba?
>
> No wasnei, nie chcemy uniknac tego, ze ostatni md5 nie powtarza
> sie z innymi, ale, ze zadne dwie sumy nie sa takie same.
>
> http://pl.wikipedia.org/wiki/Paradoks_dnia_urodzin
>
> Jakie jest prawdopodobienstwo, ze n probkach kazda trafi
> w inna liczbe. niech m = 2^128.
>
> Pierwsza moze byc dowolna, 1. Druga moze przyjac wartosc
> dowolna poza juz przybrana, trzecia - poza dwoma juz zajetymi
> wiec (1-1/m)  i (1-2/m)
>
> Lacznie p=iloczyn_{i=1..n}  ( 1 - i/m )
>
> liczenie na piechote zajeloby troche komputerowi,
> wiec trzeba kombinować. Zalozmy ze n<<m.
>
> Nazwijmy nasza wielkosc przez p i zlogarytmujmy,
> oraz skorzystajmy z log(1+x)=x (tu przydatne zalozenie)
>
> log p = - (1/m + 2/m + ...+ n/m) = - [n(n+1)/m]/ m=~= -n^2/(2m)
>
> p=exp(-n^2/2m)
>
> Nasz interesuje prawdopodobienstwo, ze wystapi co najmniej
> jedna kolizja, czyli 1-p
>
> 1-exp (-n^2/2m) = a.  a=1/2, 1/10, 1/100
>
> exp(-n^2/2m) = 1-a
> n=sqrt(  -2m*log(1-a) )
>
> a=1/2, n= 2.17e19 [hmm, mniej niz obok podawane, moze sie
> gdzies kopnalem, moze juz przyblizenie za grube]
> a=1/10 n=8e18
> 1/100 n= 2e18
>
> dla malych a mozna uzyc [modulo ewentualny blad w rachunkach]
> n=sqrt(  2m*a ) = 2.6e19 *sqrt(a)
>
Dziekuje wszystkim za sugestie.
Okazalo sie ze w rozwiazaniu ktore analizuje rzeczywiscie porownywany
jest i md5 i rozmiar. Niestety nie znalazlem informacji ze md5
zachowuje sie "liniowo" czyli ze wszystkie 128 bitow zaleza od
zawartosci pliku jednakowo. Czyli ze rzeczywiscie mamy do czynienia z
przestrzenia ktora jestesmy w stanie wykorzystac w calosci.

Ale i tak wszystkie podane wielkosci (2^64, 2^127, 2,6e19 *sqrt(0,5) )
same w sobie sa dosyc duze.

Nie zmienia to tego ze juz zhashowanie tylko 2 różnych plikow moze
wygenerowac kolizje :).

--
Lukasz Sczygiel

do góry