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

На правах рукописи

Мурин Дмитрий Михайлович

Компьютерно-аналитическое исследование

задач рюкзачного типа как средство анализа и совершенствования систем защиты информации

05.13.19 - Методы и системы защиты информации, информационная безопасность

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

" 8 АВГ

Томск - 2013

005531958

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Ярославский государственный университет им. П.Г.Демидова» на кафедре компьютерной безопасности и математических методов обработки информации.

Научный руководитель: доктор физико-математических наук, профессор

Дурнев Валерий Георгиевич

Официальные оппоненты:

Горшков Сергей Павлович, доктор физико-математических наук, войсковая часть № 71330-А, сотрудник

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

Ведущая организация: Федеральное государственное автономное

образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина»,

г. Екатеринбург

Защита состоится «3» сентября 2013 г. в 9 часов 00 минут на заседании диссертационного совета Д 212.267.22, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (корпус № 2, аудитория 2126).

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Автореферат разослан июля 2013 г.

Ученый секретарь диссертационного совета

Тренькаев Вадим Николаевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Ряд современных систем защиты информации и обеспечения информационной безопасности базируется на NP-полных Задачах. Задачи из класса NP-полных являются, в определенном смысле, «очень сложными» для решения, поэтому, с одной стороны, представляет особый интерес изучение средств и систем защиты информации, для преодоления которых необходимо решить лежащую в их основе NP-полную Задачу, а с другой стороны, методы решения индивидуальных представителей NP-полных Задач представляются естественными методами анализа эффективности разрабатываемых средств и систем защиты информации. Одной из систем защиты информации, в основе которой лежит NP-полная Задача, является асимметричная система шифрования Меркля-Хеллмана, основанная на NP-полной Задаче распознавания - Задаче о рюкзаке. В работах А. Шамира, Е. Брикелля, А. Лагариаса и Дж. Одлыжко по анализу этой системы были предложены методы решения некоторых множеств задач о рюкзаках - индивидуальных представителей вычислительной Задачи о рюкзаке. В диссертационной работе метод решения вычислительной Задачи о рюкзаке, предложенный Дж. Лагариасом и А. Одлыжко1, модифицируется в метод решения вычислительной Обобщенной Задачи о рюкзаке и методы решения систем задач о рюкзаках. Кроме того, в диссертационной работе предлагается основанный на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке метод решения за «приемлемое время» представителей NP-полных Задач - LLL-решатель.

Зарождение теории NP-полноты связывают с опубликованной в 1971 году работой С. Кука. В этой работе была установлена важность понятия «полиномиальная сводимость Задач», выделен класс Задач распознавания свойств, которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве (недетерминированной машине Тьюринга) (класс NP). Кроме того, было показано, что Задача о выполнимости конъюнктивной нормальной формы - представитель класса NP - обладает тем свойством, что любая другая Задача из класса NP может быть сведена к ней за полиномиальное время (то есть в определенном смысле Задача о выполнимости является самой сложной Задачей в классе

1 Odlyzko A.M., Lagarias J.C. Solving Low-Density Subset Sum Problems // Journal of the Association for Computing Machinery. 1985. vol. 32, № 1. p. 229-246.

1 \

NP), и установлено, что таким свойством могут обладать и другие задачи из класса NP (например, Задача о существовании в графе G клики с определенным числом вершин).

Р. Карп, опубликовавший свои результаты вслед за работой С. Кука, показал всю ширину класса «самых трудных» задач из класса NP, получившего название «класс NP-полных Задач». Оказалось, что значительная часть известных комбинаторных Задач (о коммивояжере, о клике, о вершинном покрытии и другие) принадлежит к классу NP-полных.

Одной из рассмотренных Р. Карпом NP-полных Задач была Задача о рюкзаке (распознавания) (также известная как Задача «subset sum» Задача о сумме элементов подмножества, 0-1 рюкзак), предложенная в 1978 году Р. Мерклем и М. Хеллманом в качестве основы для построения асимметричной системы шифрования.

В работе 1982 года А. Шамир2 предложил полиномиальный по времени от размерности рюкзачного вектора алгоритм, решающий «практически все» задачи о рюкзаках, рюкзачный вектор которых можно получить с помощью операции сильного модульного умножения из сверхрастущего вектора, способом, предложенным Р. Мерклем и М. Хеллманом для формирования открытых ключей из закрытых в их системе.

Несмотря на то, что А. Шамир показал, что система Меркля-Хеллмана является ненадежной, попытки ее усовершенствования до сих пор не прекращаются, о чем свидетельствуют работы Р. Гудмана и Э. Маколи3, X. Ни-деррайтера4, Б. Шора и Р. Ривеста5, В.О. Осипяна и В.В. Подколзина6. Более полный обзор работ в области анализа системы Меркля-Хеллмана и ее развития дан Б. Шнайером7.

2Shamir A. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem // Proceedings of the 23rd FOCS Symposium. 1982. p. 145-152.

3Goodman R-, McAuley A. A new trapdoor knapsack public-key cryptosystem // IEE PROCEEDINGS. 1985. Vol. 132. ,V>6. p. 289-292.

4Niederreiter H. Knapsack-Type Cryptosystems and Algebraic Coding Theory // Problems of Control and Information Theory. 1986. № 15(2). p. 159-166.

5Chor В., Rivest R. A knapsack-type public key cryptosystem based on arithmetic in finite fields // In Advances in Cryptology CRYPTO'84, LNCS, Springer-Verlag. 1985. p. 54-65.

6Осипян B.O. О криптосистемах с заданным рюкзаком // Материалы VI Международной научно-практической конференции «Информационная безопасность». Таганрог: Иэд-во ТРТУ. 2004. С. 269 271.

Осипян В.О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета. 2006. Т. 309. №2. С. 209 212.

Подколзин В.В., Осипян В.О. Об одном методе определения верхней границы числа входов для рюкзачных систем защиты информации // Вестник Воронежского института МВД России. 2010. №4. С. 83-90.

7Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Триумф, 2002. 816 с.

В 1985 году в работе Дж. Лагариаса и А. Одлыжко8 был предложен метод решения вычислительной Задачи о рюкзаке, дающий верное решение для «практически всех» задач о рюкзаке, плотность (отношение размерности вектора к двоичному логарифму его максимального элемента) которых не превышает 0,6463..., основанный на сведении вычислительной Задачи о рюкзаке к Задаче вычисления кратчайшего ненулевого вектора решетки. Этот результат был улучшен М. Костером и другими9 до плотности, меньшей 0,9408... В диссертационной работе автором рассмотрен вопрос о том, насколько существенны такие ограничения плотности.

