Задача о рюкзаке в криптографии

Для некоторых векторов Α задача о рюкзаке легко решаема. Этим свойством обладают сверхрастущие векторы[2].

Def. Рюкзачный вектор ${\displaystyle A=(a_{1},...,a_{n})}$ называется сверхрастущим, если ${\displaystyle \sum _{i=1}^{j-1}a_{i}<a_{j}}$ для ${\displaystyle j=2,...,n}$, т.е каждый член последовательности больше суммы предыдущих[18].

Пример

Пусть полный вес рюкзака ${\displaystyle P=70}$, а рюкзачный вектор задан как сверхрастущий ${\displaystyle A=(2,3,6,13,27,52)}$.

Для этого рюкзачного вектора алгоритм решения задачи о ранце прост. Берется самый большой вес, 52. Так как 52 < 70, то соответствующий предмет помещается в рюкзак. Свободное место в рюкзаке стало равным 70 — 52 = 18-ти. Далее берем предмет с весом 27. Так как 27 > 18, то в рюкзак этот предмет не войдёт. Третий предмет с весом 13 < 18 поместится в рюкзак, а свободного места останется 5. Следующий предмет с весом 6 не поместится. Аналогично предметы с весами 2 и 3 помещаются в рюкзак. Остаточный вес рюкзака стал 0, решение найдено!

Нормальный рюкзак — не со сверхвозрастающим рюкзачным вектором A. Единственный способ решения такой задачи — это проверка всех возможных, пока не найдётся правильное решение. Самый быстрый алгоритм имеет экспоненциальную зависимость от числа предметов[2].

Для целых ${\displaystyle x}$ и ${\displaystyle m\geq 2}$ обозначим ${\displaystyle (x,modm)=x-[x/m]m}$.

Пусть ${\displaystyle A=(a_{1},...,a_{n})}$ — сверхвозрастающий рюкзачный вектор. Введем целое число ${\displaystyle m>\sum _{i=1}^{n}a_{i}}$ и натуральное число ${\displaystyle t<m}$, такое что наибольший общий делитель ${\displaystyle (t,m)=1}$.

Def. Если ${\displaystyle B=(b_{1},...,b_{n})}$ такое, что ${\displaystyle b_{i}=(ta_{i},modm)}$ для ${\displaystyle i=1,..,n}$, то говорят, что ${\displaystyle B}$ получен из ${\displaystyle A}$ сильным модульным умножением[18].

Создатель криптосистемы выбирает параметры ${\displaystyle A,B,t,m}$ так, чтобы A был сверхрастущим, а B получался из A сильным модульным умножением относительно m и t.

Справедлива Лемма[19]: Пусть A — сверхрастущий вектор, а B получен из A сильным модульным умножением относительно m и t. Предположим, что u = 1/t, β — произвольное натуральное число и α =(uβ,modm). Тогда справедливо, что:

1. Задача о рюкзаке с входными данными (A,α) разрешима за линейное время, и если решение существует, то оно единственно;
2. Задача о рюкзаке с входными данными (B,β) имеет не более одного решения;
3. Если существует решение для входа (B,β), то оно совпадает с единственным решением для входа (A,α).

Пример

Создание вектора B из вектора A[18].

Пусть задан сверхрастущий вектор ${\displaystyle A=(103,107,211,430,863,1718,3449,6907,13807,27610)}$ (секретный ключ) с ${\displaystyle n=10}$. Сумма его компонент равна 55 205. Выбираем ${\displaystyle m=55207}$, а ${\displaystyle t=25236}$. Тогда условие ${\displaystyle (t,m)=1}$ выполнено.

Находится ${\displaystyle t^{-1}modm}$ по формуле ${\displaystyle (tu)modm=1}$. В данном случае:

1061 * 25 236 — 1= 485 * 55 207

Следовательно ${\displaystyle t^{-1}=u=1061}$.

Вычисляется открытый ключ B по ${\displaystyle b_{i}=(ta_{i},modm)}$ и α =(uβ,modm). Например, для ${\displaystyle a_{1},a_{6},a_{10}}$

