MD5 хэш-столкновения.

Question

Если считать от 1 до X, где X - это первое число, которое столкнулось с md5 с предыдущим номером, какое число X?

Я хочу знать, использую ли я md5 для серийных номеровСколько единиц измерения я могу рассчитывать, прежде чем я получу столкновение.

Answer 1

Теоретически, вы можете ожидать столкновения для X около 2 ⁶⁴ .Для хэш-функции с выходом n битов первые коллизии появляются, когда вы накопили около 2 ^{n / 2} выходов (не имеет значения, как вы выбираете входы; последовательные целочисленные значенияв этом нет ничего особенного).

Конечно, MD5 было показано , а не как хорошая хеш-функция.Кроме того, 2 ^{n / 2} является только средним.Так почему бы тебе не попробовать?Возьмите реализацию MD5, хэшируйте свои серийные номера и посмотрите, не получите ли вы коллизию.Базовая реализация MD5 должна иметь возможность хэшировать несколько миллионов значений в секунду, а с разумным жестким диском вы можете накопить несколько миллиардов выходных данных, отсортировать их и посмотреть, нет ли столкновения.

Answer 2

Я не могу ответить на ваш вопрос, но вы ищете uuid .Серийные номера UUID могут быть уникальными для миллионов продуктов, но вам может потребоваться проверить базу данных, чтобы уменьшить малейшую вероятность столкновения.

Answer 3

Насколько я знаю, в md5 нет известных коллизий для 2 ^ 32 (размер целого числа)

Answer 4

Я полагаю, что никто не провел какой-либо тест на этом

Учитывая, что если у вас есть простое инкрементное число, вам не нужно его хешировать

Answer 5

Я понимаю, что это старый вопрос, но я наткнулся на него, нашел гораздо лучший подход и решил поделиться им.

У вас есть верхняя граница для вашего порядкового номера N, поэтому давайте воспользуемся преимуществомтого, что.Допустим, N <2 <sup>32 ≈ 4,3 * 10 ¹⁰ .Теперь каждый раз, когда вам нужен новый идентификатор, вы просто выбираете случайное 32-битное число R и объединяете его с R xor N (нулевое число перед объединением).Это дает случайный выглядящий уникальный 64-битный идентификатор, который можно обозначить всего 16 шестнадцатеричными цифрами.

Этот подход полностью предотвращает коллизии, потому что два идентификатора, которые случайно имеют один и тот же случайный компонент, обязательно имеют разные xor-ed компоненты.

Бонусная функция: вы можете разбить такой 64-битный идентификатор на два 32-битных числа и переписать их друг с другом, чтобы восстановить исходный порядковый номер.

Answer 6

Это действительно зависит от размера вашего ввода.У идеальной хеш-функции есть коллизии в каждом (input_length / hash_length) хэше.Если вы используете небольшие коллизии, маловероятно, что , пока что было только одно коллизионное столкновение.