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