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

• Автор: Осипян, Валерий Осипович
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Ставрополь
• Количество страниц: 371 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

I. АНАЛИЗ МОДЕЛЕЙ И МЕТОДОВ РЕШЕНИЙ ПОЛНЫХ ЗАДАЧ.

1.1. Анализ алгоритмов построения полиномов с заданными свойствами в полях Галуа

1.2. Анализ алгоритмов факторизации полиномов в нолях Галуа.

1.3. Труднорешаемые задачи и модели систем защиты информации

1.4. Моделирование труднорешаемых задач с помощью диофантовых уравнений

II. МОДЕЛИРОВАНИЕ ЦИКЛИЧЕСКИХ КОДОВ НА ОСНОВЕ Хпх.

2.1. Рекуррентный метод моделирования полинома Хпх .

2.2. Численный алгоритм построения Хпх

2.3. Вычисление коэффициентов полинома Хх
2.4. Моделирование неприводимых полиномов с помощью подстановок.
2.5. Метод циклотомических классов моделирования Хпх
2.6. Моделирование циклических кодов с порождающим полиномом Xx.
2.7. Математические модели циклических кодов.
III. МЕТОДЫ ФАКТОРИЗАЦИИ ПОЛИНОМОВ В ПОЛЯХ ГАЛУА
3.1. Алгоритм факторизации полиномов над с помощью функциональных цепных дробей
3.2. Операторный метод факторизации полиномов и смежные с ним задачи
3.3. Факторизация полиномов с заданным периодом.
3.4. Метод перестановочных целых функций
3.5. Моделирование неприводимых полиномов методом анализа
IV. МОДЕЛИ И МЕТОДЫ ПАРАМЕТРИЧЕСКИХ РЕШЕНИЙ
МНОГОСТЕПЕННЫХ СИСТЕМ ДИОФАНТОВЫХ УРАВНЕНИЙ
4.1. Основные модели и методы многоиараметрических решений.
4.2. Метод решений нормальных многостепенных систем
4.3. Метод решения с помощью понижения степени.
4.4. Метод решения на основе введения целозначных функций
4.6. Метод общих решений уравнений ой степени
4.7. Модели и методы решений в целых комплексных числах
4.7.1. Решение систем второго порядка в целых комплексных числах.
4.7.2. Метод решения нормальной системы рстьего порядка.
4.7.3. Метод решения нормальной системы четвртоо порядка.
4.7.4. Метод решения нормальной сисземы пятого порядка.
4.7.5. Метод общих решений в целых и комплексных числах.
V. МАТЕМАТИЧЕСКИЕ МОДЕЛИ СИСТЕМ ЗАЩИТЫ
ИНФОРМАЦИИ НА ОСНОВЕ ПОЛНЫХ ЗАДАЧ
5.1. Модель на основе обобщенного рюкзака.
5.2. Модель на основе кода Варшамова
5.3. Моделирование с помощью универсального рюкзака.
5.4. Моделирование с помощью функционального рюкзака
5.5. Модели полиалфавитных систем защиты информации.
5.6. Моделирование систем, содержащих диофаиговую трудность.
5.6.1. Модель защиты информации на основе конструктивного рюкзака.
5.6.2. Модель защиты информации на основе закрытого рюкзака.
5.6.3. Модель с обнаружением и исправлением ошибок
5.7. Моделирование асимметричных систем на основе задачи факторизации.
5.7.1. Модель многопользовательского варианта .
5.7.2. Модель полиномиального варианта
5.8. Моделирование перестановок на основе перестановочных целых функций.
5.9. Метод композиции различных моделей.
5 Модель преобразования на основе теоремы Эйлера Ферма
VI. АЛГОРИТМЫ И ОЦЕНКИ НА ОСНОВЕ
ПРЕДЛОЖЕННЫХ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ.
6.1. Оценка значений коэффициентов Хх и гипотеза Н.Г.Чеботарва
6.2. Алгоритм защиты информации на основе модели плотного обобщнного рюкзака и его реализация на ЭВМ.
6.3. Алгоритм защиты информации па основе модели плотного универсального рюкзака и его реачизация на ЭВМ.
6.4. Алгоритм защиты информации на основе модели функционального рюкзака
Заключение
Литература


