ИСТИНА

При проведении научно-исследовательской работы по представленной теме преследуются следующие цели: • разработка, применение и исследование эффективности математических методов и подходов к анализу поведения программ; • разработка новых математических моделей и методов обеспечения безопасности информационных систем, изучение эффективности их применения. К числу основных математических задач, которые намечены для исследования в рамках предлагаемой темы, относятся следующие: • задачи анализа и верификации компьютерных программ; • задача обфускации (маскировки) компьютерных программ; • задачи обнаружения и предотвращения несанкционированного вмешательства в работу информационных систем; • задачи разработки эффективных и стойких криптографических систем, включая системы шифрования и криптографические протоколы; • задачи анализа существующих и перспективных криптографических систем, • специальные задачи разработки и анализа политик безопасности в информационных системах. Для решения этих задач планируется разработать и изучить математические модели, позволяющие проводить исследовании свойств безопасности информационных систем методами дискретной математики, алгебры, математической логики, теории чисел, теории сложности вычислений, математической криптографии.

Были получены следующие основные результаты: 1) найдены линейные зависимости в координатных последовательностях псевдослучайнх генераторов, основанных на широком классе Т-функций, что позволило разработать новый класс атак для потоковых шифраторов, основанных на этих Т-функциях; 2) получены критерии эргодичности Т-функций на 2-адических сферах, что позволило находить периоды псевдослучайных генераторов, основанных на Т-функциях такого типа; 3) найдены условия транзитивности, полной транзитивности и абсолютной транзитивности детерминированных функций, что позволило описать класс законов рекурсии псевдослучайных генераторов, обеспечивающих отсутствие лакун в распределении генерируемых последовательностей 4) получен аналитический (в терминах ряда ван дер Пута) критерий ограниченности детерминированной функции, что позволило применить методы неархимедовой динамики к изучению поведения конечных автоматов, в том числе хеш-функций; 5) разработан метод быстрого вычисления значений Т-функций, основанный на применении рядов ван дер Пута, что позволило предложить эффективные способы увеличения быстродействия криптопримитивов, основанных на Т-функциях; 6) развита неархимедова динамика на некоммутативных группах, что дает принципиальную возможность для применения неархимедовых методов к ветвящимся компьютерным программам; 7) с помощью сочетания методов неархимедова анализа и действительного анализа доказана аффинность гладких конечно-вычислимых функций действительного аргумента, что, возможно, позволит построить класс квантово-механических атак на хеш-функции. 8) Разработан новый алгоритм решения больших разреженных систем линейных уравнений над полем GF(2). Получена асимптотическая оценка его сложности, лучшая, чем для алгоритма Видемана-Копперсмита. При этом алгоритм сохраняет возможность распараллеливания высокого уровня (то есть возможность работы вычислительных узлов в основное время без коммутационной среды). Этот алгоритм применяется при решении задачи факторизации целых чисел, которая, в свою очередь, нужна для вскрытия протокола RSA. Разреженные системы могут появляться и в других разделах прикладной алгебры, при решении некоторых экономических моделей. 9) Разработан новый алгоритм решения больших разреженных систем линейных уравнений над полем GF(р). Получена асимптотическая оценка его сложности. Этот алгоритм наследует основные преимущества алгоритма над GF(2). Он применяется при решении задачи дискретного логарифмирования алгоритмами с факторной базой. Такие алгоритмы, на сегодняшний день являются самыми быстрыми и могут применяться практически во всех алгебраических конструкциях, которые сегодня используются в криптографии. Написана программа, которая за 2 дня решила систему размером 2 млн. с элементами длиной 512 бит за 2 дня. Она принята к использованию военными организациями. 10) Доказана полиномиальная эквивалентность задач дискретного логарифмирования и Диффи-Хеллмэна на некоторых эллиптических кривых, удовлетворяющих отечественному ГОСТу. 11) Получено сведение задачи Диффи-Хеллмэна на произвольной эллиптической кривой к решению системы полиномиальных уравнений с оценками на их количество и степень. Задача Диффи-Хеллмэна это задача о вскрытии протокола открытого распределения ключа для большинства современных криптосхем. 12) Разработан новый метод решения задачи проверки эквивалентности программ. При помощи этого метода удалось построить полиномиальные по времени алгоритмы проверки эквивалентности программ в различных моделях вычислений – последовательных императивных программ, металинейных рекурсивных программ, потоковых программ. 13) Разработан новый подход к решению задачи проверки логико-термальной эквивалентности программ, основанный на использовании алгебры подстановок. При помощи этого метода удалось построить более простой и эффективный алгоритм проверки логико-термальной эквивалентности программ и впервые предложить полиномиальный по времени алгоритм логико-термальной унификации программ. 14) Разработана новая формальная модель программно-конфигурируемых сетей, относительно которой сформулированы задачи верификации. 15) Изучалась структура множества открытых ключей криптосистемы Мак-Элиса—Сидельникова, построенной на основе u-кратного кода Рида—Маллера RM(r,m). Каждый открытый ключ этой криптосистемы – это класс эквивалентности множества секретных ключей. В итоге получено строение классов эквивалентности для достаточного большого множества секретных ключей. Знание строения классов эквивалентности позволило найти некоторые заведомо слабые ключи криптосистемы Мак-Элиса—Сидельникова. 16) Построена полиномиальная (эффективная атака) на криптосистему Мак-Элиса, основанную на кодах Рида—Маллера RM(r,m) в случае, когда НОД(r-1,m)=1. Для произвольных параметров предложена атака, лучшая на сегодняшний день, но не являющаяся полиномиальной. Предложена общая конструкция атак на кодовые криптосистемы. 17) Усовершенствованы методы решения двумерной задачи дискретного логарифмирования. Разработан алгоритм решения двумерной задачи дискретного логарифмирования с эффективным автоморфизмом и проведен анализ возможности их оптимизации. 18) Получены оценки средней трудоемкости решения двумерной задачи дискретного логарифмирования. 19) Исследовались ключевое пространство и сложность криптоанализа криптосистемы с открытым ключом MST3. 20) Проводились исследования по программной реализации блочного шифра Кузнечик. 21) Обнаружены содержательные (конструктивные) связи криптографических свойств дискретных функций с алгебраическими и комбинаторными свойствами их ограничений (сужений). На основе полученных результатов разработаны новые классы методов криптографического анализа; 22) Развивались методы обращения (локального обращения) криптографических функций на основе математических моделей и  методов символической динамики; 23) Развивались методы анализа алгебраических, комбинаторных и криптографических свойств булевых функций. 24) Получены новые оценки трудоемкости алгоритма Вонг для поиска коллизий хэш-функции RIPEMD. 25) Построена теоретико-графовая модель некоторых алгоритмов поиска коллизий хэш-функций SHA-1 и RIPEMD без учета зависимостей между уровнями вычислений, и в данной модели выведена точная формула средней трудоемкости этих алгоритмов.