grandov.ru страница 1
скачать файл
Вскрытие в день рождения против однонаправленных хэш-функций

Существует два способа вскрытия однонаправленных хэш-функций грубой силой. Первый наиболее очевиден: дано значение хэш-функций сообщения, Н(М), врагу хотелось бы суметь создать другой документ, М', такой, что Н(М')=Н(М). Второй способ более тонок: врагу хотелось бы найти два случайных сообщения, М и М', таких, что Н(М')=Н(М). Такой способ называется столкновением и является более простым, чем первый, способом вскрытия.

Парадокс дня рождения является стандартной статистической проблемой. Сколько человек должно собраться в одной комнате, чтобы с вероятностью 1/2 хотя бы у кого-нибудь из них был бы общий с вами день рождения? Ответ - 183. Хорошо, а сколько людей должно собраться, чтобы с вероятностью 1/2 хотя бы у двоих из них был бы общий день рождения? Ответ удивителен - 23. 23 человека, находящихся в комнате, образуют 253 различных пары.

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



Предположим, что однонаправленная хэш-функция безопасна, и лучшим способом ее вскрытия является вскрытие грубой силой. Результатом функции является число. Поиск сообщения, хэш-значение которого совпадает с заданным, в среднем потребовал бы хэширования 2 m случайных сообщений. А для обнаружения двух сообщений с одинаковым хэш-значением потребуется только 2 т/2 случайных сообщений. Компьютеру, который хэширует миллион сообщений в секунду, потребовалось бы 600000 лет, чтобы найти второе сообщение с тем же 64-битовым хэш-значением. Тот же компьютер сможет найти пару сообщений с общим хэш-значением примерно за час

Это значит, что, если вы опасаетесь вскрытия в день рождения, вы должны выбирать длину хэш-значения в два раза длиннее, чем вам потребовалось бы в противном случае. Например, если вы хотите уменьшить вероятность взлома вашей системы до 1 шанса из 280, используйте 160-битовую однонаправленную хэш-функцию.
скачать файл



Смотрите также:
Вскрытие в день рождения против однонаправленных хэш-функций
17.37kb.
Каждый день в нашей школе кто-то празднует День Рождения, но это проходит тихо, в своём классе. Мы хотим, чтобы наших именинников поздравляли все! Итак, с Днём Рождения,
114.85kb.
Терёшкина И. Г
46.6kb.
«Библиотечный калейдоскоп» 4-5 стр выпуске
256.1kb.
День рождения нкк
8.13kb.
Функции нескольких переменных
450.74kb.
Биография Пауля Ландерса (Paul Landers) день рождения: 9 декабря 1964 место рождения: Берлин цвет волос: темно-коричневый цвет глаз: орешек рост: 172 см вес: 79 кг
24kb.
Сентябрь 1 День знаний 8 Международный день распространения грамотности 9 Всемирный день красоты 26 Европейский день языков (День учителя иностранных языков) 27 День воспитателя и всех дошкольных ра­ботников Октябрь
24.65kb.
5 ноября – 120 лет со дня рождения Джона Бёрдона Сандерсона Холдейна
13.74kb.
Фмс россии управление Федеральной миграционной службы по Ханты-Мансийскому автономному округу – Югре о принимаемых уфмс россии по Ханты-Мансийскому автономному округу Югре мерах по осуществлению правоприменительных функций, функций по
201.23kb.
Организации, отметить День рождения В. И. Ленина
248.41kb.
Эквивалентность пяти классов функций элементарных по кальмару
30.66kb.