возможность столкновения 16-значного и 32-значного md5

Question

Я знаю, что строка md5 из 16 символов - это 8-й и 24-й символы строки md5 из 32 символов, например:

469e80d32c0559f8

7fef6171 469e80d32c0559f8 8b377245

Мой вопрос: задано две разные струны и вычислите их 16 и 32 md5, вероятность столкновения их 16 md5 намного больше, чем 32 md5? Или они такие же.

Спасибо.

Answer 1

Если бы MD5 был идеальной функцией ha sh (это не так), то каждый из символов в ее шестнадцатеричной строке был бы случайным числом от 0 до 15. Таким образом, 16 символов ha sh имеют коллизию. вероятность 16 ^-16 = 1 из 1,8 × 10 ¹⁹ , а 32 символа имеют вероятность столкновения 16 ^-32 = 1 из 3,4 × 10 ³⁸ , гораздо менее вероятно. Обратите внимание, что применяется парадокс дня рождения ; у вас есть примерно 50% шанс столкновения в наборе всего из 4,3 × 10 ⁹ элементов с более коротким хешем; это квадрат root от общего числа возможных хэшей.

Однако, поскольку MD5 не подходит для функции ha sh, можно намеренно спроектировать конфликт в любом случае. Рассмотрим более сильную га sh.

Answer 2

Коллизия - это ситуация, когда для двух разных сообщений, m1 и m2, ha sh совпадает, т.е. ha sh (m1) = ha sh (m2).

Чем длиннее может быть вывод функции ha sh (m), тем меньше вероятность столкновения. Например, давайте подумаем о ситуации, когда функция ha sh (m) должна отображать сообщение m только в один бит, т.е. она может отображаться только в 0 или 1. Тогда риск столкновения будет очень высоким. :)

Тогда возникает вопрос качества функции ha sh. Он должен отображать сообщение в значение с одинаковой вероятностью для всех сообщений. Для MD5 это не так, некоторые значения используются чаще. Это увеличивает риск столкновения. У MD5 есть серьезный fl aws, такой как атака на день рождения.

Мы знаем (http://www.faqs.org/rfcs/rfc4270.html), что успешные атаки против MD5 могут быть выполнены на домашнем P C. Лучше перейти на SHA-1. Microsoft рекомендует SHA256 или SHA512.