Re: Посоветовать алгор итм хэширования

От Andrew A. Mezhutkov (2:5020/400) к Serguei E. Leontiev

From: "Andrew A. Mezhutkov" <mez@voltars.ru>

Tue Aug 18 2009 02:33, Serguei E. Leontiev wrote to Alex Aka Parasite:

 SEL> From: leo@sai.msu.ru (Serguei E. Leontiev)

 SEL> Здравствуй Alex,

 SEL> Alex Aka Parasite -> All @ пн 17-авг-09 21:29 MSD:

 SEL> ...

 AAP>> 4. Там же, на винте - хранилище контента под проект. Контент

 AAP>> представляет из  себя многие и многие *миллионы* мелких бинарных

 AAP>> файлов, размером от десятков  байт до десятков килобайт, и их число

 AAP>> постоянно растет. Каждый файлик уже

 SEL> ...

 AAP>> 1. *Очень критично* отсутствие коллизий (одинакового хэша на разные по

 AAP>> составу  файлы). Учитывая количество единиц файлА - такое теоретически

 AAP>> возможно...

 SEL> Хм. Hе уверен, оценим "растущие миллионы" величиной 2^32, а десятки байт

 SEL> величиной 80 бит, и тогда вероятность коллизии внутренности самих файлов

 SEL> составит примерно 10^-2, что противоречит "очень критично" (это в

 SEL> предположении случайности).

 SEL> Таким образом, если мы оценим "очень критично" вероятностью 10^-9, то:

 SEL>   - надо, либо проверять, что содержимое файлов уникально, либо

 SEL>     добавлять уникальный идентификатор (например, имя файла);

 SEL>   - т.к. требований на необратимость не предъявлялось, то подойдёт любая

 SEL>     достаточно "случайная" функция с результатом размера больше 254-бит:

 SEL>       * CRC 256;

 SEL>       * ГОСТ Р 34.11-94;

 SEL>       * SHA-256;

 SEL>       * и т.п.

 как вариант использовать _две_ свертки, но более короткие для скорости

вычислений. SHA-180, например, и второе по вкусу...

эти вычисления можно вести в две "нитки", что сократит общее время

шлите деньги факсом

--- ifmail v.2.15dev5.4

 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)

Ответы на это письмо:

From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку

From: Username
Или коротким