Он считает биты, а не количество возможных значений.

ужен хэш из 4 символов. На данный момент я беру первые 4 символаmd5() хэш. Я хэширую строку длиной 80 символов или меньше. Приведет ли это к столкновению? или, какова вероятность столкновения, при условии, что я хэшу меньше, чем 65 536 (164) разные элементы?

Ответы на вопрос(2)

md5 это шестнадцатеричный бит. Это означает, что он может иметь одно из 16 возможных значений. Так что, если вы используете только первые 4 "шестнадцатеричных бита", это означает, что вы можете иметь16 * 16 * 16 * 16 или же16^4 или 65536 или2^16 возможности.

Таким образом, это означает, что общее доступное «пространство» для результатов составляет всего 16 бит. Теперь, согласноАтака на день рождения / ПроблемаЕсть следующие шансы на столкновение:

50% шанс ->300 записи1% шанс ->36 записи0.0000001% шанс ->2 записей.

Так что вероятность столкновений довольно высока.

Теперь вы говорите, что вам нужен хэш из 4 символов. В зависимости от точных требований вы можете сделать:

4 шестнадцатеричных бита для16^4 (65,536) возможные значения4 альфа-бита для26^4 (456,976) возможные значения4 буквенно-цифровых разряда для36^4 (1 679 616) возможных значений4 биты ascii для печати около93^4 (74,805,201) возможные значения (при условии ASCII 33 -> 126)4 полных байта для256^4 (4,294,967,296) возможных значений.

Теперь то, что вы выберете, будет зависеть от фактического варианта использования. Нужно ли передавать хеш в браузер? Как вы его храните и т. Д.

Я приведу пример каждого из них (в PHP, но должно быть легко перевести / посмотреть, что происходит):

4 шестнадцатеричных бита:

$hash = substr(md5($data), 0, 4);

4 альфа-бита:

$hash = substr(base_convert(md5($data), 16, 26)0, 4);
$hash = str_replace(range(0, 9), range('S', 'Z'), $hash);

4 буквенно-цифровых бит:

$hash = substr(base_convert(md5($data), 16, 36), 0, 4);

4 печатных бита Assci:

$hash = hash('md5', $data, true); // We want the raw bytes
$out = '';
for ($i = 0; $i < 4; $i++) {
    $out .= chr((ord($hash[$i]) % 93) + 33);
}

4 полных байта:

$hash = substr(hash('md5', $data, true), 0, 4); // We want the raw bytes
 yosser06 дек. 2011 г., 12:22
Просто быстрое исправление ошибки для вашего решения «4 альфа-бита», я думаю, что вторая строка должна быть: $ hash = str_replace (range (0, 9), range ('Q', 'Z'), $ hash);
 yosser07 дек. 2011 г., 18:25
Если подумать, второй дает a-z + Q-Z в виде диапазона = 36 ^ 4 возможных значений. .. и целое должно читаться следующим образом: $ hash = substr (base_convert (md5 ($ data), 16, 26), 0, 4); $ hash = str_replace (range (0, 9), range ('q', 'z'), $ hash);
Решение Вопроса

Удивительно высокий действительно. Как вы можете видеть изэтот график приближенной вероятности столкновения (формула изстраница википедии), всего с несколькими сотнями элементов ваша вероятность столкновения составляет более 50%.

Обратите внимание, конечно, что если вы столкнулись с возможностью того, что злоумышленник предоставит строку, вы, вероятно, можете предположить, что она на 100% - сканирование для обнаружения коллизии в 16-битном пространстве поиска может быть выполнено практически мгновенно на любом современном ПК. Или даже любой современный сотовый телефон, если на то пошло.

Ваш ответ на вопрос