Среди методов решения индивидуальных представителей NP-полных Задач за «приемлемое время» наибольшей популярностью, на наш взгляд, на текущий момент обладают методы, предполагающие сведение исходной индивидуальной задачи к задаче выполнимости конъюнктивной нормальной формы (SAT, ВЫП) с последующим решением полученной SAT-задачи с помощью специализированного программного комплекса SAT-решателя10. В этом случае SAT выступает в качестве опорной (базовой) NP-полной Задачи. В основе многих SAT-решателей лежит алгоритм DPLL, разработанный в 1960-1962 годах М. Дэвисом, X. Путманом, Дж. Логеманном и Д. Лавлендом, еще до работ С. Кука и Р. Карпа. Поэтому представляют интерес альтернативные подходы к решению за «приемлемое время» индивидуальных представителей NP-полных Задач. В диссертационной работе предлагается метод решения за «приемлемое время» представителей NP-полных Задач - LLL-решатель, основанный на уже упомянутом методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке. Предлагаемый метод, кроме прочего, интересен тем, что в его основе лежат алгебраические понятия и конструкции, что позволяет привлекать при анализе мощный аппарат этого раздела математики.

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

8Odlyzko A.M., Lagarias J.C. Solving Low-Density Subset Sum Problems, p. 229-246.

9Coster M.J., Joux A., LaMacchia B.A., Odlyzko A.M., Schnorr C.-P., Stern J. Improved low-density subset sum algorithms // Computational Complexity. 1992. №2. p. 111-128.

10Goldberg E., Novikov Y. BerkMin: A fast and robust SAT-solver // In Design, Automation, and Test in Europe. 2002. p. 142-149.

Moskcwicz M., Madigan C., Zhao Y., Zhang L., Malik S. Chaff: Engineering an EfficicnL SAT Solver //In Proc. 38th Design Automation Conference. 2001. p. 530-535

представителей КР-полных Задач за «приемлемое время» для информационной безопасности.

Объект исследования

Объектом диссертационного исследования являются ^-полные Задачи, используемые для построения систем защиты информации.

Предмет исследования

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

Цель работы

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

Для достижения указанной цели в диссертационной работе были поставлены и решены следующие задачи:

1) получить оценки числа инъективных векторов и числа сверхрастущих векторов с заданными размерностью и максимальным элементом;

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

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

4) модифицировать метод Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке применительно к случаю вычислительной

Обобщенной Задачи о рюкзаке и случаям, когда нам известно не менее двух задач о рюкзаках, имеющих одинаковое решение (система задач о рюкзаках);

5) получить верхнюю оценку плотности инъективных векторов;

6) разработать программное обеспечение, позволяющее генерировать приведенные задачи о рюкзаках с заданными размерностью вектора и максимальным элементом и решать полученные задачи с помощью метода Лагариаса-Одлыжко; поставить эксперимент по определению доли задач о рюкзаках из заранее определенного множества задач, верно решаемых с помощью метода Лагариаса-Одлыжко;

7) проанализировать возможность решения индивидуальных представителей ИР-полных Задач путем сведения их к задачам о рюкзаках и применения к последним метода Лагариаса-Одлыжко.

Области исследований

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

Методы исследований

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

Положения, выносимые на защиту

1. Установлены нижние и верхние оценки для числа сверхрастущих и инъективных векторов, элементы которых являются натуральными числами, с заданными размерностью и максимальным элементом. Показано, что число сверхрастущих и инъективных векторов фиксированной размерности г, элементы которых являются натуральными числами, растет с ростом максимального элемента вектора как полином (г — 1)-ой степени от максимального элемента вектора.

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

3. Предложены методы решения вычислительной Обобщенной Задачи о рюкзаке и систем задач о рюкзаках, основанные на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке.

4. Предложен подход к решению за «приемлемое время» индивидуальных представителей NP-полных Задач - LLL-решатель. Предложено понятие функции применимости алгоритма к множеству решаемых задач, проведена серия компьютерных экспериментов по вычислению функций применимости LLL-решателя к решению задач о рюкзаках.

5. В результате вычислительных экспериментов, в ходе которых решалось более 20 миллиардов различных задач о рюкзаках малых размерностей (г < 9), было установлено, что характер смещения ветвей функций применимости LLL-решателя с ростом г в случае, если в качестве претендента на вектор, дающий решение задачи о рюкзаке, рассматривается только первый вектор LLL-приведенного базиса, не является равномерным.

6. Установлены верхние и нижние границы для значений элементов b¡ последовательности Штерна £>i = 1, 62 = 1, 63 = 2, 64 = 3, 65 = 6, Ьб = 11, Ь? = 20, bs = 40... В предположении, что вектор (ai,..., ar) размерности г ^ 4, элементы которого строятся по следующему правилу:

г

ai = br, a2 = br + 6r_i, ..., ar = b{,

i=l

является инъективным вектором с наименьшим возможным среди инъективных векторов размерности г максимальным элементом, устанавливается, что плотность din инъективных векторов размерности г ^ 4 удовлетворяет неравенству

d < Г

^ г - 3 - 2-i log2([V2(r - 2) + 1/4 - 1/2])'

7. Установлено существование полиномиальной трансформации Задачи 3-ВЫП (распознавания) в Задачу о рюкзаке (распознавания), при которой образ Задачи 3-ВЫП попадает в область множества задач о рюкзаках с плотностью <1 < С, где С - любое положительное вещественное число, не превосходящее 3(1о§2 7)-1.

Научная новизна

Основные результаты, полученные в работе, являются новыми. Предложенный метод решения индивидуальных представителей ^-полных Задач - ЬЬЬ-решатель - является новым и достаточно перспективным для включения в перечень существующих в настоящее время средств решения индивидуальных представителей №-полных Задач за «приемлемое время». Перспективны также новые предложенные методы решения вычислительной Обобщенной Задачи о рюкзаке и систем задач о рюкзаках.

Теоретическая и практическая ценность

Работа носит теоретический характер. Методы, применяемые в этой работе, могут быть использованы при проведении исследований инъективных и сверхрастущих векторов, сложности алгоритмов, методов решения индивидуальных представителей МР-полных Задач.

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

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

Апробация результатов

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

П.Г. Демидова в 2010-2012 годах, и обсуждались на научных конференциях и выставках научно-технического творчества:

1) Одиннадцатый Всероссийский конкурс-конференция студентов и аспирантов «Информационная безопасность» Б1ВШРО-2011, г. Томск, апрель 2011 года;

2) Региональный этап Всероссийской выставки молодых исследователей, изобретателей, рационализаторов «Шаг в будущее», г. Ярославль, ноябрь

