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

Все о программировании под *nix
Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

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

Сообщение Victor Gr. »

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

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

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

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

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

Дзякуй!

Аватара пользователя
Llama
Неотъемлемая часть форума
Сообщения: 9749
Зарегистрирован: 06 фев 2002, 11:40
Откуда: Менск

Сообщение Llama »

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

Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

Сообщение Victor Gr. »

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

Аватара пользователя
Llama
Неотъемлемая часть форума
Сообщения: 9749
Зарегистрирован: 06 фев 2002, 11:40
Откуда: Менск

Сообщение Llama »

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

michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

Сообщение michael »

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

Ответить