Построение и реализация алгоритмов решения систем целочисленных неравенств в методе разделяющих плоскостей тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат наук Лапиков Игорь Игоревич

• Лапиков Игорь Игоревич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Лапиков Игорь Игоревич

Введение

Глава 1 Метод разделяющих плоскостей

1.1 Пороговые булевы и Л-значные функции и их свойства

1.2 Методы сведения нелинейных булевых уравнений к равносильным системам пороговых ограничений

1.3 Метод разделяющих плоскостей и метод разделяющей поверхности 36 Выводы по главе

Глава 2 Построение алгоритмов решения систем линейных неравенств с &-значными неизвестными и их сравнительный анализ

2.1 Концепция построения алгоритма Хачияна Л.Г

2.2 Метод эллипсоидов

2.3 Адаптивный алгоритм решения систем линейных неравенств с Л-значными неизвестными

2.4 Пространственно-декомпозиционный алгоритм на базе геометрического распараллеливания адаптивного алгоритма решения систем линейных неравенств с Л-значными неизвестными

2.5 Параметры эффективности разработанных алгоритмов и их сравнение с альтернативными методами решения систем линейных

неравенств с Л-значными неизвестными

Выводы по главе

Глава 3 Применение разработанных алгоритмов в

прикладных задачах анализа узлов защиты информации

3.1 Характеризация задач информационной безопасности, сводящихся

к анализу генераторов псевдослучайных последовательностей

3.2 Применение метода разделяющих плоскостей при изучении запретов и полузапретов с использованием разработанных алгоритмов

3.3 Применение разработанных алгоритмов в задачах анализа биективных отображений с помощью систем линейных неравенств в Л-значной области

3.4 Использование разработанных алгоритмов при анализе узла

защиты информации с Л-значными преобразованиями

3.5 Применение полиэдрального метода для восстановления линейной рекурренты, реализованной линейным регистром сдвига с трехчленным законом обратной связи, по ее старшей координатной последовательности с использованием полиэдрального метода

3.6 Применение метода эллипсоидов для распознавания и нахождения

аналитического задания пороговой Л-значной функции

Выводы по главе

Заключение

Список литературы

Приложения

A. Акт о внедрении результатов диссертационного исследований в учебный

процесс Балтийского федерального университета им. И. Канта

Б. Акт о внедрении результатов диссертационного исследования в практическую деятельность ООО «Ю-КОРП»

B. Акт о внедрении результатов диссертационного исследования в практическую деятельность ООО «Лингвистические и информационные

технологии»

Г. Свидетельство о регистрации программы для ЭВМ «Программа, реализующая адаптивный алгоритм эллипсоидов решения систем линейных

неравенств с к -значными неизвестными и его модификации»

Д. Описание состава программного продукта «Программа, реализующая адаптивный алгоритм эллипсоидов решения систем линейных неравенств с

к -значными неизвестными и его модификации»

Е. Свидетельство о регистрации программы для ЭВМ: Программный комплекс «Практические приложения адаптивного алгоритма эллипсоидов в задачах информационной безопасности, сводящихся к решению систем

неравенств с к -значными неизвестными»

Ж. Описание состава программного комплекса «Практические приложения адаптивного алгоритма эллипсоидов в задачах информационной безопасности, сводящихся к решению систем неравенств с к -значными неизвестными»

Введение диссертации (часть автореферата) на тему «Построение и реализация алгоритмов решения систем целочисленных неравенств в методе разделяющих плоскостей»

Введение

Расширение арсенала методов анализа и синтеза современных узлов защиты информации за счет использования достижений математики и физики, в том числе в действительной области является актуальным направлением развития современных систем связи.

Повышение быстродействия систем обработки и передачи информации предполагает обращение к новым физическим принципам, в частности, с привлечением оптических методов. Оптическая среда обладает целым рядом особенностей в сравнении с традиционной, в частности, в оптике относительно легко может быть выполнена операция вычисления скалярного произведения и сравнения. Сочетание этих двух операций приводит к реализации пороговой функции и делает пороговый базис перспективным для переработки информации в этой вычислительной среде, включая построение систем защиты информации.

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

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

Эффективная система информационной безопасности должна обеспечивать:

1) невозможность отслеживания потоков данных в системе;

2) защиту от несанкционированного доступа;

3) защиту прав владельцев информации;

4) аутентификацию субъектов и объектов информационного взаимодействия.

Обозначенные задачи решаются с использованием генераторов ПСП и хэширования информационных потоков, циркулирующих в системе защиты информации. При этом процесс хэширования можно рассматривать как наложение последовательности, вырабатываемой дискретным генератором на соответствующее представление информационного потока. Таким образом, совершенствование методов анализа дискретных генераторов случайных последовательностей является важным аспектом в обеспечении информационной безопасности, поскольку на основе такого анализа возможно проведение успешных атак на компьютерную систему. Решение данной научно-технической задачи обеспечит получение специалистами новых знаний и инструментов для построения стойких к атакам генераторов.

В работе рассматривается класс дискретных генераторов случайных последовательностей, анализ которых может быть сведен к системам неравенств с Л-значными неизвестными, показана возможность проведения атак на такие генераторы, предложены методы защиты от них.

Основными функциями дискретных генераторов в компьютерных системах являются:

— формирование паролей пользователей в системах разграничения доступа;

— формирование ПСП в узлах с защитными преобразованиями на базе бинарного сумматора.

— формирование прекурсоров и затемняющих множителей в протоколах слепой ЭП;

— внесение неопределенности в работы средств и объектов защиты для противодействия различного рода вредоносным программам;

— формирование неповторяющихся блоков данных для защиты от Яе1ау-атак и контроля целостности последовательности сообщений;

— внесение неопределённости в работу АПС и средств связи на пример при формировании при резервировании канала связи;

— генерация случайных последовательностей объектов при проведении теста Тьюринга.

Задачу анализа генератора ПСП можно рассматривать как основную задачу информационной безопасности для данной диссертации, к которой сводятся множественные рассмотренные выше постановки конкретных практических приложений. С алгебраической точки зрения работа широкого класса генераторов ПСП порождает систему дискретных уравнений

