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

Задача о рюкзаке (или Задача о ранце) в криптографии (англ. Knapsack problem) — это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом. Он носит название криптосистема Меркла-Хеллмана. Для шифрования сообщений использовалось решение задачи о рюкзаке, как известно, являющейся NP-сложной. Потому, как считалось, она могла обеспечивать криптостойкость системы. На данный момент создано множество рюкзачных криптосистем. Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными.

История

Проблема рюкзака лежит в основе первого алгоритма асимметричного шифрования (или иначе шифрования с открытым ключом). Идея криптографии с открытыми ключами была выдвинута американскими криптографами Уитфилдом Диффи, Мартином Хеллманом и независимо от них Ральфом Мерклом. Впервые она была представлена Диффи и Хеллманом на Национальной компьютерной конференции (англ. National Computer Conference) в 1976 году, в том же году была опубликована их совместная работа на эту тему — «New Directions in Cryptography» (рус. «Новые направления в криптографии»). Статья Меркла «Secure Communication Over Insecure Channels» (рус. «Безопасная связь по незащищённым каналам») была опубликована только в 1978 году. Новизна по отношению к распространённым на тот момент симметричным криптосистемам заключалась в использовании парных ключей — секретного (англ. private key, secret key, SK) и открытого (англ. public key, PK), создаваемых пользователем. Секретный ключ, используемый для расшифровки информации, пользователь должен скрывать, тогда как открытый ключ, необходимый лишь для шифрования, может быть общедоступным. Во многих криптосистемах из секретного ключа получают открытый ключ.

Первый алгоритм для шифрования на основе задачи о рюкзаке был разработан Мерклом и Хеллманом в 1978 году и получил название «Алгоритм Меркла-Хеллмана». Он был опубликован в одностадийном (англ. singly-iterated) и мультистадийном вариантах (англ. multiply-iterated). Алгоритм мог быть использован только для шифрования, но израильский криптоаналитик Ади Шамир адаптировал его для использования в цифровых подписях. После опубликования схемы Меркл предложил вознаграждение в 100 долларов тому, кто удачно осуществит взлом одностадийного алгоритма. В 1982 году Шамир осуществил успешную атаку и получил обещанное вознаграждение. Но даже после его уплаты Меркл был уверен в криптостойкости мультистадийной системы и предложил 1000 долларов в случае её удачного взлома. В 1984 году американский математик Эрнест Брикелл сумел осуществить взлом для сорока-стадийного варианта чуть более чем за 1 час на машине Cray-1.

Независимо друг от друга ещё в 1980 году американский математик Рон Грэм и Ади Шамир обнаружили способ повысить криптостойкость схемы Меркла-Хеллмана, но уже в 1983 году полученная схема Грэма-Шамира была взломана американским учёным Леонардом Адлеманом. Однако поиски модификаций, лишённых недостатков схемы Меркла-Хеллмана, продолжились. В 1985 году британский адъюнкт-профессор Родни Гудман и американский инженер Энтони Маколи создали схему, основанную на модульных рюкзаках с секретной лазейкой не на основе сверхвозрастающих векторов, а с использованием китайской теоремы об остатках.

Впоследствии стало ясно, что схема уязвима для атак, основанных на поиске секретных лазеек. Однако в 1990 году Валттери Ниеми предложил новую схему на основе той же задачи модульного рюкзака. Она была взломана уже в следующем году Чи Е Мэном, Антуаном Жу и Жаком Штерном независимо друг от друга, слегка различными методами. Помимо использования модульных рюкзаков были попытки применения других видов рюкзака.

Так, в 1986 году Харальд Нидеррайтер опубликовал рюкзачную криптосистему на основе алгебраической теории кодирования, которая в дальнейшем была взломана, а в 1988 году Масакацу Мории и Масао Касахара разработали криптосистему с использованием мультипликативного рюкзака. Эта идея оказалась удачной и пока система на мультипликативных рюкзаках не взломана.

В 2001 году Синъя Киути, Ясуюки Мураками и Масао Касахара предложили усовершенствование схемы Мории-Касахары на основе мультипликативных рюкзаков с использованием алгоритма Schalkwijk.