${\displaystyle b_{1}=103*25236=4579+47*55207=4579}$ и α1 = 1061 * 4579 = 103 + 88 * 55 207 = 103,

${\displaystyle b_{6}=1718*25236=17953+785*55207=17953}$ и α6 = 1061 * 17 953 = 1718 + 345 * 55 207 = 1718,

${\displaystyle b_{10}=27610*25236=53620+12620*55207=53620}$ и α10 = 1061 * 53 620 = 27 610 + 1030 * 55 207 = 27 610

Сделав аналогичные вычисления для остальных элементов получается вектор ${\displaystyle B=(4579,50316,24924,30908,27110,17953,32732,16553,22075,53620)}$

Шифрование

Применим открытый ключ B и зашифруем сообщение: DEATH GODS EAT ONLY APPLES

Вначале используется цифровое кодирование, пробелу присваивается значение 0, буквам от A до Z — значение от 1 до 26. Цифровые коды выражаются двоичными наборами. Так как вектор B имеет длину 10, то может быть использован для шифрования блоков сразу из двух букв. Шифр блока, как и раньше, получается суммированием весов предметов ${\displaystyle b_{i}}$ вошедших в рюкзак.

Расшифровка

Расшифруем первое число 95 097. Стоит отметить, что

1061* 95 097 = 1827 * 55 207 + 34 728

Рассматривается задача о ранце (A,34728). Решение получается просмотром рюкзачного вектора A справа налево. Когда число в левом столбце становится не меньше текущей просматриваемой компоненты A, пишется 1, а новое число в левом столбце получается вычитанием компоненты из предыдущего числа. В противном случаем пишется 0 и число в левом столбце не меняется. Результат приведён в таблице:

Считыванием правой колонки снизу вверх получается двоичный вектор 00100 00101,то есть DE.

Предположим, мы попытались действовать в обратном порядке. Шифрование осуществлялось бы с помощью вектора A и получалось некое число a. Но тогда пара (B,a) не обладала решением, так как нельзя вывести обычное равенство чисел из их равенства по модулю.

Для небольших рюкзачных векторов, задачу о ранце легко решить даже вручную. Реальный рюкзак должен содержать большое число элементов. Вскрытие такого рюкзака при помощи грубой силы, т.е перебором, будет трудной (невозможной) задачей. Однако рюкзачные системы не являются безопасными для криптоанализа . Шамир и Циппел (англ. Zippel) обнаружили, что зная числа ${\displaystyle t,t^{-1},m}$(«секретную лазейку») можно восстановить сверхвозрастающий вектор ${\displaystyle A}$ по нормальному открытому вектору ${\displaystyle B}$[3]. Важно то, что числа ${\displaystyle t,m}$ («секретная пара») не обязательно должны быть теми же, что использовались при создании системы легальным пользователем. Достаточно найти любую пару ${\displaystyle (t',m')}$, такую что ${\displaystyle B*(t'modm')}$ даст нам сверхрастущий вектор[20].

Задача: известен рюкзачный вектор ${\displaystyle B=(b_{1},...,b_{n})}$, используемый в качестве открытого ключа. Он получен из A — сверхвозрастающего вектора, сильным модульным умножением относительно модуля m и числа t. Нужно найти не известные нам A,t, m, а точнее m и ${\displaystyle t^{-1}=u}$ (по ним можно вычислить A). Зная их, можно расшифровать криптотекст[21].

Нахождение секретной пары

Описанный ниже подход был предложен А.Шамиром. Получаемый алгоритм будет работать за полиномиальное время. Однако следует быть осторожными в выборе размера вектора B, относительно которого алгоритм является полиномиальным. Стоит помнить, что размер вектора B зависит от числа компонент n и размеров ${\displaystyle b_{i}}$. Следовательно существуют ограничение на их выбор

Фиксируем константу пропорциональности ${\displaystyle d>1}$, и ${\displaystyle a_{i},i=[1,n]}$ компоненты сверхрастущего вектора A, состоящие из ${\displaystyle [dn]-1-n+i}$ битов. Так как старший разряд в каждой из компонент единица, то A сверхрастущий и m выбрано превосходящим по величине сумму компонент рюкзачного вектора A[20].

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

