как работает md5sum?

[dimmik.livejournal.com]

Кто-нибудь может объяснить мне на словах (без математических и прочих терминов)
как именно работает md5sum?
И почему считается (и практикой, епрст, проверено - так и есть) что для любой последовательности данных md5sum уникальна?
Хотя разумом мы понимаем что не могут 128 бит быть уникальными для всех бОльших последовательностей данных, однако по этой самой md5 и в ослах разных идентифицируют и проверяют целостность файла и все такое - типа "отпечаток пальца".

Таки как она работает и почему она "уникальна"?
Объянсите на пальцах пожалуйста.

И еще - разум подсказывает что для любого X найдутся такие K и N что md5sum^K( X ) = md5sum^N( X ) - так ли это?


Просьба к технической инфе не отсылать. Я уверен что при должных усилиях я смогу все там понять и, может быть, даже потом объяснить, но хочется "на блюдечке" объяснения на пальцах.

Comments

[neoromantic.livejournal.com]

"Как именно" - вы хотите знать алгоритм?

Ответ на основную часть вопроса - нет, md5 не уникален, конечно. Но целостность проверяется. Потому что эта хеш-функция устроена так, чтобы при небольшом изменении входных данных значение хеша изменялось сильно.

[dimmik.livejournal.com]

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

Если таковое есть, конечно.

Ну, как пример того что я хочу услышать:
Скажем, вопрос: как получается так что самолеты не сталкиваются над аэродромом?
На самом деле подробное объяснение этого заняло бы много времени.
Однако можно вкратце сказать что-то типа "операторы определяют их очередность в соответствии с своей базой и командуют кому на какой курс лечь."

[neoromantic.livejournal.com]

http://www.x-hack.ru/forum/index.php?s=bdaba193eb28795853a7daab03380ec1&act=Print&client=printer&f=22&t=391

[dimmik.livejournal.com]

Алгоритм описан, но "на пальцах" почему его результат является такой хорошей хеш-функцией я так и не нашел...
Принципиального отличия от "взять первый, седьмой, восемнадцатый, [еще 29 номеров байт]" и составить из них 128-битный хеш я не увидел.

Ну, некий сложный алгоритм.
Его "правильность" только практически определяется?

Кстати, md5sum(x) плотно заполняет область своих значений?
В смысле, верно ли что
Для любого Y, где Y - 128-битное число, найдется такой X что md5sum(X) = Y
?

[neoromantic.livejournal.com]

Ну а как вы хотите, чтобы я доказал "правильность"? Алгоритм не за 5 минут придумывался. И придумывался именно для этих целей.

Насчет плотности тоже не отвечу. Интуитивно думаю, что да.

[http://users.livejournal.com/_dilbert_/]

уже не считается что уникальная
ее скомпромитировали кетайцы... в прошлом или позапрошлом году

[rannor_ru.livejournal.com]

Она никогда не могла быть уникальной. Число комбинаций 128 бит ограничено, а количество различных строк - бесконечно ^_^

Просто появился способ получить текст с заданным хэшем

[g0mez.livejournal.com]

И вы не совсем правы. Способ был всегда - полный перебор. Появился быстрый способ создания коллизий.

[rannor_ru.livejournal.com]

Ну да, я имел ввиду достаточно быстрый способ ^_^

[binaryanimal.livejournal.com]

Просто вероятность такого совпадения ~ 2^(-128) это очень мало, поверьте ;)

[http://users.livejournal.com/_greek_/]

не уникален он. суть сводится к тому, что фиг найдешь второй текст с такой же суммой, поэтому считается надежным. кстати грубо говоря есть еще и другие "суммы", в которых используется пароль, т.е. даже если подобрать текст, то не зная пароля совпадение это не узнаешь.

[binaryanimal.livejournal.com]

Если бы сума была уникальна для каждой последовательности, то существовала бы обратная операция извлечения из 128 бит информации чего угодно - напирмер дистрибутива виндов =)))))

[maravan.livejournal.com]

хочу! :)

[dimmik.livejournal.com]

Помнится в детстве читал Гарднера (который Мартин, а не Эрл Стенли :)) и была там такая задачка.
Представим что мы имеем измеряющие инструменты абсолютной точности.
Как можно на стержень длиной один метр записать любое количество информации?

[http://users.livejournal.com/_bigbrother_/]

Ну, там не только измерительные инструменты нужны :). Там ещё сплошная среда нужна. Тот факт, что стержень состоит из атомов, убивает возможность неограниченного кодирования даже без учёта их (атомов) теплового движения :).

[alex-rex.livejournal.com]

eDonkey — крупнейший восстанавливатель файла по его md5 (http://alex-rex.livejournal.com/242185.html)

[kray-zemli.livejournal.com]

Этот алгоритм очень сложный. Основан на математической модели развития некоторого дискретного сверхнеустойчивого процесса. Вас в школе про рост энтропии учили? Вот вам простейший алгоритм генерации хеша: берем объем, берем входную информацию в качестве координат и скоростей частиц газа, моделируем процесс в объеме во времени достаточно долго по сравнению со временем релаксации, затем берем координаты нескольких первых молекул в качестве хеша. Представляете, какая каша получится?

На самом деле, MD5 используются нелинейные бинарные и арифметические функции, с набором иррациональных чисел (которые, правда, жестко заданы таблицей). Но принцип тот же. Во всяком случае, на это надеятся.