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

• Мурин, Дмитрий Михайлович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Мурин, Дмитрий Михайлович

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.7. Выводы

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

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

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

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

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

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

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

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

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

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

2.8. Выводы

А

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

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

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

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

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

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

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

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

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

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

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

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

3.4. Выводы

Заключение

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

Приложение

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

Введение

Ряд современных систем защиты информации и обеспечения информационной безопасности базируется на МР-полных Задачах Задачи из класса МР-полных являются, в определенном смысле, «очень сложными» для решения [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 < С, где С - любое положительное вещественное число, не превосходящее 3(log2 7)-1.

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

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

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

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

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

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

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

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

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

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

2011 года;

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

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

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

2012 года;

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

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

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

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

Публикации

Результаты диссертации опубликованы в 9 работах [56-64], из них 5 статей опубликованы в научных журналах, которые включены в перечень российских рецензируемых научных журналов и изданий для опубликования основных научных результатов диссертаций [56,57,59-61], 2 статьи — в научных журналах [58,64] и 2 работы — в трудах международных конференций [62,63].

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

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

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

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

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

Z - кольцо целых чисел;

К - поле действительных чисел;

Мп - ?7-мериое евклидово пространство;

|S| - число элементов в множестве S;

Z/r??Z - кольцо вычетов из т элементов, где натуральное число

т ^ 2;

L0e(bi.....bn) - линейная оболочка векторов Ъ\,..., Ьп\

L1 - ортогональное дополнение к линейному подпространству

L в евклидовом пространстве; у :— х - у присвоить значение х\

(а; Ь) - скалярное произведение векторов а и Ъ\

(а, Ь) - наибольший общий делитель чисел aeZ и b 6Е Z;

(ai...., a„) - вектор размерности щ

(х, mod т) - наименьший неотрицательный остаток от деления числа

х 6 N на число т е N; ||6|| - евклидова норма вектора b;

|a| - модуль числа а Е К;

|_.rj - наибольшее не превосходящее х е Ш целое число:

[ж] - целая часть числа х € Ж;

{ж} - дробная часть числа х € М;

[bi,..., bv] - матрица, в ¿-той строке которой стоят координаты вектора 6¿;

ViU(r, М) - множество инъективных векторов размерности г

с максимальным элементом, равным М; У gin (?"■. М) ~~ множество возрастающих инъективных векторов

размерности г с максимальным элементом, равным М; У yin (г, < М) - множество возрастающих инъективных векторов размерности г. максимальный элемент которых строго меньше М; Vfgir, М) - множество сверхрастущих векторов размерности г

с максимальным элементом, равным М: Vfg(r. < М) - множество сверхрастущих векторов размерности г,

максимальный элемент которых строго меньше М; Рг(а) - вероятность события а:

Рг(а | b) - условная вероятность, вероятность события а.

при условии, что событие b произошло.

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

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

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

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

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

В главе дается подробное описание проведенных автором компьютерных экспериментов по подсчету инъективных и сверхрастущих векторов, представлены результаты соответствующих компьютерных экспериментов (раздел 1.2): в теоремах 1 и 3 (раздел 1.3) автором устанавливаются верхние и нижние границы для числа, возрастающих инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом: в разделе 1.4 предлагается эффективный алгоритм перечисления всех сверхрастущих векторов с фиксированным максимальным элементом в лексикографическом порядке; в разделе 1.5 изучается вопрос о равномерности распределения инъективных векторов, полученных с помощью сильного модульного умножения из сверхрастущих векторов заданной размерности, среди всех инъективных векторов заданной размерности; в разделе 1.6 автором изучается вопрос о монотонности функции Р\(г,М). значение которой в точке (г. М) £ № суть число возрастающих инъективных векторов размерности г с максимальным элементом, равным М.

Изучаемые в этой главе объекты тесно связаны с системой Меркля-Хеллмана. Открытыми ключами в названной системе являются инъектив-иые векторы с натуральными элементами, закрытыми - сверхрастущие век-

торы с натуральными элементами, а в качестве запутывающего преобразования выступает сильное модульное умножение. Общее описание Задачи о рюкзаке (распознавания), Задачи о рюкзаке (вычисления) и системы Меркля-Хеллмана дано в разделе 1.1.

Основные результаты, представленные в этой главе, получены автором и опубликованы в работах [56.58,62,63].

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

Пусть А = {а\. (р>. ■ ■ ■ .аг} - множество, состоящее из натуральных (положительных целых) чисел (множество весов, рюкзачный вектор). Число г - мощность множества весов А - называется размерностью вектора (рюкзака). Для произвольного подмножества. Л* множества А (А* с А) обозначим через 5(.-4*) сумму элементов подмножества А* и назовем ее весом подмножества А*.

Определение 1. Задача о рюкзаке (распознавания). По заданному мноэюеет&у А и числу Б определить, существует ли такое подмиооюе-ство А* С А, что 5(Л*) = 5", то есть существует ли в А подмножество веса 5.

Задача о рюкзаке (распознавания) является ХР-полнон Задачей, что доказал Р. Кари в работе [36]. Это говорит о том. что Задача о рюкзаке (распознавания) представляется достаточно сложной Задачей для того, чтобы стать основой для системы защиты информации. Многие известные на настоящий момент системы защиты базируются на Задачах не более сложных, чем ХР-полные (ПБА, Эль-Гамаля и другие).

Физическая интерпретация Задачи о рюкзаке. Пусть задан набор из г пронумерованных но порядку от 1 до г гирь и контрольный вес 5 £ N. Можно ли набрать с помощью данного набора гирь контрольный вес при условии, что ¿-тая гиря обладает весом а* Е М?

Задачу о рюкзаке (распознавания) можно переформулировать следующим образом.

Условие: Задан вектор (а^ а?,. ■ ■, аг, 5) € М7""1.

Вопрос: Имеет ли уравнение

г

i = 1

где Х[,.... хг - неизвестные, решение в числах 0 и 1.

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

Определение 2. Вектор А = (ai,... ,аг) называется возрастающим, ( соответственно сверхрастуищлг), если и только если условие a¿ > а?-_] (соответственно aj > YjÍ= i a¡) выполняется для всех j, таких что 2 < j ^ г.

Определение 3. Вектор А = (ai,... ,аг) :называется иньективн.ьш, если для любых различных подмножеств А* С А и А** с А, А* ф А** суммы, элемелппов данных подлтожеств будут различны:

S{A**) ф S(A*).

Замечание 1. Для инъективного вектора все его элементы обязательно различны, а задача о рюкзаке имеет не более одного решения.

Утверждение 1. Сверхрасгпущий вектор является инъективнъш [19].

Напомним еще одно важное понятие. Пусть (х, mod т) обозначает наименьший неотрицательный остаток от деления числа х е N на число т е N.

Определение 4. Рассмотрим вектор А = (aj,....ar). целое число т > Yl)=i °"> и "натуральное число 1 < t < т такое, что их наибольший общий делитель (t.m) = 1. Если В = (bi,...,br) - такой вектор, что b¡ = (tai, mod т) для 1 ^ г ^ г. то говорят, что вектор В получен из вектора А с полющыо сильного модульного ултоэюелшя относительно модуля т и лтожителя t.

Утверждение 2. Сальное модульное умножение преобразует сверхрасту-щий вектор в инъективный [19].

В основе системы Меркля-Хеллмана лежит преобразование сверхрасту-щего вектора А = (r¿j. a¿..... ar) (a.j €E N. 1 ^ г ^ г) с помощью сильного модульного умножения относительно модуля т и взанмнопростого с ним множителя 1 < t < т в инъективный вектор В = (Ь\, Ы,.. ., Ьг) (b¿ Е N. 1 ^ г ^ г), служащий в дальнейшем открытым ключом. Следует отметить, что существуют некоторые расхождения в определении интервала., из которого выбирается модуль т. В исходной работе Р. Мерк-ля и М. Хеллмана [40] рассматривался пример с выбором т из интервала (2 Z)í=i 4 Ya=i а»'Ь а в работе А. Шамира [47] т € E=i 2 Y¿=i a¿]-

В 1982 году А. Шамир [47] показал, что система Меркля-Хеллмана не является надежной. Но несмотря на то, что с тех пор эта система стала классической и включена во многие учебные пособия [7.17,19.20], при изложении вопросов, связанных с рюкзачной системой Меркля-Хеллмана, ограничиваются общим описанием принципов ее функционирования и механизма одной из известных атак - либо атаки А. Шамира. либо атаки Лагариаса-Одлыжко. при этом вопрос об изучении свойств сильного модульного умножения. выбранного в качестве запутывающего преобразования в системе Меркля-Хеллмана. не ставится.

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

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

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

Обозначим через У/„(г, М) множество инъективных векторов размерности г с максимальным элементом, равным М; М) ~ множество возрастающих инъективных векторов размерности г с максимальным элементом, равным М; У/д(г. М) - множество сверхрастущих векторов размерности г с максимальным элементом, равным М.