2011 года;

3) XII Всероссийская выставка научно-технического творчества молодежи НТТМ-2012, г. Москва, июнь 2012 года;

4) Международная научная конференция, посвященная 35-летию математического факультета и 25-летию факультета информатики и вычислительной техники Ярославского государственного университета им. П.Г. Демидова, г. Ярославль, март 2012 года;

5) Международная молодежная конференция-школа «Современные проблемы прикладной математики и информатики», г. Дубна, 22-27 августа

2012 года;

6) 11 Всероссийская конференция «Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» - 81ВЕСКУРТЧ2», г. Иркутск, 3-7 сентября 2012 года;

7) Межрегиональная выставка работ молодых исследователей «Шаг в будущее», г. Ярославль, 1-2 ноября 2012 года.

Исследования по теме диссертационной работы были отмечены дипломом победителя конкурса научно-исследовательских работ студентов вузов Ярославской области 2010 года в области естественных наук, г. Ярославль, 2011 год; дипломом первой степени за первое место в Одиннадцатом Всероссийском конкурсе-конференции студентов и аспирантов «Информационная безопасность» 81ВШРО-2011, г. Томск, 2011 год; дипломом за победу во II Внутривузовском конкурсе лучших поисковых научно-исследовательских работ аспирантов «Подготовка научно-педагогических кадров в научно-образовательных центрах ВУЗа» 2011 года по направлению «Информатика», г. Ярославль, 2011 год; дипломом первой степени победителю Регионального этапа Всероссийской выставки молодых исследователей, изобретателей, рационализаторов «Шаг в будущее», г. Ярославль, 2011 год; дипломом лауреата премии по поддержке талантливой молодежи, установленной Указом Президента Российской Федерации от 6 апреля 2006 года № 325

«О мерах государственной поддержки талантливой молодежи»; медалью и дипломом первой степени победителя Межрегиональной выставки работ молодых исследователей «Шаг в будущее» 1-2 ноября 2012 года.

Результаты исследований внедрены и используются в рамках учебного процесса в Ярославском государственном университете им. П.Г. Демидова.

Публикации

Результаты диссертации опубликованы в 9 работах [1-9], из них 5 статей опубликованы в научных журналах, которые включены в перечень российских рецензируемых научных журналов и изданий для опубликования основных научных результатов диссертаций [1-5], 2 статьи — в научных журналах [6,7] и 2 работы — в трудах международных конференций [8,9].

Структура диссертации

Диссертация состоит из введения, трех глав, заключения, списка использованной литературы и приложения. Диссертация содержит 19 рисунков, 16 таблиц. Общий объем диссертации составляет 116 страниц.

Соответствие паспорту специальности

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

Личный вклад автора

Все результаты, выносимые на защиту, получены автором лично.

Благодарности

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

В теоремах 1 и 3 автором устанавливаются верхние и нижние границы для числа возрастающих инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом. Обозначим через Vgi„(r, М) множество возрастающих инъективных векторов размерности г с максимальным элементом, равным М\ V/g(r, М) - множество сверхрастущих векторов размерности г с максимальным элементом, равным М. Введем в рассмотрение функции Fi(r,M) и F2(r, М) с областью определения N2 такие, что

Fx{r, М) = \Vgin(r, М)F2(r, М) = \Vfg(r, М)|. Справедливы следующие теоремы.

Теорема 1. При фиксированном г S N и любом натуральном М (за исключением случая г = 1, М = 1, при котором F\(r, М) = 1) выполняется неравенство

Fi(r,M) iC где через обозначено число сочетаний.

Теорема 3. При фиксированном г ) 2 и любом натуральном М ^ 2r_1 выполняется неравенство F2(r,M) ^ Р(М), где Р(М) - некоторый полином (г — 1 )-ой степени от М.

В частности, при фиксированном г ^ 2 и любом натуральном М ^ 2Г_1 (при М < 2r_1 F2(r, М) = 0) выполняется неравенство

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

в лексикографическом порядке. Алгоритм базируется на следующих основных положениях.

Нетрудно понять, что вектор (1,2,22,..., 2Г_1) является единственным сверхрастущим вектором размерности г с максимальным элементом, не превосходящим 2Г_1. В работе доказана следующая теорема.

Теорема 2. Все сверхрастущие векторы размерности г могут, быть получены из вектора (1,2,22,..., 2Г_1) путем применения к нему некоторого набора из следующих операций:

Р[ : (аь...,аг)м. (ах + 1,а2 + 1, а3 + 2,..., аг_х + 2г_3,аг + 2Г~2),

: (аи ..., аг) (аь а2,..., ак + 1, аш + 1,..., аг_1 + 2г~к~2, аГ + 2г~к~1),

Рг-1 : (а1. • • •, аг) (аь а2,..., аг_х + 1, аг + 1), Рг '■ (аъ ...,От) (о.1,а2,... ,аг_1,аг + 1), Ро '■ (аь••■,«!■) •-»■ (^1,12) • • • ,ог-1,ат).

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

Утверждение 8. Число итераций предложенного алгоритма перечисления всех сверхрастущих векторов размерности г 4-1 с фиксированным максимальным элементом М растет при фиксированном г с ростом М как полином г-ой степени от М.