{/(хм,..., х1+п) = уг, (1)

где х - начальное заполнение регистра сдвига, /(ууп) - функция усложнения, - выходная ПСП.

Рассмотрение системы (1) выделяет две прикладные постановки - проверку совместности системы (1), и, в случае, в случае совместности, - нахождение решений, то есть состояний х . Здесь необходимо пояснить, что обнаружение факта несовместности

системы (1) позволяет сделать вывод о том, что рассматриваемы генератор по своей логике функционирования не соответствует системе (1) и работу по поиску адекватного его описания необходимо продолжить. В случае, если закон функционирования генератора определен правильно, решение системы (1) позволит получить исчерпывающую информацию о его работе и найти начальное состояние, если переменные х связаны

некоторой известной зависимостью так, что может быть выделен некоторый базис их порождающий.

Анализ генератора ПСП с нелинейной функцией усложнения / (у,..., уп) в общем

случае собой сложную прикладную задачу [1]. В диссертации для ее решения предлагается применить так называемые пороговые методы, при использовании которых исходная задача интерпретируется как задача решения систем неравенств в действительной области с булевыми или Л-значными неизвестными. Такой прием известен как метод разделяющих плоскостей, исходные положения, обоснование и развитие которого приводится в работах Балакина Г.В., Анашкиной Н.В., Никонова В.Г., Никонова Н.В., Рыбникова К.К., Шурупова А Н., 1уапевси Р.Ь., Яиёеапи Б. и других [3, 4, 7, 9, 66,72, 74, 77, 113].

В работах этих авторов основное внимание уделялось проблеме сведения исходных нелинейных систем уравнений, описывающих работу узлов защиты информации, к равносильным системам неравенств в булевой или Л-значной области. В то же время менее подробно рассматривались вопросы анализа и решения самих систем линейных неравенств, поскольку для этого предполагалось использовать известные алгоритмы линейного программирования и дискретной оптимизации, которые адаптировались к конкретной специфике задачи.

Последующие исследования показали актуальность развития новых методов решения систем линейных неравенств, поскольку именно алгоритмическая часть метода разделяющих плоскостей в конечном итоге и определяет его вычислительную сложность. Алгоритмические вопросы приобрели еще большую актуальность после появления полиномиального алгоритма Хачияна Л.Г. решения систем линейных неравенств с целочисленными коэффициентами относительно действительных неизвестных. Не

предполагая находить непосредственно целочисленные решения, алгоритм Хачияна, тем не менее, для ряда практических приложений показал свою эффективность, позволяя по найденным действительным решениям определять целочисленные путем простого округления. Особый интерес алгоритм Хачияна. представляет при рассмотрении систем неравенств с к-значными неизвестными в силу того, что при увеличении к множество решений, образующих п-мерную к-звенную решетку, приближается к множеству действительных значений п -мерного куба со стороной равной к-1.

Таким образом, можно сделать вывод о том, что исследование алгоритмов решения систем линейных неравенств, в частности алгоритма Хачияна, представляет собой важное направление для информационной безопасности в целом, что свидетельствует об актуальности темы диссертации.

Объектом исследования являются системы целочисленных неравенств, возникающих в задачах в задачах информационной безопасности, сводящихся к решению систем такого вида.

Предметом исследования являются методы решения систем линейных неравенств в действительной и дискретной областях.

Основной целью исследования является построение и реализация алгоритмов решения линейных неравенств, возникающих в прикладных задачах информационной безопасности и дискретной математики.

Задачи исследования

1. Разработать адаптивный алгоритм решения систем линейных неравенств с дискретными переменными, основанный на методе эллипсоидов Хачияна Л.Г., для задач анализа и решения систем дискретных уравнений. Установить связь числа итераций предложенных алгоритмов с реальными исходными параметрами задачи.

2. Обосновать и экспериментально подтвердить возможность применения разработанных алгоритмов для решения прикладных задач анализа узлов защиты информации, сводящихся к решению систем линейных неравенств с к -значными неизвестными.

3. Разработать методику применения построенного адаптивного алгоритма, основанного на методе эллипсоидов, для нахождения начального заполнения линейного регистра сдвига с с трехчленным законом обратной связи, реализующего линейной-рекуррентную последовательность над кольцом Ъ , по отрезку в I подряд идущих знаков

старшего разряда и на основании результатов ее применения оценить расстояние единственности задачи /0.

4. Показать возможности изучения с помощью построенного алгоритма запретов и полузапретов булевых и к -значных функций.

5. Применить модифицированный метод эллипсоидов в задаче характеризации пороговых к -значных функций и оценить параметры сложности ее решения.

6. Разработать программный комплекс, реализующий, построенные в диссертации алгоритмы.

Актуальность диссертационного исследования определяется расширением методов анализа и решения систем линейных неравенств с к -значными неизвестными и сводимых к ним прикладных задач за счет использования алгоритмов с полиномиальной оценкой сложности.

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

Область исследования. Содержание диссертации соответствует паспорту специальности 05.13.19 - «Методы и системы защиты информации, информационная безопасность» по следующим областям исследования: : 3. Методы, модели и средства выявления, идентификации и классификации угроз нарушения информационной безопасности объектов различного вида и класса.; 6. Модели и методы формирования комплексов средств противодействия угрозам хищения (разрушения, модификации) информации и нарушения информационной безопасности для различного вида объектов защиты вне зависимости от области их функционирования.

Теоретическая значимость диссертационного исследования состоит в развитии метода разделяющих плоскостей для решения систем дискретных уравнений и сводящихся к ним системам защиты информации в Л-значной логике. С теоретической точки зрения представляет интерес получение оценок расстояния единственности в задаче нахождения начального заполнения линейного регистра сдвига с трехчленным законом обратной связи по отрезку подряд идущих знаков старшего разряда.

Практическая значимость заключается в обосновании применения метода эллипсоидов для широкого круга прикладных задач анализа узлов защиты информации, представимых в виде систем неравенств с дискретными неизвестными. Важное практическое

значение имеет выполненная в процессе диссертационного исследования разработка программного комплекса.

Методология и методы исследования. В работе использованы алгебраические, комбинаторные, геометрические, алгоритмические методы исследования, методы дискретной оптимизации и параллельные вычисления.

Объем и структура диссертации

Диссертация состоит из введения, трех глав, заключения, списка использованной литературы и 7 приложений. Каждая глава завершается выводами Общий объем диссертации - 164 с. машинописного текста (с приложениями). Основная часть работы изложена на 143 с. и содержит 19 рисунков и 16 таблиц. Библиография включает 125 наименований.

В первой главе проведен анализ метода разделяющих плоскостей в булевом случае, изучаются основные проблемы его переноса в к -значную область. В параграфе 1.1 рассматриваются свойства булевых и к -значных функций. Основное внимание уделено особенностям переноса свойств при переходе из булевой в к -значную область. В параграфе 1.2 рассмотрены методы сведения нелинейных булевых и к -значных уравнений к равносильным системам линейных пороговых ограничений. Важность рассмотренных результатов обуславливается тем, что они задают математический аппарат для переноса задачи решения систем уравнений к решению систем неравенств. Параграф 1.3 посвящен обобщению фундаментальных результатов Никонова В.Г. в построении метода разделяющих плоскостей и метода разделяющих поверхностей в булевом и, соответственно, к -значном случае, которые позволяют сводить различные прикладные задачи к системам пороговых ограничений.

Вторая глава посвящена изучению и анализу метода эллипсоидов и алгоритма Хачияна и построению на их основе алгоритмов решения систем линейных неравенств с к -значными неизвестными. В параграфе 2.1 проведен анализ концепции построения полиномиального алгоритма Хачияна. В параграфе 2.2 обобщены положения метода эллипсоидов, выделены необходимые процедуры для адаптации его применения в к -значной области. На базе проведенного анализа в параграфе 2.3 построен адаптивный алгоритм эллипсоидов решения систем линейных неравенств с к -значными неизвестными, обоснована его сходимость и определены условия его применения. На основе геометрического распараллеливания адаптивного алгоритма эллипсоидов в параграфе 2.4 построен пространственно-декомпозиционный алгоритм (ПД-алгоритм) решения систем линейных неравенств с к -значными неизвестными, реализация которого обусловлена пространственной декомпозицией начальной области поиска решений. Отмечается

возможность применения адаптивного и ПД-алгоритма для доказательства несовместности систем неравенств. В параграфе 2.5 сравниваются параметры разработанных алгоритмов с альтернативными методами решения систем линейных неравенств с к -значными неизвестными. Особое внимание уделено сравнению с эвристическими алгоритмами, которое осуществлено на построенной модели случайных систем. Для решения построенных в результате моделирования случайных систем линейных неравенств с к -значными неизвестными применены разработанные алгоритмы. На основании проведенных исследовании сделан вывод об их надежности.

В третьей главе рассмотрено применение разработанных алгоритмов в прикладных задачах анализа узлов защиты информации и дискретной математики. В параграфе 3.1 дается обзор широкого круга прикладных задач обеспечения информационной безопасности, основанных на анализе генераторов ПСП. В последующих параграфах излагаются результаты эффективного применения алгоритмов, построенных во второй главе, для решения важных типовых задач информационной безопасности, включая нахождения параметров генераторов. Наряду с изложением общей логики решения, для каждой из рассмотренных задач приводятся результаты из практической реализации. В частности, в параграфе 3.2 рассмотрена задача изучения запретов и полузапретов булевых и к -значных функций. Разработанные алгоритмы применены здесь для доказательства принадлежности комбинации знаков выходной последовательности к одному из обозначенных классов. В параграфе 3.3 разработанные алгоритмы использованы для доказательства биективности отображения. В параграфе 3.4 рассмотрены схемы анализа узлов защиты информации, реализуемых комбинирующим генератором с каскадом кольцевых регистров на входе и стационарными регистром без обратной связи. Показана возможность сведения данных задач к решению систем линейных неравенств с к -значными неизвестными, для решения которых применяются разработанные алгоритмы. В параграфе 3.5 на базе разработанных алгоритмов и результатов Никонова В.Г. и других авторов построен полиэдральный метод решения задачи восстановления линейной рекурренты, реализованной линейным регистром сдвига с трехчленным законом обратной связи, по подряд идущим знакам ее старшей координатной последовательности. Для данной задачи приведены эмпирические результаты, на основании которых получена аппроксимирующая функция, характеризующая расстояние единственности задачи. В параграфе 3.6 проведен анализ возможности применения метода эллипсоидов для распознавания и нахождения аналитического задания пороговой к -значной функции, на основе которого построен алгоритм характеризации пороговых функций на базе модифицированного метода эллипсоидов Хачияна. В конце параграфа проведено сравнение

параметров разработанного алгоритма и геометрического метода Бурделева А.В., на основе которого строится комбинированный алгоритм характеризации к -значных пороговых функций. Основным результатом главы является обоснование возможности эффективного практического применения адаптивного алгоритма эллипсоидов и его модификаций в задачах информационной безопасности.

В приложениях приведены акты о внедрении результатов диссертационного исследования, свидетельства о регистрации программ для ЭВМ, описание состава разработанных в процессе диссертационного исследования программных продуктов

В заключении подведены итоги проведенных исследований, выделены основные полученные теоретические и прикладные результаты, указаны направления дальнейших исследований по данной тематике.

Реализация и внедрение результатов работы. Результаты внедрены в форме раздела в курсе лекционных занятия в образовательный процесс БФУ им. Канта при подготовке специалистов по направлению 10.05.01 «Компьютерная безопасность» (см. Приложение А), а также используются в ООО «Ю-КОРП» и ООО «Лингвистические и информационные технологии» (см. Приложения Б, В). В процессе работы над диссертационным исследование получены свидетельства о регистрации программы для ЭВМ: «Программа, реализующая адаптивный алгоритм эллипсоидов решения систем линейных неравенств с к -значными неизвестными» №2018617222 (см. Приложения Г, Д); программный комплекс «Практические приложения адаптивного алгоритма эллипсоидов в задачах информационной безопасности, сводящихся к решению систем неравенств с к -значными неизвестными» №2018616595 (см. Приложения Е, Ж ), в которых реализованы все предложенные в диссертационном исследовании алгоритм и инструменты для проведения экспериментальных исследований.

Апробация работы. Основные результаты работы докладывались на 3 конференциях:

— На ХШП Международной конференции, XIII Международной конференции молодых ученых «Информационные технологии в науке, образовании, телекоммуникации и бизнесе 'ГГ+SE15'» (2015 г.).

— На Всероссийской конференции «Сибирская научная школа-семинар с международным участием 'Компьютерная безопасность и криптография' SГBECRYPT'17» (2017 г.).

— На XI Всероссийской научной конференции ученых, специалистов и профессорско-преподавательского состава «Территориальные распределенные системы охраны» (2018 г.)

и семинарах в Балтийском Федеральном университете им. И. Канта и Федеральном исследовательском центре «Информатика и управление» Российской академии наук.

По результатам диссертационного исследования опубликовано 10 работ. Из них семь статей в рецензируемых журналах [46, 47, 48, 52-55], рекомендованных ВАК для публикации основных научных результатов диссертаций на соискание ученой. Три публикации [49-51] в материалах международных и всероссийских конференций. Результаты диссертации с достаточной полнотой опубликованы в следующих работах:

1. Лапиков, И.И. Адаптивный алгоритм решения систем линейных неравенств с k -значными неизвестными / И.И. Лапиков, В.Г. Никонов // Труды Военно-космической академии им. А.Ф. Можайского. - 2016. - №650. - С. 88-94. (научная статья в рецензируемом научном издании)

В данной статье соискателем построена новая версия алгоритма эллипсоидов, ориентированная на нахождение целочисленных (k -значных) решений в отличии от исходной позволяющей находить решения в действительной области.

2. Лапиков, И.И. О возможности геометрического распараллеливания адаптивного алгоритма решения систем неравенств с k -значными неизвестными на базе метода эллипсоидов Хачияна // Системы управления и информационные технологии. - 2016. -№2. - С. 14-19. (научная статья в рецензируемом научном издании)

В данной статье описана предложенная соискателем методика геометрического распараллеливания адаптивного алгоритма эллипсоидов.

3. Лапиков И.И. Распознавание параметров узла защиты информации реализованного пороговой k -значной функцией / А.В. Бурделев, В.Г.Никонов, И.И. Лапиков // Труды СПИИРАН. - 2016. - №3 (46). - С. 108-127. (научная статья в рецензируемом научном издании, входит в Scopus)

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

4. Лапиков, И.И. Сравнительный анализ геометрического метода и модифицированного метода эллипсоидов в задаче распознавания параметров k -значной пороговой функции / И.И. Лапиков, А.В. Бурделев // Интернет-журнал «НАУКОВЕДЕНИЕ». -2017.- Т. 9. - №6. Режим доступа: https://naukovedenie.ru/PDF/53TVN617.pdf (научная статья в рецензируемом научном издании)

В работе автору принадлежит идея применения полиномиального алгоритма эллипсоидов для распознавания пороговой k -значной функции и сравнения с соответствующими параметрами геометрического метода. На базе проведенного

сравнения автором строится комбинированный алгоритм характеризации пороговой функции.

5. Лапиков, И.И. Применение адаптивного алгоритма эллипсоидов для изучения запретов булевых и k -значных функций / И.И. Лапиков, В.Г. Никонов, Н.В. Никонов // XXI век: итоги прошлого и проблемы настоящего плюс. - 2018. - №7(41). - С. 11-17. (научная статья в рецензируемом научном издании)

В данной работе соискателем показана возможность применения адаптивного алгоритма эллипсоидов для проверки несовместности систем сдвигового типа, порождающих запреты булевых и k -значных функций.

7. Лапиков, И.И. О возможности построения пространственно-декомпозиционного алгоритма на базе геометрического распараллеливания адаптивного алгоритма эллипсоидов // Computational nanotechnology. - 2018. - Вып. 1. - С. 140-145. (научная статья в рецензируемом научном издании)

В работе изложен пространственно-декомпозиционный алгоритм, построенный на базе пространственной декомпозиции начальной области локализации решений и геометрического распараллеливания адаптивного алгоритма эллипсоидов.

8. Лапиков, И.И. Полиэдральный метод восстановления линейной рекурренты по ее старшей координатной последовательности / И.И. Лапиков // Вестник компьютерных и информационных технологий. - 2018. - №8. С. 46-56. (научная статья в рецензируемом научном издании)

В работе показана возможность применение адаптивного алгоритма эллипсоидов для восстановления линейной рекурренты над кольцом Z , реализованной

линейным регистром сдвига с трехчленным законом обратной связи, по подряд идущим знакам ее старшей координатной последовательности, которое позвонило дать оценку расстоянию единственности задачи

Степень достоверности полученных результатов подтверждается проработкой литературных источников по теме диссертации, реализацией необходимого количества численных расчётов, а также современной методикой исследования, которые соответствуют поставленным в работе целям и задачам. Научные положения, выводы и рекомендации, сформулированные в диссертации, подкреплены убедительными фактическими данными, наглядно представленными в приведенных таблицах и рисунках. Подготовка полученных результатов проведена с использованием современных программных средств. Достоверность всех полученных результатов обосновывается их

строгими математическими доказательствами. Проверка корректности результатов осуществлялась также с использованием вычислительных экспериментов

На защиту выносятся следующие основные положения:

1. Адаптивный алгоритм решения систем линейных неравенств с к -значными неизвестными, развивающий метод эллипсоидов Хачияна. [46, 48, 51].

2. Пространственно-декомпозиционный алгоритм, основанный на геометрическом распараллеливании адаптивного алгоритма эллипсоидов. [47, 48].

3. Экспериментальное доказательство возможности применения разработанных алгоритмов для решения широкого класса прикладных задач, включая анализ узлов защиты информации, сводящихся к решению систем линейных неравенств с к -значными неизвестными [49, 52].

4. Способ применения адаптивного алгоритма эллипсоидов для восстановления линейной рекурренты над кольцом И, реализованной линейным регистром сдвига с

Список литературы диссертационного исследования кандидат наук Лапиков Игорь Игоревич, 2019 год

Список литературы

[1] Алферов, А.П. Основы криптографии: Учеб. пособие для студентов вузов, обучающихся по группе специальностей в обл. информ. безопасности / А. П. Алферов,

A. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. - 2. изд., испр. и доп. - М.: Гелиос АРВ, 2002. - 480 с.

[2] Анализ алгоритмов генерации САРТСНА. 18.01.2012. [Электронный ресурс] -Режим доступа: http://intsystem.org/295/analiz-captcha-algorithms/

[3] Анашкина, Н.В. Применение алгоритмов локального поиска к решению систем псевдобулевых неравенств / Н.В. Анашкина, А.Н. Шурупов // ПДМ. Приложения. -2015. - Вып. 8. - С. 136-138.

[4] Анашкина, Н.В. Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств / Н.В. Анашкина, А.Н. Шурупов // ПДМ. Приложения. - 2014. - Вып. 7. - С. 151-153.

[5] Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман; Пер. с англ. А.О. Слисенко; Под ред. Ю.В. Матиясевича. - Москва: Мир, 1979. - 536 с.

[6] Бабаш, А.В. Запреты автоматов и двоичных функций / А. В. Бабаш // Труды по дискретной математике (РАН АКРФ). - 2006. - Т.9. - С. 7-20.

[7] Балакин, Г.В Псевдобулево направление в дискретной математике / Г.В. Балакин,

B.Г. Никонов // Обозрение прикл. промышл. матем. - 2012. - Т. 19, вып. 6.

[8] Балакин, Г.В. Линейные псевдобулевые неравенства / Г. В. Балакин // Матем. вопросы криптографии. - 2010. - Т. 1., вып. 3. - с. 5-18.

[9] Балакин, Г.В. Методы сведения булевых уравнений к системам пороговых соотношений / Г.В. Балакин, В.Г. Никонов // Обозрение прикл. промышл. матем. -1994. - Т. 1., вып. 3. - С 389-401.

[10] Балакин, Г.В. О структуре решений системы из линейных псевдобулевых неравенств / Балакин Г.В. // Матем. вопросы криптографии. - 2012. - Т. 3, вып. 3. - С. 5-20.

[11] Балакин, Г.В. Псевдобулевы решения систем нелинейных булевых уравнений / Г.В. Балакин, В.Г. Никонов // Обозрение прикладной и промышленной математики. -2014. - Т. 21., вып. 4.- С. 1-4.

[12] Беляков-Бодин, В.И. Исследование некоторых вопросов синтеза пороговых функций

/ В.И. Беляков-Бодин С.И. Розенблит // Институт теоретической и экспериментальной физики Гос. Комитета по использованию атомной энергии СССР. 1972.

[13] Бурделев, А.В. О новом алгоритме характеризации k-значных пороговых функций / А.В. Бурделев, В.Г. Никонов // Comp. nanotechnol. - 2017. - Вып. 1. - С. 7-14

[14] Бурделёв, А.В. О построении аналитического задания k-значной пороговой функции. / А.В. Бурделев, В.Г. Никонов // Computational nanotechnology. -2015. - Вып. 2. -

C. 5-13.

[15] Бутаков, Е.В. Методы синтеза релейных устройств из пороговых элементов / Е В. Бутаков. - М: Энергия, 1970. - 328 с.

[16] Былков, Д.Н. Алгоритм восстановления ЛРП над кольцом R = TL , по линейному

усложнению ее старшей координатной последовательности / Д.Н. Былков, А.А. Нечаев // Дискретная математика. - 2010. - Т. 22, №4. - С. 104-120. [ 17] Былков, Д.Н. Параметры булевых функций, построенных с использованием старших координатных последовательностей линейных рекуррент / Д.Н. Былков, О.В. Камловский // Матем. вопр. криптогр. - 2012. - Т.3, №4. -С. 25-53.

[18] Вальцев, В.Б. Некоторые структурные принципы организации высших функций мозга / В.Б. Вальцев, В.Р. Григорьев, В.Г. Никонов // Нейрокомпьютер как основа мыслящих ЭВМ. - М.: Наука. - 1993. - С. 38-46.

[19] Гершович, В.И. Метод эллипсоидов, его обобщения и приложения / В.И. Гершович, Н.З. Шор // Кибернетика. - 1982. - №5. - С. 61 - 69

[20] Глухов, М.М. Алгебра / М.М. Глухов, В.П. Елизаров, А.А. Нечаев. - Спб-Краснодар-М.: Лань, 2015. - 608 с.

[21] Горшков, С.П. О сложности задачи нахождения числа решений систем булевых уравнений / С.П. Горшков // Дискретная математика. - 1996. - Т.8, вып. 1. - С. 72-85

[22] Горшков, С.П. О сложности нахождения приведенных представлений слабо положительных и слабо отрицательных булевых функций / С.П. Горшков // Прикладная дискретная математика. - 2008. - №1(1). - С. 7-9

[23] Гуськова, А.М. Исследование эффективности применения CAPCHA как средства защиты сайтов / А.М. Гуськова, М.А. Басараб // Современные тенденции развития науки и технологий. - 2015. - №5-2. - С. 12-17.

[24] Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон; Перевод с англ. Е. В. Левнера, М. А. Фрумкина. - М.: Мир, 1982. - 416 с.

[25] Дертоузос, М. Пороговая логика / М. Дертоузос. - М.: Мир, 1963. - 344 с.

[26] Емеличев, В.А. Многогранники. Графы. Оптимизация / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. - М.:Наука, 1981. - 344 с.

[27] Еремин, И.И. Обобщение релаксационного метода Агмона-Моцкина / И.И. Еремин // УМН. - 1965. - Т. XX, вып. 2(122). - С. 183-187.

[28] Жельников В. Криптография от папируса до компьютера. - М.: ABF, 1996. - 335 с.

[29] Журавлев, Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации / Ю.И. Журавлев // Проблемы кибернетики. - 1978. - №. 33. -

С. 5-68.

[30] Золотых, Н.Ю. Расшифровка пороговых и близких к ним функций многозначной логики: дисс. ... канд. физ.-мат. наук.:05.13.17 / Золотых Николай Юрьевич. -Нижний Новгород, 1998. - 136 с.

[31] Золотых, Н.Ю. Расшифровка пороговых и близких к ним функций: дисс. ... доктора физико-математических наук: 01.01.09 / Золотых Николай Юрьевич; [Место защиты: Моск. гос. ун-т им. М.В. Ломоносова]. - Нижний Новгород. - 2013. - 208 с.

[32] Зуев, Ю. А. Регулярные булевы функции с заданной сложностью дизъюнктивных нормальных форм / Ю.А. Зуев, Л.И. Липкин // Методы дискретного анализа в изучении булевых функций и графов. - 1989. - Вып. 48. - С. 17 -22.

[33] Зуев, Ю.А. Асимптотика логарифма числа пороговых функций алгебры логики / Ю.А. Зуев // Докл. АН СССР. - 1989. - Т. 306, N 3. - С.528-530.

[34] Зуев, Ю.А. Комбинаторно-вероятностные и геометрические методы в пороговой логике / Ю.А. Зуев // Дискретная математика. - 1991. - Вып. 3, №2. - С. 47-57.

[35] Зуев, Ю.А. Пороговые функции и пороговые представления булевых функций / Ю.А. Зуев // Математические вопросы кибернетики. - 1994. - Вып. 5. - С. 5 -61.

[36] Карп, Р. Сводимость комбинаторных проблем / Р. Карп // Кибернетический сборник. -М.: Мир - 1989. - Вып. 12. - С.16-38.

[37] Козлитин, О.А Использование 2-линейного регистра сдвига для выработки псевдослучайных последовательностей / О.А. Козлитин // Матем. вопр. криптогр. -2014. - Т.5, №1. - С. 39-72.

[38] Козлитин, О.А О периодических свойствах полилинейных регистров сдвига / О.А. Козлитин // Дискр. математика. - 2017. - Т.29, №1. - С. 27-50.

[39] Коробков В. К. О некоторых алгоритмах вычисления монотонных функций алгебры логики / В.К. Коробков, Т.Л. Резник // Доклады Академии Наук СССР. - 1962. - Т. 147, № 5. - С. 1022-1025.

[40] Коробков, В. К. Оценка числа монотонных функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики / В.К. Коробков // Доклады Академии Наук СССР. - 1963. -Т. 150, № 4. - С. 744-747.

[41] Кудрявцев О.А. Реализация алгоритмов генерации случайных чисел для формирования стойких паролей / О.А. Кудрявцев, А.В. Ларюков // Прикладная математика и информатика: современные исследования в области естественных и технических наук. - 2018. - С. 425-428.

[42] Кузьмин, А.С Восстановление линейной рекурренты максимального периода над кольцом Галуа по ее старшей координатной последовательности. / А.С. Кузьмин, А.А. Нечаев // Дискрет. мат. - 2011. - Т. 23, №2. - С. 3-31.

[43] Кузьмин, А.С. / А.С. Кузьмин, В.Л. Куракин, А.А. Нечаев // Тр. По дискр. матем. -1997. - Т.1. - С. 139-202.

[44] Кузьмин, А.С. Восстановление линейной ре-курренты над примарным кольцом вычетов по ее усложнению / А.С. Кузьмин, Г.Б. Маршалко, А.А. Нечаев // Матем. вопр. криптогр. - 2010. - Т.1, №2. - С. 31-56.

[45] Кук, С. Сложность процедур вывода теорем / С. Кук // Кибернетический сборник. -М.:Мир. - 1975. - Вып. 12. - С.5-15.

[46] Лапиков, И.И. Адаптивный алгоритм решения систем линейных неравенств с k-значными неизвестными / И.И. Лапиков, В.Г. Никонов // Труды Военно-космической академии им. А.Ф. Можайского. - 2016. - №650. - С. 88-94.

[47] Лапиков, И.И. О возможности геометрического распараллеливания адаптивного алгоритма решения систем неравенств с k-значными неизвестными на базе метода эллипсоидов Хачияна // Системы управления и информационные технологии. -2016. - №2. - С. 14-19.

[48] Лапиков, И.И. О возможности построения пространственно-декомпозиционного алгоритма на базе геометрического распараллеливания адаптивного алгоритма эллипсоидов // Computational nanotechnology. - 2018. - Вып. 1. - С. 140-145.

[49] Лапиков, И.И. О возможности применения адаптивного алгоритма эллипсоидов для нахождения начального состояния комбинирующего генератора с каскадом кольцевых регистров на входе // Материалы XI Всероссийской научной конференции ученых, специалистов и профессорско- преподавательского состава «Территориальные распределенные системы охраны». - 2018. - С. 361-367.

[50] Лапиков, И.И. О возможности применения метода эллипсоидов для распознавания пороговых функций / И.И. Лапиков // ПДМ. Приложения. - 2017. - №10. - С. 163-165

[51] Лапиков, И.И. О построении алгоритма, основанного на методе эллипсоидов Хачияна Л.Г., для решения систем неравенств с к - значными неизвестными / И.И. Лапиков, В.Г. Никонов // Информационные технологии в науке, образовании и управлении: труды международной конференции IT+S&E' 15 под ред. проф. Е.Л. Глориозова. -М.: ИНИТ. - 2015. - С 262-264

[52] Лапиков, И.И. Применение адаптивного алгоритма эллипсоидов для изучения запретов булевых и ^значных функций / И.И. Лапиков, В.Г. Никонов, Н.В. Никонов // XXI век: итоги прошлого и проблемы настоящего плюс. - 2018.- №7(41).- С. 11-17.

[53] Лапиков, И.И. Применение полиэдрального метода для восстановления линейной рекурренты по ее старшей координатной последовательности / И.И. Лапиков // Вестник компьютерных и информационных технологий. - 2018.- №8. - С. 46-56.

[54] Лапиков, И.И. Распознавание параметров узла защиты информации реализованного пороговой к-значной функцией / А.В. Бурделев, В.Г.Никонов, И.И. Лапиков // Труды СПИРАН.- 2016.-№3 (46).- С. 108-127

[55] Лапиков, И.И. Сравнительный анализ геометрического метода и модифицированного метода эллипсоидов в задаче распознавания параметров к-значной пороговой функции / И.И. Лапиков, А.В. Бурделев // Интернет-журнал «НАУКОВЕДЕНИЕ». -2017.- Т. 9, №6. Режим доступа: https://naukovedenie.ru/PDF/53TVN617.pdf

[56] Логачев, О.А. Булевы функции в теории кодирования и криптологии / О.А. Логачев, А.А. Сальников, С.В. Смышляев, В.В. Ященко. - М.: Ленанд, 2015. - 576 с.

[57] Лучинин, В.В. Информационная безопасность смарт-микросхем и технологий / В.В. Лучинин, ИМ. Садовая. - Спб.: ЛЭТИ, 2015. - 157 с.

[58] Механизмы обеспечения безопасности электронных платежных систем на основе цифровых денег / А.Б. Вавренюк [и др.] // Безопасность информационных технологий. - 2011. - Т.18, №4. - С. 77-84.

[59] Минский М., Паперт С. Персептроны. / М. Минский, С. Паперт - М: Мир, 1971. -263 с.

[60] Молдовян, Н.А. Теоретический минимум и алгоритмы цифровой подписи / Н А. Молдовян. - Спб.: БВХ-Петербург, 2010. - 304 с.

[61] Морага, К. Многозначная пороговая логика. В кн.: Оптические вычисления, под. ред. Р. Арратура. / Б. Хилл, Н. Пейгамбарян, Д. Джуэлл и др. - М.: Мир, 1993. - 439 с.

[62] Немировский, А.С. Сложность задач и эффективность методов оптимизации. / А С. Немировский, Д. Б. Юдин - М.: Наука, 1979. - 383 с.

[63] Нигматулин, Р.Г. Сложность булевых функций / Р.Г. Нигматулин. - М.: Наука, 1990. - 240 с.

[64] Никонов, В.Г. Булевы графы и функции / В.Г. Никонов, Д.С. Шевелев // Дискретная математика. - 1991. - Т. 3,№ 4. - С. 51-61.

[65] Никонов, В.Г. Геометрический метод построения сбалансированных к - значных пороговых функций и синтез подстановок на их основе / В.Г. Никонов, Д.А. Сошин // Образовательные ресурсы и технологии. - 2014. - №2. - С. 76-80.

[66] Никонов, В.Г. Градиентный алгоритм решения систем линейных неравенств с к-значными неизвестными / В.Г. Никонов, П.Н. Ситников // Вестник МГУЛ - Лесной вестник. - 2008. - №2. - С. 115-120.

[67] Никонов, В.Г. Запреты к-значных функций и их связь с проблемой разрешимости систем уравнений специального вида / В.Г. Никонов, Н.В. Никонов // Вестник РУДН. Серия прикладная и компьютерная математика - 2003. - Т.2, №1. - С. 68-79.

[68] Никонов, В.Г. Классификация минимальных базисных представлений всех булевых функций от четырех переменных / В.Г. Никонов //Обозрение прикл. промышл. матем. - 1994. - Т. 1, вып. 3. - С. 458-545.

[69] Никонов, В.Г. Методы компактной реализации биективных отображений, заданных регулярными системами однотипных булевых функций / В.Г. Никонов, А.В. Саранцев // Вестник Российского университета дружбы народов. Серия: Прикладная и компьютерная математика. - 2003. - Т. 2, № 1. - С. 94-105.

[70] Никонов, В.Г. Особенности пороговых представлений к-значных функций / В.Г. Никонов, Н.В. Никонов // Труды по дискретной математике. - 2009. - Вып. 11, №1. -С. 60-85.

[71] Никонов, В.Г. Покрытия булевых графов / В.Г. Никонов // Дискретная математика. -1994. - Вып. 6, №3. - С. 21-34.

[72] Никонов, В.Г. Пороговые представления булевых функций / В.Г. Никонов // Обозрение прикладной и промышленной математики. - 1994. - Вып. 1, №3. -С. 402-457.

[73] Никонов, В.Г. Построение и классификация регулярных систем однотипных функций / В.Г. Никонов, А.В. Саранцев // Информационные технологии в науке, образовании, телекоммуникации и бизнесе: материалы XXXI Международной конференции. Т. 5 из Прил. 1. - М.: Академия естествознания. - 2004. - С. 173-174.

[74] Никонов, В.Г. Применение полиэдральных методов в прикладных математических задачах, сводящихся к анализу и решению систем линейных неравенств / Н.В. Никонов, К.К. Рыбников // Вестник МГУЛ - Лесной вестник. - 2003. - №1. - С.81-84.

[75] Никонов, Н.В. Метод растяжения в построении классов равновероятных ^значных функций с запретом / Н.В. Никонов // Ж. Обозрение прикладной и промышленной математики. - М.: ОПиПМ. - 2006.- Т.13, вып. 6. - С.961-974.

[76] Никонов, Н.В. Полиэдральные классы функций ^значной логики с обобщенными запретами и полузапретами / Н.В. Никонов // Ж. Математические вопросы криптографии. - М.: РАН, АКРФ. - 2012. - Т.3, вып.1. - С. 53-69.

[77] Никонов, Н.В. Прикладные задачи, сводящиеся к анализу и решению систем линейных неравенств. Метод разделяющих плоскостей / Н.В. Никонов, К.К. Рыбников // Вестник МГУЛ «Лесной вестник». - 2002. - №2 (22). - С. 191-195.

[78] Оценка критичности программных дефектов в условиях работы современных защитных механизмов / А.Н. Федотов [и др.] // Труды института системного программирования РАН. - 2016. - Т. 28, №5. - С.73-92.

[79] Поляк, Б.Т. Минимизация негладких функционалов / Б.Т. Поляк // Журн. Вычислительной математики и матем. физики. - 1969. - Т.9, №3. - С. 507-521.

[80] Розенблатт Ф. Принципы нейродинамики. Перцептроны и теория механизмов мозга. / Ф. Розенблатт - М.: Мир, 1963. 470 с.

[81] Ролдугин, П.В. О числе биюнктивных функций, инвариантных относительно данной подстановки / П.В. Ролдугин, А.В. Тарасов // Дискретная математика. - 2002. - Т.14, вып. 3. - С. 23-41.

[82] Селезнева, С.П. О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина / С.П. Селезнева // Дискретная математика. -1997. - Вып. 9, №4. - С. 24-31.

[83] Соколов, А.П. О конструктивной характеризации пороговых функций / А.П. Соколов // Фундаментальная и прикладная математика. - 2009. - Вып. 15. - С. 189-208.

[84] Стецюк, П.И. К методам эллипсоидов / П.И Стецюк // Теория оптимальных решений. - Киев: Институт кибернетики им. В.М. Глушкова НАН Украины. - 1999. -С. 27-33.

[85] Стецюк, П.И. К ускорению метода эллипсоидов с помощью использования шарового слоя / П.И. Стецюк, Д.М. Буханцов // Теория оптимальных решений. - Киев: Институт кибернетики им. В.М. Глушкова НАН Украины. - 2002. - С. 63-70.

[86] Стецюк, П.И. Метод центров тяжести простых тел / П.И Стецюк // Кибернетика и системный анализ. - 1996. - №5. - С. 117-138.

[87] Стецюк, П.И. Модификация метода эллипсоидов / П.И Стецюк // Информационный бюллетень Ассоциации математического программирования. Екатеринбург: УрО РАН. - 2003. - №10. - С. 216-217.

[88] Стецюк, П.И. Об ускорении сходимости методов эллипсоидов / П.И Стецюк // Труды XII Байкальской международной конференции (Иркутск, Байкал, 24 июня - 1 июля 2001 г.). -2001. - Т. 1. Математическое программирование. - С. 9-15.

[89] Стецюк, П.И. Приближенный метод эллипсоидов / П.И Стецюк // Кибернетика и системный анализ. - 2003. - №3. - С. 141-146.

[90] Сумароков, С.Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств / С.Н. Сумароков // Обозрение прикладной и промышленной математики. - 1994. - Т.1, вып. 1. - С. 33-55.

[91] Филатов, А. Ю. Развитие алгоритмов внутренних точек и их приложение к системам неравенств: дисс. ... кандидата физ.-мат. наук: 05.13.18. / Филатов Александр Юрьевич. - Иркутск. - 2001. - 123 с.

[92] Фомичев, В.М. Дискретная математика и криптология. Курс лекций / В.М. Фомичев. Под общ. ред. Д-ра физ-мат н. Н.Д. Подуфалова. - М.: Диалог-МИФИ, 2003. - 400 с.

[93] Хачиян, Л.Г. Полиномиальный алгоритм в линейном программировании / Л.Г. Хачиян // Докл. АН СССР. - 1979. - Т. 244, №5. - С. 1093-1096.

[94] Хачиян, Л.Г. Полиномиальные алгоритмы в линейном программировании / Л.Г. Хачиян // ЖВМиМФ. - 1980. - Т.20, №1. - С. 51-68.

[95] Хачиян, Л.Г. Сложность выпуклых задач вещественного и целочисленного полиномиального программирования: дисс. ... доктора физ.-мат. наук: 05.13.02. / Хачиян Леонид Генрихович. - Москва, 1983. - 252 с.

[96] Черников, С.Н. Линейные неравенства. / С.Н. Черников. - М.: Наука, 1968. - 488 с.

[97] Шабанин, О.В. О сложности дизъюнктивной нормальной формы пороговых функций / О.В. Шабанин // Дискретная математика. - 2000. - №2, т. 12. - С. 85-92.

[98] Шабанин, О.В. Сложностные параметры двоичных пороговых функций: дис. ... канд. физ-мат. наук: 01.01.09/ Шабанин Олег Васильевич. - М., 2000. - 70 с.

[99] Шоломов, Л.А. О некоторых классах логических функций, связанных с пороговыми / Л.А. Шоломов // Проблемы кибернетики. - 1965. - №13. - С. 97-114.

[100] Шор, Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования / Н.З. Шор // Кибернетика. - 1977. - №1. - С. 94-95.

[101] Шор, Н.З. Об одном семействе алгоритмов для решения задач выпуклого программирования / Н.З. Шор, В.И. Гершович // Кибернетика. - 1979. - №4. -С. 62-68.

[102] Шор,Н.З. Использование операций растяжения пространства в задачах минимизации выпуклых функций / Н.З. Шор // Кибернетика. - 1970. - №1. - С. 6-12.

[103] Юдин, Д.Б. Информационная сложность и эффективные методы решения выпуклых экстремальных задач / Д.Б. Юдин, А.С. Немировский // Экономика и математические методы. -1976. - Т. 12, вып. 2.- С. 357-369.

[104] Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. - М.:Высшая школа, 2003. - 484 с.

[105] Agmon, S. The relaxation method for linear inequalities / S. Agmon // Canadien Journal of Mathematics - 1954. №6. - P. 382-392.

[106] Anindya, D. Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces./ D. Anindya , I. Diakonikolas V. Feldman, R.A. Servedio // Journal of the ACM (JACM). -2014. - Volume 61. - Issue 2. Режим доступа: https://arxiv.org/pdf/1206.0985.pdf.

[107] Bylkov, D.N. Reconstruction of a linear recurrence of maximal period over a Galois ring of characteristic p3 by its highest digital sequence / D. N. Bylkov // Mat. Vopr. Kriptogr. -2014. - Volume 5, issue 2. - P. 29-35.

[108] Chow, C. On the characterization of threshold functions. / C. Chow // Proceedings of the Symposium on Switching Circuit Theory and Logical Design (FOCS). - 1961. - P. 34-38.

[109] Crama, I. Boolean functions Theory, Algorithms and Applications. Encyclopedia of Mathematics and its Applications. / I. Crama, P.L. Hammer. - Cambridge: Cambridge University Press. - 2011. - 710 p.

[110] Fujita, Y. The functional completeness of many-values threshold function / Y. Fujita, T. Kitahashi, K. Tanaka // Trans. L. E. C. E. - Japan. - 1970. - 53-C, №5. - P. 341-342.

[111] Golic, J.D. On the security of nonlinear filter generators / J.D. Golic // Fast Software Encryption, FSE'96 / Gollman (Ed.). Springer-Verlag Berlin Heidelberg. - 1996. - LNCS. 1039. - P. 173-188

[112] Grove, A.J. General Convergence Results for Linear Discriminant Updates. / A.J. Grove, N. Littlestone, D. Schuurmans // Machine Learning. - 2001. - № 43. - P. 173-210.

[113] Ivanescu (Hammer), P.L. Boolean methods in operator research and related areas / P.L. Ivanescu, S. Rudeanu. - Berlin Heidelberg New York: Springer Verlag, 1968. - 331 p.

[114] Karmarkar, N. A New Polynomial Time Algorithm for Linear Programming, / N. Karmarkar // Combinatorica. - 1984. -. Vol 4, nr. 4. - P. 373-395.

[115] Kumar, P.V. An expansion for the coordinates of the trace function over Galois rings / P.V. Kumar, T. Helleseth // Applicate algebra in engineering, communication and computing, Springer-Verlag. - 1997. - pp. 353-361.

[116] Kurakin, V.L. Linear recurring sequences over rings and modules / V. L. Kurakin, A.S. Kuzmin , A.V. Mihalev , A.A. Nechaev // J. of Math Sciences, 76. 1995 (Contemporary Math/ and its Appl. Thematic surveys. Vol. 10. Algebra 2. Moscow). - 1994. - №6. -P. 2793-2915.

[117] Littlestone, N. Learning quickly when irrelevant attributes abound: «A New Linear-Threshold Algorithm». / N. Littlestone //Machine Learning. - April 1988. -Volume 2, issue 4. - P. 285-318.

[118] Motzkinro T. The relaxation method for linear inequalities / T. Motzkin. I.J. Schoenberg // Canadien Journal of Mathematics. - 1954. - №6. - P. 393-404.

[119] Ngom, A. Synthesis of Multiple-Valued Logic Functions by Neural Networks, Ph.D. Thesis Dissertation. / Alioune Ngom. - Computer Science Department, University of Ottawa, Ontario. - October 1998.- 142 p.

[120] O'Donnell, R. The Chow parameters problem. / R. O'Donnell, R.A. Servedio. // STOC. -2008. - P. 517-526.

[121] Obradovic, Z. Learning with Discrete Multi-Valued Neurons / Z. Obradovich, I. Parberry // Machine Learning: Proc. 7th Int'l. Conf., ed. B. W. Porter and R.J. Mooney, Austin, TX, Morgan-Kaufmann. - 1990. - P. 392-399.

[122] Tian Tian, Injectivity of compressing map on primitive sequences over Z / Tian Tian, Weng

Feng Qi // IEEE Trans. Inform. Theory. - 2007. - V. 53, №8. - P. 2960-2966.

[123] Weng-Feng Qi, Compressing maps on primitive sequences over Z/2n and analysis of their derivative sequences: PhD Thesis. / Weng-Feng Qi. - Zhengzhou Inform. Eng. Univ., Zhengzhou, China, 1997.

[124] Xuan-Young, Zhu Compression mappings on primitive sequences over Z / Xuan-Young

Zhu, Weng Feng Qi // IEEE Trans. Inform. Theory. - 2004. - V. 50, №10. - P. 2442-2448.

[125] Xuan-Young, Zhu Uniqueness of the disturbtion of zeroes of primitive level sequences over 2y / Xuan-Young, Zhu, Weng Feng Qi // Finite fields and their applications. 2005. V. 11,

№1. - P. 30-44.

МИНИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение

высшего образования «Балтийский федеральный университет имени Иммануила Канта»

(БФУ им. И. Канта)

УТВЕРЖДАЮ

Проректор по научной работе и международным связям

I. Канта»

Э.К. Зильбер ■2018 г.

АКТ

о внедрении результатов диссертационного исследования Лапикова И.И. в образовательный процесс БФУ им. И. Канта

Результаты диссертационного исследования на соискание ученой степени кандидата технических наук «Построение и реализация алгоритмов решения систем целочисленных неравенств в методе разделяющих плоскостей» по научной специальности 05.13.19 «Методы и системы защиты информации, информационная безопасность», выполненного аспирантом Федерального государственного учреждения «Федеральный исследовательский центр «Информатика и управление» Российской академии наук» внедрены в учебный процесс Института физико-математических наук и информационных технологий БФУ им. И. Канта.

Вид результатов внедренных в учебный процесс: адаптивный алгоритм эллипсоидов решения систем целочисленных неравенств с к-значными неизвестными, пространственно-декомпозиционный алгоритм решения систем линейных неравенств с к-значными неизвестными на базе геометрического распараллеливания адаптивного алгоритма эллипсоидов, алгоритм харатери-зации к-значных пороговых функций на основе модифицированного алгоритма эллипсоидов Хачияна, применение адаптивного алгоритма эллипсоидов и его модификаций в задачах анализа узлов защиты информации, сводя-

щихся к решению систем линейных неравенств с дискретными неизвестными.

Область применения: лекционные и практические занятия по дисциплинам «Дискретная математика», «Компьютерный практикум по методам вычисления дискретного логарифма», «Технология инфраструктуры открытых ключей».

В форме методических рекомендаций по проведению лекционных занятий и практических занятий.

Настоящий акт составлен комиссией в составе: Председатель комиссии

Директор Института физико-математических наук и информационных технологий БФУ им. И. Канта

д. ф.-м. н., профессор Члены комиссии

А.В. Юров

Первый заместитель директора Института физико-математических наук и информационных технологий БФУ им. И. Канта

к. ф.-м. н, доцент ^^млЛЛуЬ^/-Шпилевой

Ведущий менеджер образовательных программ

ф/ Е.П. Новикова

Методический руководитель направлений

«Компьютерная безопасность» и «Информационная безопасность»

к. т. н., доцент С Алешников

и мал

2018 г.

АКТ

о внедрении результатов диссертационного исследования Лапикова И.И. в практическую деятельность ООО «Ю-КОРП»

Результаты диссертационного исследования на соискание ученой степени кандидата технических наук «Построение и реализация алгоритмов решения систем целочисленных неравенств в методе разделяющих плоскостей» по научной специальности 05.13.19 «Методы и системы защиты информации, информационная безопасность», выполненного аспирантом Федерального государственного учреждения «Федеральный исследовательский центр «Информатика и управление» Российской академии наук Лапиковым И.И. включающие:

— экспериментальное доказательство возможности применения разработанных алгоритмов для решения широкого класса прикладных задач, включая анализ узлов защиты информации, сводящихся к решению систем линейных неравенств с /с-значными неизвестными;

— применение модифицированного метода эллипсоидов Хачияна для характеризации /с-значной пороговой функции усложнения генератора псевдослучайной последовательности

прошли успешную апробацию в компании ООО «Ю-КОРП» и внедрены в эксплуатацию в виде модуля программного комплекса тестирования генераторов ПСП, используемых для формирования САРТСНА для разрабатываемых в компании WEB-сервисов.

Практическое использование указанных результатов позволило:

— усовершенствовать требования к используемым при реализации САРТСНА генераторам ПСП на основе предложенных в диссертационном исследовании методов анализа;

— повысить защищенность разрабатываемых WEB-сервисов за счет определения того, что пользователь или заказчик услуги сайта является человеком, а не роботом.

Считаю целесообразным рекомендовать полученные в диссертационном исследовании результаты к внедрению на различных предприятиях для решения задач разработки защищенных WEB-сервисов, решения оптимизационных задач.

Генеральный директор ООО «Ю-КОРП»

¿у-м^о 2018 г.

Е.А. Холина

Экз.1

УТВЕРЖДАЮ

Генеральный директор кандидат фи^п!©^^«1^тическ1«наук

ГВ.Федюкин

Общество с ограниченной

ответственностью «ЛИНГВИСТИЧЕСКИЕ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ» (ООО «Линфо»)

127018, г. Москва, ул. Образцова, д.38, стр. 1 тел./факс [phone] e-mail: ¡[e-mail]

№ 110-18

АКТ

О внедрении результатов диссертационной работы

Лапикова Игоря Игоревича «ПОСТРОЕНИЕ И РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ СИСТЕМ ЦЕЛОЧИСЛЕННЫХ НЕРАВЕНСТВ В МЕТОДЕ РАЗДЕЛЯЮЩИХ ПЛОСКОСТЕЙ»

Комиссия в составе:

председателя комиссии: зам. генерального директора, к.ф.-м.н., Мельникова С.Ю., членов комиссии: начальника отдела разработки программного обеспечения и

электронного обучения Пичкура К.Б.,

старшего научного сотрудника отдела информационно-аналитических технологий Скопцовой Е.В.

составила настоящий акт о том, что результаты диссертационной работы Лапикова Игоря Игоревича имеют практическую ценность и были использованы для разработки программно-аппаратного комплекса при выполнении договора № 9/184.17 от 30.08.2017 с ФГУП «РНИИРС».

Разработанные в диссертации алгоритмы реализованы в форме отдельных классов на языке С#, что позволило интегрировать их в используемые программные продукты. Программный продукт «Адаптивный алгоритм эллипсоидов решения систем линейных неравенств с ¿-значными неизвестными и его модификации» включает в себя проекты:

- НасЫуап, в котором реализован полиномиальный алгоритм Хачияна, модифицированный критерием выхода по отрицательной невязке в центре эллипсоида,

- НасЫуапЛШо1оас1, в котором реализован адаптивный алгоритм эллипсоидов для стандартных типов данных языка С# с функцией потоковой загрузки,

- НасЫуапМрй", в котором реализован адаптивный алгоритм эллипсоидов для чисел неограниченной разрядности,

- БоМюпСЬекег, в котором реализована проверка полученных решений с возможностью тотального перебора.

Использование разработанного адаптивного алгоритма эллипсоидов для целевых задач классификации оказалось более эффективным, чем использование общих алгоритмов, реализованных в универсальных математических пакетах.

Председатель комиссии: Члены комиссии:

С.Ю. Мельников К.Б. Пичкур Е.В. Скопцова

ОПИСАНИЕ состава программы для ЭВМ «Программа, реализующая адаптивный алгоритм эллипсоидов решения систем линейных неравенств с к -значными неизвестными и его модификации»

Язык разработки: C#

Среда разработки: Microsoft Visual Studio 2015.

Исходные тексты депонированы в ФГБУ «Федеральный Институт промышленной собственности. (Свидетельство о регистрации программы для ЭВМ №2018617222).

Программный продукт «Адаптивный алгоритм эллипсоидов решения систем линейных неравенств с к -значными неизвестными и его модификации» состоит из следующих проектов:

1). Проект Hachiyan, в котором реализован полиномиальный алгоритм Хачияна, модифицированный критерием выхода по отрицательной невязке в центре эллипсоида и возможностью выбора начальной локализации области решений.