Утверждение 3. |Угп(г, М)| = г! • \Ц1Ш(г. М)\.

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

□

Замечание 2. Из Утверждения 3 следует, что вместо подсчета инъективных векторов размерности г с максимальным элементам, равным М, можно ограничиться подсчетом только возрастающих инъективных векторов, удовлетворяющих этим параметрам.

Утверждение 4. Если вектор А = (ai...., аг_], аг) размерности г > 1 является инъективным. то и вектор (а.],..., а,._i) является ииъективным.

Доказательство. Поскольку вектор А — (ai...., ar_i, а,.) является инъективным, то для всех подмножеств Л* с А и Л** с А, А* ф А** суммы элементов данных подмножеств будут различны. В частности, это условие выполнено и для подмножеств А* С А\{аг} и А** С А\{аг}, поэтому вектор (a-i,.... а г-1) - инъективный.

□

Следствие 1. Если вектор («i,...,ar) размерности г > 1 не является ииъективным, то и вектор («i,... ,аг,... ,cik) размерности к > г ие является инъективным для любых a¡ € N при г + 1 ^ г ^ к.

Утверждение 5. Пусть А — (а¡,.... ar, ar_¡) - возрастающий инъективный вектор размерности г + 1 > 1 и ar+i = М, тогда a¡ < М — г + г для всех 1 ^ i ^ г.

