|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Использование решателей задачи выполнимости КНФ в криптоанализе криптосистемы Мак-Элиса, построенной на квазициклических кодах с ограниченной плотностью проверок на чётностьдипломная работа (Бакалавр)
- Научный руководитель: Чижов Иван Владимирович
- Автор: Илюхина Анастасия Сергеевна
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2019
- Аннотация: Криптосистема Мак-Элиса – одна из старейших криптосистем с открытым ключом. Она была предложена в 1978 году Р. Дж. Мак-Элисом. Стойкость криптосистемы Мак-Элиса основывается на сложности декодирования линейного кода, не имеющего видимой комбинаторной или алгебраической структуры. Кодовые криптосистемы, к которым относится криптосистема Мак-Элиса, в силу ряда причин не получили широкого распространения на практике. Однако в криптографии всегда есть острая необходимость в разработке и исследовании других криптосистем с открытым ключом. Интерес к этим криптосистемам тем, что в 2017 году Национальный институт стандартов и технологий США объявил конкурс на перспективные криптографические примитивы постквантового мира. Более половины всех заявок, представленных на конкурс, строятся на основе кодов, исправляющих ошибки. Таким образом, появилась реальная потребность в исследовании кодовых криптосистем с точки зрения возможных уязвимостей, связанных с особенностями использования их в информационных системах. В последнее время возросла популярность идеи использовать решатели задачи ВЫПОЛНИМОСТЬ для взлома блоковых криптосистем с секретным ключом и криптографических хэш-функций. Однако до недавнего времени не было работ по применению решателей задачи ВЫПОЛНИМОСТЬ для взлома кодовых криптосистем с открытым ключом. В настоящее время идеи использовать специализированные решатели в криптоанализе кодовых криптосистем набирает обороты. В выпускной квалификационной работе А. С. Илюхиной предлагается алгоритм сведения задачи поиска секретного ключа по открытому в криптосистеме Мак-Элиса, построенной на квазициклических кодах с достаточно низкой плотностью проверок на чётность, к задаче ВЫПОЛНИМОСТЬ КНФ. При этом алгоритм является полиномиальным от длины ключа и позволяет строить КНФ, которая имеет сравнительное небольшое число переменных и длину полиномиальную от параметров криптосистемы. Работоспособность предложенного алгоритма была продемонстрирована в его программной реализации на языке программирования C++. Помимо этого, в работе исследуется применимость различных решателей задачи ВЫПОЛНИМОСТЬ, представленных на конкурс SAT-competition в 2018 году, к поиску секретного ключа. В итоге наилучшие показатели были достигнуты на решатели plingeling, которому удалось восстановить секретный ключ для параметров r=41,n=82,w=14. Следует признать, что эти параметры в 10 раз меньше, чем рекомендуемые разработчиками для оригинальной криптосистемы Мак-Элиса, построенной на квазициклических кодах. Фактически работа А. С. Илюхиной показывает, что рассматриваемая криптосистема относительно плохо поддаётся этому методу криптоанализа в отличие от других её модификаций.
- Добавил в систему: Чижов Иван Владимирович