Также удачной оказалась идея Хусейна Али Хусейна, Джафара Вади Абдулы Сада и М. Калифа, предложивших в 1991 году многостадийную рюкзачную криптосистему (англ. multistage trapdoor knapsack cryptosystem). В ней фиксируется рюкзачный вектор для каждого этапа, и выход (зашифрованный текст) после каждой стадии алгоритма используется в качестве входных данных (текста) на следующий этап. Успешной атаки на данную схему не известно (на 2001 год).

Цюй Минхуа и Скотт Ванстоун в 1992 году предложили гибридную криптосистему которая основана прежде всего на задаче о ранце, но также включает в себя логарифмические подписи. В 1994 году Р. Блэкберн, Мерфи, Шон и Жак Штерн показали, что упрощённый вариант У-Вастон криптосистемы небезопасен. Эти криптосистемы были более тщательно изучены Фонг Нгуеном и Жаком Штерном в 1997 году.

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

В 1995 году были предложены сразу два новых подхода к задаче. Первый, на основе диофантовых уравнений принадлежит Линь Чжусину, Чжан Чжэньчэну, и Ли Цзятуну. Почти сразу Лай Цисун и Блэкберн, Мерфи, Шон и С. Г. Патерсон независимо друг от друга показали, что эта криптосистема не является криптостойкой.

Второй подход, основанный на задаче о мультипликативном рюкзаке, был предложен Дэвидом Наккаше и Жаком Штерном. Наккаше и Штерн предлагали 1024 немецких марок тому, кто успешно взломает их криптосхему, но информации о том, что кто-то получил это вознаграждение пока не было (на 2001 год).

В 1996 году Куникацу Кобаяси и Масаки Кимура предложили улучшенную рюкзачную криптосистему на основе новой концепции, где отправитель может выбрать ключ шифрования из целого набора ключей. Через два года Хидэнори Кувакадо и Хацукадзу Танака показали, что система потенциально небезопасна.

Последний вариант алгоритма был предложен Б. Шором и Р. Л. Ривестом в 2006 году. В 2002 году алгоритм Chor-Rivest считался безопасным.

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

В дальнейшем было предложено много алгоритмов с открытым ключом, не основанных на рюкзачных системах. Наиболее известные из них: RSA, EIGamal и Rabin. Их можно использовать и для шифрования и для цифровых подписей. Однако они медленны и не подходят для быстрой шифровки/дешифровки больших объёмов сообщений. Решением этой проблемы являются гибридные криптосистемы, шифрование сообщений осуществляется быстрым симметричным алгоритмом со случайным ключом, а алгоритм на открытых ключах применяется для шифрования самого случайного (сеансового) ключа.

Постановка задачи

Задача о рюкзаке звучит так: задан набор $A=(a_{1},...,a_{n})$ из $n$ различных положительных целых чисел. Пусть есть число $k$ так же целое и положительное. Задачей является нахождение такого набора $a_{i}$, чтобы в сумме они давали ровно $k$. Ясно, что решение этой задачи существует не всегда.

Согласно определению систем с открытым ключом, для успешного шифрования/расшифровки нужно иметь два ключа. Законный получатель сообщения знает секретный ключ A, а отправитель владеет лишь открытым ключом B. Как же помешать злоумышленнику дешифровать сообщение в случае если ему стал известен открытый ключ? Ответ прост, открытый ключ должен получаться из секретного ключа при помощи какого-либо преобразования f, обладающего следующими двумя свойствами:

• Легко вычислить $B=f(A)$, зная $A$
• Определение $A=f^{-1}(B)$, зная $B$, вероятно, трудновыполнимая задача.

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

Шифрование с помощью задачи о рюкзаке

Сообщение шифруется как решение набора задач о ранце.

Def.Рюкзачным вектором $A=(a_{1},...,a_{n})$ назовём упорядоченный набор из n предметов.

Для шифрования открытого текста в двоичном представлении его разбивают на блоки длины $n$ (например, $(11100)$ соответствует 5-ти предметам в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие. Шифровать можно двумя способами:

1) Шифр сообщения получается возведением элементов рюкзачного вектора в степень соответствующих им бит шифруемого сообщения и дальнейшим перемножением результатов, то есть если $A=(2,3,5)$, а сообщение $(100)$, то шифром будет число $2^{1}*3^{0}*5^{0}=2$. Такой способ называют мультипликативным.

