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

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

4855043

Подколзин Вадим Владиславович

МОДЕЛИРОВАНИЕ СИСТЕМ НА ОСНОВЕ ОДНОСТОРОННИХ РЮКЗАЧНЫХ ОТОБРАЖЕНИЙ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

2 9 СЕН 2011

Краснодар -2011

4855043

Работа выполнена на кафедре информационных технологий ГОУ ВПО «Кубанский государственный университет»

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

доцент

Осипян Валерий Осипович

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

доцент

Зеленков Геннадий Анатольевич

Ведущая организация: Южный федеральный университет

(г. Ростов-на-Дону)

Защита состоится 14 октября 2011 г. в 14-00 на заседании диссертационного совета Д 212.101.17 в Кубанском государственном университете по адресу: 350040, Краснодар, ул. Ставропольская, 149, ауд. 231.

С диссертацией можно ознакомиться в научной библиотеке Кубанского государственного университета, с авторефератом -на сайте http://www.kubsu.ru

кандидат физико-математических наук

Василенко Вера Викторовна

Автореферат разослан 12 сентября 2011 г.

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

В.Ю. Барсукова

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

С момента возникновения в начале 1970-х гг. понятие «ЫР-полная задача» определяет трудности, с которыми приходится сталкиваться разработчикам алгоритмов при решении задач постоянно возрастающей размерности и усложняющейся структуры. Большинство таких задач, часто встречающихся в математике, теоретическом программировании и исследовании операций, являются ТУР-полными.

Первые результаты о труднорешаемости задач - классические результаты о неразрешимости - были получены А. Тьюрингом. Он доказал, что для некоторых задач не существует алгоритма их решения. Основными объектами теории являются: класс ИР всех переборных задач и класс Р переборных задач, разрешимых за полиномиальное время на машине Тьюринга.

Большой практический мировой опыт решения дискретных задач дает основание считать, что Л^-полные задачи и задачи из класса Р сильно отличаются по трудоемкости решения, но в строгом смысле до сих пор это различие не доказано. Это, в частности, объясняется тем, что классы Р и ИР определяются с помощью понятия времени работы вычислительного устройства с потенциально неограниченной памятью. Основополагающий характер различий между классами Р и ИР впервые обсуждался в работах А. Кобхэма и Д. Эдмондса. В частности, Д. Эдмондс, отождествляя полиномиальные алгоритмы с «хорошими» алгоритмами, высказал предположение, что некоторые задачи целочисленного программирования невозможно решить такими «хорошими» алгоритмами.

В классе АТР выявлены так называемые универсальные ЛГ-полные задачи, к которым полиномиально сводится любая задача из ИР. В этом смысле универсальные задачи определяют эталон сложности. В настоящее время установлена универсальность многих задач, эквивалентных между собой относительно полиномиальной сводимости. Если бы удалось доказать, что некоторая ЛТ-полная задача принадлежит классу Р, то тем самым было бы доказано, что Р = ЫР, и можно было бы надеяться на построение эффективных алгоритмов для различных классов дискретных задач. Если же классы Р и ИР различны, то

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

Проблеме вычислительной сложности, представления и преобразования данных в современной научной литературе посвящены исследования А. Тьюринга, С. Кука, А. Кобхэма, Д. Эдмондса, В. Кли, Г. Минти, Н. Заде, М. Гэри, Д. Джонсона, Д. Хартманиса, Р. Стинза, А. Майера, Л. Стокмейера, М. Фишера, М. Рабина, У. Диффи, М. Хеллмана, Р. Меркле, А. Шамира, К. Вилиамса, Р. Карпа, В. Чора, Р. Райвеста, Е. Брикеля, А. Ростовцева, Е. Маховейко, Р. Лидла, Г. Нидеррайтера, Л. Адлемана и др. По мнению авторов, применение ИР-полных задач для моделирования систем доступности, целостности и безопасности данных является обоснованным. Качество таких систем существенно зависит как от самой задачи, так и от способа ее применения.

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

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

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

WEB-пpoгpaммиpoвaнии, баз данных и защиты информации. Для практического применения алгоритмов таких моделей важна их

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

К числу таких задач относится рассматриваемая в данном исследовании А^Р-полная задача о рюкзаке.

Основным аспектам использования ЯР-полной задачи о рюкзаке в преобразовании информации посвящены работы М. Хеллмана, Р. Меркле, А. Шамира, Н. Заде, В. Чора, Р. Райвеста, Е. Брикеля, В. Осипяна и др. Анализ трудов отечественных и зарубежных авторов показывает, что наиболее распространенными моделями, основанными на рюкзачных векторах, являются ассиметричные модели с открытым ключом.

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

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

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

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

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

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

2) исследовать применимость использования рюкзачного вектора для представления элементов заданного множества;

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

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

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

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

Научная новизна. В процессе выполнения диссертационной работы получены следующие научные результаты:

1) предложены методы анализа и определены свойства рюкзачного вектора на основе его вариации;

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

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

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

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

Теоретическая и практическая значимость работы.

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

Теоретическая значимость работы состоит в следующем:

1) предложены математические методы анализа свойств рюкзачных векторов заданной размерности;

2) разработаны методы построения инъективных рюкзачных векторов с заданными условиями;

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

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

Практическая значимость исследования определяется:

1) применимостью предложенных методов к решению задачи анализа рюкзачных односторонних отображений;

2) применимостью предложенных математических моделей и методов к решению задач построения систем на основе односторонних функций с заданными характеристиками;

3) разработкой программной системы с открытым ключом и динамическим рюкзачным вектором.

На защиту выносятся:

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

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

3. Численный метод построения инъективного рюкзачного вектора с заданными свойствами.

4. Математические модели односторонних отображений на основе динамически генерируемых рюкзачных векторов.

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

Апробация и внедрение результатов исследования проходили на базе Кубанского государственного университета, осуществлялись в форме научных докладов на XI Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2010), VII Международной конференции «Алгебра и теория чисел: современные проблемы» (Тула, 2010), VI Всероссийской научно-практической конференции

«Математические методы и информационно-технические средства» (Краснодар, 2010), I Всероссийской молодежной конференции по проблемам информационной безопасности «Перспектива-2009» (Таганрог, 2009), XIII Международной научной конференции им. Решетнева, (Красноярск, 2009), X Всероссийском симпозиуме по прикладной и промышленной математике (Санкт-Петербург, 2009), V Всероссийской научно-практической конференции «Математические методы и информационно-технические средства» (Краснодар, 2009), III Международной научно-практической конференции «Актуальные проблемы безопасности информационных технологий» (Красноярск, 2009), Международной научной конференции «Современные проблемы математики, информатики и управления» (Алматы, 2008).

Результаты исследования внедрены и используются в рамках учебного процесса в Кубанском государственном университете, Краснодарском университете МВД России, а также в программных системах ЗАО «ЭкоГрин».

