Вычислительные методы и программирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Выч. мет. программирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Выч. мет. программирование, 2015, том 16, выпуск 1, страницы 61–77 (Mi vmp519)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Задачи поиска коллизий для криптографических хеш-функций семейства MD как варианты задачи о булевой выполнимости

И. А. Богачковаa, О. С. Заикинb, С. Е. Кочемазовb, И. В. Отпущенниковb, А. А. Семёновb, О. О. Хамисовa

a Иркутский государственный университет
b Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук, г. Иркутск

Аннотация: Рассмотрена реализация разностной атаки на криптографические хеш-функции MD4 (Message Digest 4) и MD5 (Message Digest 5) через сведение задачи поиска коллизий для этих хеш-функций к задаче о булевой выполнимости (SAT, SATisfiability). Новизна полученных результатов заключается в том, что предложены существенно более экономные (в сравнении с известными) SAT-кодировки рассматриваемых алгоритмов, а также в использовании для решения полученных SAT-задач современных многопоточных и параллельных SAT-решателей. Задачи поиска одноблоковых коллизий для MD4 в данной постановке оказались чрезвычайно простыми. Кроме того, найдены несколько десятков двухблоковых коллизий для MD5. В процессе соответствующих вычислительных экспериментов определен некоторый класс сообщений, дающих коллизии: построено множество пар дающих коллизии сообщений, у которых первые 10 байтов нулевые.

Ключевые слова: криптографические хеш-функции, коллизии, разностные атаки, задача о булевой выполнимости (SAT), параллельные SAT-решатели.

Полный текст: PDF файл (455 kB)
УДК: 004.056.55, 004.832.25
Поступила в редакцию: 18.01.2015

Образец цитирования: И. А. Богачкова, О. С. Заикин, С. Е. Кочемазов, И. В. Отпущенников, А. А. Семёнов, О. О. Хамисов, “Задачи поиска коллизий для криптографических хеш-функций семейства MD как варианты задачи о булевой выполнимости”, Выч. мет. программирование, 16:1 (2015), 61–77

Цитирование в формате AMSBIB
\RBibitem{BogZaiKoc15}
\by И.~А.~Богачкова, О.~С.~Заикин, С.~Е.~Кочемазов, И.~В.~Отпущенников, А.~А.~Семёнов, О.~О.~Хамисов
\paper Задачи поиска коллизий для криптографических хеш-функций семейства MD как варианты задачи о булевой выполнимости
\jour Выч. мет. программирование
\yr 2015
\vol 16
\issue 1
\pages 61--77
\mathnet{http://mi.mathnet.ru/vmp519}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vmp519
  • http://mi.mathnet.ru/rus/vmp/v16/i1/p61

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. И. А. Богачкова, О. С. Заикин, С. Е. Кочемазов, И. В. Отпущенников, А. А. Семёнов, “Применение алгоритмов решения проблемы булевой выполнимости к криптоанализу хэш-функций семейства MD”, ПДМ. Приложение, 2015, № 8, 139–142  mathnet  crossref
    2. И. А. Грибанова, “Применение алгоритмов решения проблемы булевой выполнимости к построению разностных путей в задачах поиска коллизий криптографических хеш-функций семейства MD”, ПДМ. Приложение, 2016, № 9, 129–132  mathnet  crossref
  • Вычислительные методы и программирование
    Просмотров:
    Эта страница:114
    Полный текст:108
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021