Обозначим через У/Я(г, < М) множество сверхрастущих векторов размерности г, максимальный элемент которых строго меньше М. Пусть вектор (ах,..., аТ) € У/д(г, < М), тогда операция сильного модульного умножения относительно модуля Щ < тп ^ М и множителя 1 < £ < тп такого, что (¿, тп) = 1, с последующим применением процедуры сортировки элементов полученного вектора по возрастанию преобразует вектор (ах,..., ат) в вектор из множества Уд{п(г, < М) возрастающих инъективных векторов

размерности г, максимальный элемент которых строго меньше М. Введем обозначение SSMUt,m Для этого отображения:

SSMUrM : Vfg(r,<M) Vgin(r,<M).

В пятом разделе первой главы диссертационного исследования экспериментально изучаются вопросы о плотности покрытия множества Vgin(r, < М) элементами образа SSMUTiM(Vfg(r,< М)) и равномерности этого покрытия. Дано описание соответствующих компьютерных экспериментов.

Определение 5. Для вектора В размерности г число троек (А = (ai,... ,ar),m,t) (сверхрастущий вектор, модуль, множитель) таких, что т е (2i=i<i«,min(2^i=iai,M)], 1 < t < т., (t, т) = 1 и В = SORT((tai, modm),(ia2, mod m),..., (tar, mod m)), где SORT процедура сортировки элементов вектора по возрастанию, назовем числом представлений вектора В.

Введем в рассмотрение функцию плотности F(r, М) с областью определения N2 - ее значения суть отношение числа векторов из Vgin(r, < М), число представлений которых больше нуля, к общему числу элементов множества Vgin(r,< М). Проведенные вычислительные эксперименты позволяют выдвинуть следующую гипотезу.

Гипотеза 1. При фиксированном г £ N F(r,M) достигает 0,9 при значениях М, близких к 22г_2.

Под «достижением» в гипотезе 1 понимается, что существует такое М\ € N, близкое к 22г_2, что F(r, М\) ^ 0,9, но при этом могут существовать такие М > Mi, что F(r,М) < 0,9.

В результате компьютерных экспериментов автором установлено, что при 2 < г < 4 F(r, М) достигает 0,9 при М = 22г_2 + 2Г — 1, кроме того, покрытие множества Vgi„(r, <М) элементами образа SSMUr^i{Vfg{r, < М)) не является равномерным.

В шестом разделе первой главы изучается вопрос о монотонности функции Fi(r,M) по М. В результате компьютерных экспериментов показано, что при фиксированном 5 < г ^ 8 функция Fi(r, М) не является монотонной по М. Анализ возможных причин немонотонности функции Fj(r, М) позволяет выдвинуть следующие гипотезы.

Гипотеза 2. При фиксированном г е {2,3,4} функция F\{r,M) является монотонно возрастающей по М.

Гипотеза 3. При фиксированном г ^ 5 функция F\{r,M) не является монотонной по М.

Кроме того, в шестом разделе первой главы введено понятие ипъек-тпивного г-представления числа М - такого представления числа М в виде суммы М = 53i=ia«i что вектор (ai,... ,ar_i) является возрастающим инъективным вектором. Показано, что вопрос о монотонности функции F\{r,M) тесно связан с вопросом о том, сколько существует различных г-представлений числа М.

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

В главе рассмотрены LLL-приведенные базисы решетки (дано описание работы алгоритма построения LLL-приведенного базиса решетки, используемого автором при разработке программного обеспечения), а также вопрос о числе точек целочисленной решетки, попадающих в сферу малого радиуса в r-мерном пространстве. Эти вопросы лежат в основе метода Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке и базируются на работах А. Ленстра, X. Ленстра и Л. Ловаса11, X. Кохэна12, Дж. Лагариаса и А. Одлыжко13.

В четвертом разделе второй главы изложен метод Short Vector, предложенный Дж. Лагариасом и А. Одлыжко в работе для решения вычислительной Задачи о рюкзаке, и описан алгоритм «Оракул», выдающий за полиномиальное время один из кратчайших ненулевых векторов решеток специализированных описанных в диссертационной работе видов, идея которого была предложена в работе М. Костера и других14.

Напомним формулировку вычислительной Обобщенной Задачи о рюкзаке.

Условие: Заданы вектор А = (ai, ..., ar) € Nr, число S 6 N и натуральное число m ^ 2, причем известно, что уравнение

г

^a.Xj = S, (1)

¡=i

где Xi,... ,хг - неизвестные, имеет решение в числах 0,1,...,тп — 1.

Вопрос: Найти решение уравнения (1) в числах 0,1,..., тп — 1.

llLenstra А.К., LenstraH.W., Lovasz L. Factoring Polynomials with Rational Coefficients // Mathematische Annalen 261. 1982. p. 515-534.

12Cohen H.A. A course in computational algebraic number theory. Springer-Verlag, 1993. 545 p.

13Odlyzko A.M., Lagarias J.C. Solving Low-Density Subset Sum Problems, p. 229-246.

14Coster M.J., Joux A., LaMacchia B.A., Odlyzko A.M., Schnorr C.-P., Stern J. Improved low-density subset sum algorithms, p. 111-128.

В пятом разделе второй главы диссертации предложен метод решения вычислительной Обобщенной Задачи о рюкзаке, основанный на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке. Показано, что предложенный метод решает «практически все» вычислительные Обобщенные Задачи о рюкзаке, обладающие плотностью ¿ОЗР = < где ¿(а,*) = ах + 1п0(е-),

Рассмотрим решетку Аз, образованную следующими векторами 2>х,... ,Ьг+1 размерности г+1: 61 := (1,0,..., 0, М-а{), Ь2 := (0,1,..., 0, ЛГ-а2), ..., Ьг := (0,0, ...,1,ЛГ • аг), ЬГ+1 := (0,0,... ,0, N • 5), где N [(то — + 1 - некоторое достаточно большое натуральное

число.

Для любого натурального числа то ^ 2 справедлива следующая теорема.

Теорема 11. Пусть ах,...,аг - произвольные натуральные числа, ё= (ех,..., ег) е {0,1,..., то — 1}г - произвольный вектор и 5 = е^. Тогда вероятность ошибки при решении приведенной1 обобщенной задачи о рюкзаке, заданной значениями а*, 1 ^ ! ^ г, и 5, при условии, что плотность этой задачи йозр <-—, с помощью алгоритма «Оракул»,

тш1гоЛ( 2 1»)

примененного к решетке Аз, стремится к 0 при г —> оо.

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

"Условие: Заданы к векторов — (оц,..., аГ 1), ..., Ак = (аць,..., агк) размерности г, а^ е N для 1 < г < г, 1 < 3 ^ к, к натуральных чисел £1,..., Б к и натуральное число т ^ 2, причем известно, что система уравнений

г

ацх{ = Б,, 1 < з < к, (2)

<=1

где х\,..., хт - неизвестные, имеет решение в числах 0,1,..., то — 1.

Вопрос: Найти решение системы уравнений (2) в числах 0,1,..., тп — 1.

Предложенный метод решает «практически все» системы обобщенных задач о рюкзаках, обладающие плотностью ¿созр =

__г_ ^ _к 1п 771

Обобщенная задача о рюкзаке является приведенной, если выполнены неравенства - а1 ^

Рассмотрим решетку Л4, образованную следующими векторами bi,.. .,br+i размерности г + к: bi := (1,0,..., 0, N ■ an,N ■ ai2,.. .,N ■ ац), bz := (0,1,...,0,JV ■ вы, N ■ a22,...,N ■ a2k), ■ ■■, bT := (0,0,..., 1, N ■ arl,N-ar2,...,N-ark),br+1 := (0,0,... ,0, N ■ Su N ■ S2,..., N ■ Sk), где N > [(то — 1) + 1 - некоторое достаточно большое натуральное число.

Для любого натурального числа то ^ 2 справедлива следующая теорема.

Теорема 12. Пусть ау, 1 ^ г < г, 1 < j ^ к, - произвольные натуральные числа, причем векторы А\ = (ац,...,агi), ..., Ak = (aik, ■ ■■,о.тк) являются линейно независимыми. Пусть ё = (ei,..., ег) £ {0,1,... ,т — 1}г - произвольный вектор и Sj = eiaij для всех 1 ^ j ^ к. Тогда вероятность ошибки при решении приведенной1 системы обобщенных задач о рюкзаках, заданной значениями ау, 1 ^ i ^ г, 1 ^ j ^ к, и Sj, 1 < j ^ к,

при условии, что плотность этой системы dco3P < -п» ,, с по-

minlSo°C 2 <х)

мощью алгоритма «Оракул», примененного к решетке Л4, стремится к 0 при г сю.

В седьмом разделе второй главы рассмотрен особый случай (то = 2) системы обобщенных задач о рюкзаках - система задач о рюкзаках. С точки зрения информационной безопасности, система задач о рюкзаках тесно связана со случаем широковещательной рассылки сообщения, например, в системе Меркля-Хеллмана. Предложенный в этом разделе метод решения системы задач о рюкзаках позволяет решать «практически все» системы, обладающие плотностью ¿сзр = iog2(тахк,Г<г 1<j<kац) < ^ ' 0>9408...

Рассмотрим решетку Л5, образованную следующими векторами í>x,... ,br+i размерности г + k: bi := (1,0,... ,0 ,N ■ an,N ■ а12, ...,N- au), 62 := (0,1,...,0 ,N ■ a2í,N ■ a22,...,N ■ a2k), ..., br := (0,0,..., 1, N ■ arl,N -ar2,...,N -ark), br+1 := ..., §, N ■ Su N ■ S2,.. ., N ■ S*), где

N ^ [iVrl + 1 _ некоторое достаточно большое натуральное число.

Справедлива следующая теорема.

Теорема 13. Пусть ay, 1 ^ i < г, 1 < j ^ fc, произвольные натуральные числа, причем векторы Ai = (ац,.. .,ari), ■ ■ ■, Ak = (aik,..., ark) являются линейно независимыми. Пусть ё = (ei,..., ег) € {0,1}г - произвольный вектор и Sj = ^¡=1 e%aij для всех 1 ^ j ^ к. Тогда вероятность ошибки при решении системы задач о рюкзаках, заданной значениями a¡j, 1 < i ^ г, 1 ^ j < к, и Sj, 1 < j < fc, при условии, что плотность этой си-

1 Система обобщенных задач о рюкзаках является приведенной, если для всех 1 < j < к выполнены неравенства A X)¡=i aO ^ Sj < (m - 1) Sí-i °>j ~~ г £í=i ач-

стемы йсзр < к • 0,9408..., с помощью алгоритма «Оракул», примененного к решетке Л5, стремится к 0 при г —»■ оо.

В третьей главе диссертационного исследования установлена связь между инъективными векторами заданной размерности г, обладающими наименьшим максимальным элементом (эти векторы обладают наибольшей плотностью среди всех инъективных векторов заданной размерности) и последовательностью Штерна £>х = 1, ¿>2 = 1, Ьз = 2, 64 = 3, Ь5 = 6, бе = 11, Ь7 = 20, Ь8 = 40...

В следствии 7 и утверждении 11 получены верхние и нижние оценки для значений элементов последовательности Штерна {¿»¿}, г 6 а именно для любого натурального 1^3 выполнены неравенства

2'-2 ^ ¿,( 5> 2'-4-2-11О82([>/2(1-2)+1/4-1/2])_

Кроме того, в предположении, что один из инъективных векторов (ах,..., Ог) размерности г ^ 2, обладающий наименьшим максимальным элементом среди всех инъективных векторов размерности г, может быть построен по правилу

г

ах = ЬГ, а2 = Ьг + Ьг_х, ..., аг = У)ьи

1=1

где ЬХ1 ■ • • IЬТ - суть первые г элементов последовательности Штерна Ь\ = 1, Ьг = 1, ¿>з = 2, 64 = 3, 65 = 6, &б = И, ^ = 20, &8 = 40..., установлена верхняя граница для плотности инъективных векторов. При оговоренных условиях является справедливой следующая теорема.

Теорема 14. Плотность инъективных векторов размерности г ^ 4 удовлетворяет неравенству

й- < Г

г- 3-2-11оё2([ч/2(г - 2) Л74 - 1/2])'

Во втором разделе третьей главы рассматриваются вопросы о том, в какую область множества задач о рюкзаках (относительно плотности) попадают при полиномиальной трансформации образы ИР-полных Задач распознавания 3-ВЫП, Раскрашиваемость, Точное покрытие, и какая доля задач из образа попадает в область множества задач о рюкзаках с плотностью меньше, чем 0,9408...

Рассмотрена полиномиальная трансформация Tj Задачи о точном покрытии в Задачу о рюкзаке, впервые описанная Р. Карпом15, для которой доказано следующее утверждение (pul- параметры Задачи о точном покрытии).

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

1 < 0,9408...,

(р-1)1об2(1 + 1)

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

Показано, что задачи о точном покрытии, удовлетворяющие условию (р—1) (;+1) ^ 0,9408..., составляют значительную долю задач о точном покрытии. Доказано следующее утверждение.

Утверждение 14. Число задач о точном покрытии, удовлетворяющих условию

1 > 0,9408...,

асимптотически мало по сравнению с числом задач о точном покрытии, удовлетворяющих условию

7-^ 0,9408...

(р- 1) 1ое2(/ + 1)

Рассмотрены полиномиальная трансформация Т2 Задачи о раскра-шиваемости в Задачу о точном покрытии, описанная в монографии А. Ахо, Дж. Хопкрофта и Дж. Ульмана16, и конкатенация полиномиальных трансформаций Т\ и Т2 (обозначенная через Т\ о Т2). Доказано следующее утверждение (|У|, \Е\ и к — параметры Задачи о раскрашиваемости).

Утверждение 19. При полиномиальной трансформации Т\ о Т2 Задачи о раскрашиваемости в Задачу о рюкзаке образ задач о раскраши-

15Кагр R.M. Reducibility among combinatorial problems // Complexity of Computer Computations: Proc. of a Symp. on the Complexity of Computer Computations, The IBM Research Symposia Series. 1972. p. 85103.

16 Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. С. 439-440.

ваемости, удовлетворяющих условию

< 0,9408...,

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

Рассмотрены полиномиальная трансформация Т3 Задачи 3-ВЫП в Задачу о раскрашиваемое™, описанная в монографии А. Ахо, Дж. Хопк-рофта и Дж. Ульмана17, и конкатенация полиномиальных трансформаций

о Тг о Т3. Доказано следующее утверждение (пи< - параметры Задачи 3-ВЫП).

Утверждение 21. При полиномиальной трансформации Т10Т20Т3 Задачи 3-ВЫП в Задачу о рюкзаке образ задач 3-ВЫП, удовлетворяющих условию

---^ ^ 0,9408...,

1ое3(2(п +1)«)

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

Кроме того, показано, что справедливо следующее утверждение.

Утверждение 22. Множество задач о рюкзаках, обладающих плотностью меньшей, чем 0,9408..., является ЫР-полной Задачей.

Рассмотрена полиномиальная трансформация Т4 Задачи 3-ВЫП в Задачу о рюкзаке, описанная в монографии Т. Кормена, Ч. Лейзерсона, Р. Ривеста и К. Штайна18. Эта трансформация обладает тем свойством, что размерность г задач о рюкзаках, получаемых с ее помощью, линейно зависит от параметров Задачи 3-ВЫП, поэтому трансформация Т4 гораздо более приемлема при практической реализации, чем трансформация Т\ о Тг ° Тз, у которой эта зависимость полиномиальная. Доказана следующая теорема.

Теорема 15. При полиномиальной трансформации Т4 Задачи 3-ВЫП в Задачу о рюкзаке образ Задачи 3-ВЫП попадает в область множе-

17Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. С. 437-438.

18Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. М.: Вильяме, 2005. С. 1140-1144.

ства задач о рюкзаках с плотностью <1 < Се, где С - любое положительное вещественное число, не превосходящее 3(к^27)-1.

Теорема 15 утверждает, что каким бы положительным вещественным числом, не превосходящим щ-?, ни была ограничена плотность задач о рюкзаках, можно вложить образ Задачи 3-ВЫП в область множества задач о рюкзаках, обладающих этой плотностью. Из чего можно заключить, что любое множество задач о рюкзаках, обладающих плотностью <1 ^ является NP-пoлнoй Задачей.

В третьем разделе третьей главы предлагается подход к решению за «приемлемое время» представителей ЫР-полных Задач - ЬЬЬ-решатель, основанный на методе решения вычислительной Задачи о рюкзаке, предложенном Дж. Лагариасом и А. Одлыжко.

Для анализа результативности предлагаемого подхода вводится понятие функции применимости алгоритма (метода).

Рассматриваются функции применимости ЬЬЬ-решателя к приведенным задачам о рюкзаках при фиксированном г и тах^,^ Щ оо. Экспериментально полученные значения этих функций (при г < 9) говорят о высокой степени результативности ЬЬЬ-решателя. В результате вычислительных экспериментов, в ходе которых решались более 20 миллиардов различных задач о рюкзаках малых размерностей (г < 9), автором установлено, что характер смещения ветвей функций применимости ЬЬЬ-решателя с ростом г в случае, если в качестве претендента на вектор, дающий решение задачи о рюкзаке, рассматривается только первый вектор ЬЬЬ-приведенного базиса, не является равномерным. Этот экспериментальный результат выглядит сильнее по сравнению с прогнозом, основанным на теории Лагариаса-Одлыжко, предполагающим равномерное падение применимости ЬЬЬ-решателя.

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

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

Список публикаций по теме диссертации

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

1. Мурин, Д.М. О порядке роста числа инъективных и сверхрастущих рюкзачных векторов / Д.М. Мурин // Моделирование и анализ информационных систем. 2012. - Т. 19, №3. - С. 124-135. - 1,33 п. л.

2. Мурин, Д.М. О некоторых свойствах образов трансформированных Задач / Д.М. Мурин // Прикладная дискретная математика. — 2012. — №3(17). — С. 96102. - 0,8 п. л.

3. Мурин, Д.М. ЬЬЬ-решатель / Д.М. Мурин // Математическое моделирование. — 2012. Т. 24, № 12. С. 43 48. 0,64 п. л.

4. Мурин, Д.М. О верхней границе плотности инъективных векторов / Д.М. Мурин // Прикладная дискретная математика. — 2013. — №1(19). — С. 117-124. — 0,92 п.л.

5. Мурин, Д.М. Модификация метода Лагариаса-Одлыжко дня решения обобщенной задачи о рюкзаке и систем задач о рюкзаках / Д.М. Мурин // Прикладная дискретная математика. — 2013. — №2(20). — С. 91-100. - 1,16 п. л.

Публикации в других научных изданиях

6. Мурин, Д.М. О порядке роста числа инъективных и сверхрастущих векторов и некоторых особенностях сильного модульного умножения / Д.М. Мурин // Прикладная дискретная математика. Приложение. — 2012. — №5. — С. 19-21. - 0,23 п. л.

7. Мурин, Д.М. О некоторых свойствах инъективных векторов / Д.М. Мурин // Современные проблемы математики и информатики: сборник научных трудов молодых ученых, аспирантов и студентов. Ярославль, ЯрГУ. — 2013. — Вып. 13. — С. 4-11. - 0,8 п. л.

8. Мурин, Д.М. О некоторых свойствах отображения множества сверхрастущих векторов во множество инъективных векторов с помощью сильного модульного умножения / Д.М. Мурин // Моделирование и анализ информационных систем. Труды международной научной конференции, посвященной 35-летию математического факультета и 25-летию факультета информатики и вычислительной техники Ярославского государственного университета им. П.Г. Демидова. Ярославль, ЯрГУ. — 2012. - С. 137-139. - 0,35 п. л.

9. Мурин, Д.М. ЫХ-решатель / Д.М. Мурин // Международная молодежная конференция-школа «Современные проблемы прикладной математики и информатики», 22-27 августа 2012 г. Дубна. ОИЯИ. - 2012. - С. 155-158. - 0,4 п. л.

Ярославский государственный университет им. П.Г. Демидова

На правах рукописи

04201362081 Мурин Дмитрий Михайлович

Компьютерно-аналитическое исследование задач рюкзачного типа как средство анализа и совершенствования систем защиты

информации

05.13.19 - Методы и системы защиты информации, информационная безопасность

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель д.ф.-м.н., профессор Дурнев Валерий Георгиевич

Ярославль - 2013

Оглавление

Введение 3

Используемые обозначения 12

1. О порядке роста числа сверхрастущих и инъективных векторов и некоторых особенностях сильного модульного умножения 13

1.1. Задача о рюкзаке....................................................14

1.2. Подсчет инъективных и сверхрастущих векторов................16

1.2.1. Математические основы проведенных компьютерных экспериментов по подсчету инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом..............................................16

1.2.2. Алгоритм подсчета возрастающих инъективных векторов 17

1.2.3. Результаты компьютерных экспериментов................21

1.3. Оценки для функции Г\(г, М) и F2(г. М)........................22

1.3.1. Оценка сверху для функции ^ (г, М) ....................22

1.3.2. Оценка снизу для функции ^(г, М)......................25

1.3.3. Результаты компьютерных экспериментов................30

1.4. Алгоритм перечисления всех сверхрастущих векторов заданной размерности с фиксированным максимальным элементом 32

1.5. Некоторые особенности сильного модульного умножения ... 33

1.6. О монотонности функции ^ (г, М)................................39

1.7. Выводы..............................................................44

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

2.1. ЫХ-приведенные базисы решетки................................47

2.2. Алгоритм построения ЫХ-приведенного базиса решетки ... 51

2.3. Об оценке числа точек целочисленной решетки, попадающих

в сферу малого радиуса в г-мерном пространстве..............55

2.4. Метод Лагарнаса-Одлыжко решения Задачи о рюкзаке .... 56

2.5. Метод решения Обобщенной Задачи о рюкзаке, основанный

на методе Лагариаса-Одлыжко....................................62

2.6. Метод решения систем обобщенных задач о рюкзаках..........67

2.7. Метод решения систем задач о рюкзаках........................70

2.8. Выводы..............................................................74

А

3. О некоторых свойствах образов трансформированных Задач. ЬЬЬ-решатель 75

3.1. О верхней границе плотности инъективных векторов ..........76

3.1.1. О последовательности Штерна и результатах компьютерных экспериментов......................................76

3.1.2. О плотности инъективных векторов......................79

3.2. Некоторые свойства образов трансформированных Задач ... 86

3.2.1. Задача о точном покрытии ос Задача о рюкзаке .... 87

3.2.2. Задача о раскрашиваемости ос Задача о рюкзаке .... 93

3.2.3. Задача 3-ВЫП ос Задача о рюкзаке......................95

3.2.4. О коротком сведении Задачи 3-ВЫП к Задаче о рюкзаке 97

3.3. ЫХ-решатель............................101

3.3.1. Конструкция ЬЬЬ-решателя................101

3.3.2. Результаты компьютерных экспериментов........102

3.4. Выводы...............................106

Заключение 107

Список использованной литературы 110

Приложение 116

Введение

Ряд современных систем защиты информации и обеспечения информационной безопасности базируется на МР-полных Задачах Задачи из класса МР-полных являются, в определенном смысле, «очень сложными» для решения [8,11,16.18]. поэтому, с одной стороны, представляет особый интерес изучение средств и систем защиты информации, для преодоления которых необходимо решить лежащую в их основе МР-полную Задачу, а с другой стороны. методы решения индивидуальных представителей МР-полиых Задач представляются естественными методами анализа эффективности разрабатываемых средств и систем защиты информации. Одной из систем защиты информации, в основе которой лежит МР-полная Задача, является асимметричная система шифрования Меркля-Хеллмана [40]. основанная на КР-полпой Задаче распознавания - Задаче о рюкзаке. В работах [24.25.43,47] по анализу этой системы были предложены методы решения некоторых множеств задач о рюкзаках - индивидуальных представителей вычислительной Задачи о рюкзаке. В диссертационной работе метод решения вычислительной Задачи о рюкзаке, предложенный Дж. Лагариасом н А. Одлыжко [43], модифицируется в метод решения вычислительной Обобщенной Задачи о рюкзаке п методы решения систем задач о рюкзаках. Кроме того, в диссертационной работе предлагается основанный на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке [43] метод решения за «приемлемое время» представителей МР-полных Задач - ЬЬЬ-решатель.

Зарождение теории КР-иолпоты связывают с опубликованной в 1971 году работой С. Кука [29]. В этой работе была установлена важность понятия «полиномиальная сводимость Задач», выделен класс Задач распознавания свойств, которые могут быть решены за полиномиальное время на недетерминированном вычислительном лстройстве (недетерминированной машине Тьюринга) (класс МР). Кроме того, было показано, что Задача о выполнимости конъюнктивной нормальной формы - представитель класса МР - обладает тем свойством, что любая другая Задача из класса МР может быть сведена к ней за полиномиальное время (то есть в определенном смысле Задача о выполнимости является самой сложной Задачей в классе МР). и установлено, что таким свойством могут обладать и другие задачи из класса МР (например. Задача о существовании в графе С клики с определенным числом вершин).

Р. Карп [36]. опубликовавший своп результаты вслед за работой С. Кука, показал всю ширину класса «самых трудных» задач из класса NP. получившего название «класс NP-полных Задач». Оказалось, что значительная часть известных комбинаторных Задач (о коммивояжере, о клике, о вершинном покрытии и другие) принадлежит к классу NP-полных.

Одной из рассмотренных Р. Карпом NP-иолпых Задач была Задача о рюкзаке (распознавания) (также известная как Задача «subset sum» -Задача о сумме элементов подмножества, 0-1 рюкзак), предложенная в 1978 году Р. Мерклем и М. Хеллмаиом [40] в качестве основы для построения асимметричной системы шифрования. Анализу этой системы посвящены работы А. Шамира [46], Э.Ф. Брикелля [24,25], Дж. Лагариаса и А. Од-лыжко [43].

В ра.боте 1982 года А. Шамир [47] предложил полиномиальный по времени от размерности рюкзачного вектора алгоритм, решающий «практически все» задачи о рюкзаках, рюкзачный вектор которых можно получить с помощью операции сильного модульного умножения из сверхрастущего вектора, способом, предложенным Р. Мерклем и М. Хеллмаиом для формирования открытых ключей из закрытых в их системе.

Несмотря на то, что А. Шамир показал, что классическая система Меркля-Хеллмана является ненадежной, попытки ее усовершенствования до сих пор не прекращаются, о чем свидетельствуют работы Р. Гудмана и Э. Маколи [33], X. Нидеррайтера [42], Б. Шора и Р. Ривеста [28], В.О. Осипя-иа и В.В. Подколзина [53-55]. Более полный обзор работ в области анализа системы Меркля-Хеллмана и ее развития дан Б. Шнайером [22].

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

В 1985 году в работе Дж. Лагариаса и А. Одлыжко [43] был предложен метод решения вычислительной Задачи о рюкзаке, дающий верное решение для «практически всех» задач о рюкзаке, плотность (отношение размерности вектора к двоичному логарифму его максимального элемента) которых не превышает 0,6463.... основанный па сведении вычислительной Задачи о рюкзаке к Задаче вычисления кратчайшего ненулевого

вектора решетки. Этот результат был улучшен М. Костером и другими [30] до плотности, меньшей 0.9408... В диссертационной работе автором рассмотрен вопрос о том, насколько существенны такие ограничения плотности.

В настоящее время известно обширное множество КР-полиых Задач, для которых все попытки найти эффективные (полиномиальные) алгоритмы решения оказались безуспешными. Однако огромное значение, которое имеют эти Задачи в различных теоретических и практических областях знания, определяет развитие методов и технологий, позволяющих решать задачи -индивидуальные представители NP-полных Задач - или их подмножества за «приемлемое время». В области информационной безопасности NP-иолпые задачи традиционно возникают при изучении и моделировании атак в компьютерных системах и сетях (в процессах построения моделей и анализа результатов моделирования [51]). при анализе информационных потоков и моделей разграничения прав доступа [2]. при анализе протоколов информационной безопасности [26,45] и при решении других исследовательских вопросов.

Среди методов решения индивидуальных представителей NP-полных Задач за «приемлемое время» наибольшей популярностью, на наш взгляд, па текущий момент обладают методы, предполагающие сведение исходной индивидуальной задачи к задаче выполнимости конъюнктивной нормальной формы (SAT. ВЫП) с последующим решением полученной SAT-задачи с помощью специализированного программного комплекса - SAT-решателя [34, 41, 50]. В этом случае SAT выступает в качестве опорной (базовой) NP-полиой Задачи. В основе многих SAT-решателей лежит алгоритм DPLL. разработанный в 1960-1962 годах М. Дэвисом, X. Путмаиом, Дж. Логеманном и Д. Лавлендом [31.32], еще до работ С. Кука и Р. Карпа. Поэтому представляют интерес альтернативные подходы к решению за «приемлемое время» индивидуальных представителей NP-полных Задач. В диссертационной работе предлагается метод решения за «приемлемое время» представителей NP-полных Задач - LLL-решатель, основанный на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке [43]. Предлагаемый метод, кроме прочего, интересен тем, что в его основе лежат алгебраические понятия и конструкции, что позволяет привлекать при анализе мощный аппарат этого раздела математики.

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

системе; изучаются методы решения вычислительной Задачи о рюкзаке, разработанные в работах Дж. Лагариаса и А. Одлыжко, М. Костера и других, и предлагаются основанные на них методы решения иных задач рюкзачного типа: систем задач о рюкзаках, Обобщенной Задачи о рюкзаке, рассматривавшейся в работах В.О. Осипяна [53,54] в качестве основы для построения системы защиты.

Актуальность диссертационной работы определяется теоретической и практической значимостью метода Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке для анализа вновь предлагаемых систем защиты информации, в основе которых лежат задачи рюкзачного типа, теоретической и практической значимостью методов решения индивидуальных представителей КР-полных Задач за «приемлемое время» для информационной безопасности.

Объект исследования

Объектом диссертационного исследования являются NP-пoлныe Задачи, используемые для построения систем защиты информации.

Предмет исследования

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

Цель работы

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

Для достижения указанной цели в диссертационной работе были поставлены и решены следующие задачи:

1) получить оценки числа инъективных векторов и числа сверхрастущих векторов с заданными размерностью и максимальным элементом;

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

инъективных векторов или множеству сверхрастущих векторов; проанализировать полученные в ходе компьютерных экспериментов данные о числе инъективных векторов и числе сверхрастущих векторов с заданными размерностью и максимальным элементом, сравнить результаты с полученными оценками;

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

4) модифицировать метод Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке применительно к случаю вычислительной Обобщенной Задачи о рюкзаке и случаям, когда нам известно не менее двух задач о рюкзаках, имеющих одинаковое решение (система задач о рюкзаках);

5) получить верхнюю оценку плотности инъективных векторов;

