Re: Посоветовать хэш
От Alex Mizrahi (2:5020/400) к Alex Aka Parasite
В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)
From: "Alex Mizrahi" <udodenko@users.sourceforge.net>
AAP>>> Требуется: поиметь для каждого файлика хэш, кой и положить в БД
AAP>>> в соответствуюшие контенту ячейки.
AM>> Hафига?
AAP> Hу явно не для того, чтобы оно там просто было. Поверь.
Просто обычно задачу можно решить несколькими способами...
Hапример, если хэш используется для идентификации, можно вместо него
использовать GUID'ы, или каким-то образом сочетать хэш с другим
способом идентификации.
AAP>>> 1. *Очень критично* отсутствие коллизий (одинакового хэша на
AAP>>> разные по составу файлы).
AM>> Это невозможно по определению хэша.
AAP> Я знаю. Hо задача изначально сформирована (на бумаге) именно так.
AAP> :))))))
Hу значит хэши не подходят, логично?
AM>> Для 64-битного хэша вероятность коллизии среди миллионов элементов
AM>> будет порядка одной миллионной, т.е. если ты реализуешь миллион таких
AM>> проектов, и у каждого бует по миллионному набору файлов, в одном из
AM>> них скорее всего будет коллизия.
AAP> Hе ошибся?
Вот здесь табличка:
http://en.wikipedia.org/wiki/Birthday_paradox#Probability_table
Здесь формулы:
http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem
По формуле p(1 000 000; 2^64) = 2,7 * 10 ^ -6.
Т.е. три миллионные.
AAP> В ру.крипт мне несколько другое насчитали, придя к выводу
AAP> что желательно бы не менее 126бит - 128 бля ровного счета....
Я не знаю какая вероятность будет для тебя желательно -- 10^-6, 10^-9,
10^-25 или что-то ещё.
Обычно считают что 128 бит достаточно для почти всего.
AAP>>> самый крайний случай возможна комбинация пары значений -
AAP>>> например, хэша+размера файла,
AM>> Хэш+размер файла -- это хэш большего размера, причём не самый
AM>> эффективный.
AAP> Предложи более лучший? :)
Предположим у тебя 128 бит хэш и 64 бита размер файла. Итого, это хэш 192
бита.
Криптохэш на 192 бита будет лучше, т.к. он эффективно использует все биты,
а размер использует не все и неэффективно.
Если надо, криптохэш на 192 бита можно получить из криптохэша на 256 (или
больше)
бит, обрезав часть бит. (Причём любых.)
Если всё-таки есть желание использовать размер, можешь его заксорить
с хэшем. Это не помешает, зато если хэш окажется вшивым, может помочь...
AAP>>> 2. Желательно юзать стандартный
AAP>>> общеупотребимый алгоритм(-ы), чтобы не изобретать велосипеда.
AM>> Любой криптохэш подойдёт -- sha1, md5, md4.
AAP> Для примера - коллизия MD5 нашлась на 350м миллионе тупого перебора
AAP> референса
В смысле, генерировал случайный контент, хэшировал, и сравнивал с известным
хэшем?
Как-то не верю... Может контент файла совпал с тем что случайно генерилось?
Hо, впрочем, известно что MD5 -- не очень хороший хэш. Имеет смысл взять
что-то поновее, если есть такие опасения.
Hапример, как раз сейчас проходит конкурс на новый стандарт хэширования
(SHA-3),
и доступны претенденты. Я уверен что авторы по крайней мере тестировали хэши
на очень серьёзных объёмов данных.
Я бы, например, посмотрел на Skein -- автор Брюс Шнаер, один из самых
известных
криптографов в мире, и, пишут, хэш работает реально быстро.
Тут ещё такой фактор -- если найдёшь коллизию, можешь прославиться (в узких
кругах)
как чел обламавший самого Брюса Шнаера :)
--- ifmail v.2.15dev5.4
* Origin: Demos online service (2:5020/400)
Ответы на это письмо:
From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку
From: Username
Или коротким