выбор наиболее уникального типа хеша

[soulhunter]

выбор наиболее уникального типа хеша

Здравствуйте.

Задача - выбрать тип хеширования, который дает наиболее большую вероятность получения уникального хеша от строки любой длинны (желательно), вообще строки будут очень длинными по большей части, но могут быть и короткие изредка. Время самого процесса хеширования не так важно, на первом месте уникальность. Пока в поисках остановился на sha512, знаете ли что-нибудь получше?

 

[Mandor]

Длиннее 512 бит не встречал, как вариант:

echo hash('sha512', $st).hash('whirlpool', $st);

P.S. Не могу представить себе задачу, в которой понадобилось бы более 2^512 (= 1.3*10^154) вариантов уникальных хешей.

 

[zerkms]

soulhunter
сколько у тебя вариантов входных данных будет?

 

[soulhunter]

входные данные - это содержимое файлов, количество файлов неограничено

 

[StUV]

количество файлов неограничено

http://phpclub.ru/talk/showthread.php?s=&threadid=115107&rand=12


любой алгоритм хеширования предполагает наличие коллизий
обрисуй кратко задачу и объясни чем не устраивают примитивные алгоритмы разрешения коллизий

 

[soulhunter]

Задача следующая:

Есть робот, он сканирует файлообменные сети DC++, Torrent, Ed2k, FTP сервера и прочие файлохранилища.
Поскольку в каждой из этих сетей своя система хеширования, то, чтобы сопоставить файлы между ними - необходимо их всех скачивать и составлять свой собственный хеш и делать таблицу соответствий. Вот я и ывбираю какой алгоритм хеширования выбрать, чтобы составлять свой хеш. На данный момент сканируются только топ Российских хабов/трекеров/серверов и т.д, потом же планируется сканирование абсолютно всех существующих, поэтому количество файлов будет понятно каким...

 

[AmdY]

не самый сложный хэш плюс размер файла гарантируют уникальность.

 

[vovanium]

необходимо их всех скачивать

Интересно и как ты себе это себе представляешь? Чтобы скачать все файлы одного торрентс.ru понадобится года 3 непрырыного качания на скорости 100 Mbits, это не учитывая того что за эти 3 года там количество контента еще увеличится в несколько раз, плюс нужно поддерживать рейтинг, иначе будут банить

 

[Sad Spirit]

Автор оригинала: AmdY
не самый сложный хэш плюс размер файла гарантируют уникальность.

Рекомендую провести несложный экскремент (можно мысленно): посчитать crc32 всех возможных строк длиной 5 байт и доложить кол-во коллизий.

Но сама задача "скачать все файлы" феерическая, ага.

 

[Wicked]

you made my day

 

[Rin]

24 байта вполне достаточно -- sha1 + filesize

 

[soulhunter]

Да, сочетание хеша и размера у меня уже используется кое-где.
Ну в общем спасибо, понял я ситуацию с хешами.

Вообще проект - это новая поисковая система, по файлам, которая выдает результаты поиска не только по названиям файлов, но и по описаниям + результатам анализа содержимого файлов + результаты выдаются в сопоставленном виде из всех файлообменных систем. Файл достаточно прокачать один раз из одной системы, поэтому в случае с торентом - не обязательно качать все с торентс.ру, один раз скачать файл с любого трекера и все. Естественно нагрузка разпараллелевается - несколько десятков серверов на разных каналах, качают одновременно со всех серверов/хабов/трекеров (в случае с торентом отдача поддерживается). Так же файлы скачиваются по по приоритетности, более популярные первее (музыка, фильмы, игры), и плюс чтобы система работала - необязательно за неделю/месяц/год прокачать все - база может параллельно пополняться, а до этого делается предположительное сопоставление по рамеру, расширению и человеческому подтверждению данного предположения.

Кстати, если кто хочет подробнее узнать о проекте и, если будет желание и возможность поучаствовать - пишите на [email protected]. Только без шуток, я не утверждаю, что получится все желаемое сделать, но очень многое уже реализовано и работает в тестовом виде.

 

[nexen]

echo md5(md5(md5($str))); - обычно так - суть уникальности не в длинне строки

 

[weregod]

nexen, сотрите свой бред, вопрос не в запутывании алгоритма получения хэша, а в уникальности хэша
> echo md5(md5(md5($str)));

 

[nexen]

Автор оригинала: weregod
nexen, сотрите свой бред, вопрос не в запутывании алгоритма получения хэша, а в уникальности хэша
> echo md5(md5(md5($str)));

во первых - давайте не будем столь резко высказываться, а во вторых, что по вашему есть уникальность? - длинна строки? алгоритм шифрования ? - может ещё ,что-то ?, как по мне - 32 символа в результирующей строке - достаточно уникально. интересно - если начать подбирать строку прямо сейчас - сможет ли наконец закончить это делать ваш пра пра пра пра правнук ? )) - врядли !

 

[dimagolov]

nexen, судя по посту ты ничего не слышал по коллизии хеш ф-й вообще и MD5 в частности.

 

[vovanium]

nexen
Ты бы хоть тему почитал, никто не собирается подбирать строку. Хэш нужен чтобы файлы идентифицировать.

Как по мне то хватило бы md5+размера файла, ну или sha1 чтобы с запасом.
Если ты проиндексируешь даже миллиард файлов, то это всего 10^9, а в md5 вариантов 10^38, т.е. в принципе больше вероятность в лотерее выиграть, чем поймать на файлах совпадения, особенно при одинаковых размерах (размер ведь в любом случае сохранять нужно).

 

[SiMM]

> как по мне - 32 символа в результирующей строке - достаточно уникально.
Как по Вам - то нафига всякие md5, тем более, что смысла происходящего Вы всё равно не понимаете? Используйте substr($str,0,32) - "32 символа - достаточно уникальны".
Тройной md5 как минимум не уменьшит количество коллизий, соответственно лишён смысла в принципе.

 

[nexen]

Автор оригинала: dimagolov
nexen, судя по посту ты ничего не слышал по коллизии хеш ф-й вообще и MD5 в частности.

хорошо хоть вы мне не начали тут рассказывать ещё и о псевдоколлизиях или о методе Вана Сяоюня и Юя Хунбо - и-то ладно! ну допустим слышал я о коллизиях однако - разве вы не собираетесь проверять полученный хеш на наличие возможных совпадений ? и если таковые имеются то генерировать другой, а иначе следуя вашей логике и логины с паролями можно при регистрации не проверять - ведь по теории вероятности. . . и бла-бла-бла

Автор оригинала: SiMM
Тройной md5 как минимум не уменьшит количество коллизий, соответственно лишён смысла в принципе.

вероятность совпадения даже при однократном хешировании разных строк просто ничножна ,какова же она тогда при трехкратном хешировании ?

p.s.
учитывая то, что автор упоминал о большом количестве данных - на 32х символьном md5 можно будет ещё и сэкономить байты - хотя нужно ли это ему . . . ? - вот вопрос

 

[soulhunter]

nexen
постараюсь объяснить попроще: если ты берешь хеш от двух разных строк и ВДРУГ он совпадает - то каждый следующий хеш, взятый уже с этих одинаковых строк уж тем более будет совпадать, так что смысла в более чем однократном хешировании нет никакого.