2) Шифр сообщения получается путём умножения элементов рюкзачного вектора на соответствующий им бит шифруемого сообщения и дальнейшим сложением результатов, то есть если $A=(2,3,5)$, а сообщение $(100)$, то шифром будет число $2*1+3*0+5*0=2$. Такой способ называют аддитивным.

Пример шифротекста, полученного по аддитивному алгоритму.

Пусть задан рюкзачный вектор Α = (3 4 6 7 10 11) с длинной n = 6.

открытый текст	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
вещи в рюкзаке	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11
шифротекст	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	11

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

Сложность шифра заключается в том, что существуют две проблемы рюкзака: «лёгкая» и «трудная». «Лёгкая» проблема может быть решена за линейное время, «трудная» нет. Открытый ключ — «трудная» проблема, так как её легко применять для шифрования и невозможно для дешифровки сообщения. Закрытый ключ — «лёгкая» проблема, так как позволяет легко дешифровать сообщение. При отсутствии закрытого ключа нужно решать «трудную» проблему рюкзака. Меркл и Хеллман, используя модульную арифметику, разработали способ трансформации «лёгкого» рюкзака в «трудный».

«Лёгкая» проблема

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

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

Пример

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

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

«Трудная» проблема

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

Криптосистема с открытым ключом на основе задачи о ранце

Как и раньше под вектором A понимается секретный ключ, под вектором B открытый ключ.

Создание открытого ключа из закрытого

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

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

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

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

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

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

Пример

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

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

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

1061 * 25 236 — 1= 485 * 55 207

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

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

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

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

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

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

Шифрование

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

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

Блок исходного текста	Двоичный код	Шифр блока
DE	00100 00101	95097
AT	00001 10100	61616
H	01000 00000	50316
GO	00111 01111	207922
DS	00100 10011	118572
E	00000 00101	70173
AT	00001 10100	61616
O	00000 01111	124980
NL	01110 01100	155433
Y	11001 00000	82005
AP	00001 10000	45063
PL	10000 01100	53864
ES	00101 10011	149480

Расшифровка

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

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

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

Число	Компонента A	Символ
34728	27610	1
7118	13807	0
7118	6907	1
211	3449	0
211	1718	0
211	863	0
211	430	0
211	211	1
0	107	0
0	103	0

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

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

Криптостойкость

Безопасность рюкзачных систем

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

Как искать секретную лазейку

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$(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})$ $i=[2,n]$ — условие сверхроста

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

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

Пример.

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

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

$-E<3p-7q<E$,

$-E<2p-7q<E$

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

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

p	1	2	3	4	5	6
E	5	3	2	2	3	5

2) Видно, что все значения $p$ подходят в кандидаты (в общем случае такого может и не быть). Следовательно, интервал $(0,1)$ делим на подынтервалы: $(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)$ такие, что все три кривые $b_{i}$- прямолинейные отрезки $(b_{i}u-const_{i}^{j})$ в каждом приведенном интервале.

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

$(7u-i')+(3u-i'')+(2u-i''')<1$

$7u-i'<3u-i''$

$(7u-i')+(3u-i'')<(2u-i''')$

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

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

$12u<i,4u<j,8u<k$

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

Интервал	1/7	2/7	1/3	3/7	1/2	4/7	2/3	5/7	6/7	1
i'	0	1	2	2	3	3	4	4	5	6
i	0	0	0	1	1	1	1	2	2	2
i	0	0	0	0	0	1	1	1	1	1
i	1	2	3	4	5	6	7	8	9	10
j	0	1	2	1	2	2	3	2	3	4
k	0	1	2	3	4	3	4	5	6	7
12u<i	PART	PART	NOT	NOT	NOT	NOT	PART	NOT	PART	NOT
4u<j	NOT	PART	SAT	NOT	SAT	NOT	SAT	NOT	PART	SAT
8u<k	NOT	NOT	NOT	PART	SAT	NOT	NOT	NOT	PART	PART

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

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

Варианты задачи о ранце в криптографии

1) Рюкзак Меркла-Хеллмана (англ. Merkle-Hellman Cryptosystem).

Основная статья: Ранцевая криптосистема Меркля — Хеллмана

Открытый ключ A — сверхвозрастающий вектор, секретный ключ B получен из A сильным модульным умножением.

2) Рюкзак Грэм-Шамира (англ. Graham-Shamir Cryptosystem).