Таким образом, приведнные выше различные способы моделирования неприводимых над конечным полем полиномов заданной степени, позволяют сделать вывод о том, что вычисления можно существенно сократить, если применить новые теоретикочисловые результаты. Поэтому необходимо разработать новые конструктивные методы моделирования полиномов в явном виде над конечными полями, включающие более эффективные и гибкие подходы и для более узкого класса полиномов, но уже для полиномов с достаточно высокими степенями. В частности, необходимы методы, использующие алгебраическую структуру конечных полей, аппаратные средства современной алгебры, требующих выполнений значительно меньшего числа по сравнению с существующими методами арифметических операций и допускающих эффективную реализацию на ЭВМ. Ввиду повышенного интереса к проблемам факторизации и большой активности развития исследований в этом направлении, приведм краткую характеристику состояния этого вопроса. Отметим, что проблема создания эффективных алгоритмов разложения полиномов над конечными полями особенно важна для теории передачи и защиты информации, в частности для теории кодирования и для изучения линейных рекуррентных соотношений в конечных ПОЛЯХ. В последнее время, ввиду отсутствия алгоритма полиномиальной сложности решения данной задачи, е применяют для создания эффективных систем защиты информации. В частности, при решении задачи дискретного логарифмирования в расширенном поле к которой сводится задача логарифмирования на эллиптической кривой. Кроме того, этот алгоритм может использоваться при выборе неприводимого полинома, задающего расширенное поле. Можно привести также ряд вычислительных задач, которые тесно связаны с факторизацией полиномов над конечными полями. В предыдущем разделе мы изучили различные алгоритмы построения неприводимых над конечными полями полиномов с заданными свойствами. Теперь рассмотрим алгоритмы факторизации полиномов над конечными полями, исходя из параметров самого полинома и конечного поля, т. Очевидно, эти алгоритмы одновременно позволят нам строить новые неприводимые полиномы над конечными полями. Хорошо известно , что каждый полином положительной степени п x ,x . Пусть п и i,2vi В дальнейшем мы будем считать, что исходный полином x также нормирован и нашей ближайшей целью является практическое представление его в виде 1. Очевидно, если x НОДГх, х наибольший общий делитель полиномов x и его производной х равен единице, то x не имеет кратных сомножителей. Если же x x, то исходный полином представляет собой степень некоторого полинома x из x, а именно x x4 где некоторая степень характеристики поля . Учитывая последнее соотношение можно без ограничения общности рассмотреть полиномы, которые не имеют кратных неприводимых сомножителей. Следующая теорема является основной 8, . Теорема 1. П НОДГх, x е. Заметим, что формула 2 не дат полного разложения x, поскольку полином под произведением может оказаться приводимым в x. Если x с x для некоторого элемента с е , то по формуле 2 имеем тривиальное разложение x, что не имеет смысла в контексте данной задачи. Если же полином x таков, что по 2 можно найти нетривиальное разложение полинома x, то он называется разлагающим полиномом. Для построения алгоритма разложения необходимо найти способы построения разлагающих полиномов, что связано с вычислением наибольших общих делителей, и применить на практике это формулу возможно лишь для достаточно малых конечных полей . X . В п x матрица над , iя строка которой соответствует полиному хяЧ, приведнному по модулю x. Отметим, что возможность использования матрицы В для определения числа нормированных неприводимых сомножителей полинома x была замечена ещ раньше, а общий случай был исследован Шварцом . Результат, состоящий в том, что п к, установлен автором 5. Рассмотрим ещ один способ построения разлагающих полиномов, который связан с построением некоторого семейства линеаризованных полиномов, содержащего по крайней мере один разлагающий полином. Теорема 1. Пусть полином без кратных сомножителей xx приводим в x.