2). Проект HachiyanAutoload, в котором реализован адаптивный алгоритм эллипсоидов для стандартных типов данных языка C# с функцией потоковой загрузки неравенств и ведения лог-файла работы.

3). Проект HachiyanMpfr, в котором реализован адаптивный алгоритм эллипсоидов для чисел неограниченной разрядности, реализованной за счет адаптации библиотеки больших чисел MPFR для языка C# путем перегрузки операторов.

4). Проект HachiyanMultitask, в котором реализован ПД-алгоритм для стандартных типов данных.

5). Проект SolutionCheker, в котором реализована проверка полученных решений, а также возможна проверка путем тотального перебора.

6). Проект SolutionChekerMPFR, в котором реализована возможности проверки решений типа MPFR, то есть чисел неограниченной разрядности.

Отметим, что все реализации адаптивного алгоритма реализованы в виде отдельного класса и могут использоваться в приложениях других разработчиков.

ОПИСАНИЕ состава программного комплекса «Практические приложения адаптивного алгоритма эллипсоидов в задачах информационной безопасности, сводящихся к решению систем неравенств с к -значными неизвестными»

Язык разработки: C#

Среда разработки: Microsoft Visual Studio 2015.

Исходные тексты депонированы в ФГБУ «Федеральный Институт промышленной собственности. (Свидетельство о регистрации программы для ЭВМ №2018616595).

