Atak urodzinowy - perl

[davis166]

Witam.
Muszę stworzyć dwa dokumenty, których funkcje skrótu (liczba 3-cyfrowa, realizowana przez dzielenie modulo przez 999) będą takie same. Oczywiście treść dokumentów musi być różna. Do tego trzeba wykorzystać paradoks urodzinowy. Ktoś wie jak się za to zabrać?
Pozdrawiam

[esp666]

mozna jasniej?

[davis166]

Mam jakąśtam funkcję haszującą. Mam jej dać dwa różne dokumenty, a ona ma mi dać takie same funkcje skrótu. Np. daję "ala ma kota"(pierwszy dokument) i "ola ma psa"(drugi dokument) i dostaję 455 w obu przypadkach (to jest tzw kolizja). Funkcja haszująca bierze każdy znak z dokumentu, zamienia go na liczbę typu int, sumuje liczby i zwraca wynik dzielenia modulo sumy przez 999. Moje zadanie polega na stworzeniu takich dokumentów wykorzystując paradoks urodzinowy (czyli, w tym przypadku, wśród 38 dokumentów szansa, że dwa z nich będą miały takie same funkcje skrótu wynosi nieco ponad 50%). Na marginesie dodam, że mam to napisać w perlu. Mam nadzieję, że było w miarę jasno

[GSG-9]

że mam to napisać w perlu.

w perlu powiadasz znajdz odpowiedni dzial, zacznij cos, z checia pomozemy w miare mozliwosci

[TQM]

Temat ciekawy, postaram sie pokombinowac, tym bardziej ze Perl to moje ulubione narzedzie...

[Teesik]

Witam!
Chciałbym się przywitać,pierwszy post i z góry przeprosić - wiem że odkopuję temat z przed 7 miesięcy,ale według mnie jest na tyle ciekawy aby go odkopać.
Zakładamy że mamy funkcję hashującą,która w moim wypadku dla jednej linijki wygląda tak(dla całego pliku wystarczyłoby zliczyć wszystkie znaki):

sub hash {

$xd = shift;
	for($i = 0;$i < length($xd);$i++)
	{
		$plik += ord(substr $xd,$i,1);
	}
return $plik % 999;

}

Hm,wygląda nadzwyczaj mądrze,jednakże ma jedną podstawową wadę - dzielenie modulo.Co z nim?Jak wiemy,dzielenie modulo to reszta z dzielenia,ok.Nawet gdybyśmy mieli całą biblię,dającą sumę znaków 09582095382093512414,a dzielone modulo wychodziłoby 24,dzielone modulo znów dawałoby...24.
Idźmy więc tym tropem,może 24 jedynki dawałby radę?
Niestety,funkcja "ord" dla "1" daje 43,więc zamiast sumy 24*1=24 mielibyśmy 1032,co mod 999 daje 33(dosyć mylące).
Z pomocą i odsieczą przybyła funkcja chr(),której siostra ord() da w końcu 1.
Więc jak wyglądałby program generujący plik,który dla powyższej funkcji generowałby określony hash?

die "brak kodu do odhaszowania" unless($ARGV[0]);
open $fh,">urodziny.txt" or die "Nie ma takiego pliku";
use warnings;
$hash = chr(1) x $ARGV[0];
if($ARGV[0] == hash($hash))
{
print $fh $hash;
print "atak urodzinowy się udał się,jest w pliku urodziny.txt";
exit();
}

(Wybaczcie,że nie mam zwyczaju pisania tych komentarzy na początku...ale korzystam z ActiveState,więc jak dla mnie jest to zbędne).

Tak,być może nie jest to atak urodzinowy,ale hasze mamy takie same,więc to tak bardziej haksorsko,heh.
Pozdrawiam i dziękuję za uwagę,z chęcią posłucham opinii i ew.błędów. ;x

[TQM]

Chwile zajelo mi polapanie sie o co chodzi w poscie ale na koniec wszystko staje sie jasne :-) Fajny przyklad no i witamy na forum!