Страница 1 из 1
Дапамажыце калі ласка з разуменнем хэшу
Добавлено: 15 апр 2006, 02:47
Victor Gr.
Вось якое пытанне, адзінае, што мне трэба зразумець. І хоць розумам я ўсё разумею, але ж сэрца нешта не жадае верыць, просіць пацвярджэнне
Справа вось у чым.
Возьмем хэш-функцыю CRC16. Так? Яна робіць з дадзеных хэш даўжынёй 16 бітаў. (значыць усяго магчыма толькі 65536 варыянтаў).
І дадзеныя даўжынёй 32 біт. А іх усіх не болей за 4294967296 варыянтаў.
І калі мы зробім з УСІХ 32-бітавых дадзеных хэш даўжынёй 16 біт... Я правільна разумею, што сярод хэшаў АБАВЯЗКОВА будуць паўторы (калізіі)?
Дзякуй!
Добавлено: 15 апр 2006, 10:56
Llama
естественно
В случае когда длинна данных больше длинны хэша повторы неизбежны, вопрос только в вероятности коллизии.
Добавлено: 15 апр 2006, 11:31
Victor Gr.
Llama, а можна неяк вылічыць верагоднасць калізіі ў гэтым выпадку?
Добавлено: 15 апр 2006, 14:46
Llama
Victor Gr., я не специалист, но:
допустим, длинна хэша n элементов (например бит), количество возможных престановок элементов хэша Xn (уникальных значений)
длинна контента m элементов, количество возможных перестановок элементов контента Xm
тогда вероятность коллизии для идеального алгоритма хэширования - Xn/Xm и эта вероятность кореллирует с n/m.
Т.к. реальные алгоритмы хэширования не идеальны, то и вероятность на практике будет выше. Примеров со "взломом" shaX и mdX хватает...
Добавлено: 15 апр 2006, 16:07
michael
Llama писал(а):Victor Gr., я не специалист, но:
допустим, длинна хэша n элементов (например бит), количество возможных престановок элементов хэша Xn (уникальных значений)
длинна контента m элементов, количество возможных перестановок элементов контента Xm
тогда вероятность коллизии для идеального алгоритма хэширования - Xn/Xm и эта вероятность кореллирует с n/m.
Т.к. реальные алгоритмы хэширования не идеальны, то и вероятность на практике будет выше. Примеров со "взломом" shaX и mdX хватает...
В этом определении что-то не так... Если контент состоит из одинаковых элементов, Xm=1, в тоже время Xn может быть и больше единицы. И чему тогда равна вероятность?