X Международная студенческая научная конференция Студенческий научный форум - 2018

Задача о рюкзаке – одна из задач комбинаторной оптимизации. Задачи о загрузке (о рюкзаке) и её модификации часто возникают в экономике, прикладной математике, криптографии, логистике и генетике. Например, у человека есть рюкзак объёмом V, с которым ему надо отправится в долгое путешествие. Также имеется большое количество предметов (p – штук) объёмом v_i, i=0, … , p – 1, которое можно положить в рюкзак. Представим, что человек хороший упаковщик и может заполнить рюкзак, не оставляя в нем свободного места. Чтобы взять максимально возможный груз, сначала нужно определить комплекс предметов, который полностью заполнит рюкзак. Иными словами, требуется найти подмножество I  {1, … , p}, что _iI v_i = V, если, конечно, оно существует. Это общая задача о рюкзаке. Затем предполагаем, что V и все v_i являются натуральными числами. В таком случае, задача может быть поставлена в следующей форме.

Пусть задано множество {v_i} из p натуральных чисел и целое число V. Нужно найти такое p-разрядное двоичное число n = (ep_-1 ep_-2 … e₁e₀₎₂ (где e₁  {0,1} суть значения разрядов в двоичной записи числа n), что _i=0p^-1 e_iv_i = V, если, конечно, такое n существует.

Нужно обратить внимание на то, что, в зависимости от значений набора {v_i} и числа V, решения может и не быть вовсе, решений может быть несколько или оно будет единственным.

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

Пример 1. Набор {1,2,6,13,27} является быстрорастущим.

Вообще известно, что задача о рюкзаке относится к типу очень трудных задач, которые называют «NP-полными задачами». Это значит, что она равноценна по сложности «задаче о коммивояжере». В частности, если верна основная гипотеза теории сложности, в этом уверенно множество специалистов, то не существует такого алгоритма, который бы решал произвольную задачу о рюкзаке за время, полиномиальное по p и по log B, где B – граница для значений V и v_i.

Впрочем, задача о рюкзаке с быстрорастущим набором несравненно легче. Просмотрим (упорядоченный по убыванию) список v_i, начиная с наибольшего, до тех пор, пока не найдем первый элемент, который не превосходит V. Это значение i мы включим в множество I (т.е. положим e_i = 1), заменим V на V – v_iи продолжим просмотр списка v_i по убыванию, пока опять не найдем элемент, не превосходящий эту разность. Продолжая так действовать, мы построим подмножество элементов v_i, в сумме равных V, или же используем все элементы v_i, не доведя разность V - _iIv_iдо нуля, что будет в случае, когда задача не имеет решения.

Пример 2. Пусть v_i = {2,3,7,15,31}, а V = 24. Тогда, проходя пятерку {2,3,7,15,31} справа налево, мы видим, что e₄ = 0, e₃ = 1 (мы заменяем 24 на 24 – 15 = 9), e₂ = 1 (заменяем 9 на 9 – 7 = 2), e₁ = 1. Следовательно, n = (01101)₂ = 13.

Чтобы построить рюкзачную криптосистему (её еще называют системой Меркля-Хеллмана), сначала нужно предположить, что элементы открытого текста имеют в качестве своих числовых подобий p-разрядные двоичные числа K.

Дальше пользователь выбирает быстрорастущий набор {v₀, … , vp_-1), целое число m, большее v₀ + … + v_k-1, и взаимно простое с m целое число a, . Всё это проводится благодаря случайной процедуре.

Любой желающий может передать сообщение K = (ep_-1, … , e₁, e₀) пользователю с ключом шифрования {w_i} вычисляет С = f (K) =  _i=0^k-1 e_iw_iи передает это целое число.

Для того, чтобы прочитать это сообщение, пользователю сначала нужно найти наименьший положительный вычет V числа bC по модулю m. Так как bC   e_ibw_i  e_iv_i. Этим алгоритмом можно использовать для задачи о рюкзаке с быстрорастущим набором и найти единственное решение задачи о подмножестве с суммой, равной V.

Какое-то время специалисты очень хорошо оценивали потенциал рюкзачных криптосистем. Если задача относится к типу трудных задач, то, они считали, что система должна быть надежна.

Но все же в этих суждениях была ошибка. Вызываемые такими системами задачи о рюкзаке C =  e_iw_i, хотя они и не соответствуют быстрорастущим наборам, но имеют специфический тип, а именно, получаются из задач с быстрорастущим набором простых преобразованием: умножением всех величин на a и привидением по модулю m. В 1982 году Шамир нашел полиномиальный по p алгоритм решения задач о рюкзаке такого типа. Поэтому такая криптосистема не может считаться надежной криптосистемой с открытым ключом.

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

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

Представим, что Алиса хочет принимать сообщения в форме наборов из p битов e₀, …, ep_-1. Её открытым ключом является последовательность натуральных чисел v₀, …, vp_-1. Но теперь Боб должен посылать ей не только целое число с =  e_jv_j, но и сумму разрядов с’ =  e_j.

Алиса строит последовательность v_jследующим способом. Выбор всех параметров, которые упоминаются в этом абзаце, можно делать секретным образом, так как Бобу для посылки сообщения необходим лишь итоговый набор v₀, …, vp_-1. Сначала Алиса выбирает такую степень простого q=p^f, что q – 1 не имеет больших простых делителей, причем, как и p, так и f имеют умеренные значения. Так, в работе Чора и Райвеста 1988 году рассматривалась величина q = 197²⁴. Дальше Алиса выбирает нормированный неразложимый многочлен F(X)  Fp[X] степени f, так что F_q может рассматриваться как Fp[X]/F[X]. Она выбирает также образующий элемент g в F^*_qи целое число z. Алиса производит выбор F, g, и z каким-нибудь случайным образом.

Пусть i  F_q= Fp[X]/F(X) обозначает класс вычетов, содержащих X. Алиса выбирает в качестве k любое целое число, меньше p и f одновременно. Для j = 0, …, k – 1 она вычисляет такие неотрицательные целые b=q–1, что g^bj= t+j. И вот, Алиса делает случайную перестановку  элементов множества {0, …, k-1} и полагает v_jравным наименьшему неотрицательному вычету b_(j)+z по модулю q–1. Она объявляет (v₀, …, v_k-1) своим открытым ключом.

Расшифрование происходит следующим образом. После того, как Алиса получила от Боба c и c’, она для начала вычисляет элемент g^c-ze’, который единственным образом представляется в виде многочлена G(X)  Fp[X] степени ниже f. Но Алиса знает, что этот элемент также равен Пq^eib(j)= П(t+(j))^ej, что соответствует многочлену П(X+(j))^ej. Так как многочлены G(X) и П(X+(j))^ejимеют степень ниже f и представляют собой один и тот же элемент по модулю F(X), должно выполняться равенство

G(X) = П(x+(j))^ej.

Теперь Алиса может найти величины e_j, деля G(X) на множители.

Список используемых источников

Коблиц, Н. Курс теории чисел и криптографии [Электронный ресурс] – Режим доступа: http://bookre.org/reader?file=437457&pg=268

Код для цитирования: Скопировать