Программный продукт «Практические приложения адаптивного алгоритма эллипсоидов в задачах информационной безопасности, сводящихся к решению систем неравенств с к -значными неизвестными» состоит из следующих проектов:

1). Проект EquationGeneraror, в котором реализован генератор случайных систем линейных неравенств. (эксперимент параграфа 2.4)

2). Проект InequalityGenerator, в котором реализована генерация систем линейных неравенств знаками старшего разряда, вырабатываемыми ЛРС с трехчленным законом обратной связи (эксперимент параграфа 3.5).

3). Проект Counter, в котором реализована генерация СЛН по знакам выходной последовательности, получаемой комбинирующим генератором с каскадом кольцевых ЛРС на входе и пороговой функцией усложнения (эксперимент параграфа 3.4.1)

4). Проект Register, в котором реализована генерация СЛН по знаком выходной последовательности, получаемой автоматом на базе стационарного регистра с пороговой функцией усложнения (эксперимент пункта 3.4.2).

5). Проект GenerateDataForHachiyan, в котором реализована генерация СЛН в задаче характеризации пороговых функций по ее табличному заданию (эксперимент параграфа 3.6)

6). Проект HachiyanAutoload, в котором реализован адаптивный алгоритм эллипсоидов для стандартных типов данных языка C# с функцией потоковой загрузки неравенств и ведения лог- файла работы.

7). Проект HachiyanAllinOne, представляет собой объединенную версию проекта InequalityGenerator и HachiyanAutoload. (для проведения эксперимента по поиску расстояния единственности параграфа 3.5).