Доказательство. Вначале заметим, что элементы .... аг. ввиду того, что вектор А является возрастающим, могут принимать значения только из интервала [а,- + 1 ,М — 1]. Теперь предположим противное: пусть а,- ^ М — г + г. тогда на интервале [a¿ + 1 ,М — 1] существует не более г — г — 1 различных натуральных чисел, а элементов должно найтись г — г. следовательно, некоторые из них совпадут, что противоречит ипъективностп вектора А.

□

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

Предлагаемый автором алгоритм подсчета возрастающих инъективных векторов размерности г + 1 с фиксированным максимальным элементом ar_i = М состоит из двух блоков.

Первый блок алгоритма реализует r-разрядный счетчик по элементам ai.....аг. Если инициализация алгоритма осуществляется вектором

(ai... ...ak). то первый блок алгоритма отвечает за последовательное .увеличение на единицу до тех пор, пока значение не достигнет М — r + k (по утверждению 5 М — г + к является предельным значением элемента при 1 ^ к ^ г), после чего при к > 1 происходит увеличение на единицу элемента а элемент a.¡¿ переинициализируется значением a¿_i + 1. а

при к = 1 алгоритм заканчивает работу. Далее процедура повторяется до достижения элементом a;,._i значения М — г 4- к — 1 и так далее.

Второй блок отвечает за проверку вектора {а\,.... ак) на ипъективпость. Ввиду следствия 1 при каждом изменении элемента о./,: необходимо убедиться. что вектор (ai....,cik) является инъективным, поскольку в противном случае любой построенный вектор (а1;..., о,/г. ь .... aT+i) не будет инъективным и не будет влиять на результаты подсчета, поэтому в его построении нет необходимости. Если вектор (а\,... ,а,оказался неииъективным. необходимо увеличить о/, на 1 и повторить процедуру проверки на инъек-тнвность. Этот процесс необходимо продолжать до тех пор. пока (аь ..., а.к) не станет инъективным или не достигнет значения М — г + к. Если установлено. что вектор (о.] ,.... а/-) - инъективный, то переходим к элементу cik-\. инициализируем его значением + 1 и будем добиваться инъектив-ности вектора (ai;...; a/t-i) описанным выше способом. Если проверку на инъективность проходит вектор (а\,... ,ат), то проверяется на инъектив-иость вектор (ai,... ,ar, М), и если он оказывается инъективным, то счетчик возрастающих инъективных векторов размерности г + 1 с фиксированным максимальным элементом, равным М, увеличивается на 1.