6) разработать программное обеспечение, позволяющее генерировать приведенные задачи о рюкзаках с заданными размерностью вектора и максимальным элементом и решать полученные задачи с помощью метода Лагариаса-Одлыжко; поставить эксперимент по определению доли задач о рюкзаках, верно решаемых с помощью метода Лагариаса-Одлыжко, выбираемых из заранее определенного множества задач;

7) проанализировать возможность решения индивидуальных представителей КР-полных Задач путем сведения их к задачам о рюкзаках и применения к последним метода Лагариаса-Одлыжко.

Области исследований

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

Методы исследований

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

Положения, выносимые на защиту

1. Установлены нижние и верхние оценки для числа сверхрастущих и инъективных векторов, элементы которых являются натуральными числами, с заданными размерностью и максимальным элементом. Показано, что число сверхрастущих и инъективных векторов фиксированной размерности г, элементы которых являются натуральными числами, растет с ростом максимального элемента вектора как полином (г — 1)-ой степени от максимального элемента вектора.

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

3. Предложены методы решения вычислительной Обобщенной Задачи о рюкзаке и систем задач о рюкзаках, основанные на методе Лагариаса-Одлыжко решения вычислительной Задачи о рюкзаке.

4. Предложен подход к решению за «приемлемое время» индивидуальных представителей NP-пoлныx Задач - ЬЬЬ-решатель. Предложено понятие функции применимости алгоритма к множеству решаемых задач, проведена серия компьютерных экспериментов по вычислению функций применимости ЬЬЪ-решателя к решению задач о рюкзаках.