На основе разработанных моделей и алгоритмов реализовано программное приложение преобразования данных «Программный комплекс преобразования информации «РСЗИ ДГВП», зарегистрированное в Реестре программ для ЭВМ под номером 2011610789 от 14 января 2011 г.

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

Структура и объем работы. Диссертационная работа изложена на 155 машинописных страницах, включает 3 главы, 18 рисунков, 5 таблиц, список литературы (105 наименования).

Тема и содержание диссертационного исследования соответствует требованиям паспорта специальности 05.13.18 -математическое моделирование, численные методы и комплексы программ и соответствуют следующим областям исследования паспорта специальности: 2. Развитие качественных и приближенных аналитических методов исследования математических моделей; 4. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента; 5. Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента; 8. Разработка систем компьютерного и имитационного моделирования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснованы важность и актуальность темы диссертации, сформулированы цели исследования и решаемые задачи, определена научная новизна и приведено краткое содержание диссертационного исследования по главам.

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

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

Дальнейшее развитие рюкзачные системы получили в работах В. О. Осипяна, где используется расширение значений коэффициентов до значений из 2Р. Показано, что обобщенные рюкзачные вектора имеют свойства, аналогичные стандартным (с коэффициентами из множества {0, 1}) рюкзакам. Но для модели Ма с обобщенным рюкзачным вектором требуются дополнительные затраты при анализе, а общее решение задачи о рюкзаке Ко имеет оценку сложности р". Развитие данного подхода позволило определить системы на основе так называемых универсальных рюкзаков, для каждого компонента которых определяется свой диапазон значений коэффициентов, и функциональных рюкзаков, представляющих собой набор целочисленных функций.

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

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

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

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

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

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

Обобщенная задача о рюкзаке Ко для заданных м>еЫ и вектора А=(аи а2, ..., ап), где а,еЫ, г = 1, ..., п, имеет решение в 2Р, если существует решение х уравнения

Лхг=н>, х&Ц. (1).

И

Рюкзачный вектор А = (аь а2, ..., а„) - инъективен, если для любого натурального IV уравнение (1) имеет не более одного решения. Такие рюкзачные вектора наиболее перспективны для исследования, так как допускают однозначность нахождения решения х и выражения в условиях (1).

Определение 2.1. Вариацией вектора Л = (аи а2, ..., а„) V, / = 1, ..., п) в 2Р называется вектор АА = (5ь 52, ..., 5„), для компонентов которого выполняются соотношения

51=щ, 5,= а£ - - 1)аьу=2, ..., п.

Обозначим через рр(А) множество значений ю, для которых уравнение (1) имеет решение в 2р.

Определение 2.2. Последовательность = (и'0, н'Ь н>2, ...,

Ырп^), где wi = Ах,т, х{ = (аи а2, ...,а„), г = Е"=1

/ = 0, ...,р"-1, называется последовательностью значений вектора А в 2Р.

Обозначим как АУУ^д) последовательность {т1, т2, ..., трп_1), где т, = ур,- - ц!и1 О, ,/=1, ..., рп-1). Пусть

Ап = (аи а2, ..., а„) - рюкзачный вектор. Вектор А„ц = (аи а2, ..., а„, ап±\) получен из А„ добавлением компонента ап+1. Тогда в последовательности А И^р(Лп+1) = (А И^р(Дп)> А И^р(Ап)>

Л 5„+ь А №цр(ап)) подпоследовательность 8„ц, А УУ^д^

повторяется р— 1 раз.

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

Теорема 2.1. Пусть А„ = (аь а2, а„) - инъективный возрастающий рюкзачный вектор в Х2 размерности п {п>2). Вектор Ап+1 = (аи а2, ..., а„, ап+\) - вектор, полученный из добавлением компонента аП+1, и АА„+1 = (8Ь 62, ..., 8„, 5,^) - вариация вектора А„+1. Тогда если 5„н > 0, то А„ц = (а\, а2, ..., а„, ап+1) является инъективным возрастающим рюкзачным вектором в Ъ2 размерности п+ 1.

Теорема 2.2. Пусть А„ = (ау, а2, ..., а„) - инъективный возрастающий рюкзачный вектор в размерности п (п>2). Вектор Ап+1 = {аи а2, ..., а„, ап+\) - вектор, полученный из А„ добавлением

компонента а„и, и ЛЛ„м = (5ь 52, ..., 8,„ 5„+1) - вариация вектора

Тогда А„у\ = (аи а2, ..., ат а,ц.{) является инъективным возрастающим рюкзачным вектором в 22 размерности п + 1, если выполняются следующие условия: а) а/^п+ь

Обобщение полученных результатов на пространство 2/; позволило описать свойства /лр(А), и А а также

сформулировать и доказать критерии построения инъективных рюкзачных векторов в 2;„

Теорема 2.3. Пусть = (аь а2, ..., <з„) - инъективный рюкзачный вектор в 2Р размерности п (п>2), где г = 1, ..., л.

Вектор Ап+1 = (аа2, ..., а„, а,,+\) получен из А„ добавлением компонента а„±\<=И, А= (5Ь 52, ..., 5„, 5„+0 - вариация вектора А^ 1. Тогда если 5„+1><9, то /1|Гн = (аь а2, ..., а„, 1) - инъективный рюкзачный вектор в 2р.

Теорема 2.4. Пусть А„ = (аи а2, ..., а„) - инъективный возрастающий рюкзачный вектор в 2Р размерности п (п>2), где I = 1, ..., п. Вектор Л„+1 = (аи а2, ..., а„, а^) получен из А„ добавлением компонента а^еИ, АА„+1 = (8Ь 5

2? От

5я+1) -

вариация вектора и 5,,и<0.

Вектор А„у 1 = (аи а2, ..., а„, ап+у) является инъективным возрастающим рюкзачным в 2Р, если выполняются условия:

a) ап - Е7=г(Р ~ < 5"+ь

b) Ы^2р_1(Лп).

В диссертации исследуются взаимные свойства векторов: определяются и исследуются понятия совместимости, несовместимости, несовпадения и сравнения рюкзачных векторов. Два вектора А и В совместимы, если /ир{А) о /лр(В) Ф 0. Коэффициент совместимости ||(Л,В)|| двух различных совместимых в 2Р рюкзачных векторов А я В определяет наибольшее возможное значение количества выражений произвольного значения IV в 2Р при их совместном использовании. Вводится понятие подрюкзака (операция -<), когда всякий компонент одного вектора является компонентом другого.

Исследуются свойства таких рюкзаков, формулируется и доказывается критерий неинъективности.

Лемма 2.1. Рюкзачный вектор А = (аи а2, ..., а„) размерности п, все компоненты которого различны (V/, ] а, Ф ар ' т- у), не является инъективным тогда и только тогда, когда существуют два различных совместимых в 2Р вектора В и С таких, что В<А и С<А.