Для наглядности построим графики функций ${\displaystyle b_{i}u}$ ${\displaystyle (modm)}$. Это прямолинейные отрезки с точками разрыва ${\displaystyle u=pm/b_{i}}$,${\displaystyle p=1,2,...}$.

Для нахождение секретной пары строится график функции ${\displaystyle b_{i}u(modm)}$, который имеет пилообразную форму

Вспоминая, что ${\displaystyle b_{i}=(ta_{i},modm)}$ и ${\displaystyle t^{-1}=u}$ запишем:

${\displaystyle (b_{1}u,modm)=a_{1}}$, где ${\displaystyle u}$-искомый обратный множитель, ${\displaystyle a_{1}}$ — первая компоненты вектора ${\displaystyle A}$, по условию очень мала по сравнению с ${\displaystyle m}$. Значит, значение ${\displaystyle u}$ близко к минимуму функции ${\displaystyle b_{1}}$.

Для ${\displaystyle (b_{2}u,modm)=a_{2}}$, значение ${\displaystyle u}$ близко к минимуму функции ${\displaystyle b_{2}}$. Тогда два минимума функций ${\displaystyle b_{1}}$ и ${\displaystyle b_{2}}$ близки друг к другу. Таким образом, можно рассмотреть и остальные пилообразные кривые. Ясно, что минимумы всех этих кривых близки друг другу. Можно построить малый интервал, содержащий «точки накопления» минимумов пилообразных кривых[22]. Исходя из этого малого интервала, находятся ${\displaystyle n}$ и значение ${\displaystyle u}$ из секретной пары.

Так как значение модуля ${\displaystyle m}$ нам не известно, то изменим масштаб рисунка так, чтобы ${\displaystyle m}$ стало равно 1(поделим все длины на ${\displaystyle m}$).

Алгоритм нахождения секретной пары:

1) Отыскание кандидатов для целого ${\displaystyle p}$, таких, что ${\displaystyle p}$-й минимум функции ${\displaystyle b_{1}}$-искомая точка накопления.

Чтобы число кандидатов не было слишком большим, введем фиксированный параметр ${\displaystyle r}$-максимальное число разрешенных кандидатов.

В первой части алгоритма не обязательно рассматривать сразу все ${\displaystyle b_{2},...,b_{n}}$, следует ввести параметр ${\displaystyle s<n}$ и рассматривать ${\displaystyle s}$ компонент.

${\displaystyle p/b_{1}}$ -координата ${\displaystyle u}$ ${\displaystyle p}$-го минимума на кривой ${\displaystyle b_{1}}$.

Условие близости минимумов кривых ${\displaystyle b_{1}}$ и ${\displaystyle b_{2}}$ можно записать следующим неравенствами:

${\displaystyle -e<p/b_{1}-q/b_{2}<e}$,

${\displaystyle 1\leq p\leq b_{1}-1}$, ${\displaystyle 1\leq q\leq b_{2}-1}$

Умножим первое неравенство на ${\displaystyle b_{1}b_{2}}$:

${\displaystyle -E<pb_{2}-qb_{1}<E}$.

Всего таких неравенств ${\displaystyle s-1}$, по одному для каждого ${\displaystyle b}$

Так, первая часть алгоритма дает все такие натуральные ${\displaystyle p}$, для которых существуют натуральные ${\displaystyle q}$, такие что все ${\displaystyle s-1}$ неравенств выполняются.

2) Последовательная проверка каждого из кандидатов.

Во второй части алгоритма проверяются все ${\displaystyle i=[2,n]}$. Кандидат ${\displaystyle p}$ будет отброшен, если для некоторого ${\displaystyle i}$ нет минимума кривой ${\displaystyle b_{i}}$, лежащего около ${\displaystyle p}$-го минимума кривой ${\displaystyle b_{1}}$.

