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

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

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



ПДМ. Приложение:
Год:
Том:
Выпуск:
Страница:
Найти






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


ПДМ. Приложение, 2016, выпуск 9, страницы 129–132 (Mi pdma272)  

Вычислительные методы в дискретной математике

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

И. А. Грибанова

Институт динамики систем и теории управления им. В. М. Матросова СО РАН, г. Иркутск

Аннотация: Представлен новый метод построения разностных путей в задаче поиска коллизий криптографических хеш-функций, основанный на использовании алгоритмов решения проблемы булевой выполнимости. На начальном этапе метода строится пропозициональная кодировка задачи поиска коллизий рассматриваемой хеш-функции. Затем в полученную кодировку добавляются (в виде КНФ) дополнительные ограничения. Как правило, это значения целочисленных разностей на сообщения, дающие коллизию, а также на отдельные фрагменты дифференциального пути. В качестве отправной точки поиска можно использовать некоторый известный либо случайный дифференциальный путь (во втором случае наличие коллизий, удовлетворяющих такому пути, не гарантируется). Задача варьирования значений разности переменных, кодирующих заполнение хеш-регистров, сводится к SAT. Для эффективного решения соответствующих серий SAT-задач написана MPI-программа, работающая на вычислительном кластере. Основным результатом стало построение дифференциального пути для задачи поиска коллизий криптографической хеш-функции MD4, отличного от известных.

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 14-07-00403а
Работа выполнена при частичной финансовой поддержке РФФИ, проект № 14-07-00403а.


DOI: https://doi.org/10.17223/2226308X/9/51

Полный текст: PDF файл (635 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.7

Образец цитирования: И. А. Грибанова, “Применение алгоритмов решения проблемы булевой выполнимости к построению разностных путей в задачах поиска коллизий криптографических хеш-функций семейства MD”, ПДМ. Приложение, 2016, № 9, 129–132

Цитирование в формате AMSBIB
\RBibitem{Gri16}
\by И.~А.~Грибанова
\paper Применение алгоритмов решения проблемы булевой выполнимости к~построению разностных путей в~задачах поиска коллизий криптографических хеш-функций семейства MD
\jour ПДМ. Приложение
\yr 2016
\issue 9
\pages 129--132
\mathnet{http://mi.mathnet.ru/pdma272}
\crossref{https://doi.org/10.17223/2226308X/9/51}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdma272
  • http://mi.mathnet.ru/rus/pdma/y2016/i9/p129

    ОТПРАВИТЬ: 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
  • Прикладная дискретная математика. Приложение
    Просмотров:
    Эта страница:60
    Полный текст:14
    Литература:12

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019