Открытый ключ A — сверхвозрастающий вектор. Его элементы записываются в битовом представлении. Далее генерируются случайные числа, называемые шумом. Их битовое представление дописывается к битам рюзачного вектора слева, то есть в старший разряд.

Допустим, мы выбираем вектора $A=(1,3,5)$. Дописываем в ним префиксы из случайно выбранных чисел:

Бинарное представление	Со случайным префиксом
1 = 001	101 001 = 41
3 = 011	111 011 = 59
5 = 101	100 101 = 37

Получившийся рюкзачный вектор $(41,59,37)$ не обладает свойством сверхвозрастания. Следовательно, добавление случайного шума скрывает свойство сверхвозрастания у исходного вектора A и схема становится безопаснее.

3) Рюкзак Мории-Касахара (англ. Morii-Kasahara Cryptosystem)

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

Пусть вектор $A=(5,6,7)$. Выбираем $m=211>5*6*7=210$, простое число $p=211$ (в этой схеме $p=m$) и $e=19$, такое что $gcd(e,p-1)mod(p-1)=1$. Секретный ключ B получаем из A по формуле $b_{i}=a_{i}^{e}modp$, то есть $B=(114,66,85)$. Пусть шифруемое сообщение $(100)$, тогда шифр $114^{1}*66^{0}*85^{0}=144mod211$.

4) Рюкзак Гудмана-Макколи (англ. Goodman-McAuley Cryptosystem).

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

5) Рюкзак Накаше-Штерна (англ. Naccache-Stern Cryptosystem).

Данная схема объединяет два метода: рюкзак Меркла-Хеллмана и алгоритм Полига-Хеллмана. Дано простое число $p$, S подмножество (англ. subset product), а рюкзачный вектор $A=(a_{1},a_{2},...a_{n})$, где все $a_{i}$ взаимно простые числа. Нужно найти бинарный вектор $x=(x_{1},...,x_{n})$, такой что $\displaystyle \prod _{i=1}^{n}a_{i}^{x_{i}}mpdp=S$

6) Рюкзак Шор-Ривеста (англ. Chor-Rivest)

Основаны на алгебре в конечных полях (полях Галуа). Пусть $q=p^{h}$ и открытый ключ A состоит из элементов подполя $GF(p)$ поля $GF(q)$, то есть $(a_{1},a_{2},...a_{p})=GF(p)\in GF(q)$. Секретный ключ состоит из следующих элементов:

• элемент $t$ из $GF(q)$ с алгебраической степенью $h$
• генератор $g$ из $GF^{*}(q)$
• целое $d$ из $\mathbb {Z} (q-1)$

Тогда открытый ключ B состоит из элементов $b_{i}=d+\log _{g}(t+a_{i})mod(q-1)$.

Будущее рюкзачных систем

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

Для рюкзака весом $n=100$ одна итерация алгоритма Меркла-Хеллмана может быть более чем в 100 раз быстрее RSA (с модулем в 500 бит).

Литература

на русском языке

1. Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 160—163. — 576 с. — ISBN 978-5-8459-0987-9
2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
3. Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2.
4. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М., 1974. — 232 с.
5. В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
6. С. Окулов. Программирование в алгоритмах. — 2007. — С. 383.
7. Б. Шнайер. Прикладная криптография. — 2-е. — 2002. Архивная копия от 28 февраля 2014 на Wayback Machine
8. А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — Springer-Verlag, 1990. — С. 102—150. Архивная копия от 19 ноября 2011 на Wayback Machine
9. Коблиц Н. Курс теории чисел и криптографии — 2-е издание — М.: Научное издательство ТВП, 2001. — 254 с. — ISBN 978-5-85484-014-9, 978-5-85484-012-5

на английском языке

1. Silvano Martelo, Paolo Toth. Knapsack problems. — Wiley, 1990. — 306 с.
2. David Pisinger. Knapsack problems. — 1995. Архивная копия от 22 декабря 2012 на Wayback Machine
3. Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack problems. — 1995.

Ссылки

• Денис Алексеев. Алгоритм Рюкзака  (рус.). «Яндекс.Народ». Дата обращения: 6 декабря 2012. Архивировано 7 января 2013 года.
• Михаил Чегодарь. Применение криптографии в вопросах защиты данных, на примере рюкзачной системы шифрования  (рус.). Underground InformatioN Center. Дата обращения: 6 декабря 2012.