Определение 2.3. Два возрастающих рюкзачных вектора А = (аи а2, ..., а„) и В = (Ьи Ь2, ..., Ьк), векторы вариаций АЛ и АВ которых отличаются только значением первого компонента, называются изоморфными и обозначают А~В, если существует изоморфизм /• /ир(А)-^р1р{В).

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

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

Лемма 2.2. Пусть А = (аь а%,..., а») - инъективный рюкзачный вектор в 1Р размерности ии/^0- целое число. Тогда не существует инъективного рюкзачного вектора размерности п, посредством компонентов которого в 1Р выражаются все элементы множества {ъИ 11УерР(А)}.

Определение 2.4. Два рюкзачных вектора А = {аи а2, ..., а„) и В = Ф1, Ь2, ..., Ьк) подобны, будем обозначать А=В, если существует взаимно однозначное отображение/- А—>В такое, что:

1) УаеАЛСа) = СЦо), где Се 2\

2) Ма\ а"еА выполняетсяЛа'+а")=/[а')+Ла").

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

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

Лемма 2.3. Пусть для возрастающего вектора А„ = (а\, д2, а„) размерности п множество А = \{Вк, Ск)} образует множество всех пар различных совместимых в 2Р рюкзаков Вк и Ск таких, что Вк^Л, Ск<А и Вк<Ск. Тогда для рюкзачного вектора А уравнение (1) в гр имеет не более чем шах(1, П'^И^м ^¡11) решений.

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

Теорема 2.5. Пусть для рюкзачного вектора= (аи аг, ..., а„) размерности п множество А = {{Вк, С*)} образует множество пар различных совместимых в 2Р рюкзаков Вк и Ск таких, что Вк<А, Ск<А и Вк<Ск. Кроме того, вектор А имеет г различных повторяющихся компонентов, причем первый из них повторяется т\ раз, второй - т2, г-й - тг. Тогда уравнение (1) для рюкзачного вектора А имеет решений не более чем

И

^о.Щв.ор П

1-1 1-1

I (-1/скт,с*

т,'(Р''>

Результатом исследования свойств А является

численный метод поиска рюкзачного вектора по заданному множеству значений соответствующей односторонней функции, в основе которого лежат статистические свойства подпоследовательностей А И^р(лу

Для заданной размерности рюкзачного вектора А определяется последовательность специального вида ^((¿х^ОДАгл),...), гдс * ~ сумма элементов подпоследовательности А где к, - количество вхождений

подпоследовательности элементов 5, в А < к^ /</. Для

заданной последовательности значений IV = {и>х', ..., м'„,'} определяется множество АIV = {со/ | со/ = м/ - IV,.х', / = 1,..., т}, где

и'о' = 0. На основе АРР аналогично задается последовательность Сопоставляя выборки из п элементов последовательностей 5" и осуществляется поиск вариации АА. Применимость предложенного метода определяется тем фактом, что чем раньше элемент встречается в тем больше вероятность найти соответствующий ему элемент в

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

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

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

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

Определение 3.1. Произвольную всюду определенную функцию ^ : будем называть генератором векторов

размерности п (ГВП) в 2Р.

Вектор А = (аь а2, ..., а„) е 2р определяется генератором векторов если существует А, е Л*, Г(к) = А и будем говорить, что А задается Г в точке X. В качестве ГВП могут выступать алгоритм, аналитическая функция или их совокупность. Здесь важно то, что ДА.) может быть найдено за приемлемое (в том или ином смысле) время.

Вектор .F(X)=/leZ£ рассматривается как рюкзачный вектор размерности п. Однако возможна интерпретация Р(Х) как вариация вектора АА, на основе которого возможно получение вектора А. В обоих случаях будем говорить, что задает вектор А, обозначим его Р(Х)=>А. Требование инъективности вектора /*"(/.) обеспечивается применением теорем 2.1, 2.2, 2.3, 2.4 при определении генератора.

С целью увеличения сложности анализа разработана модель преобразования числовой последовательности с динамически изменяющимся рюкзачным вектором (ДГВП):

1) ГВП Г: К1 —> 2р является частью системы, недоступной для сторонних пользователей;

2) значение ^еЛ^ общедоступно и определяется пользователем в качестве параметра отображения;

3) значение / принимается равным 1;

4) значение] принимается равным 1;

5) значение общедоступно и определяется в качестве параметра отображения;

6) результат отображения (А, у) = />(4',) = и', для очередного значения V, последовательности исходных данных определяется на основе рюкзачного вектора Л, где

7) значения / и у увеличиваются на 1;

8) если и7<г, то следует перейти к п.6;

9) если то следует перейти к п.4;

10) последовательность (Д Ли и>ь IV,, Л2, н',+ь ^'2/, ..., и',5) является результатом отображения системой последовательности числовых значений (уь у2,..., у5).

Восстановление значений (уь у2, ..., V,) определяется функцией ^бО;) = V, для соответствующих векторов Р(ку)=>А.

Для предложенной модели доказана следующая теорема:

Теорема 3.1. При одинаковой верхней границе значений выходов ™тса сложность нахождения параметров модели с ДГВт не меньше сложности нахождения параметров модели с ГВП, если количество рюкзачных векторов Сь, используемых в модели с ДГВП, не меньше п-т+1.

Сложность поиска одностороннего отображения на основе ДГВ в 22 превышает сложность поиска одностороннего отображения на основе ГВ256 в 22 уже при преобразовании набора данных объемом 2 килобайта в условиях теоремы 3.1. Данный факт показывает практическую значимость предложенных моделей в силу возможности оптимизации ресурсов при реализации систем на их основе.

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

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

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

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

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

Общая блок-схема функционирования систем на основе ДГВП представлена на рисунке.

Генератор рюкзачного вектора А(аиа2,...,а„) :=

Р(гь ...,/"„ г,■+!, ...,/■*)

Секретный параметр

Х'=(п+и п+2, п)

I

Открытый параметр ^=(Гь г2,..., г,У,

Применение рюкзачного вектора а2,..., а„) к части исходного текста

Модуль преобразования

Размер применимости

В рамках диссертационного исследования определена математическая модель односторонней функции, основанной на обратной задаче о рюкзаке (ОДГВп) для рюкзачного вектора Л = (аь а2, ..., а„). Результирующее значение со такого отображения в Zp представляет собой последовательность значений (аь а2, ..., а„, г|0, г|ь ...,r|s), где s = [logp(ai - 1)] + 1. Первые п элементов определяются разбиением по компонентам рюкзачного вектора согласно соотношений

ап = o)div ап, a¿ = ^со - ^ O/O/j div a¿.

Последовательность Г|0Г11...Г|5 определяет представление значения со — а;-ау в системе счисления с основанием р. В целях оптимизации затрат на реализацию и уменьшения вероятности эффективного анализа значение р определяется на основе рюкзачного вектора А по правилу

р = 1 + maxi=l n_1(2, (ai+1 - l)d¿v a¿).

Приводятся различные математические модели ОДГВп.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

В процессе выполнения диссертационной работы получены следующие основные научные и практические результаты.

1. Дано математическое описание элементов множества числовых значений, выражаемых в рюкзачном векторе.

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

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

4. Построены модели односторонних отображений на основе динамически генерируемых рюкзачных векторов.

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

Список основных трудов по теме диссертации

1. Подколзин В.В., Осипян В.О. О свойствах рюкзачных систем защиты информации с открытым ключом в II Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. 2010. Вып. 3(29). С. 51-55.

2. Подколзин В. В. Построение инъективных рюкзачных векторов на основе структурных и частотных свойств числовых множеств // Экологический вестник научных центров Черноморского экономического сотрудничества. 2010. №4. С. 6467.

3. Подколзин В.В. Модель системы защиты информации с открытым ключом на основе динамической генерации рюкзачного вектора // Обозрение прикладной и промышленной математики. М.: Изд-во ОПиПМ, 2009. Т. 16, вып. 5. С. 913-914.

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

5. Осипян В.О., Подколзин В.В. Модели на основе рюкзачного вектора с обратным преобразованием // Экологический вестник научных центров Черноморского экономического сотрудничества. 2010. №4. С. 59-63.

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

рюкзака // Обозрение прикладной и промышленной математики. М.: Изд-во ОПиПМ, 2009. Т. 16, вып. 5. С. 905.

7. Подколзин В.В. Построение инъективного рюкзачного вектора для заданного множества значений на основе вариации // Обозрение прикладной и промышленной математики. М.: Изд-во ОПиПМ, 2010. Т. 17, вып. 3. С. 451-452.

8. Подколзин В.В. Модель системы защиты информации на основе обратной задачи о рюкзаке // Математические методы и информационно-технические средства: труды V Всерос. науч,-практ. конф. Краснодар: Краснодарский ун-т МВД России, 2009. С. 139-141.

9. Подколзин В.В. Об одном определении рюкзачной СЗИ с открытым ключом на основе динамически создаваемого вектора. Верхняя оценка количества решений // Материалы I Всероссийской молодежной конференции по проблемам информационной безопасности «Перспектива-2009». Таганрог: Изд-во ТТИ ЮФО, 2009. С 265-269.

10. Подколзин В.В., Осипян В. О. Алгоритм построения инъективного возрастающего рюкзачного вектора // Математические методы и информационно-технические средства: труды V Всерос. науч.-практ. конф. Краснодар: Краснодарский ун-т МВД России, 2009. С. 141-145.

11. Подколзин В.В., Осипян В.О. Верхняя граница числа решений обобщенной задачи о рюкзаке на заданном входе // Актуальные проблемы безопасности информационных технологий: материалы III Междунар. науч.-практ. конф. / под общ. ред. О. Н. Жданова, В. В. Золотарева. Красноярск: Сибирский гос. аэрокосмический ун-т, 2009. С. 28-32.

12. Подколзин В.В., Осипян В.О., Арджанов A.A. Изоморфизм рюкзачных систем защиты информации с открытым ключом // Материалы XIII Международной научной конференции им. Решетнева. Красноярск: Сибирский гос. аэрокосмический ун-т, 2009. С. 569-571.

13. Осипян В.О., Подколзин В.В. Моделирование рюкзачных систем защиты информации на основе динамически изменяемого рюкзачного вектора // Математические методы и информационно-технические средства: труды VI Всерос. науч.-практ. конф. Краснодар: Краснодарский ун-т МВД России, 2010. С. 128-132.

14. Осипян В.О., Подколзин В.В. Системы защиты информации с генератором рюкзачных векторов // Труды академии связи : научно-технический сборник № 76. С. 53-55. г. Краснодар, 2010.

15. Осипян В.О., Подколзин В.В., Арджанов A.A. О сложности задачи о плотной укладке рюкзака для выходов систем защиты информации на основе ГРВ // Математические методы и информационно-технические средства: труды V Всерос. науч.-практ. конф. Краснодар: Краснодарский ун-т МВД России, 2009. С. 136-139.

16. Осипян В.О., Подколзин В.В., Арджанов A.A. Об одной кодовой криптосистеме на основе кода Варшамова // Материалы XIII Международной научной конференции им. Решетнева Красноярск: Сибирский гос. аэрокосмический ун-т, 2009. С. 568569

17. Осипян В.О., Спирина С.Г., Подколзин В.В., Шевцова М.А. Разработка методов построения и оценка числа перестановочных целых функций над полем Галуа // Вестник КазНУ. 2008. №4 (59). С. 178-183.

18. Осипян В.О., Спирина С.Г., Подколзин В.В., Арутюнян А. С. Моделирование ранцевых криптосистем, содержащих диофантовую трудность // Чебышевский сборник Т. XI, вып. 1(33): труды VII Междунар. конф. Алгебра и теория чисел: современные проблемы. Тула: Изд-во Тул. гос. пед. ун-та им. Ломоносова, 2010. С. 209-217.

19. Осипян В.О., Спирина С.Г., Подколзин В.В. Моделирование перестановок на основе перестановочных целых функций // Современные проблемы математики, информатики и управления: материалы Междунар. науч. конф. Алматы: Институт проблем информатики и управления, 2008. С. 284-287.

20. Свидетельство о государственной регистрации программ для ЭВМ № 2011610789. Программный комплекс преобразования информации «РСЗИ ДГВП» // Подколзин В.В., Осипян В.О. ; заявитель и правообладатель ГОУ ВПО КубГУ - № 2010617352; заявл. 23.10.2010; опубл. 14.01.2011, Реестр программ для ЭВМ.

Подколзин Вадим Владиславович

МОДЕЛИРОВАНИЕ СИСТЕМ НА ОСНОВЕ ОДНОСТОРОННИХ РЮКЗАЧНЫХ

ОТОБРАЖЕНИЙ

__Автореферат

Бумага тип. № 2. Печать трафаретная. Тираж 100 экз. Заказ № 859

350040 г. Краснодар, ул. Ставропольская, 149, Центр "Универсервис", тел. 21-99-551.

ВВЕДЕНИЕ.

ГЛАВА 1. №>-ПОЛНЫЕ ЗАДАЧИ И ИХ ПРИЛОЖЕНИЯ.

1.1. ИР-полные задачи. Сложность вычислений.

1.2. Системы преобразования информации на основе КР-полной задаче о рюкзаке.

1.3. Системы, основанные на функциональных векторах.

1.4. Симметричные системы.

1.5. Хеширование.

1.6. Методы поиска функции преобразования.

ГЛАВА 2. МОДЕЛИРОВАНИЕ РЮКЗАЧНЫХ ВЕКТОРОВ С ЗАДАННЫМИ СВОЙСТВАМИ.

2.1. Инъективность рюкзачных векторов в гр.

2.2. Изоморфизм рюкзачных векторов.

2.3. Верхняя граница числа решений задачи о рюкзаке.

2.4. Построение инъективного рюкзачного вектора для заданного множества значений.

ГЛАВА 3. МОДЕЛИ И СИСТЕМЫ С ДИНАМИЧЕСКИ ОПРЕДЕЛЯЕМЫМИ ВЕКТОРАМИ.

3.1. Моделирование односторонних рюкзачных отображений.

3.2. Моделирование односторонних отображений на основе обратного рюкзачного преобразования.

3.3. Математические модели генераторов рюкзачных векторов.

3.4. Алгоритмы функционирования систем с ДГВП.

3.5. Алгоритмы функционирования систем с ОДГВп.

3.6. Программное приложение «РСЗИ ДГВП».

С момента возникновения в начале 70-х годов понятие "]УР-полная задача" определяет трудности, с которыми приходится сталкиваться разработчикам алгоритмов при решении задач постоянно возрастающей размерности и усложняющейся структуры. Большинство таких задач, часто встречающихся в математике, теоретическом программировании и исследовании операций, являются А/Р-полными.

Первые результаты о труднорешаемости задач — классические результаты о неразрешимости — были получены А. Тьюрингом [14]. Он доказал, что для некоторых задач не существует алгоритма их решения. Основными объектами теории являются: класс NР всех переборных задач и класс Р переборных задач, разрешимых за полиномиальное время на машине Тьюринга.

Большой практический мировой опыт решения дискретных задач дает основание считать, что тУР-полные задачи и задачи из класса Р сильно отличаются по трудоемкости решения, но в строгом смысле до сих пор это различие не доказано. Это, в частности, объясняется тем, что классы Р и МР определяются с помощью понятия времени работы вычислительного устройства с потенциально неограниченной памятью. Основополагающий характер различий между Р и ЫР классами впервые обсуждался в работах А. Кобхэма и Д. Эдмондса [84, 88, 89, 90]. В частности, Д. Эдмондс отождествлял полиномиальные алгоритмы с "хорошими" алгоритмами и высказал предположение, что некоторые задачи целочисленного программирования невозможно решить такими "хорошими" алгоритмами.

В классе ИР выявлены так называемые универсальные ТУР-полные задачи [14, 85, 86, 87], к которым полиномиально сводится любая задача из ИР. В этом смысле универсальные задачи определяют эталон сложности. В настоящее время установлена универсальность многих задач, эквивалентных между собой относительно полиномиальной сводимости. Если бы удалось доказать, что некоторая ТУР-полная задача принадлежит классу Р, то тем 3 самым было бы доказано, что Р=ЫР, и можно было бы надеяться на, построение эффективных алгоритмов для различных, классов дискретных . задач. Если же классы Р и Ж* различны, то необходимо разрабатывать эффективные алгоритмы для все более узких классов задач.

Проблеме вычислительной сложности-, представления и преобразования; данных в современной! научной литературе посвящены исследования А. Тьюринга, С. Кука, А. Кобхэма, Д. Эдмондса, В. Кли, Г. Минти, Н. Заде, М. Гэри, Д. Джонсона, Д. Хартманиса, Р: Спшза, А. Майера, Л. Стокмейера, М. Фишера, М. Рабина, У. Диффи, М. Хеллмана, Р. Меркле, А. Шамира, К. Вилиамса, Р. Карпа, В; Чора, Р: Райвеста, Е. Брикеля, А. Ростовцева, Е. Маховейко, Р. Лидла,. Г. Нидеррайтера, Л. Адлемана и др. По мнению авторов, применение М?-полных задач для моделирования систем, доступности, целостности и; безопасности данных является обоснованным: Качество! таких систем существенно зависит как: от самой задачи, так и от способа ее применения.

Исходя из; теоретических положений1 построения математических моделей [18, 19, 62] в диссертационной работе не рассматриваются конкретная физическая; природа, содержание и назначение; объектов, а они заменяются соответствующими; моделями. Под моделью понимается способ описания объекта, процесса или явления, отражающий, существенные,, с. точки зрения решаемой задачи, факторы или параметры [25].

Отметим, что; проблема; теоретической: информатики о существовании класса. А^Р-полных задач тесно связана; с. вопросом о существовании одно сторонних функций; Под односторонней, понимается функция, значени е которой для любого входного значения вычисляется за полиномиальное время, но не существует полиномиального алгоритма нахождения аргумента при заданном значении функции; Ни для ¡одной функции не удалось доказать, что она трудна для- обращения, хотя многие функции кажутся таковыми. В работах [95, 92, 28, 91, 96, 104] указан ряд комбинаторных и алгебраических задач, которые являются в среднем полными при равномерном распределении входов.

Использование в основе многих моделей и систем односторонних функций позволило эффективно решать задачи в областях теории кодирования, алгоритмизации, \¥ЕВ-программировании, баз данных и защиты информации. Важным моментом для практического применения алгоритмов таких моделей является их безопасность, т.е. сложность обращения, которая« зачастую определяется некоторой вычислительно трудной задачей, лежащей в ее основе. Такие задачи имеют решения, однако их нахождение требует больших вычислительных ресурсов и* временных затрат. Следовательно, выбор подходящей трудно решаемой задачи, в частности, ./УР-полной задачи, позволяет моделировать систему на должном уровне безопасности.

Одной из таких задач, рассматриваемой в данном исследовании, является тУР-полная задача о рюкзаке.

Основным аспектам использования ТУР-полной задачи о рюкзаке в преобразовании информации посвящены работы М. Хеллмана, Р. Меркле, А. Шамира, Н. Заде, В. Чора, Р. Райвеста, Е. Брикеля, В. Осипяна и др. Анализ трудов отечественных и зарубежных авторов показывает, что наиболее распространенными моделями, основанными на рюкзачных векторах, являются ассиметричные модели с открытым ключом.

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

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

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

Целью диссертационной работы является разработка математических моделей, методов и механизмов одностороннего отображения числовых данных на основе рюкзачных векторов, обращение которых требует одновременного решения нескольких ТУР-полных задач, задач дискретной интерполяции'и разбиений числовых значений, при условии* многократного изменения параметров отображения в рамках одного набора данных, что обеспечивает повышение качества систем, в которых они применяются.

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

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

2) исследовать применимость использования рюкзачного вектора для представления элементов заданного множества;

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

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

5) разработать математические модели полиалфавитных, систем? преобразования данных с открытым? ключом на основе: односторонних рюкзачных отображений.

Методы исследования;. В исследовании использованы аппарат и методы линейной? алгебры; теории чисел;, теории сложности; математического?анализа; математической ¡:статистики; теории вероятности и теории информационной безопасности. . •

Научная новизна; В процессе' выполнения диссертационной работы5 получены следующие научные результа ты:

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

2. Разработан численный» метод построения инъективных рюкзачных векторов заданной размерности; в компонентах которого выражаются элементы базового числового множества. ' \

3. Разработаны математические модели инъективных односторонних отображений на основе динамически генерируемых рюкзачных векторов и построены; алгоритмы функционирования систем на их основе. ■

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

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

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

Теоретическая значимость работы состоит в следующем:

1) предложены математические методы анализа свойств рюкзачных векторов заданной размерности;

2) разработаны методы построения инъективных рюкзачных векторов с заданными условиями;

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

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

Практическая значимость исследования определяется:

1) применимостью предложенных методов к решению задачи анализа рюкзачных односторонних отображений;

2) применимостью предложенных математических моделей и методов к решению задач построения систем на основе односторонних функций с заданными характеристиками;

3) разработкой программной системы с открытым ключом и динамическим рюкзачным вектором.

На защиту выносятся:

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

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

3. Численный метод построения инъективного рюкзачного вектора с заданными свойствами.

4. Математические модели односторонних отображений на основе динамически генерируемых рюкзачных векторов.

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

Апробация и внедрение результатов исследования проходили на базе Кубанского государственного университета, осуществлялись в форме научных докладов на XI Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2010), VII Международной конференции «Алгебра и теория чисел: современные проблемы» (Тула, 2010), VI Всероссийской научно-практической конференции «Математические методы и информационно-технические средства» (Краснодар, 2010), I Всероссийской молодежной конференции по проблемам информационной безопасности «Перспектива-2009» (Таганрог, 2009), XIII Международной научной конференции им. Решетнева, (Красноярск, 2009), X Всероссийском симпозиуме по прикладной и промышленной математике (Санкт-Петербург, 2009), V Всероссийской научно-практической конференции «Математические методы и информационно-технические средства» (Краснодар,- 2009), III Международной научно-практической конференции «Актуальные проблемы безопасности информационных технологий» (Красноярск, 2009), Международной научной конференции «Современные проблемы математики, информатики и управления» (Алматы, 2008).

Результаты исследования внедрены и используются в рамках учебного процесса в Кубанском государственном университете, Краснодарском университете МВД России, а также в программных системах ЗАО «ЭкоГрин».

На основе разработанных моделей и алгоритмов реализовано программное приложение преобразования, данных «Программный комплекс преобразования^ информации* «РСЗИ ДГВ"» зарегистрированное в Реестре программ для ЭВМ под номером 2011610789 от 14 января 2011 г.

Публикации. Основные результаты диссертационной работы изложены в 20 публикациях, 7 из которых; опубликованы в ведущих рецензируемых журналах, входящих в перечень рекомендуемых ВАК, в докладах и тезисах докладов на международных и всероссийских научно-практических конференциях.

Структура и объем работы. Диссертационная работа изложена на 155 машинописных страницах, включает 3 главы; 18 рисунков, 5 таблиц^ список литературы- (105 наименований). Основные положения: диссертационного исследования отражены в публикациях автора [4Г, 42, 43, 44, 45, 46, 48,. 49, 50, 52, 53; 54, 55; 56; 57, 58; 59^ 60, 61,105]: •

В' первой' главе проведён- анализ известных теоретических п практических: решений проблем, основанных на М'-полных задачах, рассмотрены основные . проблемы теории? и практики односторонних функций; Подчёркнуто, что; в; основе большинства- задач теории сложности, алгоритмизации^ \УЕВ1программировании; баз данных, передачи и защиты информации; лежит односторонняя функция. Под односторонней функцией понимается отображение, значение которого для любого входного значения вычисляется за полиномиальное ~ времяг но поиск обратного отображения связан- либо с ТУР-иолной задачей;, либо эффективный алгоритм, реализующий обратное отображение, еще не известен;

В главе проводится обзор наиболее известных способов'использования А'Р-полной задачи о рюкзаке, а именно систем прямого преобразования, с открытым ключом: В таких системах в; качестве открытого ключа используют неким образом преобразованный рюкзачный вектор, а метод преобразования является секретным. Метод поиска векторов, описывающих отображение исходных данных во множество значений, для таких систем определяется, прежде всего, сложностью модификации рюкзачного вектора. В частности, для системы Меркле-Хеллмана найден эффективный метод анализа, а для системы Чор-Райвестра - нет.

Дальнейшее развитие рюкзачные системы получили в работах [35, 36, 38, 39], где используется расширение значений коэффициентов до значений из Zя. Показано, что обобщенные рюкзачные вектора имеют свойства аналогичные стандартным (с коэффициентами из множества {0, 1}) рюкзакам. Но для модели Мс с обобщенным рюкзачным вектором требуются дополнительные затраты при анализе, а общее решение задачи о рюкзаке Кс имеет оценку сложности р". Развитие данного подхода позволило определить системы на основе, так называемых универсальных рюкзаков, для каждого компонента которых определяется свой диапазон значений коэффициентов, и функциональных рюкзаков, представляющих собой набор целочисленных функций [37, 40].

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

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

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

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

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

Обобщенная задача о рюкзаке Ка для заданных м>еЫ и вектора А=(а1, а2, ., а„), где а^И, 1=1, ., п, имеет решение в если существует решение х уравнения

Лхт=ы, (1).

Рюкзачный вектор А=(а], а2, . а^ - инъективен, если для любого натурального м> уравнение (1) имеет не более одного решения. Такие рюкзачные вектора являются наиболее перспективными для исследования, так как допускают однозначность нахождения решения х и выражения в условиях (1).

Определение. Вариацией вектора^ = а2, а(а,еЫ, 1=1, ., п) в 2Р, называется вектор АА=(Ъ/, 82> • ••> для компонентов которого выполняются соотношения:

3, = а,> SJ = aJ-Ъp-1)a,^jz=2- ->

1-1

Обозначим через ЦР(А) множество значений м>, для которых уравнение (1) имеет решение в 2Р.

Определение. Последовательность ^/¿р(л)к>1, где ч>1=Ах{, х1=(а!, а2, 1=У^СХ Р > р"-1, называется последовательностью значений вектора А в 2р.

Обозначим как Л последовательность (ть т2,., трп1), где т1=ыги>и О, р"-1)■ Пусть А„=(а1, а2, ., а^ - рюкзачный вектор. Вектор Ап+] =(а], а2, ., ап, ап+;) получен из А„ добавлением компонента ап+1. Тогда в последовательности подпоследовательность Зп+1, А Щ1р(Ап) повторяется р-1 раз.

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

Теорема 2.1. Пусть Ап=(а], а2, ., а^ - инъективный возрастающий рюкзачный вектор в Х2размерности п (п>2). Вектор Ап+! =(а\, а2, ., ап, ап+!) -вектор полученный из Ап добавлением компонента ап+] и ААп+1=(8], д2, 5п, дп+1) - вариация вектора Ап+1. Тогда если дп+1>0, то А„+1=(а1, а2, ., а„, ап+1) является инъективным возрастающим рюкзачным вектором в размерности п+1.

Теорема 2.2. Пусть А„=(а], а2, ., а1Ь) - инъективный возрастающий рюкзачный вектор в 22 размерности п (п>2). Вектор Ап+1 =(аъ а2, ., ап, ап+!) вектор полученный из А„ добавлением компонента ап+1 и ААп+1=('8/, 82, 8п, 8п+1) — вариация вектора Лп+].

Тогда Ап+1=(а], а2, ., ап, ап+1) является инъективным возрастающим рюкзачным вектором в 22 размерности п+1, если выполняются следующие условия: п-1 а)

1=1

Обобщение полученных результатов на пространство Zp позволило описать свойства Ц,(А), И^^л) и Л а также сформулировать и доказать критерии построения инъективных рюкзачных векторов в 2Р\

Теорема 2.3. Пусть Ап=(а1, а2, ., а„) - инъективный рюкзачный вектор в 2Р размерности п (п>2), где а^И, 1=1, ., п. Вектор Ап+! а2, ., а,„ ап+]) получен из ^„добавлением компонента ап+1еИ, ААп+1~(81, 82, 8„, 8п+¡) -вариация вектора А„+]. Тогда если 8п+1>0, то А„+1=(а1, а2, ., а„, ап+!) — инъективный рюкзачный вектор в 2Р.

Теорема 2.4. Пусть Ап=(а], а2, ., а^ - инъективный возрастающий рюкзачный вектор в 2р размерности п (п>2), где а,еМ, 1=1, п. Вектор Ап+1=(а1, а2, ., а„, ап+1) получен из Ап добавлением компонента а„+]еИ, ДАп+1=(8ь 82, 8„, 8п+1) - вариация вектора Ап+1 и 8п+1<0.

Вектор Ап+!=(а}, а2, ап, ап+1) является инъективным возрастающим рюкзачным в 2Р, если выполняется: a) а~1^(р-^)а,<5п+1 1 b)

В диссертации исследуются взаимные свойства векторов: определяются и исследуются понятия совместимости, несовместимости, несовпадения и сравнения рюкзачных векторов. Два вектора А и В совместимы, если ц,(А) п ¿ир(В) Ф 0. Коэффициент совместимости ||(Л,5)[| двух различных совместимых в 7Р рюкзачных векторов А и В определяет наибольшее возможное значение количества выражений произвольного значения м? в ZD при их совместном использовании. Автором вводится понятие подрюкзака (операция -<:) когда всякий компонент одного вектора является компонентом другого. Исследуются свойства таких рюкзаков, формулируется и доказывается критерий неинъективности:

Лемма 2.1. Рюкзачный вектор А=(аь а2, ., а^ размерности п, все компоненты которого различны (VI, ] сц Ф ар I Ф]), не является инъективным тогда, и только тогда, когда существуют два различных совместимых в 2Р вектора В и С таких, что В-< А и С<А.

Определение. Два возрастающих рюкзачных вектора А = (а1г а2, а^ и В = фи ■••, векторы вариаций АА и А/5 которых отличаются-только значением первого компонента, называются изоморфными и обозначают А~В, если существует изоморфизм/: /ир(А)—*1ир(В).

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

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

Лемма 2.2. Пусть А= (а}, а2, а,) - инъективный рюкзачный вектор в 2р размерности п и - целое число. Тогда не существует инъективного рюкзачного вектора размерности п, посредством компонентов которого в 2Р выражаются все элементы множества | лне^А)}.

Определение. Два рюкзачных вектора А=(а1, аи

В=(Ъи Ьг, Ьу) подобны, будем обозначать А=В, если существует взаимно однозначное отображение/: А-^-В такое, что:

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

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

Лемма 2.3. Пусть для возрастающего вектора А=(а1, а2, ., а,) размерности п множество А={(Вк,С^} образует множество всех пар различных совместимых в Zí, рюкзаков Вк и Ск таких, что Вк<А, Ск~<А и Вк<Ск. Тогда для рюкзачного вектора А уравнение (1) в имеет не более чем а| тах(1, П||(Д,с,)|р решений.

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

Теорема 2.5. Пусть для рюкзачного вектора А=(аи а2, а1г) размерности п, множество Л={(Вк,С&)} образует множество пар различных совместимых в 1Р рюкзаков Вк и Ск таких, что Вк-<А, Ск<А и Вк<Ск. Кроме того, вектор А имеет г различных повторяющихся компонентов, причем первый из них повторяется ту раз, второй — т2, ., г-ый — тг. Тогда уравнение (1) для рюкзачного вектора^ имеет решений не более чем

1. УаеА/(Са) — С/(а), где Се Z]

2. Уаа"еА выполняется/^'+а'^/(а^+Да

1=1 а| г [ 2*Р тах(1,П||(Д ,С,)||) П Е (~1) С'т Ст

1=1 ]-\ *=0 1 г\т;<р-У 2 *р

-I ч У

Результатом исследования свойств А Щ1р(л) является численный метод поиска рюкзачного вектора по заданному множеству значений соответствующей односторонней функции, в основе которого лежат статистические свойства подпоследовательностей А

Для заданной размерности рюкзачного вектора А определяется последовательность специального вида 3„=((кц^!), (к2Я2),.), где я,- - сумма элементов подпоследовательности А где к, - количество вхождений подпоследовательности элементов .V, в А к, < кр /</'. Для заданной последовательности значений определяется множество

АЖ-{сц' | щ-ю,- у^ы', 1=1,.т}, где \ио-0. На основе А1¥' задается последовательность -((к/э^), аналогично Сопоставляя выборки из п элементов последовательностей 5/и ^ осуществляется поиск вариации АЛ. Применимость предложенного метода определяется тем фактом, что чем раньше элемент встречается в тем больше вероятность, что соответствующий ему элемент найдется в 5"!

Показано, что для восстановления рюкзачного вектора нет необходимости иметь большой объем информации о результатах отображения, существенным является количество различных значений. Предложенный численный метод позволяет уменьшить объем вычислений при поиске рюкзачного вектора - параметра одностороннего рюкзачного отображения - на основе различных значений ,Ир(А). Обоснованы методы оптимизации численного метода для случая Z^

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

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

Определение. Произвольную всюду определенную функцию Т7; будем называть генератором векторов размерности п (ГВП) в 2Р,

Вектор А=(а], а2, ., а,)е определяется генератором векторов Р, если существует Яе Лк, что Р(Я)=А и будем говорить, что А задается Р в точке Я. В качестве ГВП могут выступать алгоритм, аналитическая функция или их совокупность. Важным здесь является то, что Р(Я) может быть найдено за приемлемое (в том или ином смысле) время.

Вектор Р(Я)=Ае2у рассматривается как рюкзачный вектор размерности п. С другой стороны, возможна интерпретация Р(Я) как вариация вектора АА, на основе которого возможно получение вектора А. В обоих случаях будем говорить, что Р(Я) задает вектор А и обозначать Р(Я)=>А. Требование инъективности вектора Р(Я) обеспечивается применением Теорем 2.1, 2.2,2.3,2.4 при определении генератора.

С целью увеличения сложности анализа разработана модель преобразования числовой последовательности с динамически изменяющимся рюкзачным вектором (ДГВП):

1) ГВП .Р: Ик —> является частью системы, недоступной для сторонних пользователей;

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

3) определить значение г равное 1;

4) определить значение] равное 1\

5) значение является общедоступным, и определяется в качестве параметра отображения;

6) определить результат отображения (Л,у)=17пр(л>1)=лу1 для очередного значения v,- последовательности исходных данных на основе рюкзачного вектора А, где Г(Яу)=>А;

7) Увеличить значения / иу на 1\

8) если ито перейти к п.6

9) если то перейти к п.4

10) последовательность (7, X¡, м>1, ., лчь ^ является результатом отображения системой последовательности числовых значений (у1, у2, ., V,);

Восстановление значений (V/, у2, ., у^) определяется функцией Роб(м?1)=л>{ для соответствующих векторов Р(Я^)=>А.

Для предложенной модели доказана следующая теорема.

Теорема 3.1. При одинаковой верхней границе значений выходов м?тах, сложность нахождения параметров модели с ДГВШ не меньше сложности нахождения параметров модели с ГВП, если количество рюкзачных векторов Сь используемых в модели с ДГВП не меньше п-т+1.

Сложность поиска одностороннего отображения на основе ДГВ44 в Z2 превышает сложность поиска одностороннего отображения на основе ГВ в 22 уже при преобразовании набора данных объемом 2 килобайта в условиях

19

Теоремы 3.1. Данный факт показывает практическую значимость предложенных моделей в силу возможности оптимизации ресурсов при реализации систем на их основе.

Применяя .правило Кергхоффса, в диссертационном исследовании; модифицированьъмодели односторонних;отображений на-основе генераторов;; векторов в части анонимности?: определения; генератора. Анализируются: методы: задания генератора рюкзачных векторов, секретных и; открытых параметров в целях увеличения , сложности поиска; функции отображения; Приводятся примеры: ГВП на основе одной или нескольких аналитических функций. Показана возможность определения-рюкзачных векторов на основе рекуррентных зависимостей. Исследуется стойкость таких моделей. Результаты исследования^ показывают неэффективность, большинства известных методов анализа.таких отображений!

Показано, что используя системы . с ДГВП можно минимизировать возможность применения статистических методов анализа, а при достаточно . большом л и алгебраических процедур анализа. Метод анализа на: основе вариации существенно?зависит от распределения?известных значений ЦР(Л). Но; модификация результатов отображения путем изменения числового значение текста посредством; корректирующей функции, свойства* которой оиисаны в работе, приводит к невозможности получения рюкзачного век гора отображения шэтим методом, так как метод-будет искать вектора по заведомо ложным данным. :

Проведен сравнительный анализ; характеристик моделей односторонних отображений на основе ГВП и ДГВ". Предложены методы их использования, в частности, приведены примеры рюкзачных систем защиты информации.

В рамках исследования созданы; различные системы преобразования данных на основе моделей с ГВП и ДГВ" с различными способами определения; генератора векторов. Показана высокая« сложность восстановления параметров преобразования таких систем, даже при небольших размерах рюкзачного вектора. Существенной характеристикой моделей с ДГВП является значение размера применимости рюкзачного вектора, которое определяет, прежде всего, количество различных рюкзачных векторов в рамках одного преобразования массива исходных данных. Указание в модели значения размера применимости рюкзачного вектора меньше размера последнего приводит к невозможности использовать непереборные методы анализа. Свойства получаемых отображений близки к полиалфавитным с малой вероятностью повторения результата для одного и того же исходного значения.

Общая блок-схема функционирования систем на основе ДГВ" представлена на рис. 1.

Рис. 1.

В рамках диссертационного исследования определена математическая модель односторонней функции, основанной на обратной задаче о рюкзаке (ОДГВ") для рюкзачного вектора А=(а!, а2, а^. Результирующее значение со такого отображения в Zp представляет собой последовательность значений (аи а2, ., (Хп, r¡0, r¡¡, .,r¡s), где s=[logp(ar!)]+!■ Первые п элементов определяются разбиением по компонентам рюкзачного вектора согласно соотношений: п an=a)div ап, oc¡=(со- YjOC, aj div a¡1

Последовательность r¡Qr¡i.T]s определяет представление значения п a-Znaj в системе счисления с основанием р. В целях оптимизации затрат м 1 на реализацию и уменьшения вероятности эффективного анализа, значение р определяется на основе рюкзачного вектора А по правилу р = 1 + maxi^n^V, (а£+1 - X)div a¿). Приводятся различные математические модели ОДГВп.

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

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

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

В диссертации используются следующие обозначения: р - простое число;

N- множество натуральных чисел и ноль;

Р, Z, R - множество простых, целых и вещественных чисел соответственно;

Zp={ 0, 1, 2, ., р- 1} - кольцо вычетов по модулю р; = - отношение сравнимости (а = b (mod т ) означает а сравнимо с b по модулю т ); х ] - наименьшая целая часть действительного числа х; х div у -целая часть от деления целого числа х на целое число у; N (*) - количество числовых значений, удовлетворяющих *; 1, . п- отрезок последовательных натуральных чисел от 1 до п\

- алфавит и множество всех слов (словарь) над ^соответственно; пространство векторов (х1г х2, . x,J, X\eZp, i=l, ., п\ R" - пространство векторов (х}, х2, . х„), x,eR, i-1, п; А = (ah а2, .,а„) - вектор размерности п > 2; AA=(S], S2, ., S^ - вариация вектора^; МТ - машина Тьюринга; ДМТ - детерминированная машина Тьюринга; Ка - задача об обобщённом рюкзаке; Ки- задача об универсальном рюкзаке; Кр - задача о функциональном рюкзаке; ГВП - генератор векторов размерности п; ДГВП - динамический генератор векторов размерности п.

Формулы, теоремы и леммы - нумеруются отдельно в каждой главе.