Autor: Piotr Gabryanczyk (pg174716_at_students.mimuw.edu.pl)
Data: Mon 12 Jul 1999 - 20:09:30 MET DST
On Sun, 20 Jun 1999, Zbyszek wrote:
> Witam
>=20
> Prosz=EA o informacj=EA, jak zrealizowa=E6 algorytm licz=B1cy sumy kontro=
lne
> dowolnych plik=F3w. Powinien on niezawodnie wykrywa=E6 jakiekolwiek modyf=
ikacje
> pliku, dla kt=F3rego wcze=B6niej wyliczy=B3 checksum=EA. Jednocze=B6nie, =
sama suma
> powinna by=E6 mo=BFliwie ma=B3a.=20
NIEZAWODNY algorytm NIE istnieje, bo takie przeksztalcenie z pliku do
checksum`y to funkcja, ktora zeby byc "niezawodnym przeksztalceniem" musi
byc roznowartosciowa, co oznacza ze rozmiar przeciwdziedziny musi byc co
najmniej taki jak rozmiar dziedziny.
Po ludzku : checksum`a musi byc inna dla kazdych dwoch roznych plikow.
Wezmy wiec plik o rozmiarze 100 bajtow. Ile jest takich roznych plikow ?
odpowiedz : X=3D 256 do potegi 100, wiec przeciwdziedzina musi przyjmowac c=
o
najmniej X wartosci a taka liczbe da sie zapisac w 100 bajtach !=20
Wniosek z tego ze najlepsza NIEZAWODNA suma kontolna pliku jest jego
kopia, (bo nic nie musimy liczyc).
Jednak nie ma co panikowac, bo istnieja przecierz dobre algorytmy do
sprawdzania poprawnosci tresci plikow (ALE NIE SA NIEZAWODNE).
Xor`y - no te sa ok`ej do momentu gdy ktos nie wpadnie na pomysl ze A xor
B =3D B xor A i moze nas paskudnie oszukac zamieniajac kilka bajtow
miejscami.=20
Liczenie sumy "po chamsku" x[1]+x[2]+...+x[n] tez nie jest za dobre bo ma
to sama wade co xor`y a dodatkowo A+B =3D (A+z) + (B-z)=20
Zatem pozostaje CRC lub kombinacje wlasnych metod zmniejszajacych ryzyko
przeklaman w zaleznosci od rodzaju danych.
Piotr Gabryanczyk
email: piotr.gabryanczyk_at_students.mimuw.edu.pl
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Tue 18 May 2004 - 18:45:08 MET DST