Проверка ипъективности вектора осуществляется с иомощыо следующей процедуры. Пусть (ai,.... о./,._] ) - инъективный вектор, и все возможные 2к~1 — 1 значения (за исключением 0) суммы Y^j=\eiaj- где ej е {ОД} для всех 1 ^ j ^ к — 1. записаны в целочисленный массив SUMS[A: — 1] в порядке возрастания. Необходимо проверить, является ли инъективным вектор (ai,...,«/,.). Сформируем новый массив SUMS[/;:] размерности 2к — 1 следующим образом: начальные 2fc_1 — 1 элементов массива SUMS [/с] - это элементы массива SUMS [к — 1], элементом массива SUMS [/с] под номером 2к~1 становится ак, а оставшиеся элементы представляют собой суммы a/f и каждого из 2к~1 — 1 элементов массива SUMS [А; — 1]. Таким образом, в массиве SUMS [А:] оказываются записанными все возможные 2к — 1 значения (за исключением 0) суммы ej°1- где e:i е 1} Для всех 1 ^ j ^ к, причем для первых 2А'~1 — 1 элементов массива SUMS[fc] = 0, а для остальных

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

Основные результаты, представленные в этой главе, опубликованы автором в работах [57,59.60,64].

Заключение

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

Возможным развитием метода получения верхней оценки для числа сверхрастущих и инъектнвиых векторов, элементы которых являются натуральными числами, с заданными размерностью и максимальным элементом, изложенного в первой главе диссертационной работы, может являться его расширение на случай обобщенных инъективных векторов, то есть таких векторов (г/1.а,), а, £ М, 1 ^ г < г. для которых существует не более одного решения Обобщенной Задачи о рюкзаке, заданной значениями ач е N. К К г. и некоторым числом 5 Е N при фиксированном значении т ^ 3.

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

ЗР = чТ<(Ш08 и Ч7<0.9408 . и ^>0.9408. • где Озр - Задача о рюкзаке, ^|<09/]08 - множество задач о рюкзаках, плотность которых удовлетворяет неравенству с/ < 0,9408. верно решаемых с помощью алгоритма «Оракул» (алгоритм выдает на них верный ответ), Ч7Оракул» (алгоритм выдаст на них ответ, по он не является верным). и-'^0.9408. - множество задач о рюкзаках, плотность которых удовлетворяет неравенству (I ^ 0,9408. Пусть эо сю

Ч1<0.9408. = ^/<0.9408 .: Ч*<0.9408 = Ы ^'г (/<0.9408. .'< г=1 г=1 где в множества Шг г/<0 9408 С Ц/"<0.си08 • ^/<0.9408 С Ч/<0.9408 входят все задачи о рюкзаках, размерность вектора которых равна г.

Теорией Лагариаса-Одлыжко устанавливается, что

1Чу/<0.9408.1 ^ г-к5с \и) ,'

•/<0.9408. при этом поведение метода на множестве с*Л/>о.9-Ш8.> теорией не рассматривается.

В третьей главе диссертационной работы установлено, что Задача о рюкзаке (распознавания) может быть полиномиально трансформирована во множество задач о рюкзаках (распознавания), плотность которых с?зр < С, где С - любое положительное вещественное число, не превосходящее 3(1с^-> Т)"1. Таким образом, показано, что у каждой задачи о рюкзаке из множества с^о.9408.; имеется полиномиально эквивалентная ей задача о рюкзаке из множества о;{|<0 Э408 и с^<0 9408 . Поэтому можно ограничиться рассмотрением множества

Теперь, если образ Задачи трансформируемой в Задачу о рюкзаке равномерно покроет множество ^<0.9408. или более плотно множество Ц/<0 9408 то в силу (16) алгоритм «Оракул» выдаст верный ответ на «практически все» задачи - индивидуальные представители трансформируемой Задачи, если же образ трансформируемой Задачи более плотно покроет множество Ч7<0 9408 ' т0 Д°ля задач, на которую алгоритм «Оракул» выдаст верный ответ, будет существенно зависеть от степени плотности.

Тот факт, что с помощью алгоритма «Оракул» можно решать многие задачи - индивидуальные представители ХР-полных Задач (теорема 15). может служить предпосылкой к тому, что детерминированного алгоритма «Оракул», выдающего один из кратчайших векторов решеток, описанных в диссертационной работе видов (А] - Л5) за полиномиальное время, скорее всего не существует. Однако результаты экспериментов но применению IX Ъ-решателя к решению задач о рюкзаках (рисунки 18 и 19) выглядят более сильными по сравнению с предсказаниями, основанными на теории Лагариаса-Одлыжко (теорема 10). Поэтому представляет интерес дальнейшее уточнение множества значений плотности задач о рюкзаках такого, что ЫХ-решатель позволит решить асимптотически большую часть задач о рюкзаках, обладающих плотностью из этого множества. Кроме того, поскольку метод Лагариаса-Одлыжко предполагает поиск «достаточно короткого», а не кратчайшего вектора решетки, то ЫХ-решатель теоретически может работать для определенных подмножеств задач о рюкзаках лучше.

