|
Вычислительные методы в дискретной математике
Применение алгоритмов решения проблемы булевой выполнимости к построению разностных путей в задачах поиска коллизий криптографических хеш-функций семейства MD
И. А. Грибанова Институт динамики систем и теории управления им. В. М. Матросова СО РАН, г. Иркутск
Аннотация:
Представлен новый метод построения разностных путей в задаче поиска коллизий криптографических хеш-функций, основанный на использовании алгоритмов решения проблемы булевой выполнимости. На начальном этапе метода строится пропозициональная кодировка задачи поиска коллизий рассматриваемой хеш-функции. Затем в полученную кодировку добавляются (в виде КНФ) дополнительные ограничения. Как правило, это значения целочисленных разностей на сообщения, дающие коллизию, а также на отдельные фрагменты дифференциального пути. В качестве отправной точки поиска можно использовать некоторый известный либо случайный дифференциальный путь (во втором случае наличие коллизий, удовлетворяющих такому пути, не гарантируется). Задача варьирования значений разности переменных, кодирующих заполнение хеш-регистров, сводится к SAT. Для эффективного решения соответствующих серий SAT-задач написана MPI-программа, работающая на вычислительном кластере. Основным результатом стало построение дифференциального пути для задачи поиска коллизий криптографической хеш-функции MD4, отличного от известных.
Ключевые слова:
криптографическая хеш-функция, коллизия, разностные атаки, задача о булевой выполнимости (SAT), хеш-функции семейства MD.
Образец цитирования:
И. А. Грибанова, “Применение алгоритмов решения проблемы булевой выполнимости к построению разностных путей в задачах поиска коллизий криптографических хеш-функций семейства MD”, ПДМ. Приложение, 2016, № 9, 129–132
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma272 https://www.mathnet.ru/rus/pdma/y2016/i9/p129
|
Статистика просмотров: |
Страница аннотации: | 133 | PDF полного текста: | 63 | Список литературы: | 23 |
|