Статьи Галерея Форум Чат Файлы HowTo Ссылки Поиск
Текущее время: 14 окт 2019, 03:03




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
СообщениеДобавлено: 15 апр 2006, 02:47 
Неотъемлемая часть форума
Аватара пользователя

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

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

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

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

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

Дзякуй!


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 15 апр 2006, 10:56 
Неотъемлемая часть форума
Аватара пользователя

У нас с: 06.02.2002
Сообщения: 9760
Откуда: Менск
естественно ;)
В случае когда длинна данных больше длинны хэша повторы неизбежны, вопрос только в вероятности коллизии.

_________________
Опыт растет прямо пропорционально выведенному из строя оборудованию


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 15 апр 2006, 11:31 
Неотъемлемая часть форума
Аватара пользователя

У нас с: 13.08.2004
Сообщения: 891
Откуда: Минск
Llama, а можна неяк вылічыць верагоднасць калізіі ў гэтым выпадку?

_________________
https://grinchik.com/


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 15 апр 2006, 14:46 
Неотъемлемая часть форума
Аватара пользователя

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

_________________
Опыт растет прямо пропорционально выведенному из строя оборудованию


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 15 апр 2006, 16:07 
Неотъемлемая часть форума

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


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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
[ All resources are available under GNU GPL ] [ Support ] [ Hosted by DataHata | MyCloud.by ] [ Powered by phpBB® Forum Software © phpBB Group ]

LVEE Winter LVEE Rambler's Top100