Зафиксируем ${\displaystyle p}$. Упорядочиваем по возрастанию все точки разрыва в интервале ${\displaystyle [p/b_{1},(p+1)/b_{1}]}$. Возьмем две соседние точки из отсортированного списка ${\displaystyle x_{i}}$ и ${\displaystyle x_{i}+1}$. В образованном ими интервале ${\displaystyle [x_{i},x_{i}+1]}$, каждая кривая ${\displaystyle b_{i}}$ — прямолинейный отрезок (уравнение ${\displaystyle b_{i}u-const_{i}^{j}}$ описывают эти отрезки).

Исходя из вышесказанного, запишем систему неравенств:

${\displaystyle x_{j}\leq u\leq x_{j}+1}$

${\displaystyle \sum _{i=1}^{n}(b_{i}u-const_{i}^{j})<1}$

${\displaystyle (b_{1}u-const_{1}^{j})+(b_{2}u-const_{2}^{j})+...+(b_{i}-1u-const_{i-1}^{j})<(b_{i}u-const_{i}^{j})}$ ${\displaystyle i=[2,n]}$ — условие сверхроста

Чтобы два числа ${\displaystyle u}$ и ${\displaystyle m}$ образовывали секретную пару, необходимо и достаточно, чтобы ${\displaystyle u/m}$ принадлежала построенному таким образом для некоторой пары ${\displaystyle (p,j)}$ интервалу. ${\displaystyle p}$, кандидат из первой части алгоритма, а ${\displaystyle j}$ индекс точки из отсортированного списка точек, соответствующего данному ${\displaystyle p}$.

Поиск закончится, когда будет найден не пустой интервал ${\displaystyle [x_{i},x_{i}+1]}$.

Пример[23].

Пускай ${\displaystyle B=(7,3,2)}$ открытый ключ из трех компонент

1) Согласно приведённым выше неравенствам:

${\displaystyle -E<3p-7q<E}$,

${\displaystyle -E<2p-7q<E}$

${\displaystyle 1\leq p\leq 6}$ , ${\displaystyle 1\leq q\leq 2}$, ${\displaystyle r=1}$.

В таблице перечислены наименьшие значения ${\displaystyle E}$ такие, что неравенства выполняются:

2) Видно, что все значения ${\displaystyle p}$ подходят в кандидаты (в общем случае такого может и не быть). Следовательно, интервал ${\displaystyle (0,1)}$ делим на подынтервалы: ${\displaystyle (0,1/7),(1/7,2/7),(2/7,1/3),(1/3,3/7),(3/7,1/2),(1/2,4/7),(4/7,2/3),(2/3,5/7),(5/7,6/7),(6/7,1)}$ такие, что все три кривые ${\displaystyle b_{i}}$- прямолинейные отрезки ${\displaystyle (b_{i}u-const_{i}^{j})}$ в каждом приведенном интервале.

Запишем неравенства:

${\displaystyle (7u-i')+(3u-i'')+(2u-i''')<1}$

${\displaystyle 7u-i'<3u-i''}$

${\displaystyle (7u-i')+(3u-i'')<(2u-i''')}$

Константы меняются в пределах ${\displaystyle 0\leq i\leq 6}$, ${\displaystyle 0\leq i'\leq 2}$, ${\displaystyle 0\leq i'''\leq 1}$ в зависимости от выбора интервала.

Применяя обозначения ${\displaystyle i=1+i'+i''+i'''}$, ${\displaystyle j=i'-i''}$, ${\displaystyle k=i'+i''-i'''}$ перепишем неравенства в более простой форме:

${\displaystyle 12u<i,4u<j,8u<k}$

Соберем в таблицу все значения констант для разных интервалов:

В последних трех строках указано, выполняется или нет каждое из неравенств : SAT - выполняется, PART-частично выполняется (появляется, когда неравенство выполняется на правой части подынтервала), NOT - не выполняется (появляется когда неравенство не выполнено на левой части подынтервала).

Интервал порождает секретную пару тогда и только тогда, когда в столбце стоят все три либо SAT либо PART. Единственный такой интервал ${\displaystyle (5/7,3/4)}$. Выбирая число из интервала, например ${\displaystyle 8/11}$(т.е ${\displaystyle m=11}$),получим сверхрастущий вектор ${\displaystyle A=(1,2,5)}$.