КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

---

Номер проекта 18-71-00150

НазваниеРазработка эволюционных стратегий поиска декомпозиций трудных вариантов задачи о булевой выполнимости с применением к обращению криптографических функций.

Руководитель Ульянцев Владимир Игоревич, Кандидат технических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет ИТМО" , г Санкт-Петербург

Конкурс №29 - Конкурс 2018 года по мероприятию «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-201 - Искусственный интеллект и принятие решений

Ключевые слова ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ, КРИПТОАНАЛИЗ, ОБРАЩЕНИЕ КРИПТОГРАФИЧЕСКОЙ ФУНКЦИИ, ЗАДАЧА О БУЛЕВОЙ ВЫПОЛНИМОСТИ (SAT), ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ, ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ, SAT-РЕШАТЕЛЬ, SAT-ДЕКОМПОЗИЦИЯ

Код ГРНТИ27.41.41

---

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

---

Аннотация
Уровень безопасности систем и протоколов передачи данных критически зависит от того, насколько обоснована стойкость используемых для защиты этих данных криптографических алгоритмов. Ввиду большого разнообразия подходов, используемых для защиты данных, ценными представляются автоматические методы, позволяющие аргументированно сравнивать стойкость различных криптографических алгоритмов. В основе таких методов должна лежать комбинаторная задача с мощной и хорошо развитой алгоритмикой. Ряд последних исследований показывает, что одной из самых многообещающих в этом плане является задача о булевой выполнимости (SAT). В рамках настоящего исследования планируется разработать новые методы поиска декомпозиционных представлений трудных вариантов задачи о булевой выполнимости и применить разработанные алгоритмы к задачам криптоанализа ряда современных шифров. Конкретно, ожидается, что будут построены новые алгоритмы, основанные на эволюционных принципах, которые позволят находить декомпозиционные представления SAT-задач (т.н. «SAT Partitionings») с лучшей оценкой трудоемкости решения, чем у известных методов. Подчеркнем, что эволюционные алгоритмы будут использоваться на этапе декомпозиции трудных вариантов (экземпляров) задачи SAT, но не при решении самих SAT-формул. Предполагается, что разработанные алгоритмы позволят для ряда шифров построить новые атаки из класса «угадывай и определяй» (guess-and-determine), которые окажутся эффективнее известных. Предполагается разработка новых стратегий параметризации SAT-решателей для их использования в задачах криптоанализа (SAT-based cryptanalysis). В этом направлении также планируется детальный анализ возможностей применения эволюционных стратегий. Актуальность настоящего исследования обосновывается тем, что методы криптоанализа являются важной составной частью процессов разработки новых систем шифрования. Современные алгоритмы решения SAT в последние годы весьма успешно применяются в криптоанализе, что позволяет рассматривать их как основу для построения целого ряда атак на известные и разрабатываемые криптографические примитивы и шифры. Тем самым такие алгоритмы могут выполнять функции экспертных систем, выдавая оценки стойкости исследуемых криптографических конструкций. В дальнейшем наиболее стойкие такие конструкции могут использоваться при разработке реальных шифров. Научная новизна настоящего исследования состоит в разработке основанных на новых принципах методов поиска декомпозиционных представлений трудных вариантов задачи SAT. Также будут предложены новые методы подбора оптимальных параметров запуска SAT-решателей для рассматриваемого класса SAT-формул. Предполагается, что разработанные методы позволят построить новые криптографические атаки, более эффективные, чем известные. Также предполагается использовать разработанные методы для аргументированного сравнения между собой различных криптографических систем.

---

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

---