аспирант Мирзаян А.В.

Использование параметрических решений систем многостепенных диофантовых уравнений при моделировании односторонних отображений на основе задачи о рюкзаке

Кубанский государственный университет, Россия

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

Рассмотрим классическую задачу о рюкзаке [1].

Задача KS. Пусть имеется набор из n предметов с заданными объёмами Ai, i = 1..n , а также рюкзак объемом V,  и необходимо найти такой набор предметов, чтобы полностью заполнить рюкзак.

Математическая модель этой задачи выглядит следующим образом:

А = ( а 1 , а 2 , ... , а n )

– рюкзачный вектор размерности n, n³ 3 из n различных натуральных компонентов а I , I = 1. . n и  (A,V) – вход задачи о рюкзаке, где V также некоторое натуральное число.

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

Рассмотрим специальный класс рюкзачных векторов. Рюкзачный вектор A называется сверхрастущим, если

, j=2..n.

Приведём без доказательства 2 леммы, которые будем использовать в дальнейшем. Доказательства лемм есть в работах [1] [2] [3].

Лемма 1. Рюкзачный вектор A=(а1, . .,аn) размерности n (n≥3) является инъективным, если он сверхрастущий.

Лемма 2. Задача KS для сверхрастущего рюкзачного вектора AS имеет алгоритм решения, линейный относительно n – длины рюкзачного вектора AS.

Таким образом, все системы защиты информации на основе проблемы о рюкзаке сводятся преобразованию открытого текста с помощью сверхрастущего вектора с последующим применением к самому вектору и полученному тексту некоторого отображения (функция взбалтывания [1]) для передачи по открытому каналу связи. Авторами первой такой системы - Меркле и Хеллманом - было предложение в качестве функции взбалтывания сильное модульное умножение. Однако в последствии эта функция оказалась слабым местом системы. Таким образом, выбор подходящей труднорешаемой задачи, в частности, NP-полной задачи, позволяет смоделировать систему защиты информации на должном уровне. Особенно, если этот выбор, как отмечал К. Шеннон, связан с задачей, которая содержит диофантовые трудности [4].

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

Пусть запись

                                    (1)

означает многостепенную систему диофантовых уравнений m-ой степени вида:

x1 l + x2 l +. . . + xn l = y1 l + y2 l +. . . + yn l или XY, l = 1 . . m.

Многостепенная система вида

называется почти идеальной, а система вида

                       (2)

идеальной или нормальной системой m-ой степени.

Пусть имеем также параметрическое решение многостепенной системы диофантовых уравнений m-й степени (1) в виде xi = xi(a, b, ..., c), yi = yi(a, b, ..., c), где a, b, ..., c, xi, yi ÎN, i=1..n. Для простоты изложения на протяжении всего раздела будем считать, что каждое параметрическое решение

      (3)

уравнения (1) содержат всего два параметра a и b: ai = ai(a, b), bi = bi(a, b),     i = 1. . n из которых можно получить целые взаимно простые решения, в частности, в натуральных числах a1, a2, ..., an, b1, b2,..., bn. В дальнейшем нас будут интересовать только решения системы (1) в натуральных числах.

Для случая n = 4, m= 5 приведём двухпараметрическое решение нормальной многостепенной системы диофантовых уравнений 4-ой степени:

19a + b, 15a + 5b, 11a + 9b, 3a + 17b, 2a + 18b  a + 19b, 5a + 15b,

9a +11b, 17a + 3b, 18a + 2b.

Сопоставим каждому решению (3) системы (2) два рюкзака

А = (а1 , а2 , ... , аm) и B = (b1, b2, ... , bm).

числовые рюкзаки А и B размерности m ≥ 3 будем называть равносильными между собой, имеющими степень n, если компоненты А и B являются решениями диофантового уравнения (1). Этот факт будем записывать следующим образом:

AB или (а1, а2, ..., аm)(b1, b2, ..., bm).                  (4)

  Очевидно, введённое бинарное отношение (4) обладает свойства:

1.     AA (рефлексивность);

2.     Если AB, то BA (симметричность);

3.     Если AB, BC, то AС (транзитивность).

 

Так, например, следующие двухпараметрические рюкзаки размерности m = 5 равносильны между собой, и имеют степень n = 4:

(19a + b, 15a + 5b, 11a + 9b, 3a + 17b, 2a + 18b)(a + 19b, 5a + 15b, 9a + 11b, 17a + 3b, 18a + 2b).

Из этого соотношения можно получить сколь угодно много равносильных числовых рюкзаков степени n = 4, придав параметрам a и b различные натуральные значения. Причём, можно подобрать a и b таким образом, чтобы один или оба числовых рюкзака степени n были инъективными. Так, например, при a = 3, b = 9 имеем следующие числовые рюкзаки степени n = 4:

(66, 90, 60, 162, 168)  (174, 150, 126, 78, 72).

Теорема Фролова  Пусть

a, b – произвольные целые числа, тогда

Если при этом a ≠ 0, то, наоборот, из (В) следует (А).

Теорема Обобщённая теорема Фролова. Пусть

                                                                                (9)

– какое-либо решение многостепенной системы диофантовых уравнений m-й степени (1)  

и

где числа r и l пробегают все без исключения натуральные числа в следующих границах 1≤ r ≤ k–1, 2r+1 ≤ l ≤ m (m = 2k или m = 2k–1), a и b – произвольные целые числа, отличные от нуля и не равные между собой. Тогда

aa1 + bb1, aa2 + bb2, …, aan + bbn ba1 + ab1, ba2 + ab2, . . ., ban + abn   (10)

также является решением этой системы, или что тоже самое: если AB, то aA+bBbA+aB.      

Теорема Тарри. Пусть

и h – произвольное число, тогда

Доказательство

Доказывается раскрытием скобок, используя формулу бинома Ньютона.

Перейдём непосредственно к построению искомого одностороннего отображения.

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

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

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

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

К решению  AB применим обобщённую теорему Фролова с коэффициентами a и b и получим решение aA+bBbA+aB (CD).

Передаём по открытому каналу связи нормальный вектор С (или D) и преобразованный текст.

В построенном таким образом отображении секретной лазейкой являются коэффициенты a и b. Обратное преобразование производится путём решения системы линейных уравнений: по вектору C и коэффициентам a и b получаем систему уравнений

aai + bbi=ci i=1..n

ba1 + ab1 +...+ ban + abn  c1+....+cn

из которой находим сверхрастущий рюкзачный вектор A и далее производим обратное преобразование переданного текста (лемма 2).

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

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

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

1. Саломаа А. Криптография с открытым ключом. Мир : Москва, 1995.

2. Мирзаян А. В. Модели систам защиты информации на основе универсального и функционального рюкзака. б.н. : Краснодар, 2005.

3. Мирзаян А. В. Математическая модель изоморфных рюкзачных систем безопасной передачи информации. Вопросы безопасной передачи информации : Москва, 2010.

4. Шеннон К. Теория связи в секретных системах. Работы по теории информации и кибернетике : Москва, 1963.

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

6. Осипян В. О. Решение в целых числах некоторых диофантовых и систем диофантовых уравнений. КубГУ : Краснодар, 1979.