5. В результате вычислительных экспериментов, в ходе которых решалось более 20 миллиардов различных задач о рюкзаках малых размерностей (г < 9), было установлено, что характер смещения ветвей функций применимости ЬЬЬ-решателя с ростом г, в случае, если в качестве претендента на вектор, дающий решение задачи о рюкзаке, рассматривается только первый вектор ЬЬЬ-приведенного базиса, не является равномерным.

6. Установлены верхние и нижние границы для значений элементов Ьг последовательности Штерна Ь\ = 1, ¿»2 = 1, 63 = 2,64 = 3, 65 = б, Ьб = 11, &7 = 20, &8 = 40... В предположении, что вектор (<21,..., аг) размерности г ^ 4, элементы которого строятся по следующему пра-

вилу:

г

ai = br, а,2 = br -Ь br-1, ..., ar = ^^

г=i

является инъективным вектором с наименьшим возможным среди инъективных векторов размерности г максимальным элементом, устанавливается, что плотность din инъективных векторов размерности г ^ 4 удовлетворяет неравенству

d < Г т ^ г - 3 - 2-i log2([V/2F^2yTT74 - 1/2])"

7. Установлено существование полиномиальной трансформации Задачи 3-ВЫП (распознавания) в Задачу о рюкзаке (распознавания),

при которой образ Задачи 3-ВЫП попадает в область множества задач о рюкзаках с плотностью d < С, где �