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

[dimmik.livejournal.com]

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

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

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


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

Comments

[neoromantic.livejournal.com]

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

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

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

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

[binaryanimal.livejournal.com]

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

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

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

[binaryanimal.livejournal.com]

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

[kray-zemli.livejournal.com]

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

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