Криптографические хеш-функции -II

[fat_crocodile]

Коллизии это здорово, но обращать функции - гораздо круче. Особенно если в истинную веру. Как это эффективно сделать, в 1980 году придумал человек с говорящей фамилией Хеллман.

Мартин Хеллман, да, это тот самый Хеллман, который вместе с Диффи. Кстати, недавно смотрел забавный фильм про его молодость. Мужик зажигал! Но, став отцом, видимо,

Comments

[0serg]

Интересный материал, спасибо!

[fat_crocodile]

А ты бери с меня пример :) И будем взаимно обогащаться.

Да, неделю назад была первая часть: http://fat-crocodile.livejournal.com/79819.html

[iliada]

Несколько комментариев:

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

"Коллизия может встретиться где угодно, так что хвост может получиться любой длины, но средняя длина более короткого хвоста, наверное, примерно 0,25*t (не возьмусь обосновать. Ясно, что меньше половины, но вот дальше надо думать)."

Если мы хотим оценить длину хвоста, то будет полезно следующее соображение: один хвост - есть случайно распределенная в интервале [0..t] величина. Более короткий хвост из двух - это min(хвост1, хвост2). Эта величина имеет распределение 2(1-x/t)x/t, где x находится в интервале [0..t], а её матожидание - t/3.

> Я, к сожалению, так и не понял, как произносить фамилию автора метода...
Йошлин. Точнее - первый слог длинный. Йоошлин (как ё-ё-ё-жик).

>До сих пор мы игнорировали стадию поиска результата итераций среди

[fat_crocodile]

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

[iliada]

Да, чтобы ты правильно понимал ситуацию: каждый раз меня отдельно радует отсутствие комментария вида "нет, это ВСЁ не так" :)
Для ясности добавлю: отличное и весьма точное изложение материала.

[fat_crocodile]

*уверенность в собственных силах наполняет меня*
Спасибо :)

Добавил про магические значения, переписал про перестановки.