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