0.9408. — Ч!

•/<0.9408. и Ч/<0.9408." чем алгоритм «Оракул». С этой точки зрения, принципиально важной представляется задача аналитического описания множества задач о рюкзаках, разрешимых с помощью ЫХ-решателя.

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

Список литературы диссертационного исследования кандидат физико-математических наук Мурин, Дмитрий Михайлович, 2013 год

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

1. The LLL Algorithm. Survey and Applications / Editor P. Nguyen, B. Vallée.

— Springer Publishing Company, Incorporated, NY, 2009. — 496 p.

2. Bishop, M. Computer security: Art and science / M. Bishop. — Addison Wesley, 2002. - 1136 p.

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

4. Hardy, G. An Introduction to the Theory of Numbers / G. Hardy, E. Wright.

— Oxford: Oxford University Press, 1975. — 421 p.

5. Sloane, N. J. A. The Encyclopedia of Integer Sequences / N. J. A. Sloane, S. Plouffe. - Academic Press, 1995. - 587 p.

6. Математическая энциклопедия / Ред. И. M. Виноградов. — M.: Советская энциклопедия, 1977. — ТЗ. — С. 537.

7. Алферов, А. П. Основы криптографии: Учебное пособие / А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. — М.: Гелиос АРВ, 2005.

— 480 с.

8. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. — М.: Мир, 1979. — 536 с.

9. Василенко, О. Н. Теоретико-числовые алгоритмы в криптографии / О. Н. Василенко. - М.: МЦНМО, 2006. - 336 с.

10. Гельфанд, И. М. Лекции по линейной алгебре / И. М. Гельфанд. — М.: Добросвет, КДУ, 2006. - С. 44-51.

11. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. — М.: Мир, 1982. — 416 с.

12. Касселс, Дж. Введение в геометрию чисел / Дж. Касселс. — М.: Мир, 1965. - 422 с.

13. Кнудт, Д. Е. Искусство программирования: в 3 томах / Д. Е. Кнудт. — М.: Издательский дом «Вильяме», 2008. — Том 1. — С. 73 и 535.

14. Копсон, Э. Т. Наглядная геометрия / Э. Т. Копсон, Д. Гильберт,

С. Э. Кон-Фоссен. - М.-Л.: ОНТИ, 1936. - 304 с.

15. Копсон, Э.Т. Асимптотические разложения / Э.Т. Копсон. — М.: Мир, 1966. - 159 с.

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

17. Маховенко, Е. Б. Теоретико-числовые методы в криптографии / Е. Б. Маховенко. - М.: Гелиос АРВ, 2006. - 320 с.

18. Пападимитриу, X. Комбинаторная оптимизация. Алгоритмы и сложность / X. Пападимитриу, К. Стайглиц. — М.: Мир, 1984. — 510 с.

19. Саломаа, А. Криптография с открытым ключом / А. Саломаа. — М.: Мир, 1995. - 318 с.

20. Смарт, Н. Криптография / Н. Смарт. — М.: Техносфера, 2006. — 528 с.

21. Фихтенгольц, Г. М. Курс дифференциального и интегрального исчисления: в 3 томах / Г. М. Фихтенгольц. - М.: ФИЗМАТЛИТ, 2001. — Том 2.

- С. 371.

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

23. Boas, P. Another NP-complete problem and the complexity of computing short vectors in a lattice / P. Boas // Tech. rep., University of Amsterdam, Department of Mathematics, Netherlands. — Technical Report 8104. — 1981.

- Юр.

24. Brickell, E. F. The cryptanalysis of knapsack cryptosystems / E. F. Brickell // Applications of Discrete Mathematics, R. D. Ringeisen and F. S. Roberts, eds. - SIAM (1988). - p. 3-23.

25. Brickell, E. F. Solving Low-Density Knapsacks / E. F. Brickell // Advances in Cryptology, Proceedings of Crypto 83, Plenun Press. — 1984. — p. 25-37.

26. Chevalier, Y. An NP Decision Procedure for Protocol Insecurity with XOR / Y. Chevalier, R. Kiisters, M. Rusinowitch, M. Turuani // Rapport de recherche, INRIA. - 2003. - №4697. - 22 p.

27. Chetcuti-Sperandio, N. How to ChooseWeightings to Avoid Collisions in a

Restricted Penalty Logic / N. Chetcuti-Sperandio, S. Lagrue // Principles

of Knowledge Representation and Reasoning: Proceedings of the Eleventh

