Дапамажыце калі ласка з разуменнем хэшу

Victor Gr. · Сообщение **Victor Gr.** » 15 апр 2006, 02:47

Вось якое пытанне, адзінае, што мне трэба зразумець. І хоць розумам я ўсё разумею, але ж сэрца нешта не жадае верыць, просіць пацвярджэнне

Справа вось у чым.

Возьмем хэш-функцыю CRC16. Так? Яна робіць з дадзеных хэш даўжынёй 16 бітаў. (значыць усяго магчыма толькі 65536 варыянтаў).

І дадзеныя даўжынёй 32 біт. А іх усіх не болей за 4294967296 варыянтаў.

І калі мы зробім з УСІХ 32-бітавых дадзеных хэш даўжынёй 16 біт... Я правільна разумею, што сярод хэшаў АБАВЯЗКОВА будуць паўторы (калізіі)?

Дзякуй!

Llama · Сообщение **Llama** » 15 апр 2006, 10:56

естественно

В случае когда длинна данных больше длинны хэша повторы неизбежны, вопрос только в вероятности коллизии.

Victor Gr. · Сообщение **Victor Gr.** » 15 апр 2006, 11:31

Llama, а можна неяк вылічыць верагоднасць калізіі ў гэтым выпадку?

Llama · Сообщение **Llama** » 15 апр 2006, 14:46

Victor Gr., я не специалист, но:
допустим, длинна хэша n элементов (например бит), количество возможных престановок элементов хэша Xn (уникальных значений)
длинна контента m элементов, количество возможных перестановок элементов контента Xm
тогда вероятность коллизии для идеального алгоритма хэширования - Xn/Xm и эта вероятность кореллирует с n/m.
Т.к. реальные алгоритмы хэширования не идеальны, то и вероятность на практике будет выше. Примеров со "взломом" shaX и mdX хватает...

michael · Сообщение **michael** » 15 апр 2006, 16:07

Llama писал(а):Victor Gr., я не специалист, но:
допустим, длинна хэша n элементов (например бит), количество возможных престановок элементов хэша Xn (уникальных значений)
длинна контента m элементов, количество возможных перестановок элементов контента Xm
тогда вероятность коллизии для идеального алгоритма хэширования - Xn/Xm и эта вероятность кореллирует с n/m.
Т.к. реальные алгоритмы хэширования не идеальны, то и вероятность на практике будет выше. Примеров со "взломом" shaX и mdX хватает...

В этом определении что-то не так... Если контент состоит из одинаковых элементов, Xm=1, в тоже время Xn может быть и больше единицы. И чему тогда равна вероятность?