International Conference, KR 2008. Sydney: AAAI Press. - 2008. - p. 340347.

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

29. Cook, S. A. The complexity of theorem-proving prcedures / S. A. Cook // Proc. 3rd Ann. ACM Symp. on Theory of Computing. — 1971. — p. 151-158.

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

31. Davis, M. A computing procedure for quantification theory / M. Davis, H. Putnam // Journal of the ACM. - 1960. - №7. - p. 201-215.

32. Davis, M. A Machine Program for Theorem Proving / M. Davis, G. Logemann, D. Loveland // Communications of the ACM. — 1962. — №5 (7). - p. 394-397.

33. Goodman, R. A new trapdoor knapsack public-key cryptosystem / R. Goodman, A. McAuley // IEE PROCEEDINGS. - 1985. - Vol. 132, №6.

- p.289-292.

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

35. Hardy, G. Some problems of partitio numerorum, III: On the expression of a number as a sum of primes / G. Hardy, J. Littlewood // Acta Math. 44. — 1923. - №1. - p. 1—70.

36. Karp, R. M. Reducibility among combinatorial problems / R. M. Karp // Complexity of Computer Computations: Proc. of a Symp. on the Complexity of Computer Computations, The IBM Research Symposia Series. — 1972. — p.85-103.

37. Kreweras, G. Sur quelques problemes relatifs au vote pondere [Some

problems of weighted voting] / G. Kreweras // Math. Sci. Humaines. — 1983.

- № 84. - p. 45-63.

38. Lenstra, A. K. Factoring Polynomials with Rational Coefficients / A. K. Lenstra, H.W. Lenstra, L. Lovasz // Mathematlsche Annalen 261. — 1982. - p. 515-534.

39. Mazo, J. E. Lattice points in high-dimensional spheres / J. E. Mazo, A.M. Odlyzko // Monatsh. Math. - 1990. - №110. - p.47-61.

40. Merkle, R. Hiding information and signature in trapdoor knapsacks / R. Merkle, M. Hellman // IEEE Transaction on Information Theory, IT-24-5, September. - 1978. - p. 525-530.

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

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

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

44. Rodriguez, A. .Étude des propriétés d'une suite numérique liée à un problème de vote pondéré / A. Rodriguez // Thèse de docteur-ingénieur, Université Pierre et Marie Curie. 1983.

45. Rusinowitch, M. Protocol Insecurity with a Finite Number of Sessions and Composed Keys is NP-complete / M. Rusinowitch, M. Turuani // Theoretical Computer Science. - 2003. — p. 174-190.

46. Shamir, A. On the Cryptocomplexity of Knapsack Systems / A. Shamir // Proceedings of the 11th ACM Symposium on the Theory of Computing. — 1979. - p. 118-129.

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

48. Stern, M. A. Aufgaben / M. A. Stern // J. Reine Angew. Math. — 1838. — №18. - p. 100.

49. Виноградов, И. М. Some theorems concerning the theory of primes / И. M. Виноградов // Математический сборник. — 1937. — Т. 2(44), №2.

- С. 179-195.

50. Заикин, О.С. Параллельная технология решения SAT-задач и ее реализация в виде пакета прикладных программ: автореф. дис. ... канд. тех. наук: 05.13.01 / Заикин Олег Сергеевич. — Томск, 2009. — 19 с.

51. Котенко, Д. И. Методы и средства моделирования атак в больших компьютерных сетях: состояние проблемы / Д. И. Котенко, И. В. Котенко, И. Б. Саенко // Труды СПИИРАН. СПб.: Наука. - 2012. - Вып. 3(22).

- С. 5-30.

52. Николенко, С. И. Криптография и решетки [Электронный ресурс] / С. И. Николенко // Computer Science клуб. — 2009. — Режим доступа: http://logic.pdmi.ras.ru/~sergey/teaehing/cscryp09/05-lattices.pdf.

53. Осипян, В. О. О криптосистемах с заданным рюкзаком / В. О. Осипян // Материалы VI Международной научно-практической конференции «Информационная безопасность» Таганрог: Изд-во ТРТУ. — 2004. — С. 269271.

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

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

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

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

58. Мурин, Д. М. О порядке роста числа инъективных и сверхрастущих векторов и некоторых особенностях сильного модульного умножения /

Д. М. Мурин // Прикладная дискретная математика. Приложение. — 2012. - №5. - С. 19-21.

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

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

- С. 117-124.

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

- С